Quantum Attacks on Beyond-Birthday-Bound MACs

Hong-Wei Sun; Bin-Bin Cai; Su-Juan Qin; Qiao-Yan Wen; Fei Gao

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 . 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-ECBCPlus, 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 or quantum queries, where is the message block size and 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-Bound MAC Quantum cryptanalysis Quantum 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: 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},
      url = {https://eprint.iacr.org/2023/025}
}