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

From Quantum Protocol Zoo
Jump to: navigation, search
Line 20: Line 20:
 
==Notation==
 
==Notation==
 
<!--  Connects the non-mathematical outline with further sections. -->
 
<!--  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>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== -->
 
<!--==Knowledge Graph== -->
 
<!-- Add this part if the protocol is already in the graph -->
 
<!-- Add this part if the protocol is already in the graph -->

Revision as of 15:21, 4 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

  • For any string and set denotes the string restricted to the bits indexed by
  • For
  • denotes the state space of a single qubit,
  • denotes the set of density operators on a Hilbert space
  • : Security parameter
  • : Length, in bits, of the message
  • : Total number of qubits sent from encrypting party to decrypting party
  • : Length, in bits, of the string used for verification of deletion
  • : Length, in bits, of the string used for extracting randomness
  • : Length, in bits, of error correction hash
  • : Length, in bits, of error syndrome
  • : Basis in which the encrypting party prepare her quantum state
  • : Threshold error rate for the verification test
  • : Set of possible bases from which \theta is chosen
  • : Universal family of hash functions used in the privacy amplification scheme
  • : Universal family of hash functions used in the error correction scheme
  • : Hash function used in the privacy amplification scheme
  • : Hash function used in the error correction scheme
  • : Function that computes the error syndrome
  • : Function that computes the corrected string

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