Editing Device-Independent Oblivious Transfer

Jump to navigation Jump to search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
Line 11: Line 11:
* The device used is computationally bounded - it cannot solve the Learning with Errors (LWE) problem 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
* 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==
==Outline==
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->
* 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==
==Notation==
<!--  Connects the non-mathematical outline with further sections. -->
<!--  Connects the non-mathematical outline with further sections. -->
* <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.
<!-- ==Knowledge Graph== -->
<!-- ==Knowledge Graph== -->
<!-- Add this part if the protocol is already in the graph -->
<!-- Add this part if the protocol is already in the graph -->
Line 47: Line 24:
==Protocol Description==
==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
===Protocol 1: Rand 1-2 OT<math>^l</math>===
===Protocol 1: DI 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:'''
::'''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:
# 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:
Line 104: Line 48:
# 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.
# 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.
<!-- INCLUDE V_i^ALPHA CALCULATION -->
<!-- INCLUDE V_i^ALPHA CALCULATION -->
# 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
# For each <math>i \in \tilde{I},</math> the sender calculates <math>v_i^{\alpha}</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>
#:<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
#: and the receiver calculates <math>v_i^{\beta}</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>
#:<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:'''
#: '''Obtaining output:'''
Line 113: Line 57:




===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.
==Properties==
==Properties==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->
* <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>
==Further Information==
*: Protocol 3 is <math>\epsilon^{\prime}</math>-sender secure, where <math>\epsilon^{\prime}</math> can be made negligible in certain conditions.
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... -->


==References==
==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>
<div style='text-align: right;'>''*contributed by Chirag Wadhwa''</div>
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Quantum Protocol Zoo:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)
Retrieved from "https://wiki.veriqloud.fr/index.php?title=Device-Independent_Oblivious_Transfer"