Prepare-and-Measure Certified Deletion: Difference between revisions
Jump to navigation
Jump to search
(Initial page) |
mNo edit summary |
||
| (3 intermediate revisions 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 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>\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== --> | <!--==Knowledge Graph== --> | ||
<!-- 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== | ||
< | ===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. --> | ||
== | ==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 00: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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\in \{0,1\}^{n}} and set Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {I}}\subseteq [n],x|_{\mathcal {I}}} denotes the string restricted to the bits indexed by
- For Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 }
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {Q}}:=\mathbb {C} ^{2}} denotes the state space of a single qubit,Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {Q}}(n):={\mathcal {Q}}^{\otimes n}}
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {D(H)}}} denotes the set of density operators on a Hilbert space Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {H}}}
- : Security parameter
- : Length, in bits, of the message
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \omega :\{0,1\}\rightarrow \mathbb {N} } : Hamming weight function
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m=\kappa (\lambda )} : 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
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \tau =\tau (\lambda )} : Length, in bits, of error correction hash
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mu =\mu (\lambda )} : Length, in bits, of error syndrome
- : Basis in which the encrypting party prepare her quantum state
- : Threshold error rate for the verification test
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Theta } : Set of possible bases from which \theta is chosen
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathfrak {H}}_{pa}} : UniversalFailed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle _{2}} family of hash functions used in the privacy amplification scheme
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathfrak {H}}_{ec}} : UniversalFailed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle _{2}} family of hash functions used in the error correction scheme
- : Hash function used in the privacy amplification scheme
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle H_{ec}} : Hash function used in the error correction scheme
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle synd} : Function that computes the error syndrome
- Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle corr} : Function that computes the corrected string
Protocol Description[edit]
Circuit 1: Key[edit]
The key generation circuit
Input : None
Output: A key state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \rho \in {\mathcal {D}}({\mathcal {Q}}(k+m+n+\mu +\tau )\otimes {\mathfrak {H}}_{pa}\otimes {\mathfrak {H}}_{ec}}
- Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \theta \gets \Theta }
- Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r|_{\tilde {\mathcal {I}}}\gets \{0,1\}^{k}} where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\tilde {\mathcal {I}}}=\{i\in [m]|\theta _{i}=1\}}
- Sample
- Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d\gets \{0,1\}^{\mu }}
- Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle e\gets \{0,1\}^{\tau }}
- Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle H_{pa}\gets {\mathfrak {H}}_{pa}}
- Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle H_{ec}\gets {\mathfrak {H}}_{ec}}
- Output Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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}|}
Circuit 2: Enc[edit]
The encryption circuit
Input : A plaintext state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\mathrm {msg} \rangle \langle \mathrm {msg} |} and a key state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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}}
Output: A ciphertext state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \rho \in {\mathcal {D}}({\mathcal {Q}}(m+n+\tau +\mu ))}
- Sample Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r|_{\mathcal {I}}\gets \{0,1\}^{s}} where
- Compute Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=H_{pa}(r|_{\mathcal {I}})} where
- Compute Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p=H_{ec}(r|_{\mathcal {I}})\oplus d}
- Compute Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q=\mathrm {synd} (r|_{\mathcal {I}})\oplus e}
- Output Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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|}
![{\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae3642241854dc14daf83232b7309f67112ca4c1)
Circuit 3: Dec[edit]
The decryption circuit
Input : A key state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sigma \in {\mathcal {D}}({\mathcal {Q}}(n))} and an error flag Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \gamma \in {\mathcal {D}}({\mathcal {Q}})}
- Compute
- Measure in the computational basis. Call the result
- Compute Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{\prime }=\mathrm {corr} (r|_{\mathcal {I}},q\oplus e)} where
- Compute Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p^{\prime }=H_{ec}(r^{\prime })\oplus d}
- If Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\neq p^{\prime }} , then set Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \gamma =|0\rangle \langle 0|} . Else, set Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \gamma =|1\rangle \langle 1|}
- Compute Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{\prime }=H_{pa}(r^{\prime })}
- Output Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \rho \otimes |c,p,q\rangle \langle c,p,q|\in {\mathcal {D}}({\mathcal {Q}}(m+n+\mu +\tau ))}
Output: A certificate string
- Measure in the Hadamard basis. Call the output y.
- Output Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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)
*contributed by Chirag Wadhwa