Device-Independent Oblivious Transfer: Difference between revisions

no edit summary
(Created page for DIOT)
 
No edit summary
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... -->
Write
33

edits