Authentication of Quantum Messages: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
No edit summary
 
(16 intermediate revisions by 3 users not shown)
Line 1: Line 1:
==Functionality==
==Functionality==
If a person sends some information over an insecure channel (a dishonest/malicious party has access to the channel), what is the guarantee that the receiver on the other end will receive the same information as sent and not something which is modified or replaced by the dishonest party? Authentication of quantum channels/quantum states/quantum messages provides 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. Note that, it is different from the functionality of [[Quantum Digital Signature|digital signatures]], a multi-party (more than two) protocol, which comes with additional properties (non-repudiation, unforgeability and transferability). Also, authenticating quantum states is possible but signing quantum states is impossible, as concluded in [[Authentication of Quantum Messages#References|(1)]].  
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. <br/> <br/>Note that, it is different from the functionality of [[Quantum Digital Signature|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 [[Authentication of Quantum Messages#References|(1)]].
Also, unlike [[Authentication of Classical Messages|classical message authentication]], quantum message authentication requires encryption. However, classical messages can be publicly readable (not encrypted) and yet authenticated.


'''Tags:''' [[:Category:Two Party Protocols|Two Party Protocol]][[Category:Two Party Protocols]], [[Quantum Digital Signature]], [[:Category:Quantum Functionality|Quantum Functionality]][[Category:Quantum Functionality]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], [[:Category:Building Blocks|Building Block]][[Category:Building Blocks]]
<br/>'''Tags:''' [[:Category:Two Party Protocols|Two Party Protocol]][[Category:Two Party Protocols]], [[Quantum Digital Signature]], [[:Category:Quantum Functionality|Quantum Functionality]][[Category:Quantum Functionality]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], [[:Category:Building Blocks|Building Block]][[Category:Building Blocks]]


==Use Case==
*No classical analogue
==Protocols==
==Protocols==
*Non-interactive Protocols
'''Non-interactive Protocols:'''
#[[Clifford Based Quantum Authentication]]: requires authenticator to be able to prepare and measure quantum states.
*[[Purity Testing based Quantum Authentication]]
#[[Polynomial Code based Quantum Authentication]]: requires authenticator to only prepare and send quantum states
*[[Polynomial Code based Quantum Authentication]]
*[[Clifford Code for Quantum Authentication]]
*[[Trap Code for Quantum Authentication]]
*[[Auth-QFT-Auth Scheme]]
*[[Unitary Design Scheme]]
'''Interactive Protocols:'''
*[[Naive approach using Quantum Teleportation]]


==Properties==
==Properties==
*Any scheme which authenticates quantum messages must also encrypt them. [[Authentication of Quantum Messages#References|(1)]]
*Any scheme, which authenticates quantum messages must also encrypt them [[Authentication of Quantum Messages#References|(1)]]. This is inherently different to the classical scenario, where encryption and authentication are two independent procedures.
*'''Definition 1:''' A quantum authentication scheme (QAS) is a pair of polynomial time quantum algorithms <math>\mathcal{S}</math> (suppliant) and <math>\mathcal{A}</math> (authenticator) together with a set of classical keys <math>K</math> such that:
 
# <math>\mathcal{S}</math> takes as input an <math>m</math>-qubit message system <math>M</math> and a key <math>k\epsilon K</math> and outputs a transmitted system <math>T</math> of <math>m + t</math> qubits.
*'''Definition: Quantum Authentication Scheme (QAS)''' <br/>A quantum authentication scheme (QAS) consists of a suppliant <math>\mathcal{S}</math>, an authenticator <math>\mathcal{A}</math> and a set of classical private keys <math>K</math>. <math>\mathcal{S}</math> and <math>\mathcal{A}</math> are each polynomial time quantum algorithms. The following is fullfilled:
# <math>\mathcal{A}</math> takes as input the (possibly altered) transmitted system <math>T</math>' and a classical key <math>k\epsilon K</math> and outputs two systems: a <math>m</math>-qubit message state <math>M</math>, and a single qubit <math>V</math> which indicates acceptance or rejection. The classical basis states of <math>V</math> are called <math>|ACC\rangle, |REJ\rangle</math> by convention. For any fixed key <math>k</math>, we denote the corresponding super-operators by <math>S_k</math> and <math>A_k</math>.
# <math>\mathcal{S}</math> takes as input a <math>m</math>-qubit message system <math>M</math> and a key <math>k\in K</math> and outputs a transmitted system <math>T</math> of <math>m + t</math> qubits.
*For non-interactive protocols, a QAS is secure with error <math>\epsilon</math> for a state <math>|\psi\rangle</math> if it satisfies:
# <math>\mathcal{A}</math> takes as input the (possibly altered) transmitted system <math>T^\prime</math> and a classical key <math>k\in K</math> and outputs two systems: a <math>m</math>-qubit message state <math>M</math>, and a single qubit <math>V</math> which indicates acceptance or rejection. The classical basis states of <math>V</math> are called <math>|\mathrm{ACC}\rangle, |\mathrm{REJ}\rangle</math> by convention. </br>For any fixed key <math>k</math>, we denote the corresponding super-operators by <math>S_k</math> and <math>A_k</math>.
#Completeness: For all keys <math>k\epsilon K: B_k(A_k(|\psi\rangle \langle\psi|)=|\psi\rangle \langle\psi| \otimes |\ACC\rangle \langle\ACC|</math>
 
#Soundness:
*'''Definition: Security of a QAS''' <br/>For non-interactive protocols, a QAS is secure with error <math>\epsilon</math> if it is complete for all states <math>|\psi\rangle</math> and has a soundness error <math>\epsilon</math> for all states <math>|\psi\rangle</math>. These two conditions are met if:
#''Completeness:'' A QAS is complete for a specific quantum state <math>|\psi\rangle</math> if <math>\forall k\in K: A_k(S_k(|\psi\rangle \langle\psi|)=|\psi\rangle \langle\psi| \otimes |\mathrm{ACC}\rangle \langle \mathrm{ACC}|.</math> <br/>This means if no adversary has acted on the encoded quantum message <math>|\psi\rangle</math>, the quantum information received by <math>\mathcal{A}</math> is the same initially sent by <math>\mathcal{S}</math> and the single qubit <math>V</math> is in state <math>|\mathrm{ACC}\rangle \langle \mathrm{ACC}|</math>. To this end, we assume that the channel between <math>\mathcal{S}</math> and <math>\mathcal{A}</math> is noiseless if no adversary intervention appeared.
#''Soundness:'' For all super-operators <math>\mathcal{O}</math>, let <math>\rho_\text{auth}</math> be the state output by <math>\mathcal{A}</math> when the adversary’s intervention is characterized by <math>\mathcal{O}</math>, that is: <math display=block>\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),</math> <br/> where again we consider a specific input state <math>|\psi\rangle</math>. Here, <math>\mathbf{E}_k</math> means the expectation when <math>k</math> is chosen uniformly at random from <math>K.</math> The QAS then has a soundness error <math>\epsilon</math> for <math>|\psi\rangle</math> if <math display=block>\mathrm{Tr}\left( P_1^{|\psi\rangle}\rho_\text{auth} \right)\geq 1-\epsilon,</math> </br>where <math>P_1^{|\psi\rangle}</math> is the projector <math display=block>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}|.</math>


==Further Information==
==Further Information==
#[https://arxiv.org/pdf/quant-ph/0205128.pdf Barnum et al (2002)] First protocol 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]]
#[https://arxiv.org/pdf/quant-ph/0205128.pdf| Barnum et al. (2002).] First protocol 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]].
<div style='text-align: right;'>''contributed by Shraddha Singh''</div>
#[https://arxiv.org/pdf/1607.03075.pdf%7C| Broadbent et al. (2016).] Paper on efficient simulation of authentication of quantum messages.
#[https://link.springer.com/chapter/10.1007/978-3-319-56617-7_12| Portmann (2017).] Paper on quantum authentication with full key recycling in the case of acceptance and partial key recycling in the case of tampering detection.
#[https://link.springer.com/article/10.1007%2Fs11047-014-9454-5| Damgård et al. (2014).] Quantum authentication with fully re-usable keys in the case of acceptance using a quantum computer.
#[https://link.springer.com/chapter/10.1007/978-3-319-56617-7_11| Fehr et al. (2017).] More efficient quantum authentication with fully re-usable keys in the case of acceptance without the need of quantum computers.
#[https://link.springer.com/chapter/10.1007/978-3-319-63715-0_12| Garg (2017).] New class of security definitions for quantum authentication and protocols fullfilling these definitions: [[Auth-QFT-Auth Scheme]], [[Unitary Design Scheme]].
 
<div style='text-align: right;'>''Contributed by Isabel Nha Minh Le and Shraddha Singh''</div>
<div style='text-align: right;'>''This page was created within the [https://www.qosf.org/qc_mentorship/| QOSF Mentorship Program Cohort 4]''</div>

Latest revision as of 18:49, 16 January 2022

Functionality[edit]

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.


Tags: Two Party Protocol, Quantum Digital Signature, Quantum Functionality, Specific Task, Building Block

Use Case[edit]

  • No classical analogue

Protocols[edit]

Non-interactive Protocols:

Interactive Protocols:

Properties[edit]

  • 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 , an authenticator and a set of classical private keys Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} . and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} are each polynomial time quantum algorithms. The following is fullfilled:
  1. takes as input a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} -qubit message system and a key and outputs a transmitted system of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m + t} qubits.
  2. takes as input the (possibly altered) transmitted system Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T^\prime} and a classical key and outputs two systems: a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} -qubit message state , and a single qubit which indicates acceptance or rejection. The classical basis states of are called by convention.
    For any fixed key , we denote the corresponding super-operators by and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_k} .
  • Definition: Security of a QAS
    For non-interactive protocols, a QAS is secure with error if it is complete for all states and has a soundness error for all states . These two conditions are met if:
  1. Completeness: A QAS is complete for a specific quantum state if
    This means if no adversary has acted on the encoded quantum message , the quantum information received by is the same initially sent by and the single qubit is in state . To this end, we assume that the channel between and is noiseless if no adversary intervention appeared.
  2. Soundness: For all super-operators , let be the state output by when the adversary’s intervention is characterized by , that is:

    where again we consider a specific input state . Here, means the expectation when is chosen uniformly at random from The QAS then has a soundness error for if

    where is the projector

Further Information[edit]

  1. Barnum et al. (2002). First protocol 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.
  2. Broadbent et al. (2016). Paper on efficient simulation of authentication of quantum messages.
  3. Portmann (2017). Paper on quantum authentication with full key recycling in the case of acceptance and partial key recycling in the case of tampering detection.
  4. Damgård et al. (2014). Quantum authentication with fully re-usable keys in the case of acceptance using a quantum computer.
  5. Fehr et al. (2017). More efficient quantum authentication with fully re-usable keys in the case of acceptance without the need of quantum computers.
  6. Garg (2017). New class of security definitions for quantum authentication and protocols fullfilling these definitions: Auth-QFT-Auth Scheme, Unitary Design Scheme.
Contributed by Isabel Nha Minh Le and Shraddha Singh
This page was created within the QOSF Mentorship Program Cohort 4