TY - GEN
T1 - Quantum security of NMAC and related constructions
AU - Song, Fang
AU - Yun, Aaram
N1 - Funding Information:
Acknowledgements. We would like to thank the anonymous reviewers of Crypto 2017 for many helpful comments. The second author was supported by Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-IT1601-07.
Publisher Copyright:
© 2017, International Association for Cryptologic Research.
PY - 2017
Y1 - 2017
N2 - We prove the security of NMAC, HMAC, AMAC, and the cascade construction with fixed input-length as quantum-secure pseudo-random functions (PRFs). Namely, they are indistinguishable from a random oracle against any polynomial-time quantum adversary that can make quantum superposition queries. In contrast, many blockcipher-based PRFs including CBC-MAC were recently broken by quantum superposition attacks. Classical proof strategies for these constructions do not generalize to the quantum setting, and we observe that they sometimes even fail completely (e.g., the universal-hash then PRF paradigm for proving security of NMAC). Instead, we propose a direct hybrid argument as a new proof strategy (both classically and quantumly). We first show that a quantum-secure PRF is secure against key-recovery attacks, and remains secure under random leakage of the key. Next, as a key technical tool, we extend the oracle indistinguishability framework of Zhandry in two directions: we consider distributions on functions rather than strings, and we also consider a relative setting, where an additional oracle, possibly correlated with the distributions, is given to the adversary as well. This enables a hybrid argument to prove the security of NMAC. Security proofs for other constructions follow similarly.
AB - We prove the security of NMAC, HMAC, AMAC, and the cascade construction with fixed input-length as quantum-secure pseudo-random functions (PRFs). Namely, they are indistinguishable from a random oracle against any polynomial-time quantum adversary that can make quantum superposition queries. In contrast, many blockcipher-based PRFs including CBC-MAC were recently broken by quantum superposition attacks. Classical proof strategies for these constructions do not generalize to the quantum setting, and we observe that they sometimes even fail completely (e.g., the universal-hash then PRF paradigm for proving security of NMAC). Instead, we propose a direct hybrid argument as a new proof strategy (both classically and quantumly). We first show that a quantum-secure PRF is secure against key-recovery attacks, and remains secure under random leakage of the key. Next, as a key technical tool, we extend the oracle indistinguishability framework of Zhandry in two directions: we consider distributions on functions rather than strings, and we also consider a relative setting, where an additional oracle, possibly correlated with the distributions, is given to the adversary as well. This enables a hybrid argument to prove the security of NMAC. Security proofs for other constructions follow similarly.
KW - AMAC
KW - Augmented cascade
KW - Cascade construction
KW - HMAC
KW - NMAC
KW - Post-quantum cryptography
KW - PRF domain extension
KW - Quantum query
KW - Quantum security
UR - http://www.scopus.com/inward/record.url?scp=85028475191&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-63715-0_10
DO - 10.1007/978-3-319-63715-0_10
M3 - Conference contribution
AN - SCOPUS:85028475191
SN - 9783319637143
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 283
EP - 309
BT - Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings
A2 - Katz, Jonathan
A2 - Shacham, Hovav
PB - Springer Verlag
Y2 - 20 August 2017 through 24 August 2017
ER -