Welcome to the resource topic for 2023/025
Title:
Quantum Attacks on Beyond-Birthday-Bound MACs
Authors: Hong-Wei Sun, Bin-Bin Cai, Su-Juan Qin, Qiao-Yan Wen, Fei Gao
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.
ePrint: https://eprint.iacr.org/2023/025
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .