Difference between revisions of "Device-Independent Oblivious Transfer"

From Quantum Protocol Zoo
Jump to: navigation, search
(Created page for DIOT)
 
Line 24: 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: DI Rand 1-2 OT<math>^l</math>===
+
===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:'''
 
::'''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 48: Line 69:
 
# 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}</math> and defines <math>w^{\alpha}</math> by
+
# 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>
 
#:<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}</math> and defines <math>w^{\beta}</math> by
+
#: 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>
 
#:<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 57: Line 78:
  
  
===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... -->

Revision as of 18:19, 20 January 2022


This 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

Notation

Protocol Description

Protocol 1: Rand 1-2 OT

  1. A device prepares uniformly random Bell pairs , where the first qubit of each pair goes to along with the string , and the second qubit of each pair goes to along with the string .
  2. R measures all qubits in the basis Computational,Hadamard where is 's choice bit. Let be the outcome. then computes , where the -th entry of is defined by
  3. picks uniformly random Computational, Hadamard, and measures the -th qubit in basis . Let be the outcome. then computes , where the -th entry of is defined by
  4. picks two uniformly random hash functions , announces and to and outputs and where Computational,Hadamard
  5. outputs


Protocol 2: Self-testing with a single verifier

  1. Alice chooses the state bases {Computational,Hadamard} uniformly at random and generates key-trapdoor pairs , where the generation procedure for and depends on and a security parameter , and likewise for and . Alice supplies Bob with . Alice and Bob then respectively send to the device.
  2. Alice and Bob receive strings and , respectively, from the device.
  3. Alice chooses a challenge type , uniformly at random and sends it to Bob. Alice and Bob then send to each component of their device.
  4. If :
    1. Alice and Bob receive strings and , respectively, from the device.
  5. If :
    1. Alice and Bob receive strings and , respectively, from the device.
    2. Alice chooses uniformly random measurement bases (questions) {Computational,Hadamard} and sends to Bob. Alice and Bob then, respectively, send and to the device.
    3. Alice and Bob receive answer bits and , respectively, from the device. Alice and Bob also receive bits and , respectively, from the device.

Protocol 3: DI Rand 1-2 OT

Data generation:
  1. The sender and receiver execute rounds of Protocol 2 (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
    If , then with probability , the receiver does not use the measurement basis question supplied by the sender and instead inputs Computational, Hadamard where is the receiver's choice bit. Let be the set of indices marking the rounds where this has been done.
    For each round , the receiver stores:
    • if
    • or if
    The sender stores and if or and if
  2. For every the sender stores the variable (round type), defined as follows:
    • if and Hadamard, then Bell
    • else, set Product
  3. For every the sender chooses , indicating a test round or generation round, as follows:
    • if Bell, choose {Test, Generate} uniformly at random
    • else, set Test
    The sender sends () to the receiver
    Testing:
  4. The receiver sends the set of indices to the sender. The receiver publishes their output for all Test rounds where . Using this published data, the sender determines the bits which an honest device would have returned.
  5. The sender computes the fraction of test rounds (for which the receiver has published data for) that failed. If this exceeds some , the protocol aborts
    Preparing data:
  6. Let and Generate} and . The sender checks if there exists a such that . If such a exists, the sender publishes and, for each , the trapdoor corresponding to the key (given by the sender in the execution of Protocol 2,Step 1); otherwise the protocol aborts.
  7. For each the sender calculates and defines by
    and the receiver calculates and defines by
    Obtaining output:
  8. The sender randomly picks two hash functions , announces and for each , and outputs and , where Computational,Hadamard
  9. Receiver outputs


Properties

Further Information

References

*contributed by Chirag Wadhwa