Authentication of quantum messages

By Howard Barnum, C. Crépeau, Daniel Gottesman, Adam D. Smith, Alain Tapp. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 2001

318 citations recorded by the source corpus.

Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical secret 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 secret, classical random key, we provide a non-interactive scheme that enables A to both encrypt and authenticate an m qubit message by encoding it into m+s qubits, where the error probability decreases exponentially in the security parameter s. The scheme requires a secret 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. This reasoning has two important consequences: It allows us to give a lower bound of 2m key bits for authenticating m qubits, which makes our protocol asymptotically optimal. Moreover, we use it to show that digitally signing quantum states is impossible.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/a06c1f6f9a8b2fc8db6b5d981c38c8c24a713c8a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Nonbinary Stabilizer Codes Over Finite Fields (2005, background): “ugh [56,70] and [79] paved the way to our approach. After circulating a ﬁrst version of this manuscript, Gottesman drew our attention to another interesting approach that was initiated by Barnum, see [12,13], where a suﬃcient condition for the existence of stabilizer codes is established using a sym”
Advances in quantum cryptography (2019, unknown): “While quantummessage-authentication-codes do exist [736], they bring extra cost.”
Quantum Digital Signatures (2001, background): “By Holevo’s theorem, Eve can acquire at most Tn bits of information about each bit string kib.”