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 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 \in \{0,1\}^n} and set ${\mathcal {I}}\subseteq [n],x|_{\mathcal {I}}$ denotes the 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 x} restricted to the bits indexed by 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 \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}}$
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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}$: UniversalFailed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle _{2}} family of hash functions used in the privacy amplification scheme
• ${\mathfrak {H}}_{ec}$: UniversalFailed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle _{2}} family of hash functions used in the error correction scheme
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \theta \gets \Theta }
2. Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r|_{\tilde {\mathcal {I}}}\gets \{0,1\}^{k}} where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\tilde {\mathcal {I}}}=\{i\in [m]|\theta _{i}=1\}}
3. Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle u\gets \{0,1\}^{n}}
4. Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d\gets \{0,1\}^{\mu }}
5. Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\mathrm {msg} \rangle \langle \mathrm {msg} |} and a key state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $\rho \in {\mathcal {D}}({\mathcal {Q}}(m+n+\tau +\mu ))$

1. Sample $r|_{\mathcal {I}}\gets \{0,1\}^{s}$ where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}
2. Compute $x=H_{pa}(r|_{\mathcal {I}})$ where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}
3. Compute $p=H_{ec}(r|_{\mathcal {I}})\oplus d$
4. Compute Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $\rho \otimes |c,p,q\rangle \langle c,p,q|\in {\mathcal {D}}({\mathcal {Q}}(m+n+\mu +\tau ))$

Output: A plaintext 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 \sigma \in \mathcal{D}(\mathcal{Q}(n))} and an error flag $\gamma \in {\mathcal {D}}({\mathcal {Q}})$

1. 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 \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 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}
3. 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 r^\prime = \mathrm{corr}(r|_\mathcal{I},q\oplus e)} 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 \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 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 \gamma = |0\rangle\langle 0|} . Else, set 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 \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 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 \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 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 \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 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} in the Hadamard basis. Call the output y.
2. 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 \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 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 \hat y^\prime = \hat y|_\mathcal{\tilde{I}}} 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 \mathcal{\tilde{I}} = \{i \in [m] | \theta_i = 1 \}}
2. 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 = 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 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 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} .