# Difference between revisions of "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

## Notation

• 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
• $m=\kappa (\lambda )$ : Total number of qubits sent from encrypting party to 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

## Protocol Description

### 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}$ 1. Sample $\theta \gets \Theta$ 2. Sample $r|_{\tilde {\mathcal {I}}}\gets \{0,1\}^{k}$ where ${\tilde {\mathcal {I}}}=\{i\in [m]|\theta _{i}=1\}$ 3. Sample $u\gets \{0,1\}^{n}$ 4. Sample $d\gets \{0,1\}^{\mu }$ 5. Sample $e\gets \{0,1\}^{\tau }$ 6. Sample $H_{pa}\gets {\mathfrak {H}}_{pa}$ 7. Sample $H_{ec}\gets {\mathfrak {H}}_{ec}$ 8. Output $\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 $|\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 ))$ 1. Sample $r|_{\mathcal {I}}\gets \{0,1\}^{s}$ where ${\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}$ 2. Compute $x=H_{pa}(r|_{\mathcal {I}})$ where ${\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}$ 3. Compute $p=H_{ec}(r|_{\mathcal {I}})\oplus d$ 4. Compute $q=\mathrm {synd} (r|_{\mathcal {I}})\oplus e$ 5. 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}})$ 1. Compute $\rho ^{\prime }=\mathrm {H} ^{\theta }\rho \mathrm {H} ^{\theta }$ 2. Measure $\rho ^{\prime }$ in the computational basis. Call the result $r$ 3. Compute $r^{\prime }=\mathrm {corr} (r|_{\mathcal {I}},q\oplus e)$ where ${\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}$ 4. Compute $p^{\prime }=H_{ec}(r^{\prime })\oplus d$ 5. If $p\neq p^{\prime }$ , then set $\gamma =|0\rangle \langle 0|$ . Else, set $\gamma =|1\rangle \langle 1|$ 6. Compute $x^{\prime }=H_{pa}(r^{\prime })$ 7. Output $\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 $\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))$ 1. Measure $\rho$ in the Hadamard basis. Call the output y.
2. 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

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