Paper 2023/025

Quantum Attacks on Beyond-Birthday-Bound MACs

Hong-Wei Sun, Beijing University of Posts and Telecommunications
Bin-Bin Cai, Beijing University of Posts and Telecommunications
Su-Juan Qin, Beijing University of Posts and Telecommunications
Qiao-Yan Wen, Beijing University of Posts and Telecommunications
Fei Gao, Beijing University of Posts and Telecommunications
Abstract

In this paper, we investigate the security of several recent MAC constructions with provable security beyond the birthday bound (called BBB MACs) in the quantum setting. On the one hand, we give periodic functions corresponding to targeted MACs (including PMACX, PMAC with parity, HPxHP, and HPxNP), and we can recover secret states using Simon algorithm, leading to forgery attacks with complexity $O(n)$. This implies our results realize an exponential speedup compared with the classical algorithm. Note that our attacks can even break some optimally secure MACs, such as mPMAC+-f, mPMAC+-p1, mPMAC+-p2, mLightMAC+-f, etc. On the other hand, we construct new hidden periodic functions based on SUM-ECBC-like MACs: SUM-ECBC, PolyMAC, GCM-SIV2, and 2K-ECBC$_{-}$Plus, where periods reveal the information of the secret key. Then, by applying Grover-meets-Simon algorithm to specially constructed functions, we can recover full keys with $O(2^{n/2}n)$ or $O(2^{m/2}n)$ quantum queries, where $n$ is the message block size and $m$ is the length of the key. Considering the previous best quantum attack, our key-recovery attacks achieve a quadratic speedup.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Beyond-Birthday-BoundMACQuantum cryptanalysisQuantum algorithm.
Contact author(s)
gaof @ bupt edu cn
History
2023-08-17: revised
2023-01-08: received
See all versions
Short URL
https://ia.cr/2023/025
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/025,
      author = {Hong-Wei Sun and Bin-Bin Cai and Su-Juan Qin and Qiao-Yan Wen and Fei Gao},
      title = {Quantum Attacks on Beyond-Birthday-Bound MACs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/025},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/025}},
      url = {https://eprint.iacr.org/2023/025}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.