Difference between revisions of "Prepare-and-Measure Certified Deletion"

From Quantum Protocol Zoo
Jump to: navigation, search
(Initial page)
 
Line 29: Line 29:
  
 
==Protocol Description==
 
==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. -->
 
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
  

Revision as of 04:29, 2 February 2022


This example protocol implements the functionality of Quantum Encryption with Certified Deletion using single-qubit state preparation and measurement.

Assumptions

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

Properties

Protocol Description

Circuit 1: Key

The key generation circuit

Input : None

Output: A key state

  1. Sample
  2. Sample where
  3. Sample
  4. Sample
  5. Sample
  6. Sample
  7. Sample
  8. Output

Circuit 2: Enc

The encryption circuit

Input : A plaintext state and a key state

Output: A ciphertext state

  1. Sample where
  2. Compute where
  3. Compute
  4. Compute
  5. Output

Circuit 3: Dec

The decryption circuit

Input : A key state and a ciphertext

Output: A plaintext state and an error flag

  1. Compute
  2. Measure in the computational basis. Call the result
  3. Compute where
  4. Compute
  5. If , then set . Else, set
  6. Compute
  7. Output

Circuit 4: Del

The deletion circuit

Input : A ciphertext

Output: A certificate string

  1. Measure in the Hadamard basis. Call the output y.
  2. Output

Circuit 5: Ver

The verification circuit

Input : A key state and a certificate string

Output: A bit

  1. Compute where
  2. Compute
  3. If , output . Else, output .

Further Information

References