New security notions and feasibility results for authentication of quantum data

Sumegha Garg, Henry Yuen, Mark Zhandry

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

23 Scopus citations


We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adversaries for both classical message authentication codes (MACs) as well as full quantum state authentication schemes. The main feature of our definitions is that they precisely characterize the effective behavior of any adversary when the authentication protocol accepts, including correlations with the key. Our definitions readily yield a host of desirable properties and interesting consequences; for example, our security definition for full quantum state authentication implies that the entire secret key can be re-used if the authentication protocol succeeds. Next, we present several protocols satisfying our security definitions. We show that the classical Wegman-Carter authentication scheme with 3-universal hashing is secure against superposition attacks, as well as adversaries with quantum side information. We then present conceptually simple constructions of full quantum state authentication. Finally, we prove a lifting theorem which shows that, as long as a protocol can securely authenticate the maximally entangled state, it can securely authenticate any state, even those that are entangled with the adversary. Thus, this shows that protocols satisfying a fairly weak form of authentication security automatically satisfy a stronger notion of security (in particular, the definition of Dupuis et al. (2012)).

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings
EditorsJonathan Katz, Hovav Shacham
PublisherSpringer Verlag
Number of pages30
ISBN (Print)9783319637143
StatePublished - 2017
Event37th Annual International Cryptology Conference, CRYPTO 2017 - Santa Barbara, United States
Duration: Aug 20 2017Aug 24 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


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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'New security notions and feasibility results for authentication of quantum data'. Together they form a unique fingerprint.

Cite this