Paper 2021/774

On Tight Quantum Security of HMAC and NMAC in the Quantum Random Oracle Model

Akinori Hosoyamada and Tetsu Iwata


HMAC and NMAC are the most basic and important constructions to convert Merkle-Damgård hash functions into message authentication codes (MACs) or pseudorandom functions (PRFs). In the quantum setting, at CRYPTO 2017, Song and Yun showed that HMAC and NMAC are quantum pseudorandom functions (qPRFs) under the standard assumption that the underlying compression function is a qPRF. Their proof guarantees security up to $O(2^{n/5})$ or $O(2^{n/8})$ quantum queries when the output length of HMAC and NMAC is $n$ bits. However, there is a gap between the provable security bound and a simple distinguishing attack that uses $O(2^{n/3})$ quantum queries. This paper settles the problem of closing the gap. We show that the tight bound of the number of quantum queries to distinguish HMAC or NMAC from a random function is $\Theta(2^{n/3})$ in the quantum random oracle model, where compression functions are modeled as quantum random oracles. To give the tight quantum bound, based on an alternative formalization of Zhandry's compressed oracle technique, we introduce a new proof technique focusing on the symmetry of quantum query records.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2021
post-quantum cryptographyprovable securityquantum securitycompressed oracle techniqueHMACNMAC
Contact author(s)
akinori hosoyamada bh @ hco ntt co jp
hosoyamada akinori @ nagoya-u jp
tetsu iwata @ nagoya-u jp
2021-06-09: received
Short URL
Creative Commons Attribution


      author = {Akinori Hosoyamada and Tetsu Iwata},
      title = {On Tight Quantum Security of HMAC and NMAC in the Quantum Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2021/774},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.