Editing Prepare-and-Measure Certified Deletion

<!-- This is a comment. You can erase them or write below -->


<!-- Intro: brief description of the protocol -->
This [https://arxiv.org/abs/1910.03551 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.
<!--Tags: related pages or category -->

==Requirements==
* '''Network Stage: ''' [[:Category:Prepare and Measure 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  
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->

==Notation==
<!--  Connects the non-mathematical outline with further sections. -->
* For any string <math>x \in \{0,1\}^n</math> and set <math>\mathcal{I} \subseteq [n], x|_\mathcal{I}</math> denotes the string <math>x</math> restricted to the bits indexed by <math>\mathcal{I}</math>
* For <math>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</math>
* <math>\mathcal{Q} := \mathbb{C}^2</math> denotes the state space of a single qubit,<math>\mathcal{Q}(n) := \mathcal{Q}^{\otimes n}</math>
* <math>\mathcal{D(H)}</math> denotes the set of density operators on a Hilbert space <math>\mathcal{H}</math>
* <math>\lambda</math>: Security parameter
* <math>n</math>: Length, in bits, of the message
* <math>\omega : \{0,1\} \rightarrow \mathbb{N}</math> : Hamming weight function
* <math>m = \kappa(\lambda)</math>: Total number of qubits sent from encrypting party to decrypting party
* <math>k</math>: Length, in bits, of the string used for verification of deletion
* <math>s = m - k</math>: Length, in bits, of the string used for extracting randomness
* <math>\tau = \tau(\lambda)</math>: Length, in bits, of error correction hash
* <math>\mu = \mu(\lambda)</math>: Length, in bits, of error syndrome
* <math>\theta</math>: Basis in which the encrypting party prepare her quantum state
* <math>\delta</math>: Threshold error rate for the verification test
* <math>\Theta</math>: Set of possible bases from which \theta is chosen
* <math>\mathfrak{H}_{pa}</math>: Universal<math>_2</math> family of hash functions used in the privacy amplification scheme
* <math>\mathfrak{H}_{ec}</math>: Universal<math>_2</math> family of hash functions used in the error correction scheme
* <math>H_{pa}</math>: Hash function used in the privacy amplification scheme
* <math>H_{ec}</math>: Hash function used in the error correction scheme
* <math>synd</math>: Function that computes the error syndrome
* <math>corr</math>: Function that computes the corrected string
<!--==Knowledge Graph== -->
<!-- Add this part if the protocol is already in the graph -->
<!-- {{graph}} -->

==Protocol Description==
===Circuit 1: ''Key''===
The key generation circuit

'''Input ''': None

'''Output''': A key state <math>\rho \in \mathcal{D}(\mathcal{Q}(k+m+n+\mu+\tau)\otimes\mathfrak{H}_{pa}\otimes\mathfrak{H}_{ec}</math>

# Sample <math>\theta \gets \Theta</math>
# Sample <math> r|_{\tilde{\mathcal{I}}} \gets \{0,1\}^k</math> where <math>\tilde{\mathcal{I}} = \{i \in [m] | \theta_i = 1\}</math>
# Sample <math>u \gets \{0,1\}^n</math>
# Sample <math>d \gets \{0,1\}^\mu</math>
# Sample <math>e \gets \{0,1\}^\tau</math>
# Sample <math>H_{pa} \gets \mathfrak{H}_{pa}</math>
# Sample <math>H_{ec} \gets \mathfrak{H}_{ec}</math>
# Output <math>\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}| </math>
===Circuit 2: ''Enc''===
The encryption circuit

'''Input :''' A plaintext state <math>|\mathrm{msg}\rangle\langle\mathrm{msg}|</math> and a key state <math>| 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}</math>

'''Output:''' A ciphertext state <math>\rho \in \mathcal{D}(\mathcal{Q}(m+n+\tau+\mu))</math>

# Sample <math>r|_\mathcal{I} \gets \{0,1\}^s</math> where <math>\mathcal{I} = \{i \in [m]| \theta_i = 0 \}</math>
# Compute <math>x = H_{pa}(r|_\mathcal{I})</math> where <math>\mathcal{I} = \{i \in [m]| \theta_i = 0 \}</math>
# Compute <math>p = H_{ec}(r|_\mathcal{I}) \oplus d</math>
# Compute <math>q = \mathrm{synd}(r|_\mathcal{I})\oplus e</math>
# Output <math>\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 |</math>
===Circuit 3: ''Dec''===
The decryption circuit

'''Input :''' A key state <math>| 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}</math> and a ciphertext <math>\rho \otimes |c,p,q\rangle\langle c,p,q| \in \mathcal{D}(\mathcal{Q}(m + n + \mu + \tau)) </math>

'''Output:''' A plaintext state <math>\sigma \in \mathcal{D}(\mathcal{Q}(n))</math> and an error flag <math>\gamma \in \mathcal{D}(\mathcal{Q})</math>

# Compute <math>\rho^\prime = \mathrm{H}^\theta \rho \mathrm{H}^\theta</math>
# Measure <math>\rho^\prime</math> in the computational basis. Call the result <math>r</math>
# Compute <math>r^\prime = \mathrm{corr}(r|_\mathcal{I},q\oplus e)</math> where <math>\mathcal{I} = \{i \in [m]|\theta_i =0\}</math>
# Compute <math>p^\prime = H_{ec}(r^\prime) \oplus d </math>
# If <math>p \neq p^\prime</math>, then set <math>\gamma = |0\rangle\langle 0|</math>. Else, set <math>\gamma = |1\rangle\langle 1|</math>
# Compute <math>x^\prime = H_{pa}(r^\prime)</math>
# Output <math>\rho \otimes \gamma = |c\oplus x^\prime \oplus u \rangle \langle c\oplus x^\prime \oplus u| \otimes \gamma </math>
===Circuit 4: ''Del''===
The deletion circuit

'''Input :''' A ciphertext <math>\rho \otimes |c,p,q\rangle\langle c,p,q| \in \mathcal{D}(\mathcal{Q}(m+n+\mu+\tau))</math>

'''Output:''' A certificate string <math>\sigma \in \mathcal{D}(\mathcal{Q}(m))</math>

# Measure <math>\rho</math> in the Hadamard basis. Call the output y.
# Output <math>\sigma = |y\rangle\langle y|</math>
===Circuit 5: ''Ver''===
The verification circuit

'''Input :''' A key state <math>| 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}</math> and a certificate string <math>|y\rangle\langle y| \in \mathcal{D}(\mathcal{Q}(m))</math>

'''Output:''' A bit

# Compute <math>\hat y^\prime = \hat y|_\mathcal{\tilde{I}}</math> where <math> \mathcal{\tilde{I}} = \{i \in [m] | \theta_i = 1 \}</math>
# Compute <math>q = r|_\tilde{\mathcal{I}}</math>
# If <math>\omega(q\oplus \hat y^\prime) < k\delta</math>, output <math>1</math>. Else, output <math>0</math>.
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->

==Properties==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->
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 <math>0^n</math>
*'''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 [https://arxiv.org/abs/1910.03551 Broadbent & Islam (2019)]

<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>