Polynomial Code based Quantum Authentication

The paper Authentication of Quantum Messages by Barnum et al. provides a non-interactive scheme with classical keys 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) without having been tampered with or modified by the dishonest party (eavesdropper).

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

Outline

The polynomial code consists of three steps: preprocessing, encryption and encoding, and decoding and decryption. Within the preprocessing, sender and receiver agree on a stabilizer purity testing code and three private, random binary keys. Within the encryption and encoding step, the sender uses one of these keys to encrypt the original message. Consequently, a second key is used to choose a specific quantum error correction code out of the stabilizer purity testing code. The chosen quantum error correction code is then used, together with the last key, to encode the encrypted quantum message. Within the last step, the decoding and decryption step, the respective keys are used by the receiver to decide whether to abort or not, and if not, to decode and decrypt the received quantum message.

Assumptions

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

Notations

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

Protocol Description

Add Input and Output for each subroutine

• Input: Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \rho } owned by ${\mathcal {S}}$; $k$, $x$, $y$ shared among ${\mathcal {S}}$ and ${\mathcal {A}}$
• Output: Receiver: accepts or aborts $\rho ^{\prime }$
  • Encryption and encoding:

1. ${\mathcal {S}}$ q-encrypts the $m$-qubit original message Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 $\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 $Q_{k}$ on his $n$ qubits in state $\sigma ^{\prime }$.
3. ${\mathcal {A}}$ compares the syndromes $y$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y^{\prime }} and aborts the process if they are different.
4. ${\mathcal {A}}$ decodes his $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