Paper 2017/509

Quantum Security of NMAC and Related Constructions

Fang Song and Aaram Yun

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2017
Keywords
cascade constructionNMACHMACaugmented cascadeAMACPRF domain extensionquantum queryquantum securitypost-quantum cryptography
Contact author(s)
aaramyun @ unist ac kr
History
2017-06-02: received
Short URL
https://ia.cr/2017/509
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/509,
      author = {Fang Song and Aaram Yun},
      title = {Quantum Security of NMAC and Related Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/509},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/509}},
      url = {https://eprint.iacr.org/2017/509}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.