Polynomial Code based Quantum Authentication

The paper Authentication of Quantum Messages by Barnum et al. provides a non-interactive scheme for the sender to encrypt as well as 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: Two Party Protocol, Quantum Functionality, Specific Task, Building Block

Assumptions

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

Notations

• ${\mathcal {S}}$: suppliant (sender)
• 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}} : authenticator (prover)
• 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} : quantum message to be sent
• 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} : number of qubits in the message $\rho$
• 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 \{Q_k\}} : stabilizer purity testing code, each stabilizer code is identified by index $k$
• $n$: number of qubits used to encode the message with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{Q_{k}\}}
• $x$: random binary $2m$-bit key
• $s$: security parameter

Properties

• For a $m$-qubit message, the protocol requires Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m+s} qubits to encode the quantum message.
• The protocol requires a private key of size $2m+O(s)$.

Protocol Description

• Preprocessing: ${\mathcal {S}}$ and ${\mathcal {A}}$ agree on some stabilizer purity testing code Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{Q_{k}\}} and some private and random binary strings Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k,x,y} .
  • $k$ is used to choose a random stabilizer code Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Q_{k}}
  • $x$ is a $2m$-bit random key used for q-encryption
  • $y$ is a random syndrome
• Encryption and encoding:

1. ${\mathcal {S}}$ q-encrypts the $m$-qubit original message $\rho$ as Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \tau } using the classical key $x$ and a quantum one-time pad. This encryption is given by $\tau =\sigma _{x}^{{\vec {t}}_{1}}\sigma _{z}^{{\vec {t}}_{2}}\rho \sigma _{z}^{{\vec {1}}_{1}}\sigma _{x}^{{\vec {t}}_{1}}$, where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\vec {t}}_{1}} and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\vec {t}}_{2}} are $m$-bit vectors and given by the random binary key $x$.
2. ${\mathcal {S}}$ then encodes Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \tau } according to $Q_{k}$ with syndrome $y$, which results in the $n$-qubit state $\sigma$. This means ${\mathcal {S}}$ encodes $\rho$ in $n$ qubits using $Q_{k}$, and then "applies" errors according to the random syndrome.
3. ${\mathcal {S}}$ sends $\sigma$ to ${\mathcal {A}}$.

• Decoding and decryption:

1. ${\mathcal {A}}$ receives the $n$ qubits, whose state is denoted 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 \sigma^\prime} .
2. ${\mathcal {A}}$ measures the syndrome Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y^{\prime }} of the code 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 Q_k} on his 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 n} qubits in 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 \sigma^\prime} .
3. 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}} compares the syndromes 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 y} 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 y^\prime} and aborts the process if they are different.
4. 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}} decodes his 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 n} -qubit word according to 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 Q_k} obtaining 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 \tau^\prime} .
5. 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}} q-decrypts 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 \tau^\prime} using the random binary strings 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 x} obtaining 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^\prime} .

References

1. Barnum et al. (2002).

contributed by Shraddha Singh and Isabel Nha Minh Le