**Low-communication parallel quantum multi-target preimage search**

*Gustavo Banegas and Daniel J. Bernstein*

**Abstract: **The most important pre-quantum threat to AES-128 is the 1994 van Oorschot--Wiener "parallel rho method", a low-communication parallel pre-quantum multi-target preimage-search algorithm. This algorithm uses a mesh of p small processors, each running for approximately 2^128/pt fast steps, to find one of t independent AES keys k_1,...,k_t, given the ciphertexts AES_{k_1}(0),...,AES_{k_t}(0) for a shared plaintext 0.

NIST has claimed a high post-quantum security level for AES-128, starting from the following rationale: "Grover's algorithm requires a long-running serial computation, which is difficult to implement in practice. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramatic." NIST has also stated that resistance to multi-key attacks is desirable; but, in a realistic parallel setting, a straightforward multi-key application of Grover's algorithm costs more than targeting one key at a time.

This paper introduces a different quantum algorithm for multi-target preimage search. This algorithm shows, in the same realistic parallel setting, that quantum preimage search benefits asymptotically from having multiple targets. The new algorithm requires a revision of NIST's AES-128, AES-192, and AES-256 security claims.

**Category / Keywords: **secret-key cryptography / quantum cryptanalysis, multi-target preimages, parallel rho method, Grover's algorithm

**Original Publication**** (in the same form): **SAC 2017, to appear

**Date: **received 18 Aug 2017, last revised 18 Aug 2017

**Contact author: **authorcontact-groverrho at box cr yp to

**Available format(s): **PDF | BibTeX Citation

**Version: **20170821:183334 (All versions of this report)

**Short URL: **ia.cr/2017/789

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]