Paper 2023/1306

Single-query Quantum Hidden Shift Attacks

Xavier Bonnetain, Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
André Schrottenloher, Univ Rennes, Inria, CNRS, IRISA

Quantum attacks using superposition queries are known to break many classically secure modes of operation. While these attacks do not necessarily threaten the security of the modes themselves, since they rely on a strong adversary model, they help us to draw limits on the provable security of these modes. Typically these attacks use the structure of the mode (stream cipher, MAC or authenticated encryption scheme) to embed a period-finding problem, which can be solved with a dedicated quantum algorithm. The hidden period can be recovered with a few superposition queries (e.g., $O(n)$ for Simon's algorithm), leading to state or key-recovery attacks. However, this strategy breaks down if the period changes at each query, e.g., if it depends on a nonce. In this paper, we focus on this case and give dedicated state-recovery attacks on the authenticated encryption schemes Rocca, Rocca-S, Tiaoxin-346 and AEGIS-128L. These attacks rely on a procedure to find a Boolean hidden shift with a single superposition query, which overcomes the change of nonce at each query. As they crucially depend on such queries, we stress that they do not break any security claim of the authors, and do not threaten the schemes if the adversary only makes classical queries.

Available format(s)
Attacks and cryptanalysis
Publication info
Quantum cryptanalysisQuantum Fourier TransformAuthenticated encryptionBoolean hidden shiftRoccaTiaoxinAEGIS
Contact author(s)
xavier bonnetain @ inria fr
2023-09-02: approved
2023-09-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xavier Bonnetain and André Schrottenloher},
      title = {Single-query Quantum Hidden Shift Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1306},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.