[Resource Topic] 2021/774: On Tight Quantum Security of HMAC and NMAC in the Quantum Random Oracle Model

Welcome to the resource topic for 2021/774

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

Authors: Akinori Hosoyamada, 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.

ePrint: https://eprint.iacr.org/2021/774

Talk: https://www.youtube.com/watch?v=N8HDM6C5SXg

Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/169/slides.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .