Authentication of Quantum Messages

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.

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

• 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 (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 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{S}} , an authenticator ${\mathcal {A}}$ 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} . ${\mathcal {S}}$ 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. 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{S}} 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 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} and a key 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\in K} and outputs a 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} 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. 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}} 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 $k\in K$ 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 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} , and a single qubit 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 V} which indicates acceptance or rejection. The classical basis states 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 V} are called 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 |\mathrm{ACC}\rangle, |\mathrm{REJ}\rangle} by convention.
   For any fixed key 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} , we denote the corresponding super-operators by 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 S_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 A_k} .

• Definition: Security of a QAS
  For non-interactive protocols, a QAS is secure with error 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 \epsilon} if it is complete for all states $|\psi \rangle$ and has a soundness error 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 \epsilon} for all states 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 |\psi\rangle} . These two conditions are met if:

1. Completeness: A QAS is complete for a specific quantum state 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 |\psi\rangle} if 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 \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 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 |\psi\rangle} , the quantum information received by 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}} is the same initially sent by 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{S}} and the single qubit 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 V} is in state $|\mathrm {ACC} \rangle \langle \mathrm {ACC} |$. To this end, we assume that the channel between 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{S}} 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}} is noiseless if no adversary intervention appeared.
2. Soundness: For all super-operators 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{O}} , let 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 \rho_\text{auth}} be the state output by 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}} when the adversary’s intervention is characterized by 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{O}} , that is: 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 \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 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 |\psi\rangle} . Here, $\mathbf {E} _{k}$ means the expectation when 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} is chosen uniformly at random from 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.} The QAS then has a soundness error 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 \epsilon} for 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 |\psi\rangle} if 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 \mathrm{Tr}\left( P_1^{|\psi\rangle}\rho_\text{auth} \right)\geq 1-\epsilon,}
   where 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 P_1^{|\psi\rangle}} is the projector 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 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

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

contributed by Shraddha Singh and Isabel Nha Minh Le