Quantum-secure message authentication codes

Dan Boneh, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary's ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, EUROCRYPT 2013 - 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Pages592-608
Number of pages17
DOIs
StatePublished - 2013
Externally publishedYes
Event32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2013 - Athens, Greece
Duration: May 26 2013May 30 2013

Publication series

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

Other

Other32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2013
CountryGreece
CityAthens
Period5/26/135/30/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • MAC
  • Quantum computing
  • chosen message attacks
  • post-quantum security

Fingerprint Dive into the research topics of 'Quantum-secure message authentication codes'. Together they form a unique fingerprint.

  • Cite this

    Boneh, D., & Zhandry, M. (2013). Quantum-secure message authentication codes. In Advances in Cryptology, EUROCRYPT 2013 - 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 592-608). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7881 LNCS). https://doi.org/10.1007/978-3-642-38348-9_35