Paper 2023/025
Quantum Attacks on Beyond-Birthday-Bound MACs
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
-
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}
}
