# Prepare-and-Measure Certified Deletion

This example protocol implements the functionality of Quantum Encryption with Certified Deletion using single-qubit state preparation and measurement.

## 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

## 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}$.