Revision History for: Authentication of Quantum Messages
- 2026-06-07 at 18:50 by Mina Doosti
Functionality Description
Quantum authentication allows the exchange of quantum messages between two parties over a insecure quantum channel with the guarantee that the received quantum information is the same as the initially sent quantum message. Imagine a person sends some quantum information to another person over an insecure channel, where a dishonest party has access to the channel. How can it be guaranteed that in the end the receiver has the same quantum information and not something modified or replaced by the dishonest party? Schemes for authentication of quantum channels/quantum states/quantum messages are families of keyed encoding and decoding maps that provide this guarantee to the users of a quantum communication line/ channel. The sender is called the suppliant (prover) and the receiver is called the authenticator. The quantum message is encoded using a quantum error correction code. Since using only one particular quantum error correction code would enable a third party to introduce an error, which is not detectable by this particular code, it is necessary to choose a random quantum error correction code from a set of codes.
Note that, it is different from the functionality of digital signatures, a multi-party (more than two) protocol, which comes with additional properties (non-repudiation, unforgeability and transferability). Authenticating quantum states is possible, but signing quantum states is impossible, as concluded in [1]. Also, unlike classical message authentication, quantum message authentication requires encryption. However, classical messages can be publicly readable (not encrypted) and yet authenticated.
Protocols
The protocols that implement this functionality are:
Classical Analogues
No content has been added to this section, yet!
Real-world Use Cases
No content has been added to this section, yet!
Properties
- Any scheme, which authenticates quantum messages must also encrypt them [1]. This is inherently different to the classical scenario, where encryption and authentication are two independent procedures.
- Definition: Quantum Authentication Scheme (QAS)
A quantum authentication scheme (QAS) consists of a suppliant $\\\mathcal{S}$, an authenticator $\\\mathcal{A}$ and a set of classical private keys $K \\\cdot \\\mathcal{S}$ and $\\\mathcal{A}$ are each polynomial time quantum algorithms. The following is fullfilled:- $S$ takes as input a $m$-qubit message system $M$ and a key $k \\\in K$ and outputs a transmitted system $T$ of $m + t$ qubits.
- $\\\mathcal{A}$ takes as input the (possibly altered) transmitted system $T^{\\\prime }$ and a classical key $k \\\in K$ and outputs two systems: a $m$-qubit message state $M$ and a single qubit $V$ which indicates acceptance or rejection. The classical basis states of $V$ are called $|\\\mathrm{ACC} \\\rangle , |\\\mathrm{REJ} \\\rangle$ by convention. For any fixed key $k$, we denote the corresponding super-operators by $S_{k}$ and $A_{k}$.
- Definition: Security of a QAS
For non-interactive protocols, a QAS is secure with error $\\\epsilon$ if it is complete for all states $|\\\psi \\\rangle$ and has a soundness error $\\\epsilon$ for all states $|\\\psi \\\rangle$. These two conditions are met if:- Completeness: A QAS is complete for a specific quantum state $\\\psi \\\rangle$ if $\\\forall k\\\in K:A_{k}(S_{k}(|\\\psi \\\rangle \\\langle \\\psi |)=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm{ACC} \\\rangle \\\langle \\\mathrm{ACC} |.$ This means if no adversary has acted on the encoded quantum message $|\\\psi \\\rangle$, the quantum information received by $\\\mathcal{A}$ is the same initially sent by $\\\mathcal{S}$ and the single qubit $V$ is in state $|\\\mathrm {ACC} \\\rangle \\\langle \\\mathrm {ACC} |$. To this end, we assume that the channel between $\\\mathcal {S}$ and $\\\mathcal {A}$ is noiseless if no adversary intervention appeared.
- Soundness: For all super-operators $\\\mathcal {O}$, let $\\\rho _{\\\text{auth}}$ be the state output by $\\\mathcal {A}$ when the adversary’s intervention is characterized by $\\\mathcal{O}$, that is: $$ \\\rho _{\\\text{auth}}=\\\mathbf {E} _{k}\\\left[{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right)\\\right]={\\\frac {1}{|K|}}\\\sum _{k}{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}_{k}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right),$$
where again we consider a specific input state $|\\\psi \\\rangle$. Here, $\\\mathbf{E} _{k}$ means the expectation when $k$ is chosen uniformly at random from $K$. The QAS then has a soundness error $\\\epsilon$ for $|\\\psi \\\rangle$ if
$$ \\\mathrm {Tr} \\\left(P_{1}^{|\\\psi \\\rangle }\\\rho _{\\\text{auth}}\\\right)\\\geq 1-\\\epsilon ,$$
where $P_{1}^{|\\\psi \\\rangle }$ is the projector $$P_{1}^{|\\\psi \\\rangle }=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes I_{V}+I_{M}\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |-|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |.$$
Further Information
Some papers related to the authentication of quantum messages:
- First protocol [1] on authentication of quantum messages. It is also used later for verification of quantum computation in Interactive Proofs for Quantum Computation. Protocol file for this article is given as the Polynomial Code based Quantum Authentication. acheck
- Paper [2] on efficient simulation of authentication of quantum messages.
- Paper [3] on quantum authentication with full key recycling in the case of acceptance and partial key recycling in the case of tampering detection.
- [4]: Quantum authentication with fully re-usable keys in the case of acceptance using a quantum computer.
- [5]: More efficient quantum authentication with fully re-usable keys in the case of acceptance without the need of quantum computers.
- New class [6] of security definitions for quantum authentication and protocols fullfilling the definitions of Auth-QFT-Auth Scheme and Unitary Design Scheme. acheck
References
* The original version of this page on the old QPZoo was created by Isabel Nha Minh Le and Shraddha Singh.
- Barnum, Howard, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. “Authentication of quantum messages.” In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 449-458. IEEE, 2002.
- Broadbent, Anne, and Evelyn Wainewright. “Efficient simulation for quantum message authentication.” In Information Theoretic Security: 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers 9, pp. 72-91. Springer International Publishing, 2016.
- Portmann, Christopher. “Quantum authentication with key recycling.” In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part III 36, pp. 339-368. Springer International Publishing, 2017.
- [Damgård et al. (2014)]
- Fehr, Serge, and Louis Salvail. “Quantum Authentication and Encryption with Key Recycling: Or: How to Re-use a One-Time Pad Even if—Safely & Feasibly.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 311-338. Cham: Springer International Publishing, 2017.
- Garg, Sumegha, Henry Yuen, and Mark Zhandry. “New security notions and feasibility results for authentication of quantum data.” In Advances in Cryptology–CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II 37, pp. 342-371. Springer International Publishing, 2017.
- 2025-06-24 at 21:22 by JuliaM
Functionality Description
Quantum authentication allows the exchange of quantum messages between two parties over a insecure quantum channel with the guarantee that the received quantum information is the same as the initially sent quantum message. Imagine a person sends some quantum information to another person over an insecure channel, where a dishonest party has access to the channel. How can it be guaranteed that in the end the receiver has the same quantum information and not something modified or replaced by the dishonest party? Schemes for authentication of quantum channels/quantum states/quantum messages are families of keyed encoding and decoding maps that provide this guarantee to the users of a quantum communication line/ channel. The sender is called the suppliant (prover) and the receiver is called the authenticator. The quantum message is encoded using a quantum error correction code. Since using only one particular quantum error correction code would enable a third party to introduce an error, which is not detectable by this particular code, it is necessary to choose a random quantum error correction code from a set of codes.
Note that, it is different from the functionality of digital signatures, a multi-party (more than two) protocol, which comes with additional properties (non-repudiation, unforgeability and transferability). Authenticating quantum states is possible, but signing quantum states is impossible, as concluded in [1]. Also, unlike classical message authentication, quantum message authentication requires encryption. However, classical messages can be publicly readable (not encrypted) and yet authenticated.
Protocols
The protocols that implement this functionality are:
Classical Analogues
No content has been added to this section, yet!
Real-world Use Cases
No content has been added to this section, yet!
Properties
- Any scheme, which authenticates quantum messages must also encrypt them [1]. This is inherently different to the classical scenario, where encryption and authentication are two independent procedures.
- Definition: Quantum Authentication Scheme (QAS)
A quantum authentication scheme (QAS) consists of a suppliant $\\\mathcal{S}$, an authenticator $\\\mathcal{A}$ and a set of classical private keys $K \\\cdot \\\mathcal{S}$ and $\\\mathcal{A}$ are each polynomial time quantum algorithms. The following is fullfilled:- $S$ takes as input a $m$-qubit message system $M$ and a key $k \\\in K$ and outputs a transmitted system $T$ of $m + t$ qubits.
- $\\\mathcal{A}$ takes as input the (possibly altered) transmitted system $T^{\\\prime }$ and a classical key $k \\\in K$ and outputs two systems: a $m$-qubit message state $M$ and a single qubit $V$ which indicates acceptance or rejection. The classical basis states of $V$ are called $|\\\mathrm{ACC} \\\rangle , |\\\mathrm{REJ} \\\rangle$ by convention. For any fixed key $k$, we denote the corresponding super-operators by $S_{k}$ and $A_{k}$.
- Definition: Security of a QAS
For non-interactive protocols, a QAS is secure with error $\\\epsilon$ if it is complete for all states $|\\\psi \\\rangle$ and has a soundness error $\\\epsilon$ for all states $|\\\psi \\\rangle$. These two conditions are met if:- Completeness: A QAS is complete for a specific quantum state $\\\psi \\\rangle$ if $\\\forall k\\\in K:A_{k}(S_{k}(|\\\psi \\\rangle \\\langle \\\psi |)=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm{ACC} \\\rangle \\\langle \\\mathrm{ACC} |.$ This means if no adversary has acted on the encoded quantum message $|\\\psi \\\rangle$, the quantum information received by $\\\mathcal{A}$ is the same initially sent by $\\\mathcal{S}$ and the single qubit $V$ is in state $|\\\mathrm {ACC} \\\rangle \\\langle \\\mathrm {ACC} |$. To this end, we assume that the channel between $\\\mathcal {S}$ and $\\\mathcal {A}$ is noiseless if no adversary intervention appeared.
- Soundness: For all super-operators $\\\mathcal {O}$, let $\\\rho _{\\\text{auth}}$ be the state output by $\\\mathcal {A}$ when the adversary’s intervention is characterized by $\\\mathcal{O}$, that is: $$ \\\rho _{\\\text{auth}}=\\\mathbf {E} _{k}\\\left[{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right)\\\right]={\\\frac {1}{|K|}}\\\sum _{k}{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}_{k}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right),$$
where again we consider a specific input state $|\\\psi \\\rangle$. Here, $\\\mathbf{E} _{k}$ means the expectation when $k$ is chosen uniformly at random from $K$. The QAS then has a soundness error $\\\epsilon$ for $|\\\psi \\\rangle$ if
$$ \\\mathrm {Tr} \\\left(P_{1}^{|\\\psi \\\rangle }\\\rho _{\\\text{auth}}\\\right)\\\geq 1-\\\epsilon ,$$
where $P_{1}^{|\\\psi \\\rangle }$ is the projector $$P_{1}^{|\\\psi \\\rangle }=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes I_{V}+I_{M}\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |-|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |.$$
Further Information
Some papers related to the authentication of quantum messages:
- First protocol [1] on authentication of quantum messages. It is also used later for verification of quantum computation in Interactive Proofs for Quantum Computation. Protocol file for this article is given as the Polynomial Code based Quantum Authentication. acheck
- Paper [2] on efficient simulation of authentication of quantum messages.
- Paper [3] on quantum authentication with full key recycling in the case of acceptance and partial key recycling in the case of tampering detection.
- [4]: Quantum authentication with fully re-usable keys in the case of acceptance using a quantum computer.
- [5]: More efficient quantum authentication with fully re-usable keys in the case of acceptance without the need of quantum computers.
- New class [6] of security definitions for quantum authentication and protocols fullfilling the definitions of Auth-QFT-Auth Scheme and Unitary Design Scheme. acheck
References
- Barnum, Howard, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. “Authentication of quantum messages.” In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 449-458. IEEE, 2002.
- Broadbent, Anne, and Evelyn Wainewright. “Efficient simulation for quantum message authentication.” In Information Theoretic Security: 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers 9, pp. 72-91. Springer International Publishing, 2016.
- Portmann, Christopher. “Quantum authentication with key recycling.” In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part III 36, pp. 339-368. Springer International Publishing, 2017.
- [Damgård et al. (2014)]
- Fehr, Serge, and Louis Salvail. “Quantum Authentication and Encryption with Key Recycling: Or: How to Re-use a One-Time Pad Even if—Safely & Feasibly.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 311-338. Cham: Springer International Publishing, 2017.
- Garg, Sumegha, Henry Yuen, and Mark Zhandry. “New security notions and feasibility results for authentication of quantum data.” In Advances in Cryptology–CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II 37, pp. 342-371. Springer International Publishing, 2017.
- 2025-05-15 at 10:59 by JuliaM
Functionality Description
Quantum authentication allows the exchange of quantum messages between two parties over a insecure quantum channel with the guarantee that the received quantum information is the same as the initially sent quantum message. Imagine a person sends some quantum information to another person over an insecure channel, where a dishonest party has access to the channel. How can it be guaranteed that in the end the receiver has the same quantum information and not something modified or replaced by the dishonest party? Schemes for authentication of quantum channels/quantum states/quantum messages are families of keyed encoding and decoding maps that provide this guarantee to the users of a quantum communication line/ channel. The sender is called the suppliant (prover) and the receiver is called the authenticator. The quantum message is encoded using a quantum error correction code. Since using only one particular quantum error correction code would enable a third party to introduce an error, which is not detectable by this particular code, it is necessary to choose a random quantum error correction code from a set of codes.
Note that, it is different from the functionality of digital signatures, a multi-party (more than two) protocol, which comes with additional properties (non-repudiation, unforgeability and transferability). Authenticating quantum states is possible, but signing quantum states is impossible, as concluded in [1]. Also, unlike classical message authentication, quantum message authentication requires encryption. However, classical messages can be publicly readable (not encrypted) and yet authenticated.
Protocols
No protocols implement this functionality yet.
Classical Analogues
No content has been added to this section, yet!
Real-world Use Cases
No content has been added to this section, yet!
Properties
- Any scheme, which authenticates quantum messages must also encrypt them [1]. This is inherently different to the classical scenario, where encryption and authentication are two independent procedures.
- Definition: Quantum Authentication Scheme (QAS)
A quantum authentication scheme (QAS) consists of a suppliant $\\\mathcal{S}$, an authenticator $\\\mathcal{A}$ and a set of classical private keys $K \\\cdot \\\mathcal{S}$ and $\\\mathcal{A}$ are each polynomial time quantum algorithms. The following is fullfilled:- $S$ takes as input a $m$-qubit message system $M$ and a key $k \\\in K$ and outputs a transmitted system $T$ of $m + t$ qubits.
- $\\\mathcal{A}$ takes as input the (possibly altered) transmitted system $T^{\\\prime }$ and a classical key $k \\\in K$ and outputs two systems: a $m$-qubit message state $M$ and a single qubit $V$ which indicates acceptance or rejection. The classical basis states of $V$ are called $|\\\mathrm{ACC} \\\rangle , |\\\mathrm{REJ} \\\rangle$ by convention. For any fixed key $k$, we denote the corresponding super-operators by $S_{k}$ and $A_{k}$.
- Definition: Security of a QAS
For non-interactive protocols, a QAS is secure with error $\\\epsilon$ if it is complete for all states $|\\\psi \\\rangle$ and has a soundness error $\\\epsilon$ for all states $|\\\psi \\\rangle$. These two conditions are met if:- Completeness: A QAS is complete for a specific quantum state $\\\psi \\\rangle$ if $\\\forall k\\\in K:A_{k}(S_{k}(|\\\psi \\\rangle \\\langle \\\psi |)=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm{ACC} \\\rangle \\\langle \\\mathrm{ACC} |.$ This means if no adversary has acted on the encoded quantum message $|\\\psi \\\rangle$, the quantum information received by $\\\mathcal{A}$ is the same initially sent by $\\\mathcal{S}$ and the single qubit $V$ is in state $|\\\mathrm {ACC} \\\rangle \\\langle \\\mathrm {ACC} |$. To this end, we assume that the channel between $\\\mathcal {S}$ and $\\\mathcal {A}$ is noiseless if no adversary intervention appeared.
- Soundness: For all super-operators $\\\mathcal {O}$, let $\\\rho _{\\\text{auth}}$ be the state output by $\\\mathcal {A}$ when the adversary’s intervention is characterized by $\\\mathcal{O}$, that is: $$ \\\rho _{\\\text{auth}}=\\\mathbf {E} _{k}\\\left[{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right)\\\right]={\\\frac {1}{|K|}}\\\sum _{k}{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}_{k}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right),$$
where again we consider a specific input state $|\\\psi \\\rangle$. Here, $\\\mathbf{E} _{k}$ means the expectation when $k$ is chosen uniformly at random from $K$. The QAS then has a soundness error $\\\epsilon$ for $|\\\psi \\\rangle$ if
$$ \\\mathrm {Tr} \\\left(P_{1}^{|\\\psi \\\rangle }\\\rho _{\\\text{auth}}\\\right)\\\geq 1-\\\epsilon ,$$
where $P_{1}^{|\\\psi \\\rangle }$ is the projector $$P_{1}^{|\\\psi \\\rangle }=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes I_{V}+I_{M}\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |-|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |.$$
Further Information
Some papers related to the authentication of quantum messages:
- First protocol [1] on authentication of quantum messages. It is also used later for verification of quantum computation in Interactive Proofs for Quantum Computation. Protocol file for this article is given as the Polynomial Code based Quantum Authentication. acheck
- Paper [2] on efficient simulation of authentication of quantum messages.
- Paper [3] on quantum authentication with full key recycling in the case of acceptance and partial key recycling in the case of tampering detection.
- [4]: Quantum authentication with fully re-usable keys in the case of acceptance using a quantum computer.
- [5]: More efficient quantum authentication with fully re-usable keys in the case of acceptance without the need of quantum computers.
- New class [6] of security definitions for quantum authentication and protocols fullfilling the definitions of Auth-QFT-Auth Scheme and Unitary Design Scheme. acheck
References
- Barnum, Howard, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. “Authentication of quantum messages.” In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 449-458. IEEE, 2002.
- Broadbent, Anne, and Evelyn Wainewright. “Efficient simulation for quantum message authentication.” In Information Theoretic Security: 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers 9, pp. 72-91. Springer International Publishing, 2016.
- Portmann, Christopher. “Quantum authentication with key recycling.” In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part III 36, pp. 339-368. Springer International Publishing, 2017.
- [Damgård et al. (2014)]
- Fehr, Serge, and Louis Salvail. “Quantum Authentication and Encryption with Key Recycling: Or: How to Re-use a One-Time Pad Even if—Safely & Feasibly.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 311-338. Cham: Springer International Publishing, 2017.
- Garg, Sumegha, Henry Yuen, and Mark Zhandry. “New security notions and feasibility results for authentication of quantum data.” In Advances in Cryptology–CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II 37, pp. 342-371. Springer International Publishing, 2017.
- 2025-05-15 at 10:56 by JuliaM
Functionality Description
Quantum authentication allows the exchange of quantum messages between two parties over a insecure quantum channel with the guarantee that the received quantum information is the same as the initially sent quantum message. Imagine a person sends some quantum information to another person over an insecure channel, where a dishonest party has access to the channel. How can it be guaranteed that in the end the receiver has the same quantum information and not something modified or replaced by the dishonest party? Schemes for authentication of quantum channels/quantum states/quantum messages are families of keyed encoding and decoding maps that provide this guarantee to the users of a quantum communication line/ channel. The sender is called the suppliant (prover) and the receiver is called the authenticator. The quantum message is encoded using a quantum error correction code. Since using only one particular quantum error correction code would enable a third party to introduce an error, which is not detectable by this particular code, it is necessary to choose a random quantum error correction code from a set of codes.
Note that, it is different from the functionality of digital signatures, a multi-party (more than two) protocol, which comes with additional properties (non-repudiation, unforgeability and transferability). Authenticating quantum states is possible, but signing quantum states is impossible, as concluded in [1]. Also, unlike classical message authentication, quantum message authentication requires encryption. However, classical messages can be publicly readable (not encrypted) and yet authenticated.
Classical Analogues
Real-world Use Cases
Properties
- Any scheme, which authenticates quantum messages must also encrypt them [1]. This is inherently different to the classical scenario, where encryption and authentication are two independent procedures.
- Definition: Quantum Authentication Scheme (QAS)
A quantum authentication scheme (QAS) consists of a suppliant $\\\mathcal{S}$, an authenticator $\\\mathcal{A}$ and a set of classical private keys $K \\\cdot \\\mathcal{S}$ and $\\\mathcal{A}$ are each polynomial time quantum algorithms. The following is fullfilled:- $S$ takes as input a $m$-qubit message system $M$ and a key $k \\\in K$ and outputs a transmitted system $T$ of $m + t$ qubits.
- $\\\mathcal{A}$ takes as input the (possibly altered) transmitted system $T^{\\\prime }$ and a classical key $k \\\in K$ and outputs two systems: a $m$-qubit message state $M$ and a single qubit $V$ which indicates acceptance or rejection. The classical basis states of $V$ are called $|\\\mathrm{ACC} \\\rangle , |\\\mathrm{REJ} \\\rangle$ by convention. For any fixed key $k$, we denote the corresponding super-operators by $S_{k}$ and $A_{k}$.
- Definition: Security of a QAS
For non-interactive protocols, a QAS is secure with error $\\\epsilon$ if it is complete for all states $|\\\psi \\\rangle$ and has a soundness error $\\\epsilon$ for all states $|\\\psi \\\rangle$. These two conditions are met if:- Completeness: A QAS is complete for a specific quantum state $\\\psi \\\rangle$ if $\\\forall k\\\in K:A_{k}(S_{k}(|\\\psi \\\rangle \\\langle \\\psi |)=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm{ACC} \\\rangle \\\langle \\\mathrm{ACC} |.$ This means if no adversary has acted on the encoded quantum message $|\\\psi \\\rangle$, the quantum information received by $\\\mathcal{A}$ is the same initially sent by $\\\mathcal{S}$ and the single qubit $V$ is in state $|\\\mathrm {ACC} \\\rangle \\\langle \\\mathrm {ACC} |$. To this end, we assume that the channel between $\\\mathcal {S}$ and $\\\mathcal {A}$ is noiseless if no adversary intervention appeared.
- Soundness: For all super-operators $\\\mathcal {O}$, let $\\\rho _{\\\text{auth}}$ be the state output by $\\\mathcal {A}$ when the adversary’s intervention is characterized by $\\\mathcal{O}$, that is: $$ \\\rho _{\\\text{auth}}=\\\mathbf {E} _{k}\\\left[{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right)\\\right]={\\\frac {1}{|K|}}\\\sum _{k}{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}_{k}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right),$$
where again we consider a specific input state $|\\\psi \\\rangle$. Here, $\\\mathbf{E} _{k}$ means the expectation when $k$ is chosen uniformly at random from $K$. The QAS then has a soundness error $\\\epsilon$ for $|\\\psi \\\rangle$ if
$$ \\\mathrm {Tr} \\\left(P_{1}^{|\\\psi \\\rangle }\\\rho _{\\\text{auth}}\\\right)\\\geq 1-\\\epsilon ,$$
where $P_{1}^{|\\\psi \\\rangle }$ is the projector $$P_{1}^{|\\\psi \\\rangle }=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes I_{V}+I_{M}\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |-|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |.$$
Future Information
Some papers related to the authentication of quantum messages:
- First protocol [1] on authentication of quantum messages. It is also used later for verification of quantum computation in Interactive Proofs for Quantum Computation. Protocol file for this article is given as the Polynomial Code based Quantum Authentication. acheck
- Paper [2] on efficient simulation of authentication of quantum messages.
- Paper [3] on quantum authentication with full key recycling in the case of acceptance and partial key recycling in the case of tampering detection.
- [4]: Quantum authentication with fully re-usable keys in the case of acceptance using a quantum computer.
- [5]: More efficient quantum authentication with fully re-usable keys in the case of acceptance without the need of quantum computers.
- New class [6] of security definitions for quantum authentication and protocols fullfilling the definitions of Auth-QFT-Auth Scheme and Unitary Design Scheme. acheck
References
- Barnum, Howard, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. “Authentication of quantum messages.” In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 449-458. IEEE, 2002.
- Broadbent, Anne, and Evelyn Wainewright. “Efficient simulation for quantum message authentication.” In Information Theoretic Security: 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers 9, pp. 72-91. Springer International Publishing, 2016.
- Portmann, Christopher. “Quantum authentication with key recycling.” In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part III 36, pp. 339-368. Springer International Publishing, 2017.
- [Damgård et al. (2014)]
- Fehr, Serge, and Louis Salvail. “Quantum Authentication and Encryption with Key Recycling: Or: How to Re-use a One-Time Pad Even if—Safely & Feasibly.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 311-338. Cham: Springer International Publishing, 2017.
- Garg, Sumegha, Henry Yuen, and Mark Zhandry. “New security notions and feasibility results for authentication of quantum data.” In Advances in Cryptology–CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II 37, pp. 342-371. Springer International Publishing, 2017.
- 2025-05-15 at 10:56 by JuliaM
Functionality Description
Quantum authentication allows the exchange of quantum messages between two parties over a insecure quantum channel with the guarantee that the received quantum information is the same as the initially sent quantum message. Imagine a person sends some quantum information to another person over an insecure channel, where a dishonest party has access to the channel. How can it be guaranteed that in the end the receiver has the same quantum information and not something modified or replaced by the dishonest party? Schemes for authentication of quantum channels/quantum states/quantum messages are families of keyed encoding and decoding maps that provide this guarantee to the users of a quantum communication line/ channel. The sender is called the suppliant (prover) and the receiver is called the authenticator. The quantum message is encoded using a quantum error correction code. Since using only one particular quantum error correction code would enable a third party to introduce an error, which is not detectable by this particular code, it is necessary to choose a random quantum error correction code from a set of codes.
Note that, it is different from the functionality of digital signatures, a multi-party (more than two) protocol, which comes with additional properties (non-repudiation, unforgeability and transferability). Authenticating quantum states is possible, but signing quantum states is impossible, as concluded in [1]. Also, unlike classical message authentication, quantum message authentication requires encryption. However, classical messages can be publicly readable (not encrypted) and yet authenticated.
Classical Analogues
Real-world Use Cases
Properties
- Any scheme, which authenticates quantum messages must also encrypt them [1]. This is inherently different to the classical scenario, where encryption and authentication are two independent procedures.
- Definition: Quantum Authentication Scheme (QAS)
A quantum authentication scheme (QAS) consists of a suppliant $\\\mathcal{S}$, an authenticator $\\\mathcal{A}$ and a set of classical private keys $K \\\cdot \\\mathcal{S}$ and $\\\mathcal{A}$ are each polynomial time quantum algorithms. The following is fullfilled:- $S$ takes as input a $m$-qubit message system $M$ and a key $k \\\in K$ and outputs a transmitted system $T$ of $m + t$ qubits.
- $\\\mathcal{A}$ takes as input the (possibly altered) transmitted system $T^{\\\prime }$ and a classical key $k \\\in K$ and outputs two systems: a $m$-qubit message state $M$ and a single qubit $V$ which indicates acceptance or rejection. The classical basis states of $V$ are called $|\\\mathrm{ACC} \\\rangle , |\\\mathrm{REJ} \\\rangle$ by convention. For any fixed key $k$, we denote the corresponding super-operators by $S_{k}$ and $A_{k}$.
- Definition: Security of a QAS
For non-interactive protocols, a QAS is secure with error $\\\epsilon$ if it is complete for all states $|\\\psi \\\rangle$ and has a soundness error $\\\epsilon$ for all states $|\\\psi \\\rangle$. These two conditions are met if:- Completeness: A QAS is complete for a specific quantum state $\\\psi \\\rangle$ if $\\\forall k\\\in K:A_{k}(S_{k}(|\\\psi \\\rangle \\\langle \\\psi |)=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm{ACC} \\\rangle \\\langle \\\mathrm{ACC} |.$ This means if no adversary has acted on the encoded quantum message $|\\\psi \\\rangle$, the quantum information received by $\\\mathcal{A}$ is the same initially sent by $\\\mathcal{S}$ and the single qubit $V$ is in state $|\\\mathrm {ACC} \\\rangle \\\langle \\\mathrm {ACC} |$. To this end, we assume that the channel between $\\\mathcal {S}$ and $\\\mathcal {A}$ is noiseless if no adversary intervention appeared.
- Soundness: For all super-operators $\\\mathcal {O}$, let $\\\rho _{\\\text{auth}}$ be the state output by $\\\mathcal {A}$ when the adversary’s intervention is characterized by $\\\mathcal{O}$, that is: $$ \\\rho _{\\\text{auth}}=\\\mathbf {E} _{k}\\\left[{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right)\\\right]={\\\frac {1}{|K|}}\\\sum _{k}{\\\mathcal {A}}_{k}\\\left({\\\mathcal {O}}({\\\mathcal {S}}_{k}(|\\\psi \\\rangle \\\langle \\\psi |))\\\right),$$
where again we consider a specific input state $|\\\psi \\\rangle$. Here, $\\\mathbf{E} _{k}$ means the expectation when $k$ is chosen uniformly at random from $K$. The QAS then has a soundness error $\\\epsilon$ for $|\\\psi \\\rangle$ if
$$ \\\mathrm {Tr} \\\left(P_{1}^{|\\\psi \\\rangle }\\\rho _{\\\text{auth}}\\\right)\\\geq 1-\\\epsilon ,$$
where $P_{1}^{|\\\psi \\\rangle }$ is the projector $$P_{1}^{|\\\psi \\\rangle }=|\\\psi \\\rangle \\\langle \\\psi |\\\otimes I_{V}+I_{M}\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |-|\\\psi \\\rangle \\\langle \\\psi |\\\otimes |\\\mathrm {REJ} \\\rangle \\\langle \\\mathrm {REJ} |.$$
Future Information
Some papers related to the authentication of quantum messages:
- First protocol [1] on authentication of quantum messages. It is also used later for verification of quantum computation in Interactive Proofs for Quantum Computation. Protocol file for this article is given as the Polynomial Code based Quantum Authentication. acheck
- Paper [2] on efficient simulation of authentication of quantum messages.
- Paper [3] on quantum authentication with full key recycling in the case of acceptance and partial key recycling in the case of tampering detection.
- [4]: Quantum authentication with fully re-usable keys in the case of acceptance using a quantum computer.
- [5]: More efficient quantum authentication with fully re-usable keys in the case of acceptance without the need of quantum computers.
- New class [6] of security definitions for quantum authentication and protocols fullfilling the definitions of Auth-QFT-Auth Scheme and Unitary Design Scheme. acheck
References
- Barnum, Howard, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. “Authentication of quantum messages.” In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pp. 449-458. IEEE, 2002.
- Broadbent, Anne, and Evelyn Wainewright. “Efficient simulation for quantum message authentication.” In Information Theoretic Security: 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers 9, pp. 72-91. Springer International Publishing, 2016.
- Portmann, Christopher. “Quantum authentication with key recycling.” In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part III 36, pp. 339-368. Springer International Publishing, 2017.
- [Damgård et al. (2014)]
- Fehr, Serge, and Louis Salvail. “Quantum Authentication and Encryption with Key Recycling: Or: How to Re-use a One-Time Pad Even if—Safely & Feasibly.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 311-338. Cham: Springer International Publishing, 2017.
- Garg, Sumegha, Henry Yuen, and Mark Zhandry. “New security notions and feasibility results for authentication of quantum data.” In Advances in Cryptology–CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II 37, pp. 342-371. Springer International Publishing, 2017.