Prepare-and-Measure Certified Deletion: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
No edit summary
No edit summary
Line 3: Line 3:


<!-- Intro: brief description of the protocol -->
<!-- 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 [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 -->
<!--Tags: related pages or category -->


==Assumptions==
==Requirements==
<!-- It describes the setting in which the protocol will be successful. -->
* '''Network Stage: ''' [[:Category:Prepare and Measure Network Stage| Prepare and Measure]]


==Outline==
==Outline==
Line 43: Line 43:
<!-- Add this part if the protocol is already in the graph -->
<!-- Add this part if the protocol is already in the graph -->
<!-- {{graph}} -->
<!-- {{graph}} -->
==Properties==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->


==Protocol Description==
==Protocol Description==
Line 110: Line 107:
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->


==Further Information==
==Properties==
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... -->
<!-- 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)]


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

Revision as of 19:21, 5 February 2022


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

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

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 .

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
  • 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

*contributed by Chirag Wadhwa