This protocol implements the functionality of Quantum Encryption with Certified Deletion using single-qubit state preparation and measurement. This scheme is limited to the single-use, private-key setting.

Quantum encryption with certified deletion

The scheme consists of 5 circuits:

1. Key: This circuit generates the key used in later stages
2. Enc: This circuit encrypts the message using the key
3. Dec: This circuit decrypts the ciphertext using the key and generates an error flag bit
4. Del: This circuit deletes the ciphertext state and generates a deletion certificate
5. Ver: This circuit verifies the validity of the deletion certificate using the key

The assumptions are similar to the assumptions for the BB84 QKD protocol.

Network Stage: Prepare and Measure

• For any string $x\in \{0,1\}^{n}$ and set $\mathcal{I}\subseteq [n],x|_{\mathcal {I}}$ denotes the string $x$ restricted to the bits indexed by $\mathcal {I}$
• For $x,\theta \in \{0,1\}^{n},|x^{\theta }\rangle =H^{\theta }|x\rangle =H^{\theta _{1}}|x_{1}\rangle \otimes H^{\theta _{2}}|x_{2}\rangle \otimes …\otimes H^{\theta _{n}}|x_{n}\rangle $
• $\mathcal{Q}:=\mathbb {C}^{2}$ denotes the state space of a single qubit, $\mathcal{Q}(n):={\mathcal {Q}}^{\otimes n}$
• $\mathcal{D(H)}$ denotes the set of density operators on a Hilbert space $\mathcal{H}$.
• $\lambda$ : Security parameter
• $n$: Length, in bits, of the message
• $\omega :\{0,1\}\rightarrow \mathbb {N}$: Hamming weight function
• $m=\kappa (\lambda)$: Total number of qubits sent from the encrypting party to the decrypting party
• $k$: Length, in bits, of the string used for verification of deletion
• $s=m-k$: Length, in bits, of the string used for extracting randomness
• $\tau =\tau (\lambda)$: Length, in bits, of error correction hash
• $\mu =\mu (\lambda)$: Length, in bits, of error syndrome
  $\theta$: Basis in which the encrypting party prepare her quantum state
• $\delta$: Threshold error rate for the verification test
• $\Theta$: Set of possible bases from which $\theta$ is chosen
• $\mathfrak {H}_{pa}$: $Universal_2$ family of hash functions used in the privacy amplification scheme
• $\mathfrak {H}_{ec}$: $Universal_2$ family of hash functions used in the error correction scheme
• $H_{pa}$: Hash function used in the privacy amplification scheme
• $H_{ec}$: Hash function used in the error correction scheme
• $synd$: Function that computes the error syndrome
• $corr$: Function that computes the corrected string

This scheme has the following properties:

• Correctness: The scheme includes syndrome and correction functions and is thus robust against a certain amount of noise, i.e. below a certain noise threshold, the decryption circuit outputs the original message with high probability.
• Ciphertext Indistinguishability: This notion implies that an adversary, given a ciphertext, cannot discern whether the original plaintext was a known message or a dummy plaintext $0^n$
• Certified Deletion Security: After producing a valid deletion certificate, the adversary cannot obtain the original message, even if the key is leaked (after deletion).

Circuit 1: Key

The key generation circuit

Input: None
Output: A key state $\rho \in \mathcal{D}(\mathcal{Q}(k + m + n + \mu + \tau) \otimes \mathfrak{H}_{pa} \otimes \mathfrak{H}_{ec})$

• Sample $\theta \gets \Theta$
• Sample $r|_{\tilde{\mathcal{I}}} \gets \{0,1\}^k$ where $\tilde{\mathcal{I}} = \{i \in [m] \mid \theta_i = 1\}$
• Sample $u \gets \{0,1\}^n$
• Sample $d \gets \{0,1\}^{\mu}$
• Sample $e \gets \{0,1\}^{\tau}$
• Sample $H_{pa} \gets \mathfrak{H}_{pa}$
• Sample $H_{ec} \gets \mathfrak{H}_{ec}$
• Output: $\rho = \big|r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec} \big\rangle \big\langle r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec} \big|$

Circuit 2: Enc

The encryption circuit

Input: A plaintext state $|\mathrm{msg}\rangle \langle \mathrm{msg}|$ and a key state
$|r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec}\rangle \langle r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec}| \in \mathcal{D}(\mathcal{Q}(k + m + n + \mu + \tau) \otimes \mathfrak{H}_{pa} \otimes \mathfrak{H}_{ec})$
Output: A ciphertext state $\rho \in \mathcal{D}(\mathcal{Q}(m + n + \tau + \mu))$

