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 $\rho \in {\mathcal {D}}({\mathcal {Q}}(k+m+n+\mu +\tau )\otimes {\mathfrak {H}}_{pa}\otimes {\mathfrak {H}}_{ec}$

1. Sample 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 \theta \gets \Theta}
2. Sample $r|_{\tilde {\mathcal {I}}}\gets \{0,1\}^{k}$ where 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 \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 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 q = \mathrm{synd}(r|_\mathcal{I})\oplus e}
5. Output 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 \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 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 \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 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 p^\prime = H_{ec}(r^\prime) \oplus d }
5. If 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 p \neq p^\prime} , then set $\gamma =|0\rangle \langle 0|$. Else, set $\gamma =|1\rangle \langle 1|$
6. Compute 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 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 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 \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 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|_\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 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\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 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 \omega(q\oplus \hat y^\prime) < k\delta} , output $1$. Else, output 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 0} .