Authentication of Quantum Messages

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.

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

Interactive Protocols:

• tbd

Properties

• Any scheme, which authenticates quantum messages must also encrypt them (1).
• 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 keys $K$. ${\mathcal {S}}$ and ${\mathcal {A}}$ are each polynomial time quantum algorithms. The following is fullfilled:

1. ${\mathcal {S}}$ takes as input an $m$-qubit message system $M$ and a key $k\in K$ and outputs a transmitted system $T$ of $m+t$ qubits.
2. ${\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 $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 $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 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 latter is the case (for a specific state $|\psi \rangle$) if:

1. Completeness: $\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 ${\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 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 ${\mathcal {A}}$ is noiseless if no adversary intervention appeared.
2. 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).$$
   
   Here, 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 \mathbf{E}_k} means the expectation when $k$ is chosen uniformly at random from $K.$ The QAS then has a soundness error $\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 $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

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