Paper 2016/296
How to Sequentialize Independent Parallel Attacks?
Sonia Bogos and Serge Vaudenay
Abstract
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 (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 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 BlumKalaiWasserman (BKW) algorithm.
Metadata
 Available format(s)
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2015
 Contact author(s)
 soniamihaela bogos @ epfl ch
 History
 20160317: received
 Short URL
 https://ia.cr/2016/296
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/296, author = {Sonia Bogos and Serge Vaudenay}, title = {How to Sequentialize Independent Parallel Attacks?}, howpublished = {Cryptology ePrint Archive, Paper 2016/296}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/296}}, url = {https://eprint.iacr.org/2016/296} }