Revision History for: Prepare-and-Measure Certified Deletion
- 2025-05-22 at 14:46 by JuliaM
implements Quantum Encryption with Certified Deletion
Introduction
This 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.
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
Assumptions
The assumptions are similar to the assumptions for the BB84 QKD protocol.
Requirements
Network Stage: Prepare and Measure
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
- $\\\omega :\\\{0,1\\\}\\\rightarrow \\\mathbb {N}$: Hamming weight function
- $m=\\\kappa (\\\lambda)$: Total number of qubits sent from the encrypting party to the 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
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 $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).
Technical 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})$- Sample $\\\theta \\\gets \\\Theta$
- Sample $r|_{\\\tilde{\\\mathcal{I}}} \\\gets \\\{0,1\\\}^k$ where $\\\tilde{\\\mathcal{I}} = \\\{i \\\in [m] \\\mid \\\theta_i = 1\\\}$
- Sample $u \\\gets \\\{0,1\\\}^n$
- Sample $d \\\gets \\\{0,1\\\}^{\\\mu}$
- Sample $e \\\gets \\\{0,1\\\}^{\\\tau}$
- Sample $H_{pa} \\\gets \\\mathfrak{H}_{pa}$
- Sample $H_{ec} \\\gets \\\mathfrak{H}_{ec}$
- Output: $\\\rho = \\\big|r|_{\\\tilde{\\\mathcal{I}}}, \\\theta, u, d, e, H_{pa}, H_{ec} \\\big\\\rangle \\\big\\\langle r|_{\\\tilde{\\\mathcal{I}}}, \\\theta, u, d, e, H_{pa}, H_{ec} \\\big|$
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))$- Sample $r|_{\\\mathcal{I}} \\\gets \\\{0,1\\\}^s$ where $\\\mathcal{I} = \\\{i \\\in [m] \\\mid \\\theta_i = 0\\\}$
- Compute $x = H_{pa}(r|_{\\\mathcal{I}})$
- Compute $p = H_{ec}(r|_{\\\mathcal{I}}) \\\oplus d$
- Compute $q = \\\mathrm{synd}(r|_{\\\mathcal{I}}) \\\oplus e$
- 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})$- Compute $\\\rho’ = H^{\\\theta} \\\rho H^{\\\theta}$
- Measure $\\\rho’$ in the computational basis. Call the result $r$
- Compute $r’ = \\\mathrm{corr}(r|_{\\\mathcal{I}}, q \\\oplus e)$ where $\\\mathcal{I} = \\\{i \\\in [m] \\\mid \\\theta_i = 0\\\}$
- Compute $p’ = H_{ec}(r’) \\\oplus d$
- If $p \\\neq p’$, then set $\\\gamma = |0\\\rangle \\\langle 0|$; else set $\\\gamma = |1\\\rangle \\\langle 1|$
- Compute $x’ = H_{pa}(r’)$
- Output: $\\\rho \\\otimes \\\gamma = |c \\\oplus x’ \\\oplus u\\\rangle \\\langle c \\\oplus x’ \\\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))$- Measure $\\\rho$ in the Hadamard basis. Call the output $y$
- 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- Compute $\\\hat{y}’ = \\\hat{y}|_{\\\tilde{\\\mathcal{I}}}$ where $\\\tilde{\\\mathcal{I}} = \\\{i \\\in [m] \\\mid \\\theta_i = 1\\\}$
- Compute $q = r|_{\\\tilde{\\\mathcal{I}}}$
- If $\\\omega(q \\\oplus \\\hat{y}’) < k\\\delta$, output $1$. Else, output $0$
Experimental Implementations
No content has been added to this section, yet!
Further Information
Some more recent relevant work includes:
- Cryptography with certified deletion [2]
- Secret sharing with certified deletion [3]
- Software with certified deletion [4]
References
- Broadbent, Anne, and Rabib Islam. “Quantum encryption with certified deletion.” In Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part III 18, pp. 92-122. Springer International Publishing, 2020.
- Bartusek, James, and Dakshita Khurana. “Cryptography with certified deletion.” In Annual International Cryptology Conference, pp. 192-223. Cham: Springer Nature Switzerland, 2023.
- Bartusek, James, and Justin Raizes. “Secret sharing with certified deletion.” In Annual International Cryptology Conference, pp. 184-214. Cham: Springer Nature Switzerland, 2024.
- Bartusek, James, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, and Bhaskar Roberts. “Software with certified deletion.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 85-111. Cham: Springer Nature Switzerland, 2024.
- 2025-05-16 at 10:41 by JuliaM
implements Quantum Encryption with Certified Deletion
Introduction
This 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.
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
Assumptions
The assumptions are similar to the assumptions for the BB84 QKD protocol.
Requirements
Network Stage: Prepare and Measure
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
- $\\\omega :\\\{0,1\\\}\\\rightarrow \\\mathbb {N}$: Hamming weight function
- $m=\\\kappa (\\\lambda)$: Total number of qubits sent from the encrypting party to the 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
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 $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).
Technical 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})$- Sample $\\\theta \\\gets \\\Theta$
- Sample $r|_{\\\tilde{\\\mathcal{I}}} \\\gets \\\{0,1\\\}^k$ where $\\\tilde{\\\mathcal{I}} = \\\{i \\\in [m] \\\mid \\\theta_i = 1\\\}$
- Sample $u \\\gets \\\{0,1\\\}^n$
- Sample $d \\\gets \\\{0,1\\\}^{\\\mu}$
- Sample $e \\\gets \\\{0,1\\\}^{\\\tau}$
- Sample $H_{pa} \\\gets \\\mathfrak{H}_{pa}$
- Sample $H_{ec} \\\gets \\\mathfrak{H}_{ec}$
- Output: $\\\rho = \\\big|r|_{\\\tilde{\\\mathcal{I}}}, \\\theta, u, d, e, H_{pa}, H_{ec} \\\big\\\rangle \\\big\\\langle r|_{\\\tilde{\\\mathcal{I}}}, \\\theta, u, d, e, H_{pa}, H_{ec} \\\big|$
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))$- Sample $r|_{\\\mathcal{I}} \\\gets \\\{0,1\\\}^s$ where $\\\mathcal{I} = \\\{i \\\in [m] \\\mid \\\theta_i = 0\\\}$
- Compute $x = H_{pa}(r|_{\\\mathcal{I}})$
- Compute $p = H_{ec}(r|_{\\\mathcal{I}}) \\\oplus d$
- Compute $q = \\\mathrm{synd}(r|_{\\\mathcal{I}}) \\\oplus e$
- 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})$- Compute $\\\rho’ = H^{\\\theta} \\\rho H^{\\\theta}$
- Measure $\\\rho’$ in the computational basis. Call the result $r$
- Compute $r’ = \\\mathrm{corr}(r|_{\\\mathcal{I}}, q \\\oplus e)$ where $\\\mathcal{I} = \\\{i \\\in [m] \\\mid \\\theta_i = 0\\\}$
- Compute $p’ = H_{ec}(r’) \\\oplus d$
- If $p \\\neq p’$, then set $\\\gamma = |0\\\rangle \\\langle 0|$; else set $\\\gamma = |1\\\rangle \\\langle 1|$
- Compute $x’ = H_{pa}(r’)$
- Output: $\\\rho \\\otimes \\\gamma = |c \\\oplus x’ \\\oplus u\\\rangle \\\langle c \\\oplus x’ \\\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))$- Measure $\\\rho$ in the Hadamard basis. Call the output $y$
- 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- Compute $\\\hat{y}’ = \\\hat{y}|_{\\\tilde{\\\mathcal{I}}}$ where $\\\tilde{\\\mathcal{I}} = \\\{i \\\in [m] \\\mid \\\theta_i = 1\\\}$
- Compute $q = r|_{\\\tilde{\\\mathcal{I}}}$
- If $\\\omega(q \\\oplus \\\hat{y}’) < k\\\delta$, output $1$. Else, output $0$
Experimental Implementations
No content has been added to this section, yet!
Further Information
Some more recent relevant work includes:
- Cryptography with certified deletion [2]
- Secret sharing with certified deletion [3]
- Software with certified deletion [4]
- 2025-05-16 at 10:41 by JuliaM
implements Quantum Encryption with Certified Deletion
Introduction
This 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.
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
Assumptions
The assumptions are similar to the assumptions for the BB84 QKD protocol.
Requirements
Network Stage: Prepare and Measure
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
- $\\\omega :\\\{0,1\\\}\\\rightarrow \\\mathbb {N}$: Hamming weight function
- $m=\\\kappa (\\\lambda)$: Total number of qubits sent from the encrypting party to the 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
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 $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).
Technical 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})$- Sample $\\\theta \\\gets \\\Theta$
- Sample $r|_{\\\tilde{\\\mathcal{I}}} \\\gets \\\{0,1\\\}^k$ where $\\\tilde{\\\mathcal{I}} = \\\{i \\\in [m] \\\mid \\\theta_i = 1\\\}$
- Sample $u \\\gets \\\{0,1\\\}^n$
- Sample $d \\\gets \\\{0,1\\\}^{\\\mu}$
- Sample $e \\\gets \\\{0,1\\\}^{\\\tau}$
- Sample $H_{pa} \\\gets \\\mathfrak{H}_{pa}$
- Sample $H_{ec} \\\gets \\\mathfrak{H}_{ec}$
- Output: $\\\rho = \\\big|r|_{\\\tilde{\\\mathcal{I}}}, \\\theta, u, d, e, H_{pa}, H_{ec} \\\big\\\rangle \\\big\\\langle r|_{\\\tilde{\\\mathcal{I}}}, \\\theta, u, d, e, H_{pa}, H_{ec} \\\big|$
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))$- Sample $r|_{\\\mathcal{I}} \\\gets \\\{0,1\\\}^s$ where $\\\mathcal{I} = \\\{i \\\in [m] \\\mid \\\theta_i = 0\\\}$
- Compute $x = H_{pa}(r|_{\\\mathcal{I}})$
- Compute $p = H_{ec}(r|_{\\\mathcal{I}}) \\\oplus d$
- Compute $q = \\\mathrm{synd}(r|_{\\\mathcal{I}}) \\\oplus e$
- 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})$- Compute $\\\rho’ = H^{\\\theta} \\\rho H^{\\\theta}$
- Measure $\\\rho’$ in the computational basis. Call the result $r$
- Compute $r’ = \\\mathrm{corr}(r|_{\\\mathcal{I}}, q \\\oplus e)$ where $\\\mathcal{I} = \\\{i \\\in [m] \\\mid \\\theta_i = 0\\\}$
- Compute $p’ = H_{ec}(r’) \\\oplus d$
- If $p \\\neq p’$, then set $\\\gamma = |0\\\rangle \\\langle 0|$; else set $\\\gamma = |1\\\rangle \\\langle 1|$
- Compute $x’ = H_{pa}(r’)$
- Output: $\\\rho \\\otimes \\\gamma = |c \\\oplus x’ \\\oplus u\\\rangle \\\langle c \\\oplus x’ \\\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))$- Measure $\\\rho$ in the Hadamard basis. Call the output $y$
- 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- Compute $\\\hat{y}’ = \\\hat{y}|_{\\\tilde{\\\mathcal{I}}}$ where $\\\tilde{\\\mathcal{I}} = \\\{i \\\in [m] \\\mid \\\theta_i = 1\\\}$
- Compute $q = r|_{\\\tilde{\\\mathcal{I}}}$
- If $\\\omega(q \\\oplus \\\hat{y}’) < k\\\delta$, output $1$. Else, output $0$
Experimental Implementations
No content has been added to this section, yet!
Further Information
Some more recent relevant work includes:
- Cryptography with certified deletion [2]
- Secret sharing with certified deletion [3]
- Software with certified deletion [4]