Paper 2021/1239
Quantum Linearization Attacks
Xavier Bonnetain, Gaëtan Leurent, María Naya-Plasencia, and André Schrottenloher
Abstract
Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes. In this paper, we introduce the \emph{quantum linearization attack}, a new way of using Simon's algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. Recovering this structure allows to perform forgeries. We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch's, Bernstein-Vazirani's, and Shor's. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks. Our attack breaks many parallelizable MACs such as LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in ASIACRYPT 2021
- Keywords
- Quantum cryptanalysisMACsSuperposition query modelSimon's algorithmDeutsch's algorithmShor's algorithmBernstein-Vazirani algorithm
- Contact author(s)
-
xavier bonnetain @ uwaterloo ca
gaetan leurent @ inria fr
maria naya_plasencia @ inria fr
andre schrottenloher @ m4x org - History
- 2021-09-20: received
- Short URL
- https://ia.cr/2021/1239
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1239,
author = {Xavier Bonnetain and Gaëtan Leurent and María Naya-Plasencia and André Schrottenloher},
title = {Quantum Linearization Attacks},
howpublished = {Cryptology ePrint Archive, Paper 2021/1239},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1239}},
url = {https://eprint.iacr.org/2021/1239}
}
