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 .