© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:quant-ph/0205128 · Annual Symposium on Foundations of Computer Science

Authentication of quantum messages

Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, Alain Tapp

Published Jun 26, 2003• 282 citations

Abstract

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.

DOI: 10.1109/sfcs.2002.1181969

Related papers

A quantum authenticated encryption scheme

Xin Lü, Zhi Ma, Dengguo Feng

Privacy and authenticity are two main tasks for secure communication. In this paper, a quantum authenticated encryption scheme is proposed. This scheme is devised to encrypt and authenticate classical information using quantum states. We assume that Alice and Bob share a classical bits string y as their private key. Alice generates quantum cipher text and authentication tag using her secret key. Bob can decrypt and verify the authenticity of the received message. Security analysis shows that the proposed protocol is a computationally secure encryption and statistically secure authentication scheme.

International Conference on Signal Processing•Jun 28, 2005•3 citations

Quantum authentication scheme based on algebraic coding

Rex A. C. Medeiros, Francisco de Assis, Júior, Bernardo L. +1 more

This paper presents a simple, but efficient class of non-interactive protocols for quantum authentication of $m$-length clas sical messages. The message is encoded using a classical linear algebraic code $C[n,m,t]$. We assume that Alice and Bob share a classical secret key, $x_{AB}$, of $n$ bits. Alice creates $n$ qubits based on the code word and the key, that indicates the bases used to create each qubit. The quantum states are sent to Bob through a noiseless quantum channel. We calculate the failure probability of the protocol considering several types of attacks.

arXiv:quant-ph/0307095•Jul 14, 2003•4 citations

The Universal Composable Security of Quantum Message Authentication with Key Recyling

Patrick M. Hayden, Debbie Leung, Dominic Mayers

