Quantum Protocol Zoo - User contributions [en]

Protocol Library

2022-02-08T23:36:11Z

Chirag:

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="7"|[[Authentication of Quantum Messages]]||[[Purity Testing based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
|[[Clifford Code for Quantum Authentication]]
|-
|[[Trap Code for Quantum Authentication]]
|-
|[[Auth-QFT-Auth Scheme for Quantum Authentication]]
|-
|[[Unitary Design Scheme for Quantum Authentication]]
|-
|[[Naive approach using Quantum Teleportation]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
|rowspan="2"|[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|[[Device-Independent Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|rowspan="4"|[[Verification of Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of NP-complete problems]]
|-
|[[Verification of Sub-Universal Quantum Computation]]
|-
|[[Classical Verification of Universal Quantum Computation]]
|-
|rowspan="5"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
|[[Practical Quantum Electronic Voting]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="3"|[[Entanglement Routing]]||[[Distributed Routing in a Quantum Internet]]
|-
|[[Routing Entanglement in the Quantum Internet]]
|-
|[[Distributing Graph States Over Arbitrary Quantum Networks]]
|-
|rowspan="1"|[[Quantum Conference Key Agreement]]||[[Anonymous Conference Key Agreement using GHZ states]]
|-
|rowspan="1"|[[Quantum Encryption with Certified Deletion]]||[[Prepare-and-Measure Certified Deletion]]
|-

Quantum Encryption with Certified Deletion

2022-02-08T23:31:30Z

Chirag:

Prepare-and-Measure Certified Deletion

2022-02-08T23:25:14Z

Chirag:

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.


==Requirements==
* '''Network Stage: ''' [[:Category:Prepare and Measure Network Stage| Prepare and Measure]]

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




==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>.


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

Quantum Encryption with Certified Deletion

2022-02-07T21:36:46Z

Chirag: Created functionality page for CDE

Prepare-and-Measure Certified Deletion

2022-02-05T18:21:58Z

Chirag:

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.


==Requirements==
* '''Network Stage: ''' [[:Category:Prepare and Measure Network Stage| Prepare and Measure]]

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




==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>.


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

Prepare-and-Measure Certified Deletion

2022-02-04T13:21:34Z

Chirag:

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.


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




==Properties==


==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>.


==Further Information==


==References==

Prepare-and-Measure Certified Deletion

2022-02-02T02:29:56Z

Chirag:

Prepare-and-Measure Certified Deletion

2022-02-01T02:13:06Z

Chirag: Initial page

Device-Independent Oblivious Transfer

2022-02-01T00:30:39Z

Chirag:

This [https://arxiv.org/abs/2111.08595 example protocol] achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.


==Assumptions==

* The quantum storage of the receiver is bounded during the execution of the protocol
* The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem during the execution of the protocol
* The device behaves in an IID manner - it behaves independently and identically during each round of the protocol

==Requirements==
* '''Network Stage: ''' [[:Category:Entanglement Distribution Network stage| Entanglement Distribution]]
* Classical communication between the parties
* Extended noisy trapdoor claw-free (ENTCF) function family

==Outline==

* The protocol consists of multiple rounds, which are randomly chosen for testing or string generation
* The testing rounds are carried out to ensure that the devices used are following the expected behaviour. The self-testing protocol used is a modification of the one used in [[Device-Independent Quantum Key Distribution | DIQKD]]. This modification is necessary as, unlike the DIQKD scenario, the parties involved in OT may not trust each other to cooperate. The self-testing protocol uses the computational assumptions associated with ''Extended noisy trapdoor claw-free'' (ENTCF) function families to certify that the device has created the desired quantum states. If the fraction of failed testing rounds exceeds a certain limit, the protocol is aborted.
* At the end of the protocol, the honest sender outputs two randomly generated strings of equal length, and the honest receiver outputs their chosen string out of the two.

==Notation==

* <math>S</math>: The sender
* <math>R</math>: The receiver
* <math>l</math>: Length of the output strings
* <math>s_0, s_1</math>: The strings output by the sender
* <math>c</math>: A bit denoting the receiver's choice
* For any bit <math>r</math>, ['''Computational, Hadamard''']<math>_r = \begin{cases}\mbox{Computational, if } r = 0\\ \mbox{Hadamard, if } r = 1\end{cases}</math>
* <math>\sigma_X = \begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix} </math>
* <math>\sigma_Z = \begin{pmatrix}1 & 0 \\ 0 & -1 \end{pmatrix} </math>
* For bits <math>v^{\alpha},v^{\beta}: |\phi^{(v^{\alpha},v^{\beta})}\rangle = (\sigma_Z^{v^{\alpha}}\sigma_X^{v^{\beta}} \otimes I) \frac{|00\rangle+|11\rangle}{\sqrt{2}}</math>
* An ENTCF family consists of two families of function pairs: <math>F</math> and <math>G</math>. A function pair <math>(f_{k,0},f_{k,1})</math>is indexed by a public key <math>k</math>. If <math>(f_{k,0},f_{k,1}) \in F</math>, then it is a ''claw-free pair''; and if <math>(f_{k,0},f_{k,1}) \in G</math>, then it is called an ''injective pair''. ENTCF families satisfy the following properties:
*# For a fixed <math>k \in K_F, f_{k,0}</math> and <math>f_{k,1}</math> are bijections with the same image; for every image <math>y</math>, there exists a unique pair <math>(x_0,x_1)</math>, called a ''claw'', such that <math>f_{k,0}(x_0) = f_{k,1}(x_1) = y</math>
*# Given a ''key'' <math>k \in K_F</math>, for a claw-free pair, it is quantum-computationally intractable (without access to ''trapdoor'' information) to compute both a <math>x_i</math> and a single generalized bit of <math>x_0 \oplus x_1</math>, where <math>(x_0,x_1)</math> forms a valid claw. This is known as the ''adaptive hardcore bit'' property.
*# For a fixed <math>k \in K_G, f_{k,0}</math> and <math>f_{k_1}</math> are injunctive functions with disjoint images.
*# Given a key <math>k \in K_F \cup K_G</math>, it is quantum-computationally hard (without access to ''trapdoor'' information) to determine whether <math>k</math> is a key for a claw-free or an injective pair. This property is known as ''injective invariance''.
*# For every <math>k \in K_F \cup K_G</math>, there exists a trapdoor <math>t_k</math> which can be sampled together with <math>k</math> and with which 2 and 4 are computationally easy.




==Protocol Description==

===Protocol 1: Rand 1-2 OT<math>^l</math>===
'''Requirements:''' Entanglement distribution, classical communication

'''Input:''' Receiver - a bit <math>c</math>

'''Output:''' Sender outputs randomly generated <math>s_0,s_1 \in \{0,1\}^l</math>, Receiver outputs <math>s_c</math>
# A device prepares <math>n</math> uniformly random Bell pairs <math>|\phi^{(v_i^{\alpha},v_i^{\beta})}\rangle, i = 1,...,n</math>, where the first qubit of each pair goes to <math>S</math> along with the string <math>v^{\alpha}</math>, and the second qubit of each pair goes to <math>R</math> along with the string <math>v^{\beta}</math>.
# R measures all qubits in the basis <math>y = [</math>'''Computational,Hadamard'''<math>]_c</math> where <math>c</math> is <math>R</math>'s choice bit. Let <math>b \in \{0,1\}^n</math> be the outcome. <math>R</math> then computes <math>b \oplus w^{\beta}</math>, where the <math>i</math>-th entry of <math>w^{\beta}</math> is defined by
#: <math>w_i^{\beta} := \begin{cases} 0, \mbox{if } y = \mbox{ Hadamard}\\ v_i^{\beta}, \mbox{if } y = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks uniformly random <math>x \in \{</math> '''Computational, Hadamard'''<math>\}^n</math>, and measures the <math>i</math>-th qubit in basis <math>x_i</math>. Let <math>a \in \{0,1\}^n</math> be the outcome. <math>S</math> then computes <math>a \oplus w^{\alpha}</math>, where the <math>i</math>-th entry of <math>w^{\alpha}</math> is defined by
#: <math>w_i^{\alpha} := \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{ Hadamard}\\ 0, \mbox{if } x_i = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks two uniformly random hash functions <math>f_0,f_1 \in F</math>, announces <math>x</math> and <math>f_0,f_1</math> to <math>R</math> and outputs <math>s_0 := f_0(a \oplus w^{\alpha} |_{I_0})</math> and <math>s_1 := f_1(a \oplus w^{\alpha} |_{I_1})</math> where <math>I_r := \{i \in I: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# <math>R</math> outputs <math>s_c = f_c(b \oplus w^{\beta} |_{I_c})</math>

===Protocol 2: Self-testing with a single verifier===
'''Requirements:''' ENTCF function family, classical communication

# Alice chooses the state bases <math>\theta^A,\theta^B \in </math> {'''Computational,Hadamard'''} uniformly at random and generates key-trapdoor pairs <math>(k^A,t^A),(k^B,t^B)</math>, where the generation procedure for <math>k^A</math> and <math>t^A</math> depends on <math>\theta^A</math> and a security parameter <math>\eta</math>, and likewise for <math>k^B</math> and <math>t^B</math>. Alice supplies Bob with <math>k^B</math>. Alice and Bob then respectively send <math>k^A, k^B</math> to the device.
# Alice and Bob receive strings <math>c^A</math> and <math>c^B</math>, respectively, from the device.
# Alice chooses a ''challenge type'' <math>CT \in \{a,b\}</math>, uniformly at random and sends it to Bob. Alice and Bob then send <math>CT</math> to each component of their device.
# If <math>CT = a</math>:
## Alice and Bob receive strings <math>z^A</math> and <math>z^B</math>, respectively, from the device.
# If <math>CT = b</math>:
## Alice and Bob receive strings <math>d^A</math> and <math>d^B</math>, respectively, from the device.
## Alice chooses uniformly random ''measurement bases (questions)'' <math>x,y \in</math> {'''Computational,Hadamard'''} and sends <math>y</math> to Bob. Alice and Bob then, respectively, send <math>x</math> and <math>y</math> to the device.
## Alice and Bob receive answer bits <math>a</math> and <math>b</math>, respectively, from the device. Alice and Bob also receive bits <math>h^A</math> and <math>h^B</math>, respectively, from the device.

===Protocol 3: DI Rand 1-2 OT<math>^l</math>===
'''Requirements:''' Entanglement distribution, ENTCF function family, classical communication

'''Input:''' Receiver - a bit <math>c</math>

'''Output:''' Sender outputs randomly generated <math>s_0,s_1 \in \{0,1\}^l</math>, Receiver outputs <math>s_c</math>
::'''Data generation:'''
# The sender and receiver execute <math>n</math> rounds of '''Protocol 2''' (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
#: If <math>CT_i = b</math>, then with probability <math>p</math>, the receiver does not use the measurement basis question supplied by the sender and instead inputs <math>y_i=[</math>'''Computational, Hadamard'''<math>]_c</math> where <math>c</math> is the receiver's choice bit. Let <math>I</math> be the set of indices marking the rounds where this has been done.
#: For each round <math> i \in \{1,...,n\} </math>, the receiver stores:
#:* <math>c_i^B</math>
#:* <math>z_i^B</math> if <math>CT_i = a</math>
#:* or <math>(d_i^B,y_i,b_i,h_i^B)</math> if <math>CT_i = b</math>
#: The sender stores <math>\theta_i^A,\theta_i^B,(k_i^A,t_i^A),(k_i^B,t_i^B),c_i^A,CT_i;</math> and <math>z_i^A</math> if <math>CT_i = a</math> or <math>(d_i^A,x_i,a_i,h_i^A)</math> and <math>y_i</math> if <math>CT_i = b</math>
# For every <math>i \in \{1,...,n\},</math> the sender stores the variable <math>RT_i</math> (round type), defined as follows:
#* if <math>CT_i = b</math> and <math>\theta_i^A = \theta_i^B = </math>'''Hadamard''', then <math>RT_i =</math> '''Bell'''
#* else, set <math>RT_i = </math> '''Product'''
# For every <math>i \in \{1,...,n\},</math> the sender chooses <math>T_i</math>, indicating a test round or generation round, as follows:
#* if <math>RT_i = </math> '''Bell''', choose <math>T_i \in</math> {'''Test, Generate'''} uniformly at random
#* else, set <math>T_i = </math> '''Test'''
#: The sender sends (<math>T_1,...,T_n</math>) to the receiver
#:
#: '''Testing:'''
# The receiver sends the set of indices <math>I</math> to the sender. The receiver publishes their output for all <math>T_i = </math> '''Test''' rounds where <math>i \notin I</math>. Using this published data, the sender determines the bits which an honest device would have returned.
# The sender computes the fraction of test rounds (for which the receiver has published data for) that failed. If this exceeds some <math>\epsilon</math>, the protocol aborts
#:
#: '''Preparing data:'''
# Let <math>\tilde{I} := \{i : i \in I</math> and <math>T_i = </math> '''Generate'''} and <math>n^{\prime} = |\tilde{I}|</math>. The sender checks if there exists a <math> k > 0 </math> such that <math>\gamma n^{\prime} \leq n^{\prime}/4 - 2l -kn^{\prime}</math>. If such a <math>k</math> exists, the sender publishes <math>\tilde{I}</math> and, for each <math>i \in \tilde{I}</math>, the trapdoor <math>t_i^B</math> corresponding to the key <math>k_i^B</math> (given by the sender in the execution of '''Protocol 2,Step 1'''); otherwise the protocol aborts.

# For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha} = d^A_i.(x_{i,0}^A \oplus x_{i,1}^A)</math> and defines <math>w^{\alpha}</math> by
#:<math>w_i^{\alpha} = \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{Hadamard}\\ 0, \mbox{if } x_i = \mbox{Computational}\end{cases}</math>
#: and the receiver calculates <math>v_i^{\beta} = = d^B_i.(x_{i,0}^B \oplus x_{i,1}^B)</math> and defines <math>w^{\beta}</math> by
#:<math>w_i^{\beta} = \begin{cases} 0, \mbox{if } y_i = \mbox{Hadamard}\\ v_i^{\beta}, \mbox{if } y_i = \mbox{Computational}\end{cases}</math>
#: '''Obtaining output:'''
# The sender randomly picks two hash functions <math>f_0,f_1 \in F</math>, announces <math>f_0,f_1</math> and <math>x_i</math> for each <math>i \in \tilde{I}</math>, and outputs <math>s_0 = f_0(a \oplus w^{\alpha}|_{\tilde{I}_0})</math> and <math>s_1 = f_1(a \oplus w^{\alpha}|_{\tilde{I}_1})</math>, where <math>\tilde{I}_r := \{i \in \tilde{I}: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# Receiver outputs <math>s_c = f_c(a \oplus w^{\beta}|_{\tilde{I}_c})</math>

==Properties==

* <math>\epsilon</math>-'''Receiver security:''' If <math>R</math> is honest, then for any <math>\tilde{S}</math>, there exist random variables <math>S_0^{\prime}, S_1^{\prime}</math> such that Pr[<math>Y = S_c^{\prime}] \geq 1 - \epsilon</math> and <math>D(\rho_{c,S_0^{\prime}, S_1^{\prime},\tilde{S}}, \rho_c \otimes \rho_{S_0^{\prime}, S_1^{\prime},\tilde{S}}) \leq \epsilon</math>
*: Protocol 3 is perfectly receiver secure, i.e. <math>\epsilon</math> = 0
* <math>\epsilon</math>-'''Sender security:''' If S is honest, then for any <math>\tilde{R}</math>, there exist a random variable <math>c^{\prime}</math> such that <math>D(\rho_{S_{1-c^{\prime}},S_{c^{\prime}},c^{\prime},\tilde{R}}, \frac{1}{2^l}I \otimes \rho_{S_{c^{\prime}},c^{\prime},\tilde{R}}) \leq \epsilon</math>
*: Protocol 3 is <math>\epsilon^{\prime}</math>-sender secure, where <math>\epsilon^{\prime}</math> can be made negligible in certain conditions.

==References==
* The protocol and its security proofs can be found in [https://arxiv.org/abs/2111.08595 Broadbent and Yuen(2021)]
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>

Practical Quantum Electronic Voting

2022-02-01T00:10:56Z

Chirag:

This [https://arxiv.org/abs/2107.14719 example protocol] achieves the functionality of [[Quantum Electronic Voting]]. In this protocol, an untrusted multipartite entanglement source can be used to carry out an election without any election authorities.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party Protocols]], [[:Category: Quantum Enhanced Classical Functionality| Quantum Enhanced Classical Functionality]], [[:Category:Specific Task | Specific Task]]

==Requirements==

* Classical communication between the voting agents
* A multipartite entanglement source connected to each agent by a quantum channel. The source need not be trusted.
* Voting agents must be able to generate random numbers

==Outline==

* In the first phase of the protocol, each agent is assigned a secret unique random index
* Next, we perform multiple rounds of voting, one for each agent. In each round, the following steps are carried out:
** The agent with the same index as the round number is designated the voter for that round
** The source distributes one qubit of a GHZ state to each agent. The voting agent randomly chooses to either '''verify''' the GHZ state or '''vote''' with a certain probability. This step, including state distribution, is repeated until the voter chooses to vote. Once voting is chosen, the voter anonymously transmits their vote to all agents.
* Finally, all the votes are tallied. All agents have the votes for each round and can thus verify the final tally.

==Notation==

* <math>N</math>: Number of agents
* <math>V = \{v_k\}_{k \in [N]} </math>: The votes
* <math>S</math>: Security parameter
* <math>\epsilon</math>: Distance from the perfect GHZ state
* <math>\delta</math>: Threshold for verification
* <math>\eta</math>: Probability of failure of verification
* '''B''': Bulletin board - <math>N</math> x <math>N</math> binary matrix. Each row corresponds to one round of voting, and each column contains the output of a single voter across all rounds
* '''E''': Vote vector - The list of votes across <math>N</math> rounds. Each element is computed as the parity of a row from '''B'''
* '''T''': Final tally





==Protocol Description==

===Protocol 1 : Quantum e-voting===
''Inputs'': <math>V = \{v_k\}_{k \in [N]} </math> - Set of votes; <math>S</math> - Security parameter; <math>\epsilon</math> - Distance from the perfect GHZ state; <math>\delta</math> - Threshold for verification; <math>\eta</math> Probability of failure of verification

''Output'': The candidate with majority votes or ''Abort''

''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels
* Phase 1 [getting unique secret indices]
** Agents perform '''UniqueIndex''' until each agent has a secret unique random index <math>\omega_k</math>
* Phase 2 [casting votes]
** For <math>l = 1</math> to <math>N</math>
*** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math>
*** Repeat until '''Voting''' is announced
**** The source distributes to each of the N agents one qubit of the GHZ source
**** All agents <math> j \in [N] </math> set rejections<math>_j = </math> trials<math>_j = 0</math>
**** The voting agent tosses log<math>_2[\frac{16N\epsilon^2}{(\epsilon^2-4\delta)^2}</math>ln<math>(\frac{1}{\eta})]</math> 
**** The agents perform '''LogicalOR''', where output 1 indicates '''Verification''' and output 0 indicates '''Voting'''. Everyone except the voting agent inputs 0; if the coin toss is 'all heads' the voting agent also inputs 0, otherwise the voting agent inputs 1
**** If '''Verification''' is chosen, the agents perform '''RandomAgent''' and the voting agent anonymously picks an agent <math>j \in [N]</math> to be the verifier. Agent <math>j</math> updates trials<math>_j+ = 1</math> and if '''Verification''' outputs reject: rejections<math>_j+ = 1</math>
*** If for any <math>j \in [N], \delta_j = \frac{rejections_j}{trials_j} > \delta </math>, the protocol ''Aborts''
*** Perform '''Voting'''. The outcome is one row of the Bulletin Board '''B'''. The parity of the row gives one entry in the vote vector '''E'''.
** Given the votes '''E''', the tally '''T''' can be computed.
*Phase 3 [Verification of results]:
** All agents perform '''LogicalOR''' with security parameter <math>S</math>, and input 1 if their vote is not the same as the entry in '''E''' for the round in which they voted, and 0 otherwise.
** If '''LogicalOR''' outputs 1, ''Abort'' the protocol. Else output the candidate with the most votes according to the tally '''T'''.

===Protocol 2 : UniqueIndex===

''Input'': Security parameter <math>S</math> to be used in '''LogicalOR''',<math>N</math> random boolean variables <math>x_i</math>.

''Output'': Each agent <math>k</math> has a secret unique index <math>\omega_k</math>.

''Resources'': Classical communication and random numbers.

# Beginning of round R = 1
# Agents perform '''LogicalOR''' with inputs <math>x_k = 0</math> if they already have an index and <math>x_k = 1</math> if they do not.
# If <math>y = 0</math>, repeat from step 2
# If an agent <math>k</math> has a bit <math>x_k = 1</math> and <math>\omega_k = 0</math> they know they are the only one and has been assigned the secret index corresponding to the round <math>\omega_k = R</math>, otherwise there is a collision.
# [notification] Everybody performs a '''LogicalOR''' with input 0, unless they received the index in this round, in which case they input 1.
# If the output of '''LogicalOR''' is 0, no index was assigned and we repeat from step 2.
# If the output of '''LogicalOR''' is 1, the index was assigned and we repeat from step 2 with R+ = 1.
# Repeat from step 2 until all indices have been assigned.

===Protocol 3 : Verification===
''Input'': A quantum state distributed and shared by <math>N</math> parties, security parameter <math>S</math> for '''RandomAgent'''.

''Output'': If the state is a GHZ state <math> \rightarrow </math> YES.

''Resources'': Classical communication, random numbers, quantum state source, quantum channels.

# Everyone executes '''RandomAgent''' to choose uniformly at random one of the voters to be the verifier.
# The verifier generates random angles <math>\theta_j \in [0, \pi)</math> for all agents including themselves, such that the sum is a multiple of <math>\pi</math>. The angles are then sent out to all the agents.
# Agent <math>j</math> measures in the basis <math>[|+_\theta\rangle,|-_\theta\rangle] = [\frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta_j}|1\rangle), \frac{1}{\sqrt{2}}(|0\rangle - e^{i\theta_j}|1\rangle)]</math> and publicly announces the result <math>Y_j = \{0,1\}</math>
# The state passes the verification test when the following condition is satisfied: if the sum of the randomly chosen angles is an even multiple of <math>\pi</math>, there must be an even number of 1 outcomes for <math>Y_j</math> , and if the sum is an odd multiple of <math>\pi</math>, there must be an odd number of 1 outcomes for <math>Y_j : \bigoplus_j Y_j = \frac{1}{\pi}\sum_i\theta_i </math> (mod 2)

===Protocol 4 : Voting===
''Input'': Voting agent preference <math>v_k</math>.

''Output'': All agents get one row of the bulletin board.

''Resources'': Classical communication, GHZ source, quantum channels.

# Each agent measures the state they received in the Hadamard basis and records the outcome.
# The outcomes of the measurement of each voter <math>k</math> is <math>d_k</math>. Then we know that <math>\sum_kd_k = 0</math> mod <math> 2</math>
# The voting agent performs an XOR between the outcome <math>d_k</math> and their vote <math>v_k</math>: <math>d_k \leftarrow d_k \oplus v_k </math>. However, this alone will still appear as a random string.
# Every agent publicly broadcasts <math>d_k</math> which gives one line <math>b_k</math> of the bulletin board '''B''' <math> = \{b_k\}</math>

===Protocol 5 : LogicalOR===
''Inputs'': <math>N</math> agents, <math>N</math> boolean variables <math>x_i</math>, security parameter <math>S = (1 - 2^{-\Gamma})^\Sigma \in (0,1)</math>

''Output'': <math>y = \vee_i^N x_i </math>

''Resources'': Classical communication and random numbers

# Decide <math>N</math> random orderings, such that each voter is the last once. For each ordering repeat \Sigma times the following.
# Each voter <math>k</math> gives an input <math>x_k</math>
# If <math>x_k = 0 </math>, set <math>p_k = 0</math>, otherwise toss <math>\Gamma</math> coins and set <math>p_k</math> to <math>1</math> if the result is ‘all heads’ and to <math>0</math> otherwise
# Then each voter generates uniformly at random an <math>N</math>-bit string <math>r_k = r_k^1r_k^2...r_k^N</math>, such that <math>\bigoplus_{i=1}^N r_k^i = p_k</math>
# Voter <math>k</math> sends <math>r_k^i</math> to voter <math>i</math> for all <math>i</math>, keeping <math>r_k^k</math>
# Each voter sums the received bits and broadcasts the parity <math>z_i = \bigoplus_{k=1}^N r_k^i </math> according to the ordering.
# Compute the parity of the original bits <math>y = \bigoplus_i z_i</math>
# From this everyone can also compute the parity of all other inputs except their own <math>w_k = \bigoplus_{i = 1}^N (z_i \otimes r_k^i)</math>
# Repeat <math>\Sigma</math> times from step 4: each time repeat with <math>p_k</math> as new inputs
# If at least once in the <math>\Sigma</math> repetitions for the various orderings <math>y = 1</math>, this is the output of the protocol, otherwise it is <math>y = 0</math>

===Protocol 6 : RandomBit===
''Input'': Security parameter S to be used in '''LogicalOR''', ''voting agent'': probability distribution D.

''Output'': The voting agent anonymously announces a random bit according to D.

''Resources'': Classical communication and random numbers.

*Perform '''LogicalOR''' with security parameter S where the voting agent inputs a random bit according to D and the other agents input 0.

===Protocol 7 : RandomAgent===

''Input'': Security parameter S to be used in '''RandomBit''', voting agent: probability distribution D.

''Output'': The voting agent anonymously chooses a random agent according to D.

''Resources'': Classical communication and random numbers.

* Repeat '''RandomBit''' log2 N times.

==Properties==

* <math>(\sigma_H,\sigma_D,\gamma)</math>-''Correctness'': This notion of approximate correctness includes two properties:
** <math>\sigma_H</math>-''Completeness'': If all agents are honest, the election is accepted with probability more than <math>\sigma_H</math> - Pr[election accepted] <math> \geq \sigma_H</math>
** <math>(\sigma_D,\gamma)</math>-''Soundness'': the probability that the election result is accepted, given that the set of the votes '''E''' computed from the bulletin board '''B''' resulting from the election is more than <math>\gamma</math> away from the real votes '''V''', is smaller than <math>\sigma_D</math> -
:: Pr[election accepted <math>| \frac{1}{N}||</math>'''V''' - '''E'''<math>||_1 \geq \gamma] \leq \sigma_D </math>
: This particular protocol is <math>([1-\epsilon(1-S)]^N, S^{N(1+\lambda)[\epsilon(1-\eta)+\eta]},(1+\lambda)[\epsilon(1-\eta)+\eta])</math>-correct, for a small constant <math>\lambda > 0</math>

* <math>\zeta</math>-''Privacy'': The privacy of the election scheme implies that for any voter <math>k</math>, the probability that any subset of malicious parties <math>D</math> that deviates from the honest protocol can guess the vote <math>v_k</math> of the voter is at most <math>\zeta</math> more than in the case they just have access to the bulletin board and to their own votes -
: <math>\forall k, </math> Pr<math>[v_k|D] -</math> Pr<math>[v_k|B,v_j \in </math> '''V'''<math>_D] \leq \zeta</math>
: This particular protocol is <math>\zeta</math>-private with <math>\zeta = (1-\eta)^N\epsilon + (1 - (1-\eta)^N)</math>

* ''Authentication'': This e-voting protocol does not provide authentication, which should be taken care of by the physical implementation of the protocol.

* ''Double voting'': Each voter can vote at most once. Since the number of voters is known in advance for this protocol, double voting is easily taken care of.

* ''Verifiability'': Each voter can verify that their vote has been counted correctly. In this protocol, the tally is performed by the voters themselves. The bulletin board produced as an output of the protocol is public and can always be checked by everyone, while still appearing random.

* ''Receipt freeness'': In order to prevent vote-selling, voters should not be able to prove how they voted. As the unique indices stay secret, voters cannot produce a receipt of their vote.

* ''Additional candidates'': The protocol described here only allows an election consisting of 2 candidates. This can be extended to more candidates by repeating the protocol multiple times in sequence. In particular, if there are K candidates, we can express each of them using log<math>_2</math>K bits and repeat the election as many times so that each vote set corresponds to one bit. This however does affect the correctness and privacy.

==Further Information==

* Proofs of the protocol properties can be found in [https://arxiv.org/abs/2107.14719 Centrone et al. (2021)]
* Protocols 5-7 are classical anonymous protocols taken from [https://arxiv.org/abs/0706.2010 Broadbent and Tapp(2007)] and used in [https://arxiv.org/abs/1811.04729 Unnikrishnan et al.(2018)]
* Protocol 3 is the same as that of [https://arxiv.org/abs/1112.5064 Pappa et al.(2011)]

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

Device-Independent Oblivious Transfer

2022-01-29T16:05:45Z

Chirag: Added requirements

This [https://arxiv.org/abs/2111.08595 example protocol] achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.


==Assumptions==

* The quantum storage of the receiver is bounded during the execution of the protocol
* The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem during the execution of the protocol
* The device behaves in an IID manner - it behaves independently and identically during each round of the protocol

==Outline==

* The protocol consists of multiple rounds, which are randomly chosen for testing or string generation
* The testing rounds are carried out to ensure that the devices used are following the expected behaviour. The self-testing protocol used is a modification of the one used in [[Device-Independent Quantum Key Distribution | DIQKD]]. This modification is necessary as, unlike the DIQKD scenario, the parties involved in OT may not trust each other to cooperate. The self-testing protocol uses the computational assumptions associated with ''Extended noisy trapdoor claw-free'' (ENTCF) function families to certify that the device has created the desired quantum states. If the fraction of failed testing rounds exceeds a certain limit, the protocol is aborted.
* At the end of the protocol, the honest sender outputs two randomly generated strings of equal length, and the honest receiver outputs their chosen string out of the two.

==Notation==

* <math>S</math>: The sender
* <math>R</math>: The receiver
* <math>l</math>: Length of the output strings
* <math>s_0, s_1</math>: The strings output by the sender
* <math>c</math>: A bit denoting the receiver's choice
* For any bit <math>r</math>, ['''Computational, Hadamard''']<math>_r = \begin{cases}\mbox{Computational, if } r = 0\\ \mbox{Hadamard, if } r = 1\end{cases}</math>
* <math>\sigma_X = \begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix} </math>
* <math>\sigma_Z = \begin{pmatrix}1 & 0 \\ 0 & -1 \end{pmatrix} </math>
* For bits <math>v^{\alpha},v^{\beta}: |\phi^{(v^{\alpha},v^{\beta})}\rangle = (\sigma_Z^{v^{\alpha}}\sigma_X^{v^{\beta}} \otimes I) \frac{|00\rangle+|11\rangle}{\sqrt{2}}</math>
* An ENTCF family consists of two families of function pairs: <math>F</math> and <math>G</math>. A function pair <math>(f_{k,0},f_{k,1})</math>is indexed by a public key <math>k</math>. If <math>(f_{k,0},f_{k,1}) \in F</math>, then it is a ''claw-free pair''; and if <math>(f_{k,0},f_{k,1}) \in G</math>, then it is called an ''injective pair''. ENTCF families satisfy the following properties:
*# For a fixed <math>k \in K_F, f_{k,0}</math> and <math>f_{k,1}</math> are bijections with the same image; for every image <math>y</math>, there exists a unique pair <math>(x_0,x_1)</math>, called a ''claw'', such that <math>f_{k,0}(x_0) = f_{k,1}(x_1) = y</math>
*# Given a ''key'' <math>k \in K_F</math>, for a claw-free pair, it is quantum-computationally intractable (without access to ''trapdoor'' information) to compute both a <math>x_i</math> and a single generalized bit of <math>x_0 \oplus x_1</math>, where <math>(x_0,x_1)</math> forms a valid claw. This is known as the ''adaptive hardcore bit'' property.
*# For a fixed <math>k \in K_G, f_{k,0}</math> and <math>f_{k_1}</math> are injunctive functions with disjoint images.
*# Given a key <math>k \in K_F \cup K_G</math>, it is quantum-computationally hard (without access to ''trapdoor'' information) to determine whether <math>k</math> is a key for a claw-free or an injective pair. This property is known as ''injective invariance''.
*# For every <math>k \in K_F \cup K_G</math>, there exists a trapdoor <math>t_k</math> which can be sampled together with <math>k</math> and with which 2 and 4 are computationally easy.




==Protocol Description==

===Protocol 1: Rand 1-2 OT<math>^l</math>===
'''Requirements:''' Entanglement distribution, classical communication

'''Input:''' Receiver - a bit <math>c</math>

'''Output:''' Sender outputs randomly generated <math>s_0,s_1 \in \{0,1\}^l</math>, Receiver outputs <math>s_c</math>
# A device prepares <math>n</math> uniformly random Bell pairs <math>|\phi^{(v_i^{\alpha},v_i^{\beta})}\rangle, i = 1,...,n</math>, where the first qubit of each pair goes to <math>S</math> along with the string <math>v^{\alpha}</math>, and the second qubit of each pair goes to <math>R</math> along with the string <math>v^{\beta}</math>.
# R measures all qubits in the basis <math>y = [</math>'''Computational,Hadamard'''<math>]_c</math> where <math>c</math> is <math>R</math>'s choice bit. Let <math>b \in \{0,1\}^n</math> be the outcome. <math>R</math> then computes <math>b \oplus w^{\beta}</math>, where the <math>i</math>-th entry of <math>w^{\beta}</math> is defined by
#: <math>w_i^{\beta} := \begin{cases} 0, \mbox{if } y = \mbox{ Hadamard}\\ v_i^{\beta}, \mbox{if } y = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks uniformly random <math>x \in \{</math> '''Computational, Hadamard'''<math>\}^n</math>, and measures the <math>i</math>-th qubit in basis <math>x_i</math>. Let <math>a \in \{0,1\}^n</math> be the outcome. <math>S</math> then computes <math>a \oplus w^{\alpha}</math>, where the <math>i</math>-th entry of <math>w^{\alpha}</math> is defined by
#: <math>w_i^{\alpha} := \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{ Hadamard}\\ 0, \mbox{if } x_i = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks two uniformly random hash functions <math>f_0,f_1 \in F</math>, announces <math>x</math> and <math>f_0,f_1</math> to <math>R</math> and outputs <math>s_0 := f_0(a \oplus w^{\alpha} |_{I_0})</math> and <math>s_1 := f_1(a \oplus w^{\alpha} |_{I_1})</math> where <math>I_r := \{i \in I: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# <math>R</math> outputs <math>s_c = f_c(b \oplus w^{\beta} |_{I_c})</math>

===Protocol 2: Self-testing with a single verifier===
'''Requirements:''' ENTCF function family, classical communication

# Alice chooses the state bases <math>\theta^A,\theta^B \in </math> {'''Computational,Hadamard'''} uniformly at random and generates key-trapdoor pairs <math>(k^A,t^A),(k^B,t^B)</math>, where the generation procedure for <math>k^A</math> and <math>t^A</math> depends on <math>\theta^A</math> and a security parameter <math>\eta</math>, and likewise for <math>k^B</math> and <math>t^B</math>. Alice supplies Bob with <math>k^B</math>. Alice and Bob then respectively send <math>k^A, k^B</math> to the device.
# Alice and Bob receive strings <math>c^A</math> and <math>c^B</math>, respectively, from the device.
# Alice chooses a ''challenge type'' <math>CT \in \{a,b\}</math>, uniformly at random and sends it to Bob. Alice and Bob then send <math>CT</math> to each component of their device.
# If <math>CT = a</math>:
## Alice and Bob receive strings <math>z^A</math> and <math>z^B</math>, respectively, from the device.
# If <math>CT = b</math>:
## Alice and Bob receive strings <math>d^A</math> and <math>d^B</math>, respectively, from the device.
## Alice chooses uniformly random ''measurement bases (questions)'' <math>x,y \in</math> {'''Computational,Hadamard'''} and sends <math>y</math> to Bob. Alice and Bob then, respectively, send <math>x</math> and <math>y</math> to the device.
## Alice and Bob receive answer bits <math>a</math> and <math>b</math>, respectively, from the device. Alice and Bob also receive bits <math>h^A</math> and <math>h^B</math>, respectively, from the device.

===Protocol 3: DI Rand 1-2 OT<math>^l</math>===
'''Requirements:''' Entanglement distribution, ENTCF function family, classical communication

'''Input:''' Receiver - a bit <math>c</math>

'''Output:''' Sender outputs randomly generated <math>s_0,s_1 \in \{0,1\}^l</math>, Receiver outputs <math>s_c</math>
::'''Data generation:'''
# The sender and receiver execute <math>n</math> rounds of '''Protocol 2''' (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
#: If <math>CT_i = b</math>, then with probability <math>p</math>, the receiver does not use the measurement basis question supplied by the sender and instead inputs <math>y_i=[</math>'''Computational, Hadamard'''<math>]_c</math> where <math>c</math> is the receiver's choice bit. Let <math>I</math> be the set of indices marking the rounds where this has been done.
#: For each round <math> i \in \{1,...,n\} </math>, the receiver stores:
#:* <math>c_i^B</math>
#:* <math>z_i^B</math> if <math>CT_i = a</math>
#:* or <math>(d_i^B,y_i,b_i,h_i^B)</math> if <math>CT_i = b</math>
#: The sender stores <math>\theta_i^A,\theta_i^B,(k_i^A,t_i^A),(k_i^B,t_i^B),c_i^A,CT_i;</math> and <math>z_i^A</math> if <math>CT_i = a</math> or <math>(d_i^A,x_i,a_i,h_i^A)</math> and <math>y_i</math> if <math>CT_i = b</math>
# For every <math>i \in \{1,...,n\},</math> the sender stores the variable <math>RT_i</math> (round type), defined as follows:
#* if <math>CT_i = b</math> and <math>\theta_i^A = \theta_i^B = </math>'''Hadamard''', then <math>RT_i =</math> '''Bell'''
#* else, set <math>RT_i = </math> '''Product'''
# For every <math>i \in \{1,...,n\},</math> the sender chooses <math>T_i</math>, indicating a test round or generation round, as follows:
#* if <math>RT_i = </math> '''Bell''', choose <math>T_i \in</math> {'''Test, Generate'''} uniformly at random
#* else, set <math>T_i = </math> '''Test'''
#: The sender sends (<math>T_1,...,T_n</math>) to the receiver
#:
#: '''Testing:'''
# The receiver sends the set of indices <math>I</math> to the sender. The receiver publishes their output for all <math>T_i = </math> '''Test''' rounds where <math>i \notin I</math>. Using this published data, the sender determines the bits which an honest device would have returned.
# The sender computes the fraction of test rounds (for which the receiver has published data for) that failed. If this exceeds some <math>\epsilon</math>, the protocol aborts
#:
#: '''Preparing data:'''
# Let <math>\tilde{I} := \{i : i \in I</math> and <math>T_i = </math> '''Generate'''} and <math>n^{\prime} = |\tilde{I}|</math>. The sender checks if there exists a <math> k > 0 </math> such that <math>\gamma n^{\prime} \leq n^{\prime}/4 - 2l -kn^{\prime}</math>. If such a <math>k</math> exists, the sender publishes <math>\tilde{I}</math> and, for each <math>i \in \tilde{I}</math>, the trapdoor <math>t_i^B</math> corresponding to the key <math>k_i^B</math> (given by the sender in the execution of '''Protocol 2,Step 1'''); otherwise the protocol aborts.

# For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha} = d^A_i.(x_{i,0}^A \oplus x_{i,1}^A)</math> and defines <math>w^{\alpha}</math> by
#:<math>w_i^{\alpha} = \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{Hadamard}\\ 0, \mbox{if } x_i = \mbox{Computational}\end{cases}</math>
#: and the receiver calculates <math>v_i^{\beta} = = d^B_i.(x_{i,0}^B \oplus x_{i,1}^B)</math> and defines <math>w^{\beta}</math> by
#:<math>w_i^{\beta} = \begin{cases} 0, \mbox{if } y_i = \mbox{Hadamard}\\ v_i^{\beta}, \mbox{if } y_i = \mbox{Computational}\end{cases}</math>
#: '''Obtaining output:'''
# The sender randomly picks two hash functions <math>f_0,f_1 \in F</math>, announces <math>f_0,f_1</math> and <math>x_i</math> for each <math>i \in \tilde{I}</math>, and outputs <math>s_0 = f_0(a \oplus w^{\alpha}|_{\tilde{I}_0})</math> and <math>s_1 = f_1(a \oplus w^{\alpha}|_{\tilde{I}_1})</math>, where <math>\tilde{I}_r := \{i \in \tilde{I}: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# Receiver outputs <math>s_c = f_c(a \oplus w^{\beta}|_{\tilde{I}_c})</math>

==Properties==

* <math>\epsilon</math>-'''Receiver security:''' If <math>R</math> is honest, then for any <math>\tilde{S}</math>, there exist random variables <math>S_0^{\prime}, S_1^{\prime}</math> such that Pr[<math>Y = S_c^{\prime}] \geq 1 - \epsilon</math> and <math>D(\rho_{c,S_0^{\prime}, S_1^{\prime},\tilde{S}}, \rho_c \otimes \rho_{S_0^{\prime}, S_1^{\prime},\tilde{S}}) \leq \epsilon</math>
*: Protocol 3 is perfectly receiver secure, i.e. <math>\epsilon</math> = 0
* <math>\epsilon</math>-'''Sender security:''' If S is honest, then for any <math>\tilde{R}</math>, there exist a random variable <math>c^{\prime}</math> such that <math>D(\rho_{S_{1-c^{\prime}},S_{c^{\prime}},c^{\prime},\tilde{R}}, \frac{1}{2^l}I \otimes \rho_{S_{c^{\prime}},c^{\prime},\tilde{R}}) \leq \epsilon</math>
*: Protocol 3 is <math>\epsilon^{\prime}</math>-sender secure, where <math>\epsilon^{\prime}</math> can be made negligible in certain conditions.

==References==
* The protocol and its security proofs can be found in [https://arxiv.org/abs/2111.08595 Broadbent and Yuen(2021)]
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>

Device-Independent Oblivious Transfer

2022-01-23T09:34:10Z

Chirag:

This [https://arxiv.org/abs/2111.08595 example protocol] achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.


==Assumptions==

* The quantum storage of the receiver is bounded during the execution of the protocol
* The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem during the execution of the protocol
* The device behaves in an IID manner - it behaves independently and identically during each round of the protocol

==Outline==

* The protocol consists of multiple rounds, which are randomly chosen for testing or string generation
* The testing rounds are carried out to ensure that the devices used are following the expected behaviour. The self-testing protocol used is a modification of the one used in DIQKD. This modification is necessary as, unlike the DIQKD scenario, the parties involved in OT may not trust each other to cooperate. The self-testing protocol uses the computational assumptions associated with ''Extended noisy trapdoor claw-free'' (ENTCF) function families to certify that the device has created the desired quantum states. If the fraction of failed testing rounds exceeds a certain limit, the protocol is aborted.
* At the end of the protocol, the honest sender outputs two randomly generated strings of equal length, and the honest receiver outputs their chosen string out of the two.

==Notation==

* <math>S</math>: The sender
* <math>R</math>: The receiver
* <math>l</math>: Length of the output strings
* <math>s_0, s_1</math>: The strings output by the sender
* <math>c</math>: A bit denoting the receiver's choice
* For any bit <math>r</math>, ['''Computational, Hadamard''']<math>_r = \begin{cases}\mbox{Computational, if } r = 0\\ \mbox{Hadamard, if } r = 1\end{cases}</math>
* <math>\sigma_X = \begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix} </math>
* <math>\sigma_Z = \begin{pmatrix}1 & 0 \\ 0 & -1 \end{pmatrix} </math>
* For bits <math>v^{\alpha},v^{\beta}: |\phi^{(v^{\alpha},v^{\beta})}\rangle = (\sigma_Z^{v^{\alpha}}\sigma_X^{v^{\beta}} \otimes I) \frac{|00\rangle+|11\rangle}{\sqrt{2}}</math>
* An ENTCF family consists of two families of function pairs: <math>F</math> and <math>G</math>. A function pair <math>(f_{k,0},f_{k,1})</math>is indexed by a public key <math>k</math>. If <math>(f_{k,0},f_{k,1}) \in F</math>, then it is a ''claw-free pair''; and if <math>(f_{k,0},f_{k,1}) \in G</math>, then it is called an ''injective pair''. ENTCF families satisfy the following properties:
*# For a fixed <math>k \in K_F, f_{k,0}</math> and <math>f_{k,1}</math> are bijections with the same image; for every image <math>y</math>, there exists a unique pair <math>(x_0,x_1)</math>, called a ''claw'', such that <math>f_{k,0}(x_0) = f_{k,1}(x_1) = y</math>
*# Given a ''key'' <math>k \in K_F</math>, for a claw-free pair, it is quantum-computationally intractable (without access to ''trapdoor'' information) to compute both a <math>x_i</math> and a single generalized bit of <math>x_0 \oplus x_1</math>, where <math>(x_0,x_1)</math> forms a valid claw. This is known as the ''adaptive hardcore bit'' property.
*# For a fixed <math>k \in K_G, f_{k,0}</math> and <math>f_{k_1}</math> are injunctive functions with disjoint images.
*# Given a key <math>k \in K_F \cup K_G</math>, it is quantum-computationally hard (without access to ''trapdoor'' information) to determine whether <math>k</math> is a key for a claw-free or an injective pair. This property is known as ''injective invariance''.
*# For every <math>k \in K_F \cup K_G</math>, there exists a trapdoor <math>t_k</math> which can be sampled together with <math>k</math> and with which 2 and 4 are computationally easy.




==Protocol Description==

===Protocol 1: Rand 1-2 OT<math>^l</math>===
# A device prepares <math>n</math> uniformly random Bell pairs <math>|\phi^{(v_i^{\alpha},v_i^{\beta})}\rangle, i = 1,...,n</math>, where the first qubit of each pair goes to <math>S</math> along with the string <math>v^{\alpha}</math>, and the second qubit of each pair goes to <math>R</math> along with the string <math>v^{\beta}</math>.
# R measures all qubits in the basis <math>y = [</math>'''Computational,Hadamard'''<math>]_c</math> where <math>c</math> is <math>R</math>'s choice bit. Let <math>b \in \{0,1\}^n</math> be the outcome. <math>R</math> then computes <math>b \oplus w^{\beta}</math>, where the <math>i</math>-th entry of <math>w^{\beta}</math> is defined by
#: <math>w_i^{\beta} := \begin{cases} 0, \mbox{if } y = \mbox{ Hadamard}\\ v_i^{\beta}, \mbox{if } y = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks uniformly random <math>x \in \{</math> '''Computational, Hadamard'''<math>\}^n</math>, and measures the <math>i</math>-th qubit in basis <math>x_i</math>. Let <math>a \in \{0,1\}^n</math> be the outcome. <math>S</math> then computes <math>a \oplus w^{\alpha}</math>, where the <math>i</math>-th entry of <math>w^{\alpha}</math> is defined by
#: <math>w_i^{\alpha} := \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{ Hadamard}\\ 0, \mbox{if } x_i = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks two uniformly random hash functions <math>f_0,f_1 \in F</math>, announces <math>x</math> and <math>f_0,f_1</math> to <math>R</math> and outputs <math>s_0 := f_0(a \oplus w^{\alpha} |_{I_0})</math> and <math>s_1 := f_1(a \oplus w^{\alpha} |_{I_1})</math> where <math>I_r := \{i \in I: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# <math>R</math> outputs <math>s_c = f_c(b \oplus w^{\beta} |_{I_c})</math>

===Protocol 2: Self-testing with a single verifier===
# Alice chooses the state bases <math>\theta^A,\theta^B \in </math> {'''Computational,Hadamard'''} uniformly at random and generates key-trapdoor pairs <math>(k^A,t^A),(k^B,t^B)</math>, where the generation procedure for <math>k^A</math> and <math>t^A</math> depends on <math>\theta^A</math> and a security parameter <math>\eta</math>, and likewise for <math>k^B</math> and <math>t^B</math>. Alice supplies Bob with <math>k^B</math>. Alice and Bob then respectively send <math>k^A, k^B</math> to the device.
# Alice and Bob receive strings <math>c^A</math> and <math>c^B</math>, respectively, from the device.
# Alice chooses a ''challenge type'' <math>CT \in \{a,b\}</math>, uniformly at random and sends it to Bob. Alice and Bob then send <math>CT</math> to each component of their device.
# If <math>CT = a</math>:
## Alice and Bob receive strings <math>z^A</math> and <math>z^B</math>, respectively, from the device.
# If <math>CT = b</math>:
## Alice and Bob receive strings <math>d^A</math> and <math>d^B</math>, respectively, from the device.
## Alice chooses uniformly random ''measurement bases (questions)'' <math>x,y \in</math> {'''Computational,Hadamard'''} and sends <math>y</math> to Bob. Alice and Bob then, respectively, send <math>x</math> and <math>y</math> to the device.
## Alice and Bob receive answer bits <math>a</math> and <math>b</math>, respectively, from the device. Alice and Bob also receive bits <math>h^A</math> and <math>h^B</math>, respectively, from the device.

===Protocol 3: DI Rand 1-2 OT<math>^l</math>===
::'''Data generation:'''
# The sender and receiver execute <math>n</math> rounds of '''Protocol 2''' (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
#: If <math>CT_i = b</math>, then with probability <math>p</math>, the receiver does not use the measurement basis question supplied by the sender and instead inputs <math>y_i=[</math>'''Computational, Hadamard'''<math>]_c</math> where <math>c</math> is the receiver's choice bit. Let <math>I</math> be the set of indices marking the rounds where this has been done.
#: For each round <math> i \in \{1,...,n\} </math>, the receiver stores:
#:* <math>c_i^B</math>
#:* <math>z_i^B</math> if <math>CT_i = a</math>
#:* or <math>(d_i^B,y_i,b_i,h_i^B)</math> if <math>CT_i = b</math>
#: The sender stores <math>\theta_i^A,\theta_i^B,(k_i^A,t_i^A),(k_i^B,t_i^B),c_i^A,CT_i;</math> and <math>z_i^A</math> if <math>CT_i = a</math> or <math>(d_i^A,x_i,a_i,h_i^A)</math> and <math>y_i</math> if <math>CT_i = b</math>
# For every <math>i \in \{1,...,n\},</math> the sender stores the variable <math>RT_i</math> (round type), defined as follows:
#* if <math>CT_i = b</math> and <math>\theta_i^A = \theta_i^B = </math>'''Hadamard''', then <math>RT_i =</math> '''Bell'''
#* else, set <math>RT_i = </math> '''Product'''
# For every <math>i \in \{1,...,n\},</math> the sender chooses <math>T_i</math>, indicating a test round or generation round, as follows:
#* if <math>RT_i = </math> '''Bell''', choose <math>T_i \in</math> {'''Test, Generate'''} uniformly at random
#* else, set <math>T_i = </math> '''Test'''
#: The sender sends (<math>T_1,...,T_n</math>) to the receiver
#:
#: '''Testing:'''
# The receiver sends the set of indices <math>I</math> to the sender. The receiver publishes their output for all <math>T_i = </math> '''Test''' rounds where <math>i \notin I</math>. Using this published data, the sender determines the bits which an honest device would have returned.
# The sender computes the fraction of test rounds (for which the receiver has published data for) that failed. If this exceeds some <math>\epsilon</math>, the protocol aborts
#:
#: '''Preparing data:'''
# Let <math>\tilde{I} := \{i : i \in I</math> and <math>T_i = </math> '''Generate'''} and <math>n^{\prime} = |\tilde{I}|</math>. The sender checks if there exists a <math> k > 0 </math> such that <math>\gamma n^{\prime} \leq n^{\prime}/4 - 2l -kn^{\prime}</math>. If such a <math>k</math> exists, the sender publishes <math>\tilde{I}</math> and, for each <math>i \in \tilde{I}</math>, the trapdoor <math>t_i^B</math> corresponding to the key <math>k_i^B</math> (given by the sender in the execution of '''Protocol 2,Step 1'''); otherwise the protocol aborts.

# For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha} = d^A_i.(x_{i,0}^A \oplus x_{i,1}^A)</math> and defines <math>w^{\alpha}</math> by
#:<math>w_i^{\alpha} = \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{Hadamard}\\ 0, \mbox{if } x_i = \mbox{Computational}\end{cases}</math>
#: and the receiver calculates <math>v_i^{\beta} = = d^B_i.(x_{i,0}^B \oplus x_{i,1}^B)</math> and defines <math>w^{\beta}</math> by
#:<math>w_i^{\beta} = \begin{cases} 0, \mbox{if } y_i = \mbox{Hadamard}\\ v_i^{\beta}, \mbox{if } y_i = \mbox{Computational}\end{cases}</math>
#: '''Obtaining output:'''
# The sender randomly picks two hash functions <math>f_0,f_1 \in F</math>, announces <math>f_0,f_1</math> and <math>x_i</math> for each <math>i \in \tilde{I}</math>, and outputs <math>s_0 = f_0(a \oplus w^{\alpha}|_{\tilde{I}_0})</math> and <math>s_1 = f_1(a \oplus w^{\alpha}|_{\tilde{I}_1})</math>, where <math>\tilde{I}_r := \{i \in \tilde{I}: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# Receiver outputs <math>s_c = f_c(a \oplus w^{\beta}|_{\tilde{I}_c})</math>

==Properties==

* <math>\epsilon</math>-'''Receiver security:''' If <math>R</math> is honest, then for any <math>\tilde{S}</math>, there exist random variables <math>S_0^{\prime}, S_1^{\prime}</math> such that Pr[<math>Y = S_c^{\prime}] \geq 1 - \epsilon</math> and <math>D(\rho_{c,S_0^{\prime}, S_1^{\prime},\tilde{S}}, \rho_c \otimes \rho_{S_0^{\prime}, S_1^{\prime},\tilde{S}}) \leq \epsilon</math>
*: Protocol 3 is perfectly receiver secure, i.e. <math>\epsilon</math> = 0
* <math>\epsilon</math>-'''Sender security:''' If S is honest, then for any <math>\tilde{R}</math>, there exist a random variable <math>c^{\prime}</math> such that <math>D(\rho_{S_{1-c^{\prime}},S_{c^{\prime}},c^{\prime},\tilde{R}}, \frac{1}{2^l}I \otimes \rho_{S_{c^{\prime}},c^{\prime},\tilde{R}}) \leq \epsilon</math>
*: Protocol 3 is <math>\epsilon^{\prime}</math>-sender secure, where <math>\epsilon^{\prime}</math> can be made negligible in certain conditions.

==References==
* The protocol and its security proofs can be found in [https://arxiv.org/abs/2111.08595 Broadbent and Yuen(2021)]
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>

Device-Independent Oblivious Transfer

2022-01-22T15:38:20Z

Chirag:

This [https://arxiv.org/abs/2111.08595 example protocol] achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.


==Assumptions==

* The quantum storage of the receiver is bounded during the execution of the protocol
* The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem during the execution of the protocol
* The device behaves in an IID manner - it behaves independently and identically during each round of the protocol

==Outline==

* The protocol consists of multiple rounds, which are randomly chosen for testing or string generation
* The testing rounds are carried out to ensure that the devices used are following the expected behaviour. The self-testing protocol used is a modification of the one used in DIQKD. This modification is necessary as, unlike the DIQKD scenario, the parties involved in OT may not trust each other to cooperate. The self-testing protocol uses the computational assumptions associated with ''Extended noisy trapdoor claw-free'' (ENTCF) function families to certify that the device has created the desired quantum states. If the fraction of failed testing rounds exceeds a certain limit, the protocol is aborted.
* At the end of the protocol, the honest sender outputs two randomly generated strings of equal length, and the honest receiver outputs their chosen string out of the two.

==Notation==

* <math>S</math>: The sender
* <math>R</math>: The receiver
* <math>l</math>: Length of the output strings
* <math>s_0, s_1</math>: The strings output by the sender
* <math>c</math>: A bit denoting the receiver's choice
* For any bit <math>r</math>, ['''Computational, Hadamard''']<math>_r = \begin{cases}\mbox{Computational, if } r = 0\\ \mbox{Hadamard, if } r = 1\end{cases}</math>
* <math>\sigma_X = \begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix} </math>
* <math>\sigma_Z = \begin{pmatrix}1 & 0 \\ 0 & -1 \end{pmatrix} </math>
* For bits <math>v^{\alpha},v^{\beta}: |\phi^{(v^{\alpha},v^{\beta})}\rangle = (\sigma_Z^{v^{\alpha}}\sigma_X^{v^{\beta}} \otimes I) \frac{|00\rangle+|11\rangle}{\sqrt{2}}</math>
* An ENTCF family consists of two families of function pairs: <math>F</math> and <math>G</math>. A function pair <math>(f_{k,0},f_{k,1})</math>is indexed by a public key <math>k</math>. If <math>(f_{k,0},f_{k,1}) \in F</math>, then it is a ''claw-free pair''; and if <math>(f_{k,0},f_{k,1}) \in G</math>, then it is called an ''injective pair''. ENTCF families satisfy the following properties:
*# For a fixed <math>k \in K_F, f_{k,0}</math> and <math>f_{k,1}</math> are bijections with the same image; for every image <math>y</math>, there exists a unique pair <math>(x_0,x_1)</math>, called a ''claw'', such that <math>f_{k,0}(x_0) = f_{k,1}(x_1) = y</math>
*# Given a ''key'' <math>k \in K_F</math>, for a claw-free pair, it is quantum-computationally intractable (without access to ''trapdoor'' information) to compute both a <math>x_i</math> and a single generalized bit of <math>x_0 \oplus x_1</math>, where <math>(x_0,x_1)</math> forms a valid claw. This is known as the ''adaptive hardcore bit'' property.
*# For a fixed <math>k \in K_G, f_{k,0}</math> and <math>f_{k_1}</math> are injunctive functions with disjoint images.
*# Given a key <math>k \in K_F \cup K_G</math>, it is quantum-computationally hard (without access to ''trapdoor'' information) to determine whether <math>k</math> is a key for a claw-free or an injective pair. This property is known as ''injective invariance''.
*# For every <math>k \in K_F \cup K_G</math>, there exists a trapdoor <math>t_k</math> which can be sampled together with <math>k</math> and with which 2 and 4 are computationally easy.




==Protocol Description==

===Protocol 1: Rand 1-2 OT<math>^l</math>===
# A device prepares <math>n</math> uniformly random Bell pairs <math>|\phi^{(v_i^{\alpha},v_i^{\beta})}\rangle, i = 1,...,n</math>, where the first qubit of each pair goes to <math>S</math> along with the string <math>v^{\alpha}</math>, and the second qubit of each pair goes to <math>R</math> along with the string <math>v^{\beta}</math>.
# R measures all qubits in the basis <math>y = [</math>'''Computational,Hadamard'''<math>]_c</math> where <math>c</math> is <math>R</math>'s choice bit. Let <math>b \in \{0,1\}^n</math> be the outcome. <math>R</math> then computes <math>b \oplus w^{\beta}</math>, where the <math>i</math>-th entry of <math>w^{\beta}</math> is defined by
#: <math>w_i^{\beta} := \begin{cases} 0, \mbox{if } y = \mbox{ Hadamard}\\ v_i^{\beta}, \mbox{if } y = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks uniformly random <math>x \in \{</math> '''Computational, Hadamard'''<math>\}^n</math>, and measures the <math>i</math>-th qubit in basis <math>x_i</math>. Let <math>a \in \{0,1\}^n</math> be the outcome. <math>S</math> then computes <math>a \oplus w^{\alpha}</math>, where the <math>i</math>-th entry of <math>w^{\alpha}</math> is defined by
#: <math>w_i^{\alpha} := \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{ Hadamard}\\ 0, \mbox{if } x_i = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks two uniformly random hash functions <math>f_0,f_1 \in F</math>, announces <math>x</math> and <math>f_0,f_1</math> to <math>R</math> and outputs <math>s_0 := f_0(a \oplus w^{\alpha} |_{I_0})</math> and <math>s_1 := f_1(a \oplus w^{\alpha} |_{I_1})</math> where <math>I_r := \{i \in I: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# <math>R</math> outputs <math>s_c = f_c(b \oplus w^{\beta} |_{I_c})</math>

===Protocol 2: Self-testing with a single verifier===
# Alice chooses the state bases <math>\theta^A,\theta^B \in </math> {'''Computational,Hadamard'''} uniformly at random and generates key-trapdoor pairs <math>(k^A,t^A),(k^B,t^B)</math>, where the generation procedure for <math>k^A</math> and <math>t^A</math> depends on <math>\theta^A</math> and a security parameter <math>\eta</math>, and likewise for <math>k^B</math> and <math>t^B</math>. Alice supplies Bob with <math>k^B</math>. Alice and Bob then respectively send <math>k^A, k^B</math> to the device.
# Alice and Bob receive strings <math>c^A</math> and <math>c^B</math>, respectively, from the device.
# Alice chooses a ''challenge type'' <math>CT \in \{a,b\}</math>, uniformly at random and sends it to Bob. Alice and Bob then send <math>CT</math> to each component of their device.
# If <math>CT = a</math>:
## Alice and Bob receive strings <math>z^A</math> and <math>z^B</math>, respectively, from the device.
# If <math>CT = b</math>:
## Alice and Bob receive strings <math>d^A</math> and <math>d^B</math>, respectively, from the device.
## Alice chooses uniformly random ''measurement bases (questions)'' <math>x,y \in</math> {'''Computational,Hadamard'''} and sends <math>y</math> to Bob. Alice and Bob then, respectively, send <math>x</math> and <math>y</math> to the device.
## Alice and Bob receive answer bits <math>a</math> and <math>b</math>, respectively, from the device. Alice and Bob also receive bits <math>h^A</math> and <math>h^B</math>, respectively, from the device.

===Protocol 3: DI Rand 1-2 OT<math>^l</math>===
::'''Data generation:'''
# The sender and receiver execute <math>n</math> rounds of '''Protocol 2''' (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
#: If <math>CT_i = b</math>, then with probability <math>p</math>, the receiver does not use the measurement basis question supplied by the sender and instead inputs <math>y_i=[</math>'''Computational, Hadamard'''<math>]_c</math> where <math>c</math> is the receiver's choice bit. Let <math>I</math> be the set of indices marking the rounds where this has been done.
#: For each round <math> i \in \{1,...,n\} </math>, the receiver stores:
#:* <math>c_i^B</math>
#:* <math>z_i^B</math> if <math>CT_i = a</math>
#:* or <math>(d_i^B,y_i,b_i,h_i^B)</math> if <math>CT_i = b</math>
#: The sender stores <math>\theta_i^A,\theta_i^B,(k_i^A,t_i^A),(k_i^B,t_i^B),c_i^A,CT_i;</math> and <math>z_i^A</math> if <math>CT_i = a</math> or <math>(d_i^A,x_i,a_i,h_i^A)</math> and <math>y_i</math> if <math>CT_i = b</math>
# For every <math>i \in \{1,...,n\},</math> the sender stores the variable <math>RT_i</math> (round type), defined as follows:
#* if <math>CT_i = b</math> and <math>\theta_i^A = \theta_i^B = </math>'''Hadamard''', then <math>RT_i =</math> '''Bell'''
#* else, set <math>RT_i = </math> '''Product'''
# For every <math>i \in \{1,...,n\},</math> the sender chooses <math>T_i</math>, indicating a test round or generation round, as follows:
#* if <math>RT_i = </math> '''Bell''', choose <math>T_i \in</math> {'''Test, Generate'''} uniformly at random
#* else, set <math>T_i = </math> '''Test'''
#: The sender sends (<math>T_1,...,T_n</math>) to the receiver
#:
#: '''Testing:'''
# The receiver sends the set of indices <math>I</math> to the sender. The receiver publishes their output for all <math>T_i = </math> '''Test''' rounds where <math>i \notin I</math>. Using this published data, the sender determines the bits which an honest device would have returned.
# The sender computes the fraction of test rounds (for which the receiver has published data for) that failed. If this exceeds some <math>\epsilon</math>, the protocol aborts
#:
#: '''Preparing data:'''
# Let <math>\tilde{I} := \{i : i \in I</math> and <math>T_i = </math> '''Generate'''} and <math>n^{\prime} = |\tilde{I}|</math>. The sender checks if there exists a <math> k > 0 </math> such that <math>\gamma n^{\prime} \leq n^{\prime}/4 - 2l -kn^{\prime}</math>. If such a <math>k</math> exists, the sender publishes <math>\tilde{I}</math> and, for each <math>i \in \tilde{I}</math>, the trapdoor <math>t_i^B</math> corresponding to the key <math>k_i^B</math> (given by the sender in the execution of '''Protocol 2,Step 1'''); otherwise the protocol aborts.

# For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha} = d^A_i.(x_{i,0}^A \oplus x_{i,1}^A)</math> and defines <math>w^{\alpha}</math> by
#:<math>w_i^{\alpha} = \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{Hadamard}\\ 0, \mbox{if } x_i = \mbox{Computational}\end{cases}</math>
#: and the receiver calculates <math>v_i^{\beta} = = d^B_i.(x_{i,0}^B \oplus x_{i,1}^B)</math> and defines <math>w^{\beta}</math> by
#:<math>w_i^{\beta} = \begin{cases} 0, \mbox{if } y_i = \mbox{Hadamard}\\ v_i^{\beta}, \mbox{if } y_i = \mbox{Computational}\end{cases}</math>
#: '''Obtaining output:'''
# The sender randomly picks two hash functions <math>f_0,f_1 \in F</math>, announces <math>f_0,f_1</math> and <math>x_i</math> for each <math>i \in \tilde{I}</math>, and outputs <math>s_0 = f_0(a \oplus w^{\alpha}|_{\tilde{I}_0})</math> and <math>s_1 = f_1(a \oplus w^{\alpha}|_{\tilde{I}_1})</math>, where <math>\tilde{I}_r := \{i \in \tilde{I}: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# Receiver outputs <math>s_c = f_c(a \oplus w^{\beta}|_{\tilde{I}_c})</math>

==Properties==


==Further Information==


==References==

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

Device-Independent Oblivious Transfer

2022-01-22T15:35:24Z

Chirag: Added outline and notation

This [https://arxiv.org/abs/2111.08595 example protocol] achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.


==Assumptions==

* The quantum storage of the receiver is bounded during the execution of the protocol
* The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem during the execution of the protocol
* The device behaves in an IID manner - it behaves independently and identically during each round of the protocol

==Outline==

* The protocol consists of multiple rounds, which are randomly chosen for testing or string generation
* The testing rounds are carried out to ensure that the devices used are following the expected behaviour. The self-testing protocol used is a modification of the one used in DIQKD. This modification is necessary as, unlike the DIQKD scenario, the parties involved in OT may not trust each other to cooperate. The self-testing protocol uses the computational assumptions associated with ''Extended noisy trapdoor claw-free'' (ENTCF) function families to certify that the device has created the desired quantum states. If the fraction of failed testing rounds exceeds a certain limit, the protocol is aborted.
* Following the generation rounds, the honest sender outputs two randomly generated strings of equal length, and the honest receiver outputs their chosen string out of the two.

==Notation==

* <math>S</math>: The sender
* <math>R</math>: The receiver
* <math>l</math>: Length of the output strings
* <math>s_0, s_1</math>: The strings output by the sender
* <math>c</math>: A bit denoting the receiver's choice
* For any bit <math>r</math>, ['''Computational, Hadamard''']<math>_r = \begin{cases}\mbox{Computational, if } r = 0\\ \mbox{Hadamard, if } r = 1\end{cases}</math>

* <math>\sigma_Z = \begin{pmatrix}1 & 0 \\ 0 & -1 \end{pmatrix} </math>
* For bits <math>v^{\alpha},v^{\beta}: |\phi^{(v^{\alpha},v^{\beta})}\rangle = (\sigma_Z^{v^{\alpha}}\sigma_X^{v^{\beta}} \otimes I) \frac{|00\rangle+|11\rangle}{\sqrt{2}}</math>
* An ENTCF family consists of two families of function pairs: <math>F</math> and <math>G</math>. A function pair <math>(f_{k,0},f_{k,1})</math>is indexed by a public key <math>k</math>. If <math>(f_{k,0},f_{k,1}) \in F</math>, then it is a ''claw-free pair''; and if <math>(f_{k,0},f_{k,1}) \in G</math>, then it is called an ''injective pair''. ENTCF families satisfy the following properties:
*# For a fixed <math>k \in K_F, f_{k,0}</math> and <math>f_{k,1}</math> are bijections with the same image; for every image <math>y</math>, there exists a unique pair <math>(x_0,x_1)</math>, called a ''claw'', such that <math>f_{k,0}(x_0) = f_{k,1}(x_1) = y</math>
*# Given a ''key'' <math>k \in K_F</math>, for a claw-free pair, it is quantum-computationally intractable (without access to ''trapdoor'' information) to compute both a <math>x_i</math> and a single generalized bit of <math>x_0 \oplus x_1</math>, where <math>(x_0,x_1)</math> forms a valid claw. This is known as the ''adaptive hardcore bit'' property.
*# For a fixed <math>k \in K_G, f_{k,0}</math> and <math>f_{k_1}</math> are injunctive functions with disjoint images.
*# Given a key <math>k \in K_F \cup K_G</math>, it is quantum-computationally hard (without access to ''trapdoor'' information) to determine whether <math>k</math> is a key for a claw-free or an injective pair. This property is known as ''injective invariance''.
*# For every <math>k \in K_F \cup K_G</math>, there exists a trapdoor <math>t_k</math> which can be sampled together with <math>k</math> and with which 2 and 4 are computationally easy.




==Protocol Description==

===Protocol 1: Rand 1-2 OT<math>^l</math>===
# A device prepares <math>n</math> uniformly random Bell pairs <math>|\phi^{(v_i^{\alpha},v_i^{\beta})}\rangle, i = 1,...,n</math>, where the first qubit of each pair goes to <math>S</math> along with the string <math>v^{\alpha}</math>, and the second qubit of each pair goes to <math>R</math> along with the string <math>v^{\beta}</math>.
# R measures all qubits in the basis <math>y = [</math>'''Computational,Hadamard'''<math>]_c</math> where <math>c</math> is <math>R</math>'s choice bit. Let <math>b \in \{0,1\}^n</math> be the outcome. <math>R</math> then computes <math>b \oplus w^{\beta}</math>, where the <math>i</math>-th entry of <math>w^{\beta}</math> is defined by
#: <math>w_i^{\beta} := \begin{cases} 0, \mbox{if } y = \mbox{ Hadamard}\\ v_i^{\beta}, \mbox{if } y = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks uniformly random <math>x \in \{</math> '''Computational, Hadamard'''<math>\}^n</math>, and measures the <math>i</math>-th qubit in basis <math>x_i</math>. Let <math>a \in \{0,1\}^n</math> be the outcome. <math>S</math> then computes <math>a \oplus w^{\alpha}</math>, where the <math>i</math>-th entry of <math>w^{\alpha}</math> is defined by
#: <math>w_i^{\alpha} := \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{ Hadamard}\\ 0, \mbox{if } x_i = \mbox{ Computational}\end{cases}</math>
# <math>S</math> picks two uniformly random hash functions <math>f_0,f_1 \in F</math>, announces <math>x</math> and <math>f_0,f_1</math> to <math>R</math> and outputs <math>s_0 := f_0(a \oplus w^{\alpha} |_{I_0})</math> and <math>s_1 := f_1(a \oplus w^{\alpha} |_{I_1})</math> where <math>I_r := \{i \in I: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# <math>R</math> outputs <math>s_c = f_c(b \oplus w^{\beta} |_{I_c})</math>

===Protocol 2: Self-testing with a single verifier===
# Alice chooses the state bases <math>\theta^A,\theta^B \in </math> {'''Computational,Hadamard'''} uniformly at random and generates key-trapdoor pairs <math>(k^A,t^A),(k^B,t^B)</math>, where the generation procedure for <math>k^A</math> and <math>t^A</math> depends on <math>\theta^A</math> and a security parameter <math>\eta</math>, and likewise for <math>k^B</math> and <math>t^B</math>. Alice supplies Bob with <math>k^B</math>. Alice and Bob then respectively send <math>k^A, k^B</math> to the device.
# Alice and Bob receive strings <math>c^A</math> and <math>c^B</math>, respectively, from the device.
# Alice chooses a ''challenge type'' <math>CT \in \{a,b\}</math>, uniformly at random and sends it to Bob. Alice and Bob then send <math>CT</math> to each component of their device.
# If <math>CT = a</math>:
## Alice and Bob receive strings <math>z^A</math> and <math>z^B</math>, respectively, from the device.
# If <math>CT = b</math>:
## Alice and Bob receive strings <math>d^A</math> and <math>d^B</math>, respectively, from the device.
## Alice chooses uniformly random ''measurement bases (questions)'' <math>x,y \in</math> {'''Computational,Hadamard'''} and sends <math>y</math> to Bob. Alice and Bob then, respectively, send <math>x</math> and <math>y</math> to the device.
## Alice and Bob receive answer bits <math>a</math> and <math>b</math>, respectively, from the device. Alice and Bob also receive bits <math>h^A</math> and <math>h^B</math>, respectively, from the device.

===Protocol 3: DI Rand 1-2 OT<math>^l</math>===
::'''Data generation:'''
# The sender and receiver execute <math>n</math> rounds of '''Protocol 2''' (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
#: If <math>CT_i = b</math>, then with probability <math>p</math>, the receiver does not use the measurement basis question supplied by the sender and instead inputs <math>y_i=[</math>'''Computational, Hadamard'''<math>]_c</math> where <math>c</math> is the receiver's choice bit. Let <math>I</math> be the set of indices marking the rounds where this has been done.
#: For each round <math> i \in \{1,...,n\} </math>, the receiver stores:
#:* <math>c_i^B</math>
#:* <math>z_i^B</math> if <math>CT_i = a</math>
#:* or <math>(d_i^B,y_i,b_i,h_i^B)</math> if <math>CT_i = b</math>
#: The sender stores <math>\theta_i^A,\theta_i^B,(k_i^A,t_i^A),(k_i^B,t_i^B),c_i^A,CT_i;</math> and <math>z_i^A</math> if <math>CT_i = a</math> or <math>(d_i^A,x_i,a_i,h_i^A)</math> and <math>y_i</math> if <math>CT_i = b</math>
# For every <math>i \in \{1,...,n\},</math> the sender stores the variable <math>RT_i</math> (round type), defined as follows:
#* if <math>CT_i = b</math> and <math>\theta_i^A = \theta_i^B = </math>'''Hadamard''', then <math>RT_i =</math> '''Bell'''
#* else, set <math>RT_i = </math> '''Product'''
# For every <math>i \in \{1,...,n\},</math> the sender chooses <math>T_i</math>, indicating a test round or generation round, as follows:
#* if <math>RT_i = </math> '''Bell''', choose <math>T_i \in</math> {'''Test, Generate'''} uniformly at random
#* else, set <math>T_i = </math> '''Test'''
#: The sender sends (<math>T_1,...,T_n</math>) to the receiver
#:
#: '''Testing:'''
# The receiver sends the set of indices <math>I</math> to the sender. The receiver publishes their output for all <math>T_i = </math> '''Test''' rounds where <math>i \notin I</math>. Using this published data, the sender determines the bits which an honest device would have returned.
# The sender computes the fraction of test rounds (for which the receiver has published data for) that failed. If this exceeds some <math>\epsilon</math>, the protocol aborts
#:
#: '''Preparing data:'''
# Let <math>\tilde{I} := \{i : i \in I</math> and <math>T_i = </math> '''Generate'''} and <math>n^{\prime} = |\tilde{I}|</math>. The sender checks if there exists a <math> k > 0 </math> such that <math>\gamma n^{\prime} \leq n^{\prime}/4 - 2l -kn^{\prime}</math>. If such a <math>k</math> exists, the sender publishes <math>\tilde{I}</math> and, for each <math>i \in \tilde{I}</math>, the trapdoor <math>t_i^B</math> corresponding to the key <math>k_i^B</math> (given by the sender in the execution of '''Protocol 2,Step 1'''); otherwise the protocol aborts.

# For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha} = d^A_i.(x_{i,0}^A \oplus x_{i,1}^A)</math> and defines <math>w^{\alpha}</math> by
#:<math>w_i^{\alpha} = \begin{cases} v_i^{\alpha}, \mbox{if } x_i = \mbox{Hadamard}\\ 0, \mbox{if } x_i = \mbox{Computational}\end{cases}</math>
#: and the receiver calculates <math>v_i^{\beta} = = d^B_i.(x_{i,0}^B \oplus x_{i,1}^B)</math> and defines <math>w^{\beta}</math> by
#:<math>w_i^{\beta} = \begin{cases} 0, \mbox{if } y_i = \mbox{Hadamard}\\ v_i^{\beta}, \mbox{if } y_i = \mbox{Computational}\end{cases}</math>
#: '''Obtaining output:'''
# The sender randomly picks two hash functions <math>f_0,f_1 \in F</math>, announces <math>f_0,f_1</math> and <math>x_i</math> for each <math>i \in \tilde{I}</math>, and outputs <math>s_0 = f_0(a \oplus w^{\alpha}|_{\tilde{I}_0})</math> and <math>s_1 = f_1(a \oplus w^{\alpha}|_{\tilde{I}_1})</math>, where <math>\tilde{I}_r := \{i \in \tilde{I}: x_i = [</math>'''Computational,Hadamard'''<math>]_r\}</math>
# Receiver outputs <math>s_c = f_c(a \oplus w^{\beta}|_{\tilde{I}_c})</math>

==Properties==


==Further Information==


==References==

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

Device-Independent Oblivious Transfer

2022-01-20T16:19:27Z

Chirag:

Protocol Library

2022-01-19T19:13:53Z

Chirag: Added Conference Key Agreement functionality and protocol

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="5"|[[Authentication of Quantum Messages]]||[[Purity Testing based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
|[[Clifford Code for Quantum Authentication]]
|-
|[[Trap Code for Quantum Authentication]]
|-
|[[Naive approach using Quantum Teleportation]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|rowspan="4"|[[Verification of Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of NP-complete problems]]
|-
|[[Verification of Sub-Universal Quantum Computation]]
|-
|[[Classical Verification of Universal Quantum Computation]]
|-
|rowspan="5"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
|[[Practical Quantum Electronic Voting]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="3"|[[Entanglement Routing]]||[[Routing Entanglement in the Quantum Internet]]
|-
|[[Distributed Routing in a Quantum Internet]]
|-
|[[Distributing Graph States Over Arbitrary Quantum Networks]]
|-
|rowspan="1"|[[Quantum Conference Key Agreement]]||[[Anonymous Conference Key Agreement using GHZ states]]
|-

Quantum Conference Key Agreement

2022-01-19T19:08:40Z

Chirag: Added Protocols section

==Functionality==
Conference key agreement (CKA), or multipartite key distribution is a cryptographic task where more than two parties wish to establish a common secret key. It is possible to compose bipartite QKD protocols to accomplish this task. However, protocols based on multipartite quantum correlations may be more efficient and practical in future large scale quantum networks.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party Protocols]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category: Specific Task|Specific Task]]


==Properties==

An ideal CKA protocol, with <math>N</math> users, Alice, Bob<math>_1</math>, Bob<math>_2</math>, ..., Bob<math>_{N-1}</math> should have the following properties:

* '''Correctness:''' A CKA protocol is said to be ''correct'' if all parties receive the same key at the end of the protocol with high probability.
: Formally, a CKA protocol is <math>\epsilon_{corr}</math>-correct if:
:: <math>p(K_A = K_{B_1} = ... = K_{B_{N-1}}) \geq 1 - \epsilon_{corr}</math>
: where <math>K_A, K_{B_i}</math> are the final keys held by Alice and Bob<math>_i</math>, and <math>p(K_A = K_{B_1} = ... = K_{B_{N-1}})</math> is the probability that all final keys are identical.
* '''Secrecy:''' A CKA protocol is said to be ''secret'' if an eavesdropper Eve cannot differentiate between the key established and a random bitstring.
: Formally, a CKA protocol is <math>\epsilon_{sec}</math>-secret if, for <math>\Omega</math> being the event that the protocol does not abort,
:: <math>p(\Omega)\frac{1}{2}||\rho_{K_AE|\Omega} - \tau_{K_A}\otimes\rho_{E|\Omega}|| \leq \epsilon_{sec}</math>,
: where <math>p(\Omega)</math> is the probability of the event <math>\Omega</math>, <math>\rho_{K_AE|\Omega}</math> is the state shared by Alice and Eve at the end of the protocol given the event <math>\Omega</math>, <math>\tau_{K_A} = \frac{1}{|S|}\sum_{s_i \in S} |s_i\rangle \langle s_i|</math> is the maximally mixed state over all possible values that the key <math>K_A</math> can assume, and <math>S = \{0,1\}^{\times l}</math> where <math>l</math> is the length of the key <math>K_A</math>.
* '''Completeness:''' A quantum CKA protocol is <math>\epsilon_c</math>-complete if there exists an honest implementation of the protocols, such that the probability of not aborting is greater than <math>1-\epsilon_c</math>.
==Generic Protocol Structure==
* '''Preparation and distribution:''' A source distributes a multipartite entangled state to the <math>N</math> parties. This step is repeated <math>n</math>
* '''Measurements:''' Upon receiving the systems, the parties perform local measurements and record the classical outcome. The measurements are randomly chosen according to the specifications of the protocol. One of the possible measurement settings is used with higher probability and is called the <u>key generation</u> measurements. The other measurements are used for <u>test rounds</u>, which only occasionally occur.
* '''Parameter estimation:''' The parties announce the inputs and outputs of their test rounds and of some randomly chosen key generation rounds which are used to estimate their correlation and the potential influence of an eavesdropper. At the end of this step, each party is left with a string of <math>n_{raw} < n</math> bits, which constitute their <u>raw key</u>.
* '''Information reconciliation (error correction):''' The parties publicly exchange classical information in order for the Bobs to correct their raw keys to match Alice's string. In the multipartite case, the information reconciliation protocol needs to account for the correction of the strings of all the Bobs.
* '''Privacy amplification:''' Alice randomly picks a hash function, chosen among a two-universal family of hash functions, and communicates it to the Bobs. Every party applies the hash function to turn her/his partially secure string of <math>n_{raw}</math> bits into a secure key of <math> l < n_{raw}</math> bits.

==Protocols==
* [[Prepare-and-measure Conference Key Agreement]]
* [[Anonymous Conference Key Agreement using GHZ states]]
* [[W-State based Conference Key Agreement]]
* [[Continuous Variable Conference Key Agreement]]
* [[Device Independent Conference Key Agreement]]


==References==
* [https://arxiv.org/abs/2003.10186 Murta et al.(2020)] discusses the properties of the functionality and provides various example protocols

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

Anonymous Conference Key Agreement using GHZ states

2022-01-19T18:45:29Z

Chirag: Fixed section name

This [https://arxiv.org/abs/2007.07995 example protocol] achieves the functionality of quantum conference key agreement. This protocol allows multiple parties in a quantum network to establish a shared secret key anonymously.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party Protocols]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category: Specific Task|Specific Task]]

==Requirements==

We require the following resources for this protocol:
# A source of n-party GHZ states
# Private randomness sources
# A randomness source that is not associated with any party
# A classical broadcasting channel
# Pairwise private communication channels

==Outline==

* First, the sender notifies each receiver in the network anonymously
* The entanglement source generates and distributes sufficient GHZ states to all nodes in the network
* The GHZ states are distilled to establish multipartite entanglement shared only by the participating parties (the sender and receivers)
* Each GHZ state is randomly chosen to be used for either Verification or Key Generation. For Key Generation rounds, a single bit of the key is established using one GHZ state by measuring in the Z-basis
* If the sender is content with the Verification results, they can anonymously validate the protocol and conclude that the key has been established successfully.

==Notation==

*<math>n</math>: Total number of nodes in the network

*<math>m</math>: Number of receiving nodes

*<math>L</math>: Number of GHZ states used

*<math>D</math>: Security parameter; expected number of GHZ states used to establish one bit of key

*<math>k</math>-partite GHZ state: <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes k} + |1\rangle^{\otimes k})</math>




==Protocol Description==

===Protocol 1: Anonymous Verifiable Conference Key Agreement===
''Input'': Parameters <math>L</math> and <math>D</math>

''Requirements'': A source of n-party GHZ states; private randomness sources; a randomness source that is not associated with any party; a classical broadcasting channel; pairwise private communication channels

''Goal'': Anonymoous generation of key between sender and <math>m</math> receivers

# The sender notifies the <math>m</math> receivers by running the ''Notification'' protocol
# The source generates and shares <math>L</math> GHZ states
# The parties run the ''Anonymous Multipartite Entanglement'' protocol on the GHZ states
# For each <math>(m+1)</math>-partite GHZ state, the parties do the following:
#* They ask a source of randomness to broadcast a bit <math>b</math> such that Pr<math>[b=1] = \frac{1}{D}</math>
#* '''Verification round: '''If b = 0, the sender runs ''Verification'' as verifier on the state corresponding to that round, while only considering the announcements of the <math>m</math> receivers. The remaining parties announce random values.
#* '''KeyGen round: '''If b = 1, the sender and receivers measure in the Z-basis.
# If the sender is content with the checks of the ''Verification'' protocol, they can anonymously validate the protocol

===Protocol 2: Notification===
''Input: '' Sender's choice of <math>m</math> receivers

''Goal: '' The <math>m</math> receivers get notified

''Requirements: '' Private pairwise classical communication channels and randomness sources

For agent <math>i = 1,...,n</math>:
# All agents <math>j \in \{1,...,n\}</math> do the following:
#* '''When agent <math>j</math> is the sender''': If <math>i</math> is not a receiver, the sender chooses <math>n</math> random bits <math>\{r_{j,k}^i\}_{k = 1}^n</math> such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 0</math>. Otherwise, if <math>i</math> is a receiver, the sender chooses <math>n</math> random bits such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 1</math>. The sender sends bit <math>r_{j,k}^i</math> to agent <math>k</math>
#* '''When agent <math>j</math> is not the sender''': The agent chooses <math>n</math> random bits <math>\{r_{j,k}^i\}_{k = 1}^n</math> such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 0</math> and sends bit <math>r_{j,k}^i</math> to agent <math>k</math>
# All agents <math>k \in \{1,...,n\}</math> receive <math>\{r_{j,k}^i\}_{j = 1}^n</math>, and compute <math>z_k^i = \bigoplus_{j=1}^n r_{j,k}^i</math> and send it to agent <math>i</math>
# Agent <math>i</math> takes the received <math>\{z_k^i\}_{k=1}^n</math> to compute <math>z^i = \bigoplus_{k=1}^nz_k^i</math>. If <math>z^i = 1</math>, they are thereby notified to be a designated receiver.

===Protocol 3: Anonymous Multiparty Entanglement===
''Input: '' <math>n</math>-partite GHZ state <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes n} + |1\rangle^{\otimes n})</math>

''Output: '' <math>(m+1)</math>-partite GHZ state <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes (m+1)} + |1\rangle^{\otimes (m+1)})</math> shared between the sender and receivers

''Requirements: '' A broadcast channel; private randomness sources

# Sender and receivers draw a random bit each. Everyone else measures their qubits in the X-basis, yielding a measurement outcome bit <math>x_i</math>
# All parties broadcast their bits in a random order, or if possible, simultaneously.
# The sender applies a Z gate to their qubit if the parity of the non-participating parties' bits is odd.

===Protocol 4: Verification===

''Input: '' A verifier V; a shared state between <math>k</math> parties

''Goal: '' Verification or rejection of the shared state as the GHZ<math>_k</math> state by V

''Requirements: '' Private randomness sources; a classical broadcasting channel

# Everyone but V draws a random bit <math>b_i</math> and measures in the X or Y basis if their bit equals 0 or 1 respectively, obtaining a measurement outcome <math>m_i</math>. V chooses both bits at random
# Everyone (including V) broadcasts <math>(b_i,m_i)</math>
# V resets her bit such that <math>\sum_ib_i = 0 (</math>mod <math>2)</math>. She measures in the X or Y basis if her bit equals 0 or 1 respectively, thereby also resetting her <math>m_i = m_v</math>
# V accepts the state if and only if <math>\sum_im_i = \frac{1}{2}\sum_ib_i (</math>mod <math>2)</math>

==Properties==

* Protocol 1 has an asymptotic key rate of <math>\frac{L}{D}</math>
* This protocol satisfies the following notions of anonymity:
** '''Sender Anonymity''': A protocol allows a sender to remain anonymous sending a message to <math>m</math> receivers, if an adversary who corrupts <math>t \leq n-2 </math> players, cannot guess the identity of the sender with probability higher than <math> \frac{1}{n-t}</math>
** '''Receiver Anonymity''': A protocol allows a receiver to remain anonymous receiving a message, if an adversary who corrupts <math>t \leq n-2 </math> players, cannot guess the identity of the receiver with probability higher than <math> \frac{1}{n-t}</math>
* Error correction and privacy amplification must be carried out anonymously and are not considered in the analysis of this protocol.

==References==
* The protocols and their security analysis, along with an experimental implementation for <math>n = 4</math> can be found in [https://arxiv.org/abs/2007.07995 Hahn et al.(2020)]
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>

Quantum Conference Key Agreement

2022-01-19T17:59:26Z

Chirag: Created functionality page for CKA

==Functionality==
Conference key agreement (CKA), or multipartite key distribution is a cryptographic task where more than two parties wish to establish a common secret key. It is possible to compose bipartite QKD protocols to accomplish this task. However, protocols based on multipartite quantum correlations may be more efficient and practical in future large scale quantum networks.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party Protocols]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category: Specific Task|Specific Task]]


==Properties==

An ideal CKA protocol, with <math>N</math> users, Alice, Bob<math>_1</math>, Bob<math>_2</math>, ..., Bob<math>_{N-1}</math> should have the following properties:

* '''Correctness:''' A CKA protocol is <math>\epsilon_{corr}</math>-correct if:
*: <math>p(K_A = K_{B_1} = ... = K_{B_{N-1}}) \geq 1 - \epsilon_{corr}</math>
: where <math>K_A, K_{B_i}</math> are the final keys held by Alice and Bob<math>_i</math>, and <math>p(K_A = K_{B_1} = ... = K_{B_{N-1}})</math> is the probability that all final keys are identical.
* '''Secrecy:''' A CKA protocol is <math>\epsilon_{sec}</math>-secret if, for <math>\Omega</math> being the event that the protocol does not abort,
*: <math>p(\Omega)\frac{1}{2}||\rho_{K_AE|\Omega} - \tau_{K_A}\otimes\rho_{E|\Omega}|| \leq \epsilon_{sec}</math>,
: where <math>p(\Omega)</math> is the probability of the event <math>\Omega</math>, <math>\rho_{K_AE|\Omega}</math> is the state shared by Alice and Eve at the end of the protocol given the event <math>\Omega</math>, <math>\tau_{K_A} = \frac{1}{|S|}\sum_{s_i \in S} |s_i\rangle \langle s_i|</math> is the maximally mixed state over all possible values that the key <math>K_A</math> can assume, and <math>S = \{0,1\}^{\times l}</math> where <math>l</math> is the length of the key <math>K_A</math>.
* '''Completeness:''' A quantum CKA protocol is <math>\epsilon_c</math>-complete if there exists an honest implementation of the protocols, such that the probability of not aborting is greater than <math>1-\epsilon_c</math>.
==Generic Protocol Structure==
* '''Preparation and distribution:''' A source distributes a multipartite entangled state to the <math>N</math> parties. This step is repeated <math>n</math>
* '''Measurements:''' Upon receiving the systems, the parties perform local measurements and record the classical outcome. The measurements are randomly chosen according to the specifications of the protocol. One of the possible measurement settings is used with higher probability and is called the <u>key generation</u> measurements. The other measurements are used for <u>test rounds</u>, which only occasionally occur.
* '''Parameter estimation:''' The parties announce the inputs and outputs of their test rounds and of some randomly chosen key generation rounds which are used to estimate their correlation and the potential influence of an eavesdropper. At the end of this step, each party is left with a string of <math>n_{raw} < n</math> bits, which constitute their <u>raw key</u>.
* '''Information reconciliation (error correction):''' The parties publicly exchange classical information in order for the Bobs to correct their raw keys to match Alice's string. In the multipartite case, the information reconciliation protocol needs to account for the correction of the strings of all the Bobs.
* '''Privacy amplification:''' Alice randomly picks a hash function, chosen among a two-universal family of hash functions, and communicates it to the Bobs. Every party applies the hash function to turn her/his partially secure string of <math>n_{raw}</math> bits into a secure key of <math> l < n_{raw}</math> bits.



==References==
* [https://arxiv.org/abs/2003.10186 Murta et al.(2020)] discusses the properties of the functionality and provides various example protocols

Device-Independent Oblivious Transfer

2022-01-16T14:21:18Z

Chirag: Created page for DIOT

Anonymous Conference Key Agreement using GHZ states

2022-01-11T19:33:42Z

Chirag: Created page for Anonymous QCKA

This [https://arxiv.org/abs/2007.07995 example protocol] achieves the functionality of quantum conference key agreement. This protocol allows multiple parties in a quantum network to establish a shared secret key anonymously.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party Protocols]], [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]], [[:Category: Specific Task|Specific Task]]

==Assumptions==

We require the following resources for this protocol:
# A source of n-party GHZ states
# Private randomness sources
# A randomness source that is not associated with any party
# A classical broadcasting channel
# Pairwise private communication channels

==Outline==

* First, the sender notifies each receiver in the network anonymously
* The entanglement source generates and distributes sufficient GHZ states to all nodes in the network
* The GHZ states are distilled to establish multipartite entanglement shared only by the participating parties (the sender and receivers)
* Each GHZ state is randomly chosen to be used for either Verification or Key Generation. For Key Generation rounds, a single bit of the key is established using one GHZ state by measuring in the Z-basis
* If the sender is content with the Verification results, they can anonymously validate the protocol and conclude that the key has been established successfully.

==Notation==

*<math>n</math>: Total number of nodes in the network

*<math>m</math>: Number of receiving nodes

*<math>L</math>: Number of GHZ states used

*<math>D</math>: Security parameter; expected number of GHZ states used to establish one bit of key

*<math>k</math>-partite GHZ state: <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes k} + |1\rangle^{\otimes k})</math>




==Protocol Description==

===Protocol 1: Anonymous Verifiable Conference Key Agreement===
''Input'': Parameters <math>L</math> and <math>D</math>

''Requirements'': A source of n-party GHZ states; private randomness sources; a randomness source that is not associated with any party; a classical broadcasting channel; pairwise private communication channels

''Goal'': Anonymoous generation of key between sender and <math>m</math> receivers

# The sender notifies the <math>m</math> receivers by running the ''Notification'' protocol
# The source generates and shares <math>L</math> GHZ states
# The parties run the ''Anonymous Multipartite Entanglement'' protocol on the GHZ states
# For each <math>(m+1)</math>-partite GHZ state, the parties do the following:
#* They ask a source of randomness to broadcast a bit <math>b</math> such that Pr<math>[b=1] = \frac{1}{D}</math>
#* '''Verification round: '''If b = 0, the sender runs ''Verification'' as verifier on the state corresponding to that round, while only considering the announcements of the <math>m</math> receivers. The remaining parties announce random values.
#* '''KeyGen round: '''If b = 1, the sender and receivers measure in the Z-basis.
# If the sender is content with the checks of the ''Verification'' protocol, they can anonymously validate the protocol

===Protocol 2: Notification===
''Input: '' Sender's choice of <math>m</math> receivers

''Goal: '' The <math>m</math> receivers get notified

''Requirements: '' Private pairwise classical communication channels and randomness sources

For agent <math>i = 1,...,n</math>:
# All agents <math>j \in \{1,...,n\}</math> do the following:
#* '''When agent <math>j</math> is the sender''': If <math>i</math> is not a receiver, the sender chooses <math>n</math> random bits <math>\{r_{j,k}^i\}_{k = 1}^n</math> such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 0</math>. Otherwise, if <math>i</math> is a receiver, the sender chooses <math>n</math> random bits such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 1</math>. The sender sends bit <math>r_{j,k}^i</math> to agent <math>k</math>
#* '''When agent <math>j</math> is not the sender''': The agent chooses <math>n</math> random bits <math>\{r_{j,k}^i\}_{k = 1}^n</math> such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 0</math> and sends bit <math>r_{j,k}^i</math> to agent <math>k</math>
# All agents <math>k \in \{1,...,n\}</math> receive <math>\{r_{j,k}^i\}_{j = 1}^n</math>, and compute <math>z_k^i = \bigoplus_{j=1}^n r_{j,k}^i</math> and send it to agent <math>i</math>
# Agent <math>i</math> takes the received <math>\{z_k^i\}_{k=1}^n</math> to compute <math>z^i = \bigoplus_{k=1}^nz_k^i</math>. If <math>z^i = 1</math>, they are thereby notified to be a designated receiver.

===Protocol 3: Anonymous Multiparty Entanglement===
''Input: '' <math>n</math>-partite GHZ state <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes n} + |1\rangle^{\otimes n})</math>

''Output: '' <math>(m+1)</math>-partite GHZ state <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes (m+1)} + |1\rangle^{\otimes (m+1)})</math> shared between the sender and receivers

''Requirements: '' A broadcast channel; private randomness sources

# Sender and receivers draw a random bit each. Everyone else measures their qubits in the X-basis, yielding a measurement outcome bit <math>x_i</math>
# All parties broadcast their bits in a random order, or if possible, simultaneously.
# The sender applies a Z gate to their qubit if the parity of the non-participating parties' bits is odd.

===Protocol 4: Verification===

''Input: '' A verifier V; a shared state between <math>k</math> parties

''Goal: '' Verification or rejection of the shared state as the GHZ<math>_k</math> state by V

''Requirements: '' Private randomness sources; a classical broadcasting channel

# Everyone but V draws a random bit <math>b_i</math> and measures in the X or Y basis if their bit equals 0 or 1 respectively, obtaining a measurement outcome <math>m_i</math>. V chooses both bits at random
# Everyone (including V) broadcasts <math>(b_i,m_i)</math>
# V resets her bit such that <math>\sum_ib_i = 0 (</math>mod <math>2)</math>. She measures in the X or Y basis if her bit equals 0 or 1 respectively, thereby also resetting her <math>m_i = m_v</math>
# V accepts the state if and only if <math>\sum_im_i = \frac{1}{2}\sum_ib_i (</math>mod <math>2)</math>

==Properties==

* Protocol 1 has an asymptotic key rate of <math>\frac{L}{D}</math>
* This protocol satisfies the following notions of anonymity:
** '''Sender Anonymity''': A protocol allows a sender to remain anonymous sending a message to <math>m</math> receivers, if an adversary who corrupts <math>t \leq n-2 </math> players, cannot guess the identity of the sender with probability higher than <math> \frac{1}{n-t}</math>
** '''Receiver Anonymity''': A protocol allows a receiver to remain anonymous receiving a message, if an adversary who corrupts <math>t \leq n-2 </math> players, cannot guess the identity of the receiver with probability higher than <math> \frac{1}{n-t}</math>
* Error correction and privacy amplification must be carried out anonymously and are not considered in the analysis of this protocol.

==References==
* The protocols and their security analysis, along with an experimental implementation for <math>n = 4</math> can be found in [https://arxiv.org/abs/2007.07995 Hahn et al.(2020)]

Copy Protection of Compute and Compare Programs

2022-01-11T17:56:08Z

Chirag: /* Properties */

The [https://arxiv.org/abs/2009.13865 example protocol] achieves the functionality of [[Copy Protection| Copy Protection]] allowing a Vendor to send a program to a Client such that the Client cannot duplicate it. This protocol, in particular, achieves copy-protection for 'compute-and-compare' programs.<br/><br/>

'''Tags:''' [[:Category:Two Party Protocols|Two Party Protocols]], [[:Category:Quantum Functionality|Quantum Functionality]], [[:Category:Universal Task|Universal Task]], Computational Security

==Assumptions==

* Vendor and Client are connected by quantum and classical channels
* Vendor can create and transmit BB84 states
* Client has the capability to perform universal quantum computation

==Outline==

Any Copy Protection protocol consists of two algorithms: '''Protect''' and '''Eval'''. For the family of compute-and-compare programs, these algorithms are described as follows:
*'''Protect''': The Vendor encodes the required qubits into BB84 states using the program description. The Vendor then calculates the output of some hash function on the program description as input. The encoded qubits and the hashed description are sent to the Client as output.
*'''Eval''': The Client decrypts the received qubits using the input on which they wish to evaluate the program. Using these qubits as inputs, the Client computes the same hash function (on ancillary qubits) and coherently compares it with the hashed description received from the vendor. The Client finally measures and outputs the result of the comparison.

==Notation==

* <math>P_y</math> : The point function to be copy-protected in [[#Protocol 1 - Copy protection of point functions|Protocol 1]]. <math>P_y</math> is completely specified by a string of <math>n</math> bits, <math>y</math>. <math>P_y(x) = 1</math> if <math>x = y</math> and <math>0</math> otherwise
* <math>CC[f,y]</math> : The compute-and-compare program to be copy-protected in [[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]]. It is completely specified by an efficiently computable function <math>f: \{0,1\}^n \rightarrow \{0,1\}^m</math> and a string of <math>m</math> bits, <math>y</math>. <math>CC[f,y](x)</math> is <math>1</math> if <math>f(x) = y</math> and <math>0</math> otherwise.
* <math>n</math> : Size of input string <math>x</math>
* <math>\lambda</math>: Security parameter
* <math>G : \{0,1\}^n \rightarrow \{0,1\}^{m(\lambda)} </math> (Hash function)
* <math>H : \{0,1\}^{m(\lambda)} \rightarrow \{0,1\}^\lambda </math> (Hash function)
* <math>|x^\theta\rangle = H^\theta |x\rangle = H^{\theta_1} \otimes ... \otimes H^{\theta_\lambda} |x\rangle</math>, where <math>\theta</math> is a <math>\lambda</math>-bit string <math>\theta_1,...,\theta_\lambda</math>




==Protocol Description==

First, we define a protocol for copy-protection of point functions. This protocol can then be extended to a protocol for compute-and-compare programs.
===Protocol 1 - Copy protection of point functions===
====PF-Protect(<math>\lambda,y</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>y</math> - description of point function <math>P_y</math>
* Set <math>\theta = G(y)</math>
* Sample <math>v \leftarrow \{0,1\}^{m(\lambda)}</math> uniformly at random
* Let <math>z = H(v)</math>
* Output (<math>|v^\theta\rangle,z</math>)

====PF-Eval(<math>\lambda,(\rho,z),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(\rho,z)</math> - Alleged copy-protected program; <math>x</math> - Input on which the program is to be evaluated
* Set <math>\theta^\prime = G(x)</math>
* Apply the Hadamard operator <math>H^{\theta^\prime}</math> to <math>\rho</math>
* Append <math>n+1</math> ancillary qubits to <math>\rho</math>, all in state <math>|0\rangle</math>
* Compute the hash function <math>H</math> onto the first <math>n</math> ancillary qubits with <math>\rho</math> as input
* Coherently measure whether the first <math>n</math> ancilla qubits are in state <math>|z\rangle</math>, recording the result in the last ancilla qubit
* Uncompute the hash function <math>H</math> and undo the Hadamards <math>H^{\theta^\prime}</math>
* Measure the last ancilla qubit to obtain a bit <math>b</math> as output

===Protocol 2 - Copy protection of compute-and-compare programs===
====CC-Protect(<math>\lambda,(f,y)</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,y)</math> - description of compute-and-compare program <math>CC[f,y]</math>
* Let <math>\rho = </math> '''PF-Protect'''(<math>\lambda,y</math>)
* Output (<math>f,\rho</math>)

====CC-Eval(<math>\lambda,(f,\rho),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,\rho)</math> - Alleged copy protected program; <math>x</math> - Input on which the program is to be evaluated
* Compute <math>y^\prime = f(x)</math>
* Let <math>b \leftarrow </math> '''PF-Eval'''(<math>\lambda,\rho,y^\prime</math>). Output <math>b</math>.

==Properties==

*Both protocols have provable non-trivial security in the quantum random oracle model. Informally, a query bounded adversary fails at pirating with at least some constant probability.
*The Client should be able to perform universal quantum computation in order to compute the hash function <math>H</math>
*The protected programs obtained in both protocols allow polynomially-many evaluations (as we evaluate the copy-protected programs reversibly).
*[[#Protocol 1 - Copy protection of point functions|Protocol 1]] also satisfies the primitive of Virtual Black Box Obfuscation
*By adding a verification step, [[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]] can be extended to the weaker primitive of Secure Software Leasing. This protocol for Secure Software Leasing does however provide a standard level of security, i.e. the adversarial success probability is negligible in the security parameter.

==Further Information==

For the security proof and extension of the protocols to other functionalities, refer to the same paper by [http://arxiv.org/abs/2009.13865 Coladangelo et al. (2020)]
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>

Anonymous Conference Key Agreement using GHZ states

2022-01-07T19:59:16Z

Chirag:

This [https://arxiv.org/abs/2007.07995 example protocol] achieves the functionality of quantum conference key agreement. This protocol allows multiple parties in a quantum network to establish a shared secret key anonymously.



==Assumptions==

We require the following for this protocol:
# A source of n-party GHZ states
# Private randomness sources
# A randomness source that is not associated with any party
# A classical broadcasting channel
# Pairwise private communication channels

==Outline==

* First, the sender notifies each receiver in the network anonymously
* The entanglement source generates and distributes sufficient GHZ states to all nodes in the network
* The GHZ states are distilled to establish multipartite entanglement shared only by the participating parties (the sender and receivers)
* Each GHZ state is randomly chosen to be used for either Verification or Key Generation. For Key Generation rounds, a single bit of the key is established using one GHZ state by measuring in the Z-basis
* If the sender is content with the Verification results, they can anonymously validate the protocol and conclude that the key has been established successfully.

==Notation==






==Protocol Description==

===Protocol 1: Anonymous Verifiable Conference Key Agreement===
''Input'': Parameters <math>L</math> and <math>D</math>

''Requirements'': A source of n-party GHZ states; private randomness sources; a randomness source that is not associated with any party; a classical broadcasting channel; pairwise private communication channels

''Goal'': Anonymoous generation of key between sender and <math>m</math> receivers

# The sender notifies the <math>m</math> receivers by running the ''Notification'' protocol
# The source generates and shares <math>L</math> GHZ states
# The parties run the ''Anonymous Multipartite Entanglement'' protocol on the GHZ states
# For each <math>(m+1)</math>-partite GHZ state, the parties do the following:
#* They ask a source of randomness to broadcast a bit <math>b</math> such that Pr<math>[b=1] = \frac{1}{D}</math>
#* '''Verification round: '''If b = 0, the sender runs ''Verification'' as verifier on the state corresponding to that round, while only considering the announcements of the <math>m</math> receivers. The remaining parties announce random values.
#* '''KeyGen round: '''If b = 1, the sender and receivers measure in the Z-basis.
# If the sender is content with the checks of the ''Verification'' protocol, they can anonymously validate the protocol

===Protocol 2: Notification===
''Input: '' Sender's choice of <math>m</math> receivers

''Goal: '' The <math>m</math> receivers get notified

''Requirements: '' Private pairwise classical communication channels and randomness sources

For agent <math>i = 1,...,n</math>:
# All agents <math>j \in \{1,...,n\}</math> do the following:
#* '''When agent <math>j</math> is the sender''': If <math>i</math> is not a receiver, the sender chooses <math>n</math> random bits <math>\{r_{j,k}^i\}_{k = 1}^n</math> such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 0</math>. Otherwise, if <math>i</math> is a receiver, the sender chooses <math>n</math> random bits such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 1</math>. The sender sends bit <math>r_{j,k}^i</math> to agent <math>k</math>
#* '''When agent <math>j</math> is not the sender''': The agent chooses <math>n</math> random bits <math>\{r_{j,k}^i\}_{k = 1}^n</math> such that <math>\bigoplus_{k=1}^n r_{j,k}^i = 0</math> and sends bit <math>r_{j,k}^i</math> to agent <math>k</math>
# All agents <math>k \in \{1,...,n\}</math> receive <math>\{r_{j,k}^i\}_{j = 1}^n</math>, and compute <math>z_k^i = \bigoplus_{j=1}^n r_{j,k}^i</math> and send it to agent <math>i</math>
# Agent <math>i</math> takes the received <math>\{z_k^i\}_{k=1}^n</math> to compute <math>z^i = \bigoplus_{k=1}^nz_k^i</math>. If <math>z^i = 1</math>, they are thereby notified to be a designated receiver.

===Protocol 3: Anonymous Multiparty Entanglement===
''Input: '' <math>n</math>-partite GHZ state <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes n} + |1\rangle^{\otimes n})</math>

''Output: '' <math>(m+1)</math>-partite GHZ state <math>\frac{1}{\sqrt{2}}(|0\rangle^{\otimes (m+1)} + |1\rangle^{\otimes (m+1)})</math> shared between the sender and receivers

''Requirements: '' A broadcast channel; private randomness sources

# Sender and receivers draw a random bit each. Everyone else measures their qubits in the X-basis, yielding a measurement outcome bit <math>x_i</math>
# All parties broadcast their bits in a random order, or if possible, simultaneously.
# The sender applies a Z gate to their qubit if the parity of the non-participating parties' bits is odd.

===Protocol 4: Verification===

''Input: '' A verifier V; a shared state between <math>k</math> parties

''Goal: '' Verification or rejection of the shared state as the GHZ<math>_k</math> state by V

''Requirements: '' Private randomness sources; a classical broadcasting channel

# Everyone but V draws a random bit <math>b_i</math> and measures in the X or Y basis if their bit equals 0 or 1 respectively, obtaining a measurement outcome <math>m_i</math>. V chooses both bits at random
# Everyone (including V) broadcasts <math>(b_i,m_i)</math>
# V resets her bit such that <math>\sum_ib_i = 0 (</math>mod <math>2)</math>. She measures in the X or Y basis if her bit equals 0 or 1 respectively, thereby also resetting her <math>m_i = m_v</math>
# V accepts the state if and only if <math>\sum_im_i = \frac{1}{2}\sum_ib_i (</math>mod <math>2)</math>
==Properties==


==Further Information==


==References==

Anonymous Conference Key Agreement using GHZ states

2022-01-07T13:50:18Z

Chirag: Created page with "  This [https://arxiv.org/abs/2007.07995 example protocol] achie..."

Protocol Library

2021-12-17T11:01:39Z

Chirag: Added link to Practical Quantum E-voting

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="5"|[[Authentication of Quantum Messages]]||[[Purity Testing based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
|[[Clifford Code for Quantum Authentication]]
|-
|[[Trap Code for Quantum Authentication]]
|-
|[[Naive approach using Quantum Teleportation]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|rowspan="4"|[[Verification of Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of NP-complete problems]]
|-
|[[Verification of Sub-Universal Quantum Computation]]
|-
|[[Classical Verification of Universal Quantum Computation]]
|-
|rowspan="5"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
|[[Practical Quantum Electronic Voting]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="2"|[[Entanglement Routing]]||[[Routing Entanglement in the Quantum Internet]]
|-
|[[Distributing Graph States Over Arbitrary Quantum Networks]]

Practical Quantum Electronic Voting

2021-12-16T22:30:15Z

Chirag: Add assumptions and further information

This [https://arxiv.org/abs/2107.14719 example protocol] achieves the functionality of [[Quantum Electronic Voting]]. In this protocol, an untrusted multipartite entanglement source can be used to carry out an election without any election authorities.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party Protocols]], [[:Category: Quantum Enhanced Classical Functionality| Quantum Enhanced Classical Functionality]], [[:Category:Specific Task | Specific Task]]

==Assumptions==

* Voting agents can communicate classically.
* Voting agents can generate random numbers.
* There is a multipartite entanglement source connected to each agent by a quantum channel. The source need not be trusted.

==Outline==

* In the first phase of the protocol, each agent is assigned a secret unique random index
* Next, we perform multiple rounds of voting, one for each agent. In each round, the following steps are carried out:
** The agent with the same index as the round number is designated the voter for that round
** The source distributes one qubit of a GHZ state to each agent. The voting agent randomly chooses to either '''verify''' the GHZ state or '''vote''' with a certain probability. This step, including state distribution, is repeated until the voter chooses to vote. Once voting is chosen, the voter anonymously transmits their vote to all agents.
* Finally, all the votes are tallied. All agents have the votes for each round and can thus verify the final tally.

==Notation==

* <math>N</math>: Number of agents
* <math>V = \{v_k\}_{k \in [N]} </math>: The votes
* <math>S</math>: Security parameter
* <math>\epsilon</math>: Distance from the perfect GHZ state
* <math>\delta</math>: Threshold for verification
* <math>\eta</math>: Probability of failure of verification
* '''B''': Bulletin board - <math>N</math> x <math>N</math> binary matrix. Each row corresponds to one round of voting, and each column contains the output of a single voter across all rounds
* '''E''': Vote vector - The list of votes across <math>N</math> rounds. Each element is computed as the parity of a row from '''B'''
* '''T''': Final tally





==Protocol Description==

===Protocol 1 : Quantum e-voting===
''Inputs'': <math>V = \{v_k\}_{k \in [N]} </math> - Set of votes; <math>S</math> - Security parameter; <math>\epsilon</math> - Distance from the perfect GHZ state; <math>\delta</math> - Threshold for verification; <math>\eta</math> Probability of failure of verification

''Output'': The candidate with majority votes or ''Abort''

''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels
* Phase 1 [getting unique secret indices]
** Agents perform '''UniqueIndex''' until each agent has a secret unique random index <math>\omega_k</math>
* Phase 2 [casting votes]
** For <math>l = 1</math> to <math>N</math>
*** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math>
*** Repeat until '''Voting''' is announced
**** The source distributes to each of the N agents one qubit of the GHZ source
**** All agents <math> j \in [N] </math> set rejections<math>_j = </math> trials<math>_j = 0</math>
**** The voting agent tosses log<math>_2[\frac{16N\epsilon^2}{(\epsilon^2-4\delta)^2}</math>ln<math>(\frac{1}{\eta})]</math> 
**** The agents perform '''LogicalOR''', where output 1 indicates '''Verification''' and output 0 indicates '''Voting'''. Everyone except the voting agent inputs 0; if the coin toss is 'all heads' the voting agent also inputs 0, otherwise the voting agent inputs 1
**** If '''Verification''' is chosen, the agents perform '''RandomAgent''' and the voting agent anonymously picks an agent <math>j \in [N]</math> to be the verifier. Agent <math>j</math> updates trials<math>_j+ = 1</math> and if '''Verification''' outputs reject: rejections<math>_j+ = 1</math>
*** If for any <math>j \in [N], \delta_j = \frac{rejections_j}{trials_j} > \delta </math>, the protocol ''Aborts''
*** Perform '''Voting'''. The outcome is one row of the Bulletin Board '''B'''. The parity of the row gives one entry in the vote vector '''E'''.
** Given the votes '''E''', the tally '''T''' can be computed.
*Phase 3 [Verification of results]:
** All agents perform '''LogicalOR''' with security parameter <math>S</math>, and input 1 if their vote is not the same as the entry in '''E''' for the round in which they voted, and 0 otherwise.
** If '''LogicalOR''' outputs 1, ''Abort'' the protocol. Else output the candidate with the most votes according to the tally '''T'''.

===Protocol 2 : UniqueIndex===

''Input'': Security parameter <math>S</math> to be used in '''LogicalOR''',<math>N</math> random boolean variables <math>x_i</math>.

''Output'': Each agent <math>k</math> has a secret unique index <math>\omega_k</math>.

''Resources'': Classical communication and random numbers.

# Beginning of round R = 1
# Agents perform '''LogicalOR''' with inputs <math>x_k = 0</math> if they already have an index and <math>x_k = 1</math> if they do not.
# If <math>y = 0</math>, repeat from step 2
# If an agent <math>k</math> has a bit <math>x_k = 1</math> and <math>\omega_k = 0</math> they know they are the only one and has been assigned the secret index corresponding to the round <math>\omega_k = R</math>, otherwise there is a collision.
# [notification] Everybody performs a '''LogicalOR''' with input 0, unless they received the index in this round, in which case they input 1.
# If the output of '''LogicalOR''' is 0, no index was assigned and we repeat from step 2.
# If the output of '''LogicalOR''' is 1, the index was assigned and we repeat from step 2 with R+ = 1.
# Repeat from step 2 until all indices have been assigned.

===Protocol 3 : Verification===
''Input'': A quantum state distributed and shared by <math>N</math> parties, security parameter <math>S</math> for '''RandomAgent'''.

''Output'': If the state is a GHZ state <math> \rightarrow </math> YES.

''Resources'': Classical communication, random numbers, quantum state source, quantum channels.

# Everyone executes '''RandomAgent''' to choose uniformly at random one of the voters to be the verifier.
# The verifier generates random angles <math>\theta_j \in [0, \pi)</math> for all agents including themselves, such that the sum is a multiple of <math>\pi</math>. The angles are then sent out to all the agents.
# Agent <math>j</math> measures in the basis <math>[|+_\theta\rangle,|-_\theta\rangle] = [\frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta_j}|1\rangle), \frac{1}{\sqrt{2}}(|0\rangle - e^{i\theta_j}|1\rangle)]</math> and publicly announces the result <math>Y_j = \{0,1\}</math>
# The state passes the verification test when the following condition is satisfied: if the sum of the randomly chosen angles is an even multiple of <math>\pi</math>, there must be an even number of 1 outcomes for <math>Y_j</math> , and if the sum is an odd multiple of <math>\pi</math>, there must be an odd number of 1 outcomes for <math>Y_j : \bigoplus_j Y_j = \frac{1}{\pi}\sum_i\theta_i </math> (mod 2)

===Protocol 4 : Voting===
''Input'': Voting agent preference <math>v_k</math>.

''Output'': All agents get one row of the bulletin board.

''Resources'': Classical communication, GHZ source, quantum channels.

# Each agent measures the state they received in the Hadamard basis and records the outcome.
# The outcomes of the measurement of each voter <math>k</math> is <math>d_k</math>. Then we know that <math>\sum_kd_k = 0</math> mod <math> 2</math>
# The voting agent performs an XOR between the outcome <math>d_k</math> and their vote <math>v_k</math>: <math>d_k \leftarrow d_k \oplus v_k </math>. However, this alone will still appear as a random string.
# Every agent publicly broadcasts <math>d_k</math> which gives one line <math>b_k</math> of the bulletin board '''B''' <math> = \{b_k\}</math>

===Protocol 5 : LogicalOR===
''Inputs'': <math>N</math> agents, <math>N</math> boolean variables <math>x_i</math>, security parameter <math>S = (1 - 2^{-\Gamma})^\Sigma \in (0,1)</math>

''Output'': <math>y = \vee_i^N x_i </math>

''Resources'': Classical communication and random numbers

# Decide <math>N</math> random orderings, such that each voter is the last once. For each ordering repeat \Sigma times the following.
# Each voter <math>k</math> gives an input <math>x_k</math>
# If <math>x_k = 0 </math>, set <math>p_k = 0</math>, otherwise toss <math>\Gamma</math> coins and set <math>p_k</math> to <math>1</math> if the result is ‘all heads’ and to <math>0</math> otherwise
# Then each voter generates uniformly at random an <math>N</math>-bit string <math>r_k = r_k^1r_k^2...r_k^N</math>, such that <math>\bigoplus_{i=1}^N r_k^i = p_k</math>
# Voter <math>k</math> sends <math>r_k^i</math> to voter <math>i</math> for all <math>i</math>, keeping <math>r_k^k</math>
# Each voter sums the received bits and broadcasts the parity <math>z_i = \bigoplus_{k=1}^N r_k^i </math> according to the ordering.
# Compute the parity of the original bits <math>y = \bigoplus_i z_i</math>
# From this everyone can also compute the parity of all other inputs except their own <math>w_k = \bigoplus_{i = 1}^N (z_i \otimes r_k^i)</math>
# Repeat <math>\Sigma</math> times from step 4: each time repeat with <math>p_k</math> as new inputs
# If at least once in the <math>\Sigma</math> repetitions for the various orderings <math>y = 1</math>, this is the output of the protocol, otherwise it is <math>y = 0</math>

===Protocol 6 : RandomBit===
''Input'': Security parameter S to be used in '''LogicalOR''', ''voting agent'': probability distribution D.

''Output'': The voting agent anonymously announces a random bit according to D.

''Resources'': Classical communication and random numbers.

*Perform '''LogicalOR''' with security parameter S where the voting agent inputs a random bit according to D and the other agents input 0.

===Protocol 7 : RandomAgent===

''Input'': Security parameter S to be used in '''RandomBit''', voting agent: probability distribution D.

''Output'': The voting agent anonymously chooses a random agent according to D.

''Resources'': Classical communication and random numbers.

* Repeat '''RandomBit''' log2 N times.

==Properties==

* <math>(\sigma_H,\sigma_D,\gamma)</math>-''Correctness'': This notion of approximate correctness includes two properties:
** <math>\sigma_H</math>-''Completeness'': If all agents are honest, the election is accepted with probability more than <math>\sigma_H</math> - Pr[election accepted] <math> \geq \sigma_H</math>
** <math>(\sigma_D,\gamma)</math>-''Soundness'': the probability that the election result is accepted, given that the set of the votes '''E''' computed from the bulletin board '''B''' resulting from the election is more than <math>\gamma</math> away from the real votes '''V''', is smaller than <math>\sigma_D</math> -
:: Pr[election accepted <math>| \frac{1}{N}||</math>'''V''' - '''E'''<math>||_1 \geq \gamma] \leq \sigma_D </math>
: This particular protocol is <math>([1-\epsilon(1-S)]^N, S^{N(1+\lambda)[\epsilon(1-\eta)+\eta]},(1+\lambda)[\epsilon(1-\eta)+\eta])</math>-correct, for a small constant <math>\lambda > 0</math>

* <math>\zeta</math>-''Privacy'': The privacy of the election scheme implies that for any voter <math>k</math>, the probability that any subset of malicious parties <math>D</math> that deviates from the honest protocol can guess the vote <math>v_k</math> of the voter is at most <math>\zeta</math> more than in the case they just have access to the bulletin board and to their own votes -
: <math>\forall k, </math> Pr<math>[v_k|D] -</math> Pr<math>[v_k|B,v_j \in </math> '''V'''<math>_D] \leq \zeta</math>
: This particular protocol is <math>\zeta</math>-private with <math>\zeta = (1-\eta)^N\epsilon + (1 - (1-\eta)^N)</math>

* ''Authentication'': This e-voting protocol does not provide authentication, which should be taken care of by the physical implementation of the protocol.

* ''Double voting'': Each voter can vote at most once. Since the number of voters is known in advance for this protocol, double voting is easily taken care of.

* ''Verifiability'': Each voter can verify that their vote has been counted correctly. In this protocol, the tally is performed by the voters themselves. The bulletin board produced as an output of the protocol is public and can always be checked by everyone, while still appearing random.

* ''Receipt freeness'': In order to prevent vote-selling, voters should not be able to prove how they voted. As the unique indices stay secret, voters cannot produce a receipt of their vote.

* ''Additional candidates'': The protocol described here only allows an election consisting of 2 candidates. This can be extended to more candidates by repeating the protocol multiple times in sequence. In particular, if there are K candidates, we can express each of them using log<math>_2</math>K bits and repeat the election as many times so that each vote set corresponds to one bit. This however does affect the correctness and privacy.

==Further Information==

* Proofs of the protocol properties can be found in [https://arxiv.org/abs/2107.14719 Centrone et al. (2021)]
* Protocols 5-7 are classical anonymous protocols taken from [https://arxiv.org/abs/0706.2010 Broadbent and Tapp(2007)] and used in [https://arxiv.org/abs/1811.04729 Unnikrishnan et al.(2018)]
* Protocol 3 is the same as that of [https://arxiv.org/abs/1112.5064 Pappa et al.(2011)]

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

Practical Quantum Electronic Voting

2021-12-16T17:07:40Z

Chirag: Add protocol properties and minor edits

This [https://arxiv.org/abs/2107.14719 example protocol] achieves the functionality of [[Quantum Electronic Voting]]. In this protocol, an untrusted multipartite entanglement source can be used to carry out an election without any election authorities.



==Assumptions==


==Outline==

* In the first phase of the protocol, each agent is assigned a secret unique random index
* Next, we perform multiple rounds of voting, one for each agent. In each round, the following steps are carried out:
** The agent with the same index as the round number is designated the voter for that round
** The source distributes one qubit of a GHZ state to each agent. The voting agent randomly chooses to either '''verify''' the GHZ state or '''vote''' with a certain probability. This step, including state distribution, is repeated until the voter chooses to vote. Once voting is chosen, the voter anonymously transmits their vote to all agents.
* Finally, all the votes are tallied. All agents have the votes for each round and can thus verify the final tally.

==Notation==

* <math>N</math>: Number of agents
* <math>V = \{v_k\}_{k \in [N]} </math>: The votes
* <math>S</math>: Security parameter
* <math>\epsilon</math>: Distance from the perfect GHZ state
* <math>\delta</math>: Threshold for verification
* <math>\eta</math>: Probability of failure of verification
* '''B''': Bulletin board - <math>N</math> x <math>N</math> binary matrix. Each row corresponds to one round of voting, and each column contains the output of a single voter across all rounds
* '''E''': Vote vector - The list of votes across <math>N</math> rounds. Each element is computed as the parity of a row from '''B'''
* '''T''': Final tally





==Protocol Description==

===Protocol 1 : Quantum e-voting===
''Inputs'': <math>V = \{v_k\}_{k \in [N]} </math> - Set of votes; <math>S</math> - Security parameter; <math>\epsilon</math> - Distance from the perfect GHZ state; <math>\delta</math> - Threshold for verification; <math>\eta</math> Probability of failure of verification

''Output'': The candidate with majority votes or ''Abort''

''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels
* Phase 1 [getting unique secret indices]
** Agents perform '''UniqueIndex''' until each agent has a secret unique random index <math>\omega_k</math>
* Phase 2 [casting votes]
** For <math>l = 1</math> to <math>N</math>
*** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math>
*** Repeat until '''Voting''' is announced
**** The source distributes to each of the N agents one qubit of the GHZ source
**** All agents <math> j \in [N] </math> set rejections<math>_j = </math> trials<math>_j = 0</math>
**** The voting agent tosses log<math>_2[\frac{16N\epsilon^2}{(\epsilon^2-4\delta)^2}</math>ln<math>(\frac{1}{\eta})]</math> 
**** The agents perform '''LogicalOR''', where output 1 indicates '''Verification''' and output 0 indicates '''Voting'''. Everyone except the voting agent inputs 0; if the coin toss is 'all heads' the voting agent also inputs 0, otherwise the voting agent inputs 1
**** If '''Verification''' is chosen, the agents perform '''RandomAgent''' and the voting agent anonymously picks an agent <math>j \in [N]</math> to be the verifier. Agent <math>j</math> updates trials<math>_j+ = 1</math> and if '''Verification''' outputs reject: rejections<math>_j+ = 1</math>
*** If for any <math>j \in [N], \delta_j = \frac{rejections_j}{trials_j} > \delta </math>, the protocol ''Aborts''
*** Perform '''Voting'''. The outcome is one row of the Bulletin Board '''B'''. The parity of the row gives one entry in the vote vector '''E'''.
** Given the votes '''E''', the tally '''T''' can be computed.
*Phase 3 [Verification of results]:
** All agents perform '''LogicalOR''' with security parameter <math>S</math>, and input 1 if their vote is not the same as the entry in '''E''' for the round in which they voted, and 0 otherwise.
** If '''LogicalOR''' outputs 1, ''Abort'' the protocol. Else output the candidate with the most votes according to the tally '''T'''.

===Protocol 2 : UniqueIndex===

''Input'': Security parameter <math>S</math> to be used in '''LogicalOR''',<math>N</math> random boolean variables <math>x_i</math>.

''Output'': Each agent <math>k</math> has a secret unique index <math>\omega_k</math>.

''Resources'': Classical communication and random numbers.

# Beginning of round R = 1
# Agents perform '''LogicalOR''' with inputs <math>x_k = 0</math> if they already have an index and <math>x_k = 1</math> if they do not.
# If <math>y = 0</math>, repeat from step 2
# If an agent <math>k</math> has a bit <math>x_k = 1</math> and <math>\omega_k = 0</math> they know they are the only one and has been assigned the secret index corresponding to the round <math>\omega_k = R</math>, otherwise there is a collision.
# [notification] Everybody performs a '''LogicalOR''' with input 0, unless they received the index in this round, in which case they input 1.
# If the output of '''LogicalOR''' is 0, no index was assigned and we repeat from step 2.
# If the output of '''LogicalOR''' is 1, the index was assigned and we repeat from step 2 with R+ = 1.
# Repeat from step 2 until all indices have been assigned.

===Protocol 3 : Verification===
''Input'': A quantum state distributed and shared by <math>N</math> parties, security parameter <math>S</math> for '''RandomAgent'''.

''Output'': If the state is a GHZ state <math> \rightarrow </math> YES.

''Resources'': Classical communication, random numbers, quantum state source, quantum channels.

# Everyone executes '''RandomAgent''' to choose uniformly at random one of the voters to be the verifier.
# The verifier generates random angles <math>\theta_j \in [0, \pi)</math> for all agents including themselves, such that the sum is a multiple of <math>\pi</math>. The angles are then sent out to all the agents.
# Agent <math>j</math> measures in the basis <math>[|+_\theta\rangle,|-_\theta\rangle] = [\frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta_j}|1\rangle), \frac{1}{\sqrt{2}}(|0\rangle - e^{i\theta_j}|1\rangle)]</math> and publicly announces the result <math>Y_j = \{0,1\}</math>
# The state passes the verification test when the following condition is satisfied: if the sum of the randomly chosen angles is an even multiple of <math>\pi</math>, there must be an even number of 1 outcomes for <math>Y_j</math> , and if the sum is an odd multiple of <math>\pi</math>, there must be an odd number of 1 outcomes for <math>Y_j : \bigoplus_j Y_j = \frac{1}{\pi}\sum_i\theta_i</math>

===Protocol 4 : Voting===
''Input'': Voting agent preference <math>v_k</math>.

''Output'': All agents get one row of the bulletin board.

''Resources'': Classical communication, GHZ source, quantum channels.

# Each agent measures the state they received in the Hadamard basis and records the outcome.
# The outcomes of the measurement of each voter <math>k</math> is <math>d_k</math>. Then we know that <math>\sum_kd_k = 0</math> mod <math> 2</math>
# The voting agent performs an XOR between the outcome <math>d_k</math> and their vote <math>v_k</math>: <math>d_k \leftarrow d_k \oplus v_k </math>. However, this alone will still appear as a random string.
# Every agent publicly broadcasts <math>d_k</math> which gives one line <math>b_k</math> of the bulletin board '''B''' <math> = \{b_k\}</math>

===Protocol 5 : LogicalOR===
''Inputs'': <math>N</math> agents, <math>N</math> boolean variables <math>x_i</math>, security parameter <math>S = (1 - 2^{-\Gamma})^\Sigma \in (0,1)</math>

''Output'': <math>y = \vee_i^N x_i </math>

''Resources'': Classical communication and random numbers

# Decide <math>N</math> random orderings, such that each voter is the last once. For each ordering repeat \Sigma times the following.
# Each voter <math>k</math> gives an input <math>x_k</math>
# If <math>x_k = 0 </math>, set <math>p_k = 0</math>, otherwise toss <math>\Gamma</math> coins and set <math>p_k</math> to <math>1</math> if the result is ‘all heads’ and to <math>0</math> otherwise
# Then each voter generates uniformly at random an <math>N</math>-bit string <math>r_k = r_k^1r_k^2...r_k^N</math>, such that <math>\bigoplus_{i=1}^N r_k^i = p_k</math>
# Voter <math>k</math> sends <math>r_k^i</math> to voter <math>i</math> for all <math>i</math>, keeping <math>r_k^k</math>
# Each voter sums the received bits and broadcasts the parity <math>z_i = \bigoplus_{k=1}^N r_k^i </math> according to the ordering.
# Compute the parity of the original bits <math>y = \bigoplus_i z_i</math>
# From this everyone can also compute the parity of all other inputs except their own <math>w_k = \bigoplus_{i = 1}^N (z_i \otimes r_k^i)</math>
# Repeat <math>\Sigma</math> times from step 4: each time repeat with <math>p_k</math> as new inputs
# If at least once in the <math>\Sigma</math> repetitions for the various orderings <math>y = 1</math>, this is the output of the protocol, otherwise it is <math>y = 0</math>

===Protocol 6 : RandomBit===
''Input'': Security parameter S to be used in '''LogicalOR''', ''voting agent'': probability distribution D.

''Output'': The voting agent anonymously announces a random bit according to D.

''Resources'': Classical communication and random numbers.

*Perform '''LogicalOR''' with security parameter S where the voting agent inputs a random bit according to D and the other agents input 0.

===Protocol 7 : RandomAgent===

''Input'': Security parameter S to be used in '''RandomBit''', voting agent: probability distribution D.

''Output'': The voting agent anonymously chooses a random agent according to D.

''Resources'': Classical communication and random numbers.

* Repeat '''RandomBit''' log2 N times.

==Properties==

* <math>(\sigma_H,\sigma_D,\gamma)</math>-''Correctness'': This notion of approximate correctness includes two properties:
** <math>\sigma_H</math>-''Completeness'': If all agents are honest, the election is accepted with probability more than <math>\sigma_H</math> - Pr[election accepted] <math> \geq \sigma_H</math>
** <math>(\sigma_D,\gamma)</math>-''Soundness'': the probability that the election result is accepted, given that the set of the votes '''E''' computed from the bulletin board '''B''' resulting from the election is more than <math>\gamma</math> away from the real votes '''V''', is smaller than <math>\sigma_D</math> -
:: Pr[election accepted <math>| \frac{1}{N}||</math>'''V''' - '''E'''<math>||_1 \geq \gamma] \leq \sigma_D </math>
: This particular protocol is <math>([1-\epsilon(1-S)]^N, S^{N(1+\lambda)[\epsilon(1-\eta)+\eta]},(1+\lambda)[\epsilon(1-\eta)+\eta])</math>-correct, for a small constant <math>\lambda > 0</math>

* <math>\zeta</math>-''Privacy'': The privacy of the election scheme implies that for any voter <math>k</math>, the probability that any subset of malicious parties <math>D</math> that deviates from the honest protocol can guess the vote <math>v_k</math> of the voter is at most <math>\zeta</math> more than in the case they just have access to the bulletin board and to their own votes -
: <math>\forall k, </math> Pr<math>[v_k|D] -</math> Pr<math>[v_k|B,v_j \in </math> '''V'''<math>_D] \leq \zeta</math>
: This particular protocol is <math>\zeta</math>-private with <math>\zeta = (1-\eta)^N\epsilon + (1 - (1-\eta)^N)</math>

* ''Authentication'': This e-voting protocol does not provide authentication, which should be taken care of by the physical implementation of the protocol.

* ''Double voting'': Each voter can vote at most once. Since the number of voters is known in advance for this protocol, double voting is easily taken care of.

* ''Verifiability'': Each voter can verify that their vote has been counted correctly. In this protocol, the tally is performed by the voters themselves. The bulletin board produced as an output of the protocol is public and can always be checked by everyone, while still appearing random.

* ''Receipt freeness'': In order to prevent vote-selling, voters should not be able to prove how they voted. As the unique indices stay secret, voters cannot produce a receipt of their vote.

* ''Additional candidates'': The protocol described here only allows an election consisting of 2 candidates. This can be extended to more candidates by repeating the protocol multiple times in sequence. In particular, if there are K candidates, we can express each of them using log<math>_2</math>K bits and repeat the election as many times so that each vote set corresponds to one bit. This however does affect the correctness and privacy.
==Further Information==


==References==

Practical Quantum Electronic Voting

2021-12-15T21:14:45Z

Chirag: Initial protocol page for Practical Quantum Electonic Voting

This [https://arxiv.org/abs/2107.14719 example protocol] achieves the functionality of [[Quantum Electronic Voting]]. In this protocol, an untrusted multipartite entanglement source can be used to carry out an election without any election authorities.



==Assumptions==


==Outline==

* In the first phase of the protocol, each agent is assigned a secret unique random index
* Next, we perform multiple rounds of voting, one for each agent. In each round, the following steps are carried out:
** The agent with the same index as the round number is designated the voter for that round
** The source distributes one qubit of a GHZ state to each agent. The voting agent randomly chooses to either '''verify''' the GHZ state or '''vote''' with a certain probability. This step, including state distribution, is repeated until the voter chooses to vote. Once voting is chosen, the voter anonymously transmits their vote to all agents.
* Finally, all the votes are tallied. All agents have the votes for each round and can thus verify the final tally.

==Notation==

* <math>N</math>: Number of agents
* <math>V = \{v_k\}_{k \in [N]} </math>: The votes
* <math>S</math>: Security parameter
* <math>\epsilon</math>: Distance from the perfect GHZ state
* <math>\delta</math>: Threshold for verification
* <math>\eta</math>: Probability of failure of verification
* '''B''': Bulletin board - <math>N</math> x <math>N</math> binary matrix. Each row corresponds to one round of voting, and each column contains the output of a single voter across all rounds
* '''E''': Vote vector - The list of votes across <math>N</math> rounds. Each element is computed as the parity of a row from '''B'''
* '''T''': Final tally





==Protocol Description==

===Protocol 1 : Quantum e-voting===
''Inputs'': <math>V = \{v_k\}_{k \in [N]} </math> - Set of votes; <math>S</math> - Security parameter; <math>\epsilon</math> - Distance from the perfect GHZ state; <math>\delta</math> - Threshold for verification; <math>\eta</math> Probability of failure of verification

''Output'': The candidate with majority votes or ''Abort''

''Resources'': Classical communication, random numbers, N-qubit GHZ source, quantum channels
* Phase 1 [getting unique secret indices]
** Agents perform [[#Protocol 5 : UniqueIndex| UniqueIndex]] until each agent has a secret unique random index <math>\omega_k</math>
* Phase 2 [casting votes]
** For <math>l = 1</math> to <math>N</math>
*** The voting agent is the agent <math>k</math> with <math>\omega_k = l</math>
*** Repeat until [[#Protocol 7 : Voting| Voting]] is announced
**** The source distributes to each of the N agents one qubit of the GHZ source
**** All agents <math> j \in [N] </math> set rejections<math>_j = </math> trials<math>_j = 0</math>
**** The voting agent tosses log<math>_2[\frac{16N\epsilon^2}{(\epsilon^2-4\delta)^2}</math>ln<math>(\frac{1}{\eta})]</math> 
**** The agents perform [[#Protocol 2 : LogicalOR| LogicalOR]], where output 1 indicates [[#Protocol 6 : Verification| Verification]] and output 0 indicates [[#Protocol 7 : Voting| Voting]]. Everyone except the voting agent inputs 0; if the coin toss is 'all heads' the voting agent also inputs 0, otherwise the voting agent inputs 1
**** If [[#Protocol 6 : Verification| Verification]] is chosen, the agents perform [[#Protocol 4 : RandomAgent| RandomAgent]] and the voting agent anonymously picks an agent <math>j \in [N]</math> to be the verifier. Agent <math>j</math> updates trials<math>_j+ = 1</math> and if [[#Protocol 6 : Verification| Verification]] outputs reject: rejections<math>_j+ = 1</math>
*** If for any <math>j \in [N], \delta_j = \frac{rejections_j}{trials_j} > \delta </math>, the protocol ''Aborts''
*** Perform [[#Protocol 7 : Voting| Voting]]. The outcome is one row of the Bulletin Board '''B'''. The parity of the row gives one entry in the vote vector '''E'''.
** Given the votes '''E''', the tally '''T''' can be computed.
*Phase 3 [Verification of results]:
** All agents perform [[#Protocol 2 : LogicalOR| LogicalOR]] with security parameter <math>S</math>, and input 1 if their vote is not the same as the entry in '''E''' for the round in which they voted, and 0 otherwise.
** If [[#Protocol 2 : LogicalOR| LogicalOR]] outputs 1, ''Abort'' the protocol. Else output the candidate with the most votes according to the tally '''T'''.

===Protocol 2 : LogicalOR===
''Inputs'': <math>N</math> agents, <math>N</math> boolean variables <math>x_i</math>, security parameter <math>S = (1 - 2^{-\Gamma})^\Sigma \in (0,1)</math>

''Output'': <math>y = \vee_i^N x_i </math>

''Resources'': Classical communication and random numbers

# Decide <math>N</math> random orderings, such that each voter is the last once. For each ordering repeat \Sigma times the following.
# Each voter <math>k</math> gives an input <math>x_k</math>
# If <math>x_k = 0 </math>, set <math>p_k = 0</math>, otherwise toss <math>\Gamma</math> coins and set <math>p_k</math> to <math>1</math> if the result is ‘all heads’ and to <math>0</math> otherwise
# Then each voter generates uniformly at random an <math>N</math>-bit string <math>r_k = r_k^1r_k^2...r_k^N</math>, such that <math>\bigoplus_{i=1}^N r_k^i = p_k</math>
# Voter <math>k</math> sends <math>r_k^i</math> to voter <math>i</math> for all <math>i</math>, keeping <math>r_k^k</math>
# Each voter sums the received bits and broadcasts the parity <math>z_i = \bigoplus_{k=1}^N r_k^i </math> according to the ordering.
# Compute the parity of the original bits <math>y = \bigoplus_i z_i</math>
# From this everyone can also compute the parity of all other inputs except their own <math>w_k = \bigoplus_{i = 1}^N (z_i \otimes r_k^i)</math>
# Repeat <math>\Sigma</math> times from step 4: each time repeat with <math>p_k</math> as new inputs
# If at least once in the <math>\Sigma</math> repetitions for the various orderings <math>y = 1</math>, this is the output of the protocol, otherwise it is <math>y = 0</math>

===Protocol 3 : RandomBit===
''Input'': Security parameter S to be used in [[#Protocol 2 : LogicalOR| LogicalOR]], ''voting agent'': probability distribution D.

''Output'': The voting agent anonymously announces a random bit according to D.

''Resources'': Classical communication and random numbers.

*Perform [[#Protocol 2 : LogicalOR| LogicalOR]] with security parameter S where the voting agent inputs a random bit according to D and the other agents input 0.

===Protocol 4 : RandomAgent===

''Input'': Security parameter S to be used in [[#Protocol 3 : RandomBit| RandomBit]], voting agent: probability distribution D.

''Output'': The voting agent anonymously chooses a random agent according to D.

''Resources'': Classical communication and random numbers.

* Repeat [[#Protocol 3 : RandomBit| RandomBit]] log2 N times.

===Protocol 5 : UniqueIndex===

''Input'': Security parameter <math>S</math> to be used in LogicalOR,<math>N</math> random boolean variables <math>x_i</math>.

''Output'': Each agent <math>k</math> has a secret unique index <math>\omega_k</math>.

''Resources'': Classical communication and random numbers.

# Beginning of round R = 1
# Agents perform [[#Protocol 2 : LogicalOR| LogicalOR]] with inputs <math>x_k = 0</math> if they already have an index and <math>x_k = 1</math> if they do not.
# If <math>y = 0</math>, repeat from step 2
# If an agent <math>k</math> has a bit <math>x_k = 1</math> and <math>\omega_k = 0</math> they know they are the only one and has been assigned the secret index corresponding to the round <math>\omega_k = R</math>, otherwise there is a collision.
# \[notification\] Everybody performs a [[#Protocol 2 : LogicalOR| LogicalOR]] with input 0, unless they received the index in this round, in which case they input 1.
# If the output of [[#Protocol 2 : LogicalOR| LogicalOR]] is 0, no index was assigned and we repeat from step 2.
# If the output of [[#Protocol 2 : LogicalOR| LogicalOR]] is 1, the index was assigned and we repeat from step 2 with R+ = 1.
# Repeat from step 2 until all indices have been assigned.

===Protocol 6 : Verification===
''Input'': A quantum state distributed and shared by <math>N</math> parties, security parameter <math>S</math> for [[#Protocol 4 : RandomAgent| RandomAgent]].

''Output'': If the state is a GHZ state <math> \rightarrow </math> YES.

''Resources'': Classical communication, random numbers, quantum state source, quantum channels.

# Everyone executes [[#Protocol 4 : RandomAgent| RandomAgent]] to choose uniformly at random one of the voters to be the verifier.
# The verifier generates random angles <math>\theta_j \in [0, \pi)</math> for all agents including themselves, such that the sum is a multiple of <math>\pi</math>. The angles are then sent out to all the agents.
# Agent <math>j</math> measures in the basis <math>[|+_\theta\rangle,|-_\theta\rangle] = [\frac{1}{\sqrt{2}}(|0\rangle + e^{i\theta_j}|1\rangle), \frac{1}{\sqrt{2}}(|0\rangle - e^{i\theta_j}|1\rangle)]</math> and publicly announces the result <math>Y_j = \{0,1\}</math>
# The state passes the verification test when the following condition is satisfied: if the sum of the randomly chosen angles is an even multiple of <math>\pi</math>, there must be an even number of 1 outcomes for <math<Y_j</math> , and if the sum is an odd multiple of <math>\pi</math>, there must be an odd number of 1 outcomes for <math>Y_j : \bigoplus_j Y_j = \frac{1}{\pi}\sum_i\theta_i</math>

===Protocol 7 : Voting===
''Input'': Voting agent preference <math>v_k</math>.

''Output'': All agents get one row of the bulletin board.

''Resources'': Classical communication, GHZ source, quantum channels.

# Each agent measures the state they received in the Hadamard basis and records the outcome.
# The outcomes of the measurement of each voter <math>k</math> is <math>d_k</math>. Then we know that <math>\sum_kd_k = 0</math> mod <math> 2</math>
# The voting agent performs an XOR between the outcome <math>d_k</math> and their vote <math>v_k</math>: <math>d_k \leftarrow d_k \oplus v_k </math>. However, this alone will still appear as a random string.
# Every agent publicly broadcasts <math>d_k</math> which gives one line <math>b_k</math> of the bulletin board '''B''' <math> = \{b_k\}</math>
==Properties==


==Further Information==


==References==

Practical Quantum Electronic Voting

2021-12-15T20:51:43Z

Chirag: Created page with "  This [https://arxiv.org/abs/2107.14719 example protocol] achi..."

Quantum Protocol Zoo:About

2021-12-12T10:11:21Z

Chirag:

*'''THE ZOO FOUNDERS'''<br/>
** Elham Kashefi
** Shraddha Singh

*'''THE ZOO REVIEWERS'''<br/>
** Céline Chevalier
** Marc Kaplan
** Elham Kashefi
** Niraj Kumar
** Atul Mantri
** Harold Ollivier
** Shraddha Singh

*'''THE ZOO CONTRIBUTORS'''<br/>
** Mashid Delavar
** Bas Dirke
** Mina Doosti
** Victoria Lipinska
** Natansh Mathur
** Gláucia Murta
** Rhea Parekh
** Jérémy Ribeiro
** Shraddha Singh
** Gozde Ustun
** Chirag Wadhwa

*'''THE ZOO SPONSORS'''<br/>

{{galery}}

Copy Protection of Compute and Compare Programs

2021-12-12T10:10:10Z

Chirag:

The [https://arxiv.org/abs/2009.13865 example protocol] achieves the functionality of [[Copy Protection| Copy Protection]] allowing a Vendor to send a program to a Client such that the Client cannot duplicate it. This protocol, in particular, achieves copy-protection for 'compute-and-compare' programs.<br/><br/>

'''Tags:''' [[:Category:Two Party Protocols|Two Party Protocols]], [[:Category:Quantum Functionality|Quantum Functionality]], [[:Category:Universal Task|Universal Task]], Computational Security

==Assumptions==

* Vendor and Client are connected by quantum and classical channels
* Vendor can create and transmit BB84 states
* Client has the capability to perform universal quantum computation

==Outline==

Any Copy Protection protocol consists of two algorithms: '''Protect''' and '''Eval'''. For the family of compute-and-compare programs, these algorithms are described as follows:
*'''Protect''': The Vendor encodes the required qubits into BB84 states using the program description. The Vendor then calculates the output of some hash function on the program description as input. The encoded qubits and the hashed description are sent to the Client as output.
*'''Eval''': The Client decrypts the received qubits using the input on which they wish to evaluate the program. Using these qubits as inputs, the Client computes the same hash function (on ancillary qubits) and coherently compares it with the hashed description received from the vendor. The Client finally measures and outputs the result of the comparison.

==Notation==

* <math>P_y</math> : The point function to be copy-protected in [[#Protocol 1 - Copy protection of point functions|Protocol 1]]. <math>P_y</math> is completely specified by a string of <math>n</math> bits, <math>y</math>. <math>P_y(x) = 1</math> if <math>x = y</math> and <math>0</math> otherwise
* <math>CC[f,y]</math> : The compute-and-compare program to be copy-protected in [[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]]. It is completely specified by an efficiently computable function <math>f: \{0,1\}^n \rightarrow \{0,1\}^m</math> and a string of <math>m</math> bits, <math>y</math>. <math>CC[f,y](x)</math> is <math>1</math> if <math>f(x) = y</math> and <math>0</math> otherwise.
* <math>n</math> : Size of input string <math>x</math>
* <math>\lambda</math>: Security parameter
* <math>G : \{0,1\}^n \rightarrow \{0,1\}^{m(\lambda)} </math> (Hash function)
* <math>H : \{0,1\}^{m(\lambda)} \rightarrow \{0,1\}^\lambda </math> (Hash function)
* <math>|x^\theta\rangle = H^\theta |x\rangle = H^{\theta_1} \otimes ... \otimes H^{\theta_\lambda} |x\rangle</math>, where <math>\theta</math> is a <math>\lambda</math>-bit string <math>\theta_1,...,\theta_\lambda</math>




==Protocol Description==

First, we define a protocol for copy-protection of point functions. This protocol can then be extended to a protocol for compute-and-compare programs.
===Protocol 1 - Copy protection of point functions===
====PF-Protect(<math>\lambda,y</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>y</math> - description of point function <math>P_y</math>
* Set <math>\theta = G(y)</math>
* Sample <math>v \leftarrow \{0,1\}^{m(\lambda)}</math> uniformly at random
* Let <math>z = H(v)</math>
* Output (<math>|v^\theta\rangle,z</math>)

====PF-Eval(<math>\lambda,(\rho,z),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(\rho,z)</math> - Alleged copy-protected program; <math>x</math> - Input on which the program is to be evaluated
* Set <math>\theta^\prime = G(x)</math>
* Apply the Hadamard operator <math>H^{\theta^\prime}</math> to <math>\rho</math>
* Append <math>n+1</math> ancillary qubits to <math>\rho</math>, all in state <math>|0\rangle</math>
* Compute the hash function <math>H</math> onto the first <math>n</math> ancillary qubits with <math>\rho</math> as input
* Coherently measure whether the first <math>n</math> ancilla qubits are in state <math>|z\rangle</math>, recording the result in the last ancilla qubit
* Uncompute the hash function <math>H</math> and undo the Hadamards <math>H^{\theta^\prime}</math>
* Measure the last ancilla qubit to obtain a bit <math>b</math> as output

===Protocol 2 - Copy protection of compute-and-compare programs===
====CC-Protect(<math>\lambda,(f,y)</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,y)</math> - description of compute-and-compare program <math>CC[f,y]</math>
* Let <math>\rho = </math> '''PF-Protect'''(<math>\lambda,y</math>)
* Output (<math>f,\rho</math>)

====CC-Eval(<math>\lambda,(f,\rho),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,\rho)</math> - Alleged copy protected program; <math>x</math> - Input on which the program is to be evaluated
* Compute <math>y^\prime = f(x)</math>
* Let <math>b \leftarrow </math> '''PF-Eval'''(<math>\lambda,\rho,y^\prime</math>). Output <math>b</math>.

==Properties==

*[[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]] has provable non-trivial security in the quantum random oracle model. Informally, a query bounded adversary fails at pirating with at least some constant probability.
*The Client should be able to perform universal quantum computation in order to compute the hash function <math>H</math>
*The protected programs obtained in both protocols allow polynomially-many evaluations (as we evaluate the copy-protected programs reversibly).
*[[#Protocol 1 - Copy protection of point functions|Protocol 1]] also satisfies the primitive of Virtual Black Box Obfuscation
*By adding a verification step, [[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]] can be extended to the weaker primitive of Secure Software Leasing. This protocol for Secure Software Leasing does however provide a standard level of security, i.e. the adversarial success probability is negligible in the security parameter.

==Further Information==

For the security proof and extension of the protocols to other functionalities, refer to the same paper by [http://arxiv.org/abs/2009.13865 Coladangelo et al. (2020)]
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>

Protocol Library

2021-12-09T16:57:22Z

Chirag: Added link to Copy Protection for Compute and Compare Programs

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="1"|[[Authentication of Quantum Messages]]||[[Polynomial Code based Quantum Authentication]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|[[Verification of Universal Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of Sub-Universal Quantum Computation]]||[[-]]
|-
|[[Verification of NP-complete problems]]||[[-]]
|-
|[[Classical Verification of Universal Quantum Computation]]||[[-]]
|-
|rowspan="4"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="1"|[[Entanglement Routing]]||[[Distributing Graph States Over Arbitrary Quantum Networks]]

Copy Protection of Compute and Compare Programs

2021-12-09T16:07:11Z

Chirag: Created page for copy protection of compare and compute programs

The [https://arxiv.org/abs/2009.13865 example protocol] achieves the functionality of [[Copy Protection| Copy Protection]] allowing a Vendor to send a program to a Client such that the Client cannot duplicate it. This protocol, in particular, achieves copy-protection for 'compute-and-compare' programs.<br/><br/>

'''Tags:''' [[:Category:Two Party Protocols|Two Party Protocols]], [[:Category:Quantum Functionality|Quantum Functionality]], [[:Category:Universal Task|Universal Task]], Computational Security

==Assumptions==

* Vendor and Client are connected by quantum and classical channels
* Vendor can create and transmit BB84 states
* Client has the capability to perform universal quantum computation

==Outline==

Any Copy Protection protocol consists of two algorithms: '''Protect''' and '''Eval'''. For the family of compute-and-compare programs, these algorithms are described as follows:
*'''Protect''': The Vendor encodes λ qubits into BB84 states using the program description. The Vendor then calculates the output of some hash function on the program description as input. The encoded qubits and the hashed description are sent to the Client as output.
*'''Eval''': The Client decrypts the received qubits using the input on which they wish to evaluate the program. Using these qubits as inputs, the Client computes the same hash function (on ancillary qubits) and coherently compares it with the hashed description received from the vendor. The Client finally measures and outputs the result of the comparison.

==Notation==

* <math>P_y</math> : The point function to be copy-protected in [[#Protocol 1 - Copy protection of point functions|Protocol 1]]. <math>P_y</math> is completely specified by a string of <math>n</math> bits, <math>y</math>. <math>P_y(x) = 1</math> if <math>x = y</math> and <math>0</math> otherwise
* <math>CC[f,y]</math> : The compute-and-compare program to be copy-protected in [[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]]. It is completely specified by an efficiently computable function <math>f: \{0,1\}^n \rightarrow \{0,1\}^m</math> and a string of <math>m</math> bits, <math>y</math>. <math>CC[f,y](x)</math> is <math>1</math> if <math>f(x) = y</math> and <math>0</math> otherwise.
* <math>n</math> : Size of input string <math>x</math>
* <math>\lambda</math>: Security parameter
* <math>G : \{0,1\}^n \rightarrow \{0,1\}^{m(\lambda)} </math> (Hash function)
* <math>H : \{0,1\}^{m(\lambda)} \rightarrow \{0,1\}^\lambda </math> (Hash function)
* <math>|x^\theta\rangle = H^\theta |x\rangle = H^{\theta_1} \otimes ... \otimes H^{\theta_\lambda} |x\rangle</math>, where <math>\theta</math> is a <math>\lambda</math>-bit string <math>\theta_1,...,\theta_\lambda</math>




==Protocol Description==

First, we define a protocol for copy-protection of point functions. This protocol can then be extended to a protocol for compute-and-compare programs.
===Protocol 1 - Copy protection of point functions===
====PF-Protect(<math>\lambda,y</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>y</math> - description of point function <math>P_y</math>
* Set <math>\theta = G(y)</math>
* Sample <math>v \leftarrow \{0,1\}^{m(\lambda)}</math> uniformly at random
* Let <math>z = H(v)</math>
* Output (<math>|v^\theta\rangle,z</math>)

====PF-Eval(<math>\lambda,(\rho,z),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(\rho,z)</math> - Alleged copy-protected program; <math>x</math> - Input on which the program is to be evaluated
* Set <math>\theta^\prime = G(x)</math>
* Apply the Hadamard operator <math>H^{\theta^\prime}</math> to <math>\rho</math>
* Append <math>n+1</math> ancillary qubits to <math>\rho</math>, all in state <math>|0\rangle</math>
* Compute the hash function <math>H</math> onto the first <math>n</math> ancillary qubits with <math>\rho</math> as input
* Coherently measure whether the first <math>n</math> ancilla qubits are in state <math>|z\rangle</math>, recording the result in the last ancilla qubit
* Uncompute the hash function <math>H</math> and undo the Hadamards <math>H^{\theta^\prime}</math>
* Measure the last ancilla qubit to obtain a bit <math>b</math> as output

===Protocol 2 - Copy protection of compute-and-compare programs===
====CC-Protect(<math>\lambda,(f,y)</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,y)</math> - description of compute-and-compare program <math>CC[f,y]</math>
* Let <math>\rho = </math> '''PF-Protect'''(<math>\lambda,y</math>)
* Output (<math>f,\rho</math>)

====CC-Eval(<math>\lambda,(f,\rho),x</math>)====
''Inputs'': <math>\lambda</math> - security parameter; <math>(f,\rho)</math> - Alleged copy protected program; <math>x</math> - Input on which the program is to be evaluated
* Compute <math>y^\prime = f(x)</math>
* Let <math>b \leftarrow </math> '''PF-Eval'''(<math>\lambda,\rho,y^\prime</math>). Output <math>b</math>.

==Properties==

*[[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]] has provable non-trivial security in the quantum random oracle model. Informally, a query bounded adversary fails at pirating with at least some constant probability.
*The Client should be able to perform universal quantum computation in order to compute the hash function <math>H</math>
*The protected programs obtained in both protocols allow polynomially-many evaluations (as we evaluate the copy-protected programs reversibly).
*[[#Protocol 1 - Copy protection of point functions|Protocol 1]] also satisfies the primitive of Virtual Black Box Obfuscation
*By adding a verification step, [[#Protocol 2 - Copy protection of compute-and-compare programs|Protocol 2]] can be extended to the weaker primitive of Secure Software Leasing. This protocol for Secure Software Leasing does however provide a standard level of security, i.e. the adversarial success probability is negligible in the security parameter.

==Further Information==

For the security proof and extension of the protocols to other functionalities, refer to the same paper by [http://arxiv.org/abs/2009.13865 Coladangelo et al. (2020)]