• Sample $r|_{\mathcal{I}} \gets \{0,1\}^s$ where $\mathcal{I} = \{i \in [m] \mid \theta_i = 0\}$
• Compute $x = H_{pa}(r|_{\mathcal{I}})$
• Compute $p = H_{ec}(r|_{\mathcal{I}}) \oplus d$
• Compute $q = \mathrm{synd}(r|_{\mathcal{I}}) \oplus e$
• Output: $\rho = |r^{\theta}\rangle \langle r^{\theta}| \otimes |\mathrm{msg} \oplus x \oplus u, p, q\rangle \langle \mathrm{msg} \oplus x \oplus u, p, q|$

Circuit 3: Dec

The decryption circuit
Input: A key state
$|r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec}\rangle \langle r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec}| \in \mathcal{D}(\mathcal{Q}(k + m + n + \mu + \tau) \otimes \mathfrak{H}_{pa} \otimes \mathfrak{H}_{ec})$ and a ciphertext
$\rho \otimes |c, p, q\rangle \langle c, p, q| \in \mathcal{D}(\mathcal{Q}(m + n + \mu + \tau))$
Output: A plaintext state $\sigma \in \mathcal{D}(\mathcal{Q}(n))$ and an error flag $\gamma \in \mathcal{D}(\mathcal{Q})$

• Compute $\rho’ = H^{\theta} \rho H^{\theta}$
• Measure $\rho’$ in the computational basis. Call the result $r$
• Compute $r’ = \mathrm{corr}(r|_{\mathcal{I}}, q \oplus e)$ where $\mathcal{I} = \{i \in [m] \mid \theta_i = 0\}$
• Compute $p’ = H_{ec}(r’) \oplus d$
• If $p \neq p’$, then set $\gamma = |0\rangle \langle 0|$; else set $\gamma = |1\rangle \langle 1|$
• Compute $x’ = H_{pa}(r’)$
• Output: $\rho \otimes \gamma = |c \oplus x’ \oplus u\rangle \langle c \oplus x’ \oplus u| \otimes \gamma$

Circuit 4: Del

The deletion circuit

Input: A ciphertext $\rho \otimes |c, p, q\rangle \langle c, p, q| \in \mathcal{D}(\mathcal{Q}(m + n + \mu + \tau))$
Output: A certificate string $\sigma \in \mathcal{D}(\mathcal{Q}(m))$

• Measure $\rho$ in the Hadamard basis. Call the output $y$
• Output: $\sigma = |y\rangle \langle y|$

Circuit 5: Ver

The verification circuit

Input: A key state $|r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec}\rangle \langle r|_{\tilde{\mathcal{I}}}, \theta, u, d, e, H_{pa}, H_{ec}| \in \mathcal{D}(\mathcal{Q}(k + m + n + \mu + \tau) \otimes \mathfrak{H}_{pa} \otimes \mathfrak{H}_{ec})$ and a certificate string $|y\rangle \langle y| \in \mathcal{D}(\mathcal{Q}(m))$
Output: A bit

• Compute $\hat{y}’ = \hat{y}|_{\tilde{\mathcal{I}}}$ where $\tilde{\mathcal{I}} = \{i \in [m] \mid \theta_i = 1\}$
• Compute $q = r|_{\tilde{\mathcal{I}}}$
• If $\omega(q \oplus \hat{y}’) < k\delta$, output $1$. Else, output $0$

Some more recent relevant work includes:

• Cryptography with certified deletion [2]
• Secret sharing with certified deletion [3]
• Software with certified deletion [4]

1. Broadbent, Anne, and Rabib Islam. “Quantum encryption with certified deletion.” In Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part III 18, pp. 92-122. Springer International Publishing, 2020.
2. Bartusek, James, and Dakshita Khurana. “Cryptography with certified deletion.” In Annual International Cryptology Conference, pp. 192-223. Cham: Springer Nature Switzerland, 2023.
3. Bartusek, James, and Justin Raizes. “Secret sharing with certified deletion.” In Annual International Cryptology Conference, pp. 184-214. Cham: Springer Nature Switzerland, 2024.
4. Bartusek, James, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, and Bhaskar Roberts. “Software with certified deletion.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 85-111. Cham: Springer Nature Switzerland, 2024.