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.

Requirements

• Network Stage: Prepare and Measure

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 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} \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 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,\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}
• 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{Q} := \mathbb{C}^2} denotes the state space of a single qubit,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{Q}(n) := \mathcal{Q}^{\otimes n}}
• ${\mathcal {D(H)}}$ denotes the set of density operators on a Hilbert space 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{H}}
• 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 \lambda} : Security parameter
• 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 n} : Length, in bits, of the message
• 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 : \{0,1\} \rightarrow \mathbb{N}}  : Hamming weight function
• 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 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
• 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 s = m - k} : Length, in bits, of the string used for extracting randomness
• 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 \tau = \tau(\lambda)} : Length, in bits, of error correction hash
• 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 \mu = \mu(\lambda)} : Length, in bits, of error syndrome
• 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} : Basis in which the encrypting party prepare her quantum 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 \delta} : Threshold error rate for the verification test
• 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} : Set of possible bases from which \theta is chosen
• 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 \mathfrak{H}_{pa}} : UniversalFailed 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 _2} family of hash functions used in the privacy amplification scheme
• 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 \mathfrak{H}_{ec}} : UniversalFailed 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 _2} family of hash functions used in the error correction scheme
• 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 H_{pa}} : Hash function used in the privacy amplification scheme
• 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 H_{ec}} : Hash function used in the error correction scheme
• 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 synd} : Function that computes the error syndrome
• 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 corr} : Function that computes the corrected string

Protocol Description

Circuit 1: Key

The key generation circuit

Input : None

Output: 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 \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 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}}} \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 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 u \gets \{0,1\}^n}
4. 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 d \gets \{0,1\}^\mu}
5. 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 e \gets \{0,1\}^\tau}
6. 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 H_{pa} \gets \mathfrak{H}_{pa}}
7. 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 H_{ec} \gets \mathfrak{H}_{ec}}
8. 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|_\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 (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 |\mathrm{msg}\rangle\langle\mathrm{msg}|} and 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}}

Output: A ciphertext 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 \rho \in \mathcal{D}(\mathcal{Q}(m+n+\tau+\mu))}

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 r|_\mathcal{I} \gets \{0,1\}^s} 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 \}}
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 x = H_{pa}(r|_\mathcal{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{I} = \{i \in [m]| \theta_i = 0 \}}
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 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 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 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 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 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 \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} .

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 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^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).

References

• The scheme along with its formal security definitions and their proofs can be found in Broadbent & Islam (2019)

*contributed by Chirag Wadhwa