Prepare-and-Measure Certified Deletion: Difference between revisions
No edit summary |
mNo edit summary |
||
(One intermediate revision by the same user not shown) | |||
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 --> | ||
== | ==Requirements== | ||
* '''Network Stage: ''' [[:Category:Prepare and Measure Network Stage| Prepare and Measure]] | |||
==Outline== | ==Outline== | ||
Line 26: | Line 26: | ||
* <math>\lambda</math>: Security parameter | * <math>\lambda</math>: Security parameter | ||
* <math>n</math>: Length, in bits, of the message | * <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>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>k</math>: Length, in bits, of the string used for verification of deletion | ||
Line 43: | Line 44: | ||
<!-- Add this part if the protocol is already in the graph --> | <!-- Add this part if the protocol is already in the graph --> | ||
<!-- {{graph}} --> | <!-- {{graph}} --> | ||
==Protocol Description== | ==Protocol Description== | ||
Line 110: | Line 108: | ||
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. --> | <!-- 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> |
Latest revision as of 01:25, 9 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[edit]
- Network Stage: Prepare and Measure
Outline[edit]
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[edit]
- 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
- : Hamming weight function
- : 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[edit]
Circuit 1: Key[edit]
The key generation circuit
Input : None
Output: A key state
- Sample
- Sample where
- Sample
- Sample
- Sample
- Sample
- Sample
- Output
Circuit 2: Enc[edit]
The encryption circuit
Input : A plaintext state and a key state
Output: A ciphertext state
- Sample where
- Compute where
- Compute
- Compute
- Output Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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[edit]
The decryption circuit
Input : A key state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle | 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho \otimes |c,p,q\rangle\langle c,p,q| \in \mathcal{D}(\mathcal{Q}(m + n + \mu + \tau)) }
Output: A plaintext state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma \in \mathcal{D}(\mathcal{Q}(n))} and an error flag Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma \in \mathcal{D}(\mathcal{Q})}
- Compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho^\prime = \mathrm{H}^\theta \rho \mathrm{H}^\theta}
- Measure Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho^\prime} in the computational basis. Call the result Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r}
- Compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r^\prime = \mathrm{corr}(r|_\mathcal{I},q\oplus e)} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{I} = \{i \in [m]|\theta_i =0\}}
- Compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^\prime = H_{ec}(r^\prime) \oplus d }
- If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \neq p^\prime} , then set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma = |0\rangle\langle 0|} . Else, set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma = |1\rangle\langle 1|}
- Compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^\prime = H_{pa}(r^\prime)}
- Output Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho \otimes \gamma = |c\oplus x^\prime \oplus u \rangle \langle c\oplus x^\prime \oplus u| \otimes \gamma }
Circuit 4: Del[edit]
The deletion circuit
Input : A ciphertext Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho \otimes |c,p,q\rangle\langle c,p,q| \in \mathcal{D}(\mathcal{Q}(m+n+\mu+\tau))}
Output: A certificate string Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma \in \mathcal{D}(\mathcal{Q}(m))}
- Measure Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} in the Hadamard basis. Call the output y.
- Output Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma = |y\rangle\langle y|}
Circuit 5: Ver[edit]
The verification circuit
Input : A key state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle | 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |y\rangle\langle y| \in \mathcal{D}(\mathcal{Q}(m))}
Output: A bit
- Compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat y^\prime = \hat y|_\mathcal{\tilde{I}}} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{\tilde{I}} = \{i \in [m] | \theta_i = 1 \}}
- Compute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q = r|_\tilde{\mathcal{I}}}
- If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega(q\oplus \hat y^\prime) < k\delta} , output Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} . Else, output Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} .
Properties[edit]
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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).
References[edit]
- The scheme along with its formal security definitions and their proofs can be found in Broadbent & Islam (2019)