Uncloneable Encryption

This example protocol achieves the task of Unclonable Encryption in which the sender sends classical message encoded using quantum states to the receiver. An eavesdropper can neither decrypt the message without the key nor can he copy the encrypted message for later decoding without getting caught.

Assumptions

• Classical authenticated channels are available between sender and receiver.

Outline

The protocol requires a pre-shared set of four keys that are partially consumed in the protocol and that can be regenerated by using the protocol itself.

Encoding phase:

The message is divided into parts (registers). A polynomial of degree equal to the number of parts is defined with the value of the registers as its coefficients. The constant term is chosen such that the first key value is a root of the polynomial. The string formed by coefficients of the polynomial is then XORed with the second key value. This classical pre-processing step is reminiscent to Shamir Secret Sharing scheme.

Both codes are then used in conjunction with the obtained string to pick a string to encode the pre-processed string such that the first one offers error protection against noise in the channel and the second one for privacy amplification.

The obtained classical string is then encoded in the computational or Hadamard basis according to the corresponding bit in the fourth key value and sent to the receiver.

Decoding phase:

Upon receiving the qubits, they are measured in the computational or Hadamard basis according to the corresponding bit in the fourth key value.

Calculate the parity checks of the first classical code. If they are not equal to the third shared key value, there are errors in the state, which can be corrected using the standard decoding map. Evaluate the parity checks of $C_{2}/C_{1}^{\perp }$, producing another string.

The string obtained is XORed with the second key value and used as coefficients of a polynomial. The polynomial is then evaluated at the first key value and if it gives zero, the message is accepted. It is rejected otherwise.

Notation

• $n$: Bit length of the message.
• $r$: Number of registers of size 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} the message is divided into.
• $s$: Bit length of each register the message is divided into.
• 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} : Random key of length $s$.
• $m_{k}$: Value of the $k^{th}$ register for $k\in \{0,1,..,r\}$
• $e$: Random key of length $n+s$.
• $c_{1}$: Random key for selecting the coset from $C_{1}$.
• $C_{1}$: Classical linear code for correcting bit flip errors.
• $C_{2}$: Classical linear code for performing privacy amplification.
• $y$: XORed product 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 e} and $m_{k}$s.
• 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 z} : Random string from the coset 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} selected from $C_{1}/C_{2}^{\perp }$.
• 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} : Bit length 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 z} .
• $b$: Random key of length $N$.

Requirements

Network stage: Prepare and measure.

• A classical linear code for correcting bit-flip errors.
• A classical linear code for performing privacy amplification.
• Basic state preparation and measurement devices.
• A classical and a quantum channel between the sender and the receiver.

Properties

• It uses up more than twice as much key as a classical one-time pad but the key can be partially reused upon successful transmission. The scheme can also be used to regenerate the keys itself.
• The protocol can be used for QKD with some slight modifications.

Protocol Description

Pre-shared key $(k,e,c_{1},b)$ is established.

Encoding:

1. Divide the $n$-bit message into $r$ groups of $s$ bits.
2. Define a polynomial $f$ of degree 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 r} whose first $r$ coefficients are the registers 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_0, m_1,\ldots, m_{r-1}} of the $n$-bit message.
3. The constant term, $m_{r}$, is chosen such that $f(k)=0$.
4. XOR the string $(m_{0},\ldots ,m_{r})$ with $e$, producing a new classical string $y$ of length 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+s} bits.
5. Consider the particular coset of the classical error-correcting 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 C_1} given by the syndrome $c_{1}$.
6. Pick the string $z$ at random so that its coset 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 C_1/C_2^{\perp}} in the coset 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 c_1} 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 C_1} corresponds to $y$
7. Transmit $N$ qubits after operations based on b such that:
   1. When the $i^{th}$ bit of $b$ is $0$, transmit the $i^{th}$ bit of $z$ in the computational basis.
   2. When the $i^{th}$ bit of $b$ is $1$, transmit the $i^{th}$ bit of $z$ in the Hadamard basis.

Decoding:

1. Upon receiving the $N$ qubits, measure in the computational basis if the $i^{th}$ bit of $b$ is $0$, else in the Hadamard basis the $i^{th}$ bit of $b$ is $1$, to get $z$.
2. Calculate the parity checks of the classical code $C_{1}^{\perp }$. If they are not equal to the string $c_{1}$, there are errors in the state, which can be corrected using the standard decoding map.
3. Evaluate the parity checks of $C_{2}/C_{1}^{\perp }$, producing a $n+s$-bit string $y$.
4. XOR $y$ with $e$, producing a new string $(m_{0},\ldots ,m_{r})$.
5. Consider the $(m_{0},\ldots ,m_{r})$ as the coefficients of a polynomial $f$. Accept only if $f(k)=0$.

*contributed by Natansh Mathur