Cryptology ePrint Archive: Report 2021/774

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

Akinori Hosoyamada and Tetsu Iwata

Abstract: 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.

Category / Keywords: secret-key cryptography / post-quantum cryptography, provable security, quantum security, compressed oracle technique, HMAC, NMAC

Original Publication (with major differences): IACR-CRYPTO-2021

Date: received 8 Jun 2021

Contact author: akinori hosoyamada bh at hco ntt co jp, hosoyamada akinori at nagoya-u jp, tetsu iwata at nagoya-u jp

Available format(s): PDF | BibTeX Citation

Version: 20210609:063101 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]