Quantum Protocol Zoo - User contributions [en]

Protocol Library

2021-12-10T18:41:08Z

137.226.108.44:

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="5"|[[Authentication of Quantum Messages]]||[[Purity Testing based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
|[[Clifford Code for Quantum Authentication]]
|-
|[[Trap Code for Quantum Authentication]]
|-
|[[Naive approach using Quantum Teleportation]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|[[Verification of Universal Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of Sub-Universal Quantum Computation]]||[[-]]
|-
|[[Verification of NP-complete problems]]||[[-]]
|-
|[[Classical Verification of Universal Quantum Computation]]||[[-]]
|-
|rowspan="4"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="1"|[[Entanglement Routing]]||[[Distributing Graph States Over Arbitrary Quantum Networks]]

Trap Code for Quantum Authentication

2021-12-08T17:24:39Z

137.226.108.44: Created page with "==Notation== *<math>\rho</math>: 1-qubit input state ==Protocol Description== *'''''Encoding:''''' #Input: <math>\rho</math>, pair of keys <math>k=(k_1, k_2)</math> #Apply a..."

==Notation==
*<math>\rho</math>: 1-qubit input state

==Protocol Description==
*'''''Encoding:'''''
#Input: <math>\rho</math>, pair of keys <math>k=(k_1, k_2)</math>
#Apply an <math>[[n,1,d]]</math> error correction code (corrects up to <math>t</math> errors, <math>d=2t+1</math>)
#Append an additional trap register of <math>n</math> qubits in state <math>|0\rangle\langle 0|^{\otimes n}</math>
#Append a second additional trap register of <math>n</math> qubits in state <math>|+\rangle\langle +|^{\otimes n}</math>
#Permute the total <math>3n</math>-qubit register by <math>\pi_{k_1}</math> according to the key <math>k_1</math>
#Apply a Pauli encryption <math>P_{k_2}</math> according to key <math>k_2</math>
*'''''Decoding:'''''
#Input: <math>\rho^\prime</math> (state after encoding), pair of keys <math>k=(k_1, k_2)</math>
#Apply <math>P_{k_2}</math> according to key <math>k_2</math>
#Apply inverse permutation <math>\pi_{k_1}^\dagger</math> according to the key <math>k_1</math>
#Measure the last <math>n</math> qubits in the Hadamard basis
#Measure the second last <math>n</math> qubits in the computational basis </br>a. If the two measurements result in <math>|+\rangle\langle +|</math> and <math>|0\rangle\langle 0|</math>, an additional flag qubit in state <math>|\mathrm{ACC}\rangle\langle\mathrm{ACC}|</math> is appended and the quantum message is decoded according to the error correction code </br>b. Otherwise, an additional flag qubit in state <math>|\mathrm{REJ}\rangle\langle\mathrm{REJ}|</math> is appended and the (disturbed) encoded quantum message is replaced by a fixed state <math>\Omega</math>

==References==
#[https://arxiv.org/pdf/1211.1080.pdf| Broadbent et al. (2012)]
#[https://arxiv.org/pdf/1607.03075.pdf| Broadbent and Wainewright (2016).]

Polynomial Code based Quantum Authentication

2021-12-08T17:24:32Z

137.226.108.44:

The paper [https://arxiv.org/pdf/quant-ph/0205128.pdf Authentication of Quantum Messages by Barnum et al.] provides a non-interactive scheme for the sender to encrypt as well as [[Authentication of Quantum Messages|authenticate quantum messages]]. It was the first protocol designed to achieve the task of authentication for quantum states, i.e. it gives the guarantee that the message sent by a party (suppliant) over a communication line is received by a party on the other end (authenticator) as it is and, has not been tampered with or modified by the dishonest party (eavesdropper).

'''Tags:''' [[:Category:Two Party Protocols|Two Party Protocol]][[Category:Two Party Protocols]], [[:Category:Quantum Functionality|Quantum Functionality]][[Category:Quantum Functionality]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], [[:Category:Building Blocks|Building Block]][[Category:Building Blocks]]

==Assumptions==
*The sender and the receiver share a private, classical random key drawn from a probability distribution

==Notations==
*<math>\mathcal{S}</math>: suppliant (sender)
*<math>\mathcal{A}</math>: authenticator (prover)
*<math>\rho</math>: quantum message to be sent
*<math>m</math>: number of qubits in the message <math>\rho</math>
*<math>\{Q_k\}</math>: [[Stabilizer Purity Testing Code | stabilizer purity testing code]], each stabilizer code is identified by index <math>k</math>
*<math>n</math>: number of qubits used to encode the message with <math>\{Q_k\}</math>
*<math>x</math>: random binary <math>2m</math>-bit key
*<math>s</math>: security parameter

==Properties==
*For a <math>m</math>-qubit message, the protocol requires <math>m+s</math> qubits to encode the quantum message.
*The protocol requires a private key of size <math>2m+O(s)</math>.

==Protocol Description==
*'''''Preprocessing:''''' <math>\mathcal{S}</math> and <math>\mathcal{A}</math> agree on some [[Stabilizer Purity Testing Code | stabilizer purity testing code]] <math>\{Q_k\}</math> and some private and random binary strings <math>k, x, y</math>.
**<math>k</math> is used to choose a random stabilizer code <math>Q_k</math>
**<math>x</math> is a <math>2m</math>-bit random key used for q-encryption
**<math>y</math> is a random syndrome
*'''''Encryption and encoding:'''''
#<math>\mathcal{S}</math> q-encrypts the <math>m</math>-qubit original message <math>\rho</math> as <math>\tau</math> using the classical key <math>x</math> and a [[Quantum One-Time Pad | quantum one-time pad]]. This encryption is given by <math>\tau = \sigma_x^{\vec{t}_1}\sigma_z^{\vec{t}_2}\rho\sigma_z^{\vec{1}_1}\sigma_x^{\vec{t}_1}</math>, where <math>\vec{t}_1</math> and <math>\vec{t}_2</math> are <math>m</math>-bit vectors and given by the random binary key <math>x</math>.
#<math>\mathcal{S}</math> then encodes <math>\tau</math> according to <math>Q_k</math> with syndrome <math>y</math>, which results in the <math>n</math>-qubit state <math>\sigma</math>. This means <math>\mathcal{S}</math> encodes <math>\rho</math> in <math>n</math> qubits using <math>Q_k</math>, and then "applies" errors according to the random syndrome.
#<math>\mathcal{S}</math> sends <math>\sigma</math> to <math>\mathcal{A}</math>.
*'''''Decoding and decryption:'''''
#<math>\mathcal{A}</math> receives the <math>n</math> qubits, whose state is denoted by <math>\sigma^\prime</math>.
#<math>\mathcal{A}</math> measures the syndrome <math>y^\prime</math> of the code <math>Q_k</math> on his <math>n</math> qubits in state <math>\sigma^\prime</math>.
#<math>\mathcal{A}</math> compares the syndromes <math>y</math> and <math>y^\prime</math> and aborts the process if they are different.
#<math>\mathcal{A}</math> decodes his <math>n</math>-qubit word according to <math>Q_k</math> obtaining <math>\tau^\prime</math>.
#<math>\mathcal{A}</math> q-decrypts <math>\tau^\prime</math> using the random binary strings <math>x</math> obtaining <math>\rho^\prime</math>.

==Further Information==

==References==
#[https://arxiv.org/pdf/quant-ph/0205128.pdf| Barnum et al. (2002).]
<div style='text-align: right;'>''contributed by Shraddha Singh and Isabel Nha Minh Le''</div>

Clifford Code for Quantum Authentication

2021-12-08T17:22:12Z

137.226.108.44: Created page with "The Clifford Authentication Scheme was introduced in the paper [https://arxiv.org/pdf/0810.5375.pdf| Interactive Proofs For Quantum Computations by Aharanov et al.]. ==Outlin..."

The Clifford Authentication Scheme was introduced in the paper [https://arxiv.org/pdf/0810.5375.pdf| Interactive Proofs For Quantum Computations by Aharanov et al.].

==Outline==
The Clifford code encodes a <math>m</math>-qubit message by appending an auxiliary register with <math>d</math> qubits in <math>|0\rangle</math>. It then applies a random Clifford operator on all <math>m+d</math> qubits. By measuring only the auxiliary register, the authenticator decides, whether to accept the received state or whether to abort.

==Notations==
*<math>\mathcal{S}</math>: suppliant (sender)
*<math>\mathcal{A}</math>: authenticator (prover)
*<math>\rho</math>: <math>m</math>-qubit state to be transmitted
*<math>d\in\mathbb{N}</math>: security parameter defining the number of qubits in the auxiliary register
*<math>n=m+d</math>: total number of qubits used
*<math>\{C_k\}</math>: set of Clifford operations on <math>n</math> qubits labelled by key <math>k\in\mathcal{K}</math>

==Properties==
*The Clifford code is quantum authentication scheme with security <math>2^{-d}</math>

==Protocol Description==
*'''''Encoding:''''' <math>\mathcal{E}_k: \rho \mapsto C_k\left( \rho \otimes |0\rangle\langle 0|^{\otimes d} \right)C_k^\dagger</math>
#<math>\mathcal{S}</math> appends an auxiliary register of <math>d</math> qubits in state <math>|0\rangle\langle 0|</math> to the quantum message <math>\rho</math>, which results in <math>\rho\otimes|0\rangle\langle0|^{\otimes d}</math>.
#<math>\mathcal{S}</math> then applies <math>C_k</math> for a uniformly random <math>k\in\mathcal{K}</math> on the total state.
#<math>\mathcal{S}</math> sends the result to <math>\mathcal{A}</math>.
*'''''Decoding:''''' Mathematically, the decoding process is described by <math display=block>\mathcal{D}_k: \rho^\prime \mapsto \mathrm{tr}_0\left( \mathcal{P}_\mathrm{acc} C_k^\dagger (\rho^\prime) C_k \mathcal{P}_\mathrm{acc}^\dagger \right) \otimes |\mathrm{ACC}\rangle\langle \mathrm{ACC}| + \mathrm{tr}\left( \mathcal{P}_\mathrm{rej} C_k^\dagger (\rho^\prime) C_k \mathcal{P}_\mathrm{rej}^\dagger \right) \Omega \otimes |\mathrm{REJ}\rangle\langle\mathrm{REJ}|</math> In the above, <math>\mathrm{tr}_0</math> is the trace over the auxiliary register only, and <math>\mathrm{tr}</math> is the trace over the quantum message system and the auxiliary system. Furthermore, <math>\mathcal{P}_\mathrm{acc}=\mathbb{1}^{\otimes n} \otimes |0\rangle\langle 0|^{\otimes d}</math> and <math>\mathcal{P}_\mathrm{rej}=\mathbb{1}^{\otimes (n+d)} - \mathcal{P}_\mathrm{acc}</math> are projective measurement operators.
#<math>\mathcal{A}</math> applies the inverse Clifford <math>C_k^\dagger</math> to the received state, which is denoted by <math>\rho^\prime</math>.
#<math>\mathcal{A}</math> measures the auxiliary register in the computational basis.</br>a. If all <math>d</math> auxiliary qubits are 0, the state is accepted and an additional flag qubit in state <math>|\mathrm{ACC}\rangle\langle\mathrm{ACC}|</math> is appended.</br>b. Otherwise, the remaining system is traced out and replaced with a fixed <math>m</math>-qubit state <math>\Omega</math> and an additional flag qubit in state <math>|\mathrm{REJ}\rangle\langle \mathrm{REJ}|</math> is appended.

==References==
#[https://arxiv.org/pdf/0810.5375.pdf| Aharanov et al. (2008).]
#[https://arxiv.org/pdf/1607.03075.pdf| Broadbent and Wainewright (2016).]
<div style='text-align: right;'>''contributed by Shraddha Singh and Isabel Nha Minh Le''</div>

Authentication of Quantum Messages

2021-12-08T17:21:37Z

137.226.108.44:

==Functionality==
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.

<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==
'''Non-interactive Protocols:'''
*[[Purity Testing based Quantum Authentication]]
*[[Polynomial Code based Quantum Authentication]]
*[[Clifford Code for Quantum Authentication]]
*[[Trap Code for Quantum Authentication]]
'''Interactive Protocols:'''
*[[Naive approach using Quantum Teleportation]]

==Properties==
*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: 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{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.
# <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>.
*'''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==
#[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 and Isabel Nha Minh Le''</div>

Authentication of Quantum Messages

2021-11-28T15:48:45Z

137.226.108.44:

==Functionality==
Imagine a person sends some quantum information to another pereson 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? 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. <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.

<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==
'''Non-interactive Protocols:'''
*[[Purity Testing based Quantum Authentication]]
*[[Polynomial Code based Quantum Authentication]]
*[[Clifford Code for Quantum Authentication]]
'''Interactive Protocols:'''
*tbd

==Properties==
*Any scheme, which authenticates quantum messages must also encrypt them [[Authentication of Quantum Messages#References|(1)]].
*'''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 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{S}</math> takes as input an <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.
# <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>.
*'''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>. The latter is the case (for a specific state <math>|\psi\rangle</math>) if:
#''Completeness:'' <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/>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==
#[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 and Isabel Nha Minh Le''</div>