How to Sequentialize Independent Parallel Attacks? - Biased Distributions Have a Phase Transition
| Autor: | Sonia Bogos, Serge Vaudenay |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
LPN
Brute-force search Cryptography 0102 computer and information sciences 02 engineering and technology 01 natural sciences law.invention symbols.namesake Gaussian elimination cryptanalysis law password guessing 0202 electrical engineering electronic engineering information engineering Search problem Finite set Mathematics Password cryptography business.industry Password cracking 020206 networking & telecommunications 010201 computation theory & mathematics symbols business Cryptanalysis Algorithm |
| Zdroj: | Advances in Cryptology – ASIACRYPT 2015 ISBN: 9783662487990 ASIACRYPT (2) |
| DOI: | 10.1007/978-3-662-48800-3_29 |
| Popis: | We assume a scenario where an attacker can mount several independent attacks on a single CPU. Each attack can be run several times in independent ways. Each attack can succeed after a given number of steps with some given and known probability. A natural question is to wonder what is the optimal strategy to run steps of the attacks in a sequence. In this paper, we develop a formalism to tackle this problem. When the number of attacks is infinite, we show that there is a magic number of steps m such that the optimal strategy is to run an attack for m steps and to try again with another attack until one succeeds. We also study the case of a finite number of attacks. We describe this problem when the attacks are exhaustive key searches, but the result is more general. We apply our result to the learning parity with noise $$\mathsf {LPN}$$ problem and the password search problem. Although the optimal m decreases as the distribution is more biased, we observe a phase transition in all cases: the decrease is very abrupt from m corresponding to exhaustive search on a single target to $$m=1$$ corresponding to running a single step of the attack on each target. For all practical biased examples, we show that the best strategy is to use $$m=1$$. For $$\mathsf {LPN}$$, this means to guess that the noise vector is 0 and to solve the secret by Gaussian elimination. This is actually better than all variants of the Blum-Kalai-Wasserman $$\mathsf {BKW}$$ algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|