Paper 2002/082

Authentication of Quantum Messages

Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, and Alain Tapp

Abstract

Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical private key want to exchange a classical message with the guarantee that the message has not been modified or replaced by a dishonest party with control of the communication line. In this paper we study the authentication of messages composed of quantum states. We give a formal definition of authentication in the quantum setting. Assuming A and B have access to an insecure quantum channel and share a private, classical random key, we provide a non-interactive scheme that both enables A to encrypt and authenticate (with unconditional security) an m qubit message by encoding it into m+s qubits, where the probability decreases exponentially in the security parameter s. The scheme requires a private key of size 2m+O(s). To achieve this, we give a highly efficient protocol for testing the purity of shared EPR pairs. It has long been known that learning information about a general quantum state will necessarily disturb it. We refine this result to show that such a disturbance can be done with few side effects, allowing it to circumvent cryptographic protections. Consequently, any scheme to authenticate quantum messages must also encrypt them. In contrast, no such constraint exists classically: authentication and encryption are independent tasks, and one can authenticate a message while leaving it publicly readable. This reasoning has two important consequences: On one hand, it allows us to give a lower bound of 2m key bits for authenticating m qubits, which makes our protocol asymptotically optimal. On the other hand, we use it to show that digitally signing quantum states is impossible, even with only computational security.

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
quantum cryptographyauthentication codesdigital signatures
Contact author(s)
asmith @ theory lcs mit edu
History
2002-06-26: received
Short URL
https://ia.cr/2002/082
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/082,
      author = {Howard Barnum and Claude Crepeau and Daniel Gottesman and Adam Smith and Alain Tapp},
      title = {Authentication of Quantum Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2002/082},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/082}},
      url = {https://eprint.iacr.org/2002/082}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.