# Prepare-and-Measure Certified Deletion

This example 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.

## Outline

The scheme consists of 5 circuits-

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

## Notation

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

## Protocol Description

### Circuit 1: Key

The key generation circuit

Input : None

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

1. Sample ${\displaystyle \theta \gets \Theta }$
2. Sample ${\displaystyle r|_{\tilde {\mathcal {I}}}\gets \{0,1\}^{k}}$ where ${\displaystyle {\tilde {\mathcal {I}}}=\{i\in [m]|\theta _{i}=1\}}$
3. Sample ${\displaystyle u\gets \{0,1\}^{n}}$
4. Sample ${\displaystyle d\gets \{0,1\}^{\mu }}$
5. Sample ${\displaystyle e\gets \{0,1\}^{\tau }}$
6. Sample ${\displaystyle H_{pa}\gets {\mathfrak {H}}_{pa}}$
7. Sample ${\displaystyle H_{ec}\gets {\mathfrak {H}}_{ec}}$
8. Output ${\displaystyle \rho =|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}|}$

### Circuit 2: Enc

The encryption circuit

Input : A plaintext state ${\displaystyle |\mathrm {msg} \rangle \langle \mathrm {msg} |}$ and a key state ${\displaystyle |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 ${\displaystyle \rho \in {\mathcal {D}}({\mathcal {Q}}(m+n+\tau +\mu ))}$

1. Sample ${\displaystyle r|_{\mathcal {I}}\gets \{0,1\}^{s}}$ where ${\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}$
2. Compute ${\displaystyle x=H_{pa}(r|_{\mathcal {I}})}$ where ${\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}$
3. Compute ${\displaystyle p=H_{ec}(r|_{\mathcal {I}})\oplus d}$
4. Compute ${\displaystyle q=\mathrm {synd} (r|_{\mathcal {I}})\oplus e}$
5. Output ${\displaystyle \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 ${\displaystyle |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 ${\displaystyle \rho \otimes |c,p,q\rangle \langle c,p,q|\in {\mathcal {D}}({\mathcal {Q}}(m+n+\mu +\tau ))}$

Output: A plaintext state ${\displaystyle \sigma \in {\mathcal {D}}({\mathcal {Q}}(n))}$ and an error flag ${\displaystyle \gamma \in {\mathcal {D}}({\mathcal {Q}})}$

1. Compute ${\displaystyle \rho ^{\prime }=\mathrm {H} ^{\theta }\rho \mathrm {H} ^{\theta }}$
2. Measure ${\displaystyle \rho ^{\prime }}$ in the computational basis. Call the result ${\displaystyle r}$
3. Compute ${\displaystyle r^{\prime }=\mathrm {corr} (r|_{\mathcal {I}},q\oplus e)}$ where ${\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}$
4. Compute ${\displaystyle p^{\prime }=H_{ec}(r^{\prime })\oplus d}$
5. If ${\displaystyle p\neq p^{\prime }}$, then set ${\displaystyle \gamma =|0\rangle \langle 0|}$. Else, set ${\displaystyle \gamma =|1\rangle \langle 1|}$
6. Compute ${\displaystyle x^{\prime }=H_{pa}(r^{\prime })}$
7. Output ${\displaystyle \rho \otimes \gamma =|c\oplus x^{\prime }\oplus u\rangle \langle c\oplus x^{\prime }\oplus u|\otimes \gamma }$

### Circuit 4: Del

The deletion circuit

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

Output: A certificate string ${\displaystyle \sigma \in {\mathcal {D}}({\mathcal {Q}}(m))}$

1. Measure ${\displaystyle \rho }$ in the Hadamard basis. Call the output y.
2. Output ${\displaystyle \sigma =|y\rangle \langle y|}$

### Circuit 5: Ver

The verification circuit

Input : A key state ${\displaystyle |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 ${\displaystyle |y\rangle \langle y|\in {\mathcal {D}}({\mathcal {Q}}(m))}$

Output: A bit

1. Compute ${\displaystyle {\hat {y}}^{\prime }={\hat {y}}|_{\mathcal {\tilde {I}}}}$ where ${\displaystyle {\mathcal {\tilde {I}}}=\{i\in [m]|\theta _{i}=1\}}$
2. Compute ${\displaystyle q=r|_{\tilde {\mathcal {I}}}}$
3. If ${\displaystyle \omega (q\oplus {\hat {y}}^{\prime }), output ${\displaystyle 1}$. Else, output ${\displaystyle 0}$.

## Properties

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 ${\displaystyle 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).