Quantum security of NMAC and related constructions: PRF domain extension against quantum attacks

Fang Song, Aaram Yun

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Scopus citations


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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings
EditorsJonathan Katz, Hovav Shacham
PublisherSpringer Verlag
Number of pages27
ISBN (Print)9783319637143
StatePublished - 2017
Event37th Annual International Cryptology Conference, CRYPTO 2017 - Santa Barbara, United States
Duration: 20 Aug 201724 Aug 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10402 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference37th Annual International Cryptology Conference, CRYPTO 2017
Country/TerritoryUnited States
CitySanta Barbara

Bibliographical note

Publisher Copyright:
© 2017, International Association for Cryptologic Research.


  • AMAC
  • Augmented cascade
  • Cascade construction
  • HMAC
  • NMAC
  • PRF domain extension
  • Post-quantum cryptography
  • Quantum query
  • Quantum security


Dive into the research topics of 'Quantum security of NMAC and related constructions: PRF domain extension against quantum attacks'. Together they form a unique fingerprint.

Cite this