Paper 2017/509

Quantum Security of NMAC and Related Constructions

Fang Song and Aaram Yun


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.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2017
cascade constructionNMACHMACaugmented cascadeAMACPRF domain extensionquantum queryquantum securitypost-quantum cryptography
Contact author(s)
aaramyun @ unist ac kr
2017-06-02: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.