Low-communication parallel quantum multi-target preimage search

G.S. Banegas; D.J. Bernstein

doi:10.1007/978-3-319-72565-9_16

Low-communication parallel quantum multi-target preimage search

G.S. Banegas
, D.J. Bernstein

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

14 Citations (Scopus)

1 Downloads (Pure)

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 2128/pt fast steps, to find one of t independent AES keys k 1 ,…,k t k1,…,kt , given the ciphertexts Open image in new window 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.

Original language	English
Title of host publication	Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers
Subtitle of host publication	24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised selected papers
Editors	Carlisle Adams, Jan Camenisch
Place of Publication	Dordrecht
Publisher	Springer
Chapter	16
Pages	325-335
Number of pages	11
ISBN (Electronic)	978-3-319-72565-9
ISBN (Print)	978-3-319-72564-2
DOIs	https://doi.org/10.1007/978-3-319-72565-9_16
Publication status	Published - 23 Dec 2017
Event	24th International Conference on Selected Areas in Cryptography (SAC 2017) - Ottawa, Canada Duration: 16 Aug 2017 → 18 Aug 2017 Conference number: 24

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10719 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Selected Areas in Cryptography (SAC 2017)
Abbreviated title	SAC 2017
Country/Territory	Canada
City	Ottawa
Period	16/08/17 → 18/08/17

Keywords

Grover’s algorithm
Multi-target preimages
Parallel rho method
Quantum cryptanalysis

Access to Document

10.1007/978-3-319-72565-9_16

Cite this

Banegas, G. S., & Bernstein, D. J. (2017). Low-communication parallel quantum multi-target preimage search. In C. Adams, & J. Camenisch (Eds.), Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised selected papers (pp. 325-335). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10719 LNCS). Springer. https://doi.org/10.1007/978-3-319-72565-9_16

Banegas, G.S. ; Bernstein, D.J. / Low-communication parallel quantum multi-target preimage search. Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised selected papers. editor / Carlisle Adams ; Jan Camenisch. Dordrecht : Springer, 2017. pp. 325-335 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5a49045ff2a94754b7fa1bb30b183deb,

title = "Low-communication parallel quantum multi-target preimage search",

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 2128/pt fast steps, to find one of t independent AES keys k 1 ,…,k t k1,…,kt , given the ciphertexts Open image in new window for a shared plaintext 0. NIST has claimed a high post-quantum security level for AES-128, starting from the following rationale: “Grover{\textquoteright}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{\textquoteright}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{\textquoteright}s AES-128, AES-192, and AES-256 security claims. ",

keywords = "Grover{\textquoteright}s algorithm, Multi-target preimages, Parallel rho method, Quantum cryptanalysis",

author = "G.S. Banegas and D.J. Bernstein",

year = "2017",

month = dec,

day = "23",

doi = "10.1007/978-3-319-72565-9\_16",

language = "English",

isbn = "978-3-319-72564-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "325--335",

editor = "Carlisle Adams and Jan Camenisch",

booktitle = "Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers",

address = "Germany",

note = "24th International Conference on Selected Areas in Cryptography (SAC 2017), SAC 2017 ; Conference date: 16-08-2017 Through 18-08-2017",

}

Banegas, GS & Bernstein, DJ 2017, Low-communication parallel quantum multi-target preimage search. in C Adams & J Camenisch (eds), Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised selected papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10719 LNCS, Springer, Dordrecht, pp. 325-335, 24th International Conference on Selected Areas in Cryptography (SAC 2017), Ottawa, Quebec, Canada, 16/08/17. https://doi.org/10.1007/978-3-319-72565-9_16

Low-communication parallel quantum multi-target preimage search. / Banegas, G.S.; Bernstein, D.J.
Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised selected papers. ed. / Carlisle Adams; Jan Camenisch. Dordrecht: Springer, 2017. p. 325-335 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10719 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Banegas, G.S.

AU - Bernstein, D.J.

N1 - Conference code: 24

PY - 2017/12/23

Y1 - 2017/12/23

N2 - 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 2128/pt fast steps, to find one of t independent AES keys k 1 ,…,k t k1,…,kt , given the ciphertexts Open image in new window 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.

AB - 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 2128/pt fast steps, to find one of t independent AES keys k 1 ,…,k t k1,…,kt , given the ciphertexts Open image in new window 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.

KW - Grover’s algorithm

KW - Multi-target preimages

KW - Parallel rho method

KW - Quantum cryptanalysis

UR - https://www.scopus.com/pages/publications/85041860434

U2 - 10.1007/978-3-319-72565-9_16

DO - 10.1007/978-3-319-72565-9_16

M3 - Conference contribution

SN - 978-3-319-72564-2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 325

EP - 335

BT - Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers

A2 - Adams, Carlisle

A2 - Camenisch, Jan

PB - Springer

CY - Dordrecht

T2 - 24th International Conference on Selected Areas in Cryptography (SAC 2017)

Y2 - 16 August 2017 through 18 August 2017

ER -

Banegas GS, Bernstein DJ. Low-communication parallel quantum multi-target preimage search. In Adams C, Camenisch J, editors, Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised selected papers. Dordrecht: Springer. 2017. p. 325-335. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-72565-9_16

Low-communication parallel quantum multi-target preimage search

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this