Barnum, Crepeau, Gottesman, Tapp, and Smith (quant-ph/0205128) proposed methods for authentication of quantum messages. The first method is an interactive protocol (TQA') based on teleportation. The second method is a noninteractive protocol (QA) in which the sender first encrypts the message using a protocol QEnc and then encodes the quantum ciphertext with an error correcting code chosen secretly from a set (a purity test code (PTC)). Encryption was shown to be necessary for authentication. We augment the protocol QA with an extra step which recycles the entire encryption key provided QA accepts the message. We analyze the resulting integrated protocol for quantum authentication and key generation, which we call QA+KG. Our main result is a proof that QA+KG is universal composably (UC) secure in the Ben-Or-Mayers model (quant-ph/0409062). More specifically, this implies the UC-security of (a) QA, (b) recycling of the encryption key in QA, and (c) key-recycling of the encryption scheme QEnc by appending PTC. For an m-qubit message, encryption requires 2m bits of key; but PTC can be performed using only O(log m) + O(log e) bits of key for probability of failure e. Thus, we reduce the key required for both QA and QEnc, from linear to logarithmic net consumption, at the expense of one bit of back communication which can happen any time after the conclusion of QA and before reusing the key. UC-security of QA also extends security to settings not obvious from quant-ph/0205128. Our security proof structure is inspired by and similar to that of quant-ph/0205128, reducing the security of QA to that of TQA'. In the process, we define UC-secure entanglement, and prove the UC-security of the entanglement generating protocol given in quant-ph/0205128, which could be of independent interest.

arXiv:1610.09434•Oct 29, 2016•13 citations

Protocols for Message Authentication from a Weak Secret

Li Guo, Gang Yao

An authentication protocol is a procedure by which a sender tries to convey n bits of information, which we call an input message, to a receiver. An adversary controls the network over which the sender and the receiver talk and may change any message before it reaches its destination. This paper deals with the simple scenario where two parties, Alice and Bob, communicate and want to assure that the message received by Bob is the one sent by Alice. Unconditional cryptographic security cannot be generated simply from scratch, but must be based on some given primitive to start with. In this paper, we introduce a message authentication protocol with unconditional cryptographic security. More precisely, we give protocols using a weakly secret key allowing for the exchange of authenticated messages.

Applied Mechanics and Materials•Aug 30, 2013•0 citations

Quantum Authentication Protocol for Classical Messages Based on Bell states and Hash Function

Xiangjun Xin, Xiaolin Hua, Jianpo Song +1 more

Quantum authentication protocols can be used to authenticate both quantum messages and classical messages.In this paper, a new quantum authentication protocol of classical messages is proposed.In our protocol, a sequence of Bell states is shared by the message sender and the corresponding receiver.This sequence is used as the authentication key.Four different unitary operations U 0 , U 1 , U 2 and U 3 are used to encode a classical message m and its hash value h(m) into a sequence of Bell states.To authenticate the classical message, the message receiver extracts m and h(m) from the qubits owned by himself/herself, and verifies whether h(m) matches m.The adversary's disturbance to the quantum channel can be detected by checking whether h(m) matches m.The transmitted message has the properties of both secrecy and authentication.Our quantum authentication protocol is secure against message attack and no-message attack.

International Journal of Security and Its Applications•Jul 31, 2015•5 citations

Quantum public-key algorithms to encrypt and authenticate quantum messages with information-theoretic security

Min Liang, Li Yang

Public-key cryptosystems for quantum messages are considered from two aspects: public-key encryption and public-key authentication. Firstly, we propose a general construction of quantum public-key encryption scheme, and then construct an information-theoretic secure instance. Then, we propose a quantum public-key authentication scheme, which can protect the integrity of quantum messages. This scheme can both encrypt and authenticate quantum messages. It is information-theoretic secure with regard to encryption, and the success probability of tampering decreases exponentially with the security parameter with regard to authentication. Compared with classical public-key cryptosystems, one private-key in our schemes corresponds to an exponential number of public-keys, and every quantum public-key used by the sender is an unknown quantum state to the sender.

arXiv:1205.2246•May 10, 2012•1 citation

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.

Privacy and authenticity are two main tasks for secure communication. In this paper, a quantum authenticated encryption scheme is proposed. This scheme is devised to encrypt and authenticate classical information using quantum states. We assume that Alice and Bob share a classical bits string y as their private key. Alice generates quantum cipher text and authentication tag using her secret key. Bob can decrypt and verify the authenticity of the received message. Security analysis shows that the proposed protocol is a computationally secure encryption and statistically secure authentication scheme.

This paper presents a simple, but efficient class of non-interactive protocols for quantum authentication of

m

-length clas sical messages. The message is encoded using a classical linear algebraic code

C[n,m,t]

. We assume that Alice and Bob share a classical secret key,

x_{AB}

, of

n

bits. Alice creates

n

qubits based on the code word and the key, that indicates the bases used to create each qubit. The quantum states are sent to Bob through a noiseless quantum channel. We calculate the failure probability of the protocol considering several types of attacks.

Barnum, Crepeau, Gottesman, Tapp, and Smith (quant-ph/0205128) proposed methods for authentication of quantum messages. The first method is an interactive protocol (TQA') based on teleportation. The second method is a noninteractive protocol (QA) in which the sender first encrypts the message using a protocol QEnc and then encodes the quantum ciphertext with an error correcting code chosen secretly from a set (a purity test code (PTC)). Encryption was shown to be necessary for authentication. We augment the protocol QA with an extra step which recycles the entire encryption key provided QA accepts the message. We analyze the resulting integrated protocol for quantum authentication and key generation, which we call QA+KG. Our main result is a proof that QA+KG is universal composably (UC) secure in the Ben-Or-Mayers model (quant-ph/0409062). More specifically, this implies the UC-security of (a) QA, (b) recycling of the encryption key in QA, and (c) key-recycling of the encryption scheme QEnc by appending PTC. For an m-qubit message, encryption requires 2m bits of key; but PTC can be performed using only O(log m) + O(log e) bits of key for probability of failure e. Thus, we reduce the key required for both QA and QEnc, from linear to logarithmic net consumption, at the expense of one bit of back communication which can happen any time after the conclusion of QA and before reusing the key. UC-security of QA also extends security to settings not obvious from quant-ph/0205128. Our security proof structure is inspired by and similar to that of quant-ph/0205128, reducing the security of QA to that of TQA'. In the process, we define UC-secure entanglement, and prove the UC-security of the entanglement generating protocol given in quant-ph/0205128, which could be of independent interest.

An authentication protocol is a procedure by which a sender tries to convey n bits of information, which we call an input message, to a receiver. An adversary controls the network over which the sender and the receiver talk and may change any message before it reaches its destination. This paper deals with the simple scenario where two parties, Alice and Bob, communicate and want to assure that the message received by Bob is the one sent by Alice. Unconditional cryptographic security cannot be generated simply from scratch, but must be based on some given primitive to start with. In this paper, we introduce a message authentication protocol with unconditional cryptographic security. More precisely, we give protocols using a weakly secret key allowing for the exchange of authenticated messages.

Quantum authentication protocols can be used to authenticate both quantum messages and classical messages.In this paper, a new quantum authentication protocol of classical messages is proposed.In our protocol, a sequence of Bell states is shared by the message sender and the corresponding receiver.This sequence is used as the authentication key.Four different unitary operations U 0 , U 1 , U 2 and U 3 are used to encode a classical message m and its hash value h(m) into a sequence of Bell states.To authenticate the classical message, the message receiver extracts m and h(m) from the qubits owned by himself/herself, and verifies whether h(m) matches m.The adversary's disturbance to the quantum channel can be detected by checking whether h(m) matches m.The transmitted message has the properties of both secrecy and authentication.Our quantum authentication protocol is secure against message attack and no-message attack.

Public-key cryptosystems for quantum messages are considered from two aspects: public-key encryption and public-key authentication. Firstly, we propose a general construction of quantum public-key encryption scheme, and then construct an information-theoretic secure instance. Then, we propose a quantum public-key authentication scheme, which can protect the integrity of quantum messages. This scheme can both encrypt and authenticate quantum messages. It is information-theoretic secure with regard to encryption, and the success probability of tampering decreases exponentially with the security parameter with regard to authentication. Compared with classical public-key cryptosystems, one private-key in our schemes corresponds to an exponential number of public-keys, and every quantum public-key used by the sender is an unknown quantum state to the sender.