Device-Independent Oblivious Transfer

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

Protocol Description

Protocol 1: DI Rand 1-2 OT$^{l}$

Data generation:

1. The sender and receiver execute $n$ rounds of Protocol 2 (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:

   If $CT_{i}=b$, then with probability $p$, the receiver does not use the measurement basis question supplied by the sender and instead inputs $y_{i}=[$Computational, Hadamard$]_{c}$ where Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle c} is the receiver's choice bit. Let $I$ be the set of indices marking the rounds where this has been done.

   For each round Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i\in \{1,...,n\}} , the receiver stores:

   • $c_{i}^{B}$
   • $z_{i}^{B}$ if $CT_{i}=a$
   • or $(d_{i}^{B},y_{i},b_{i},h_{i}^{B})$ if $CT_{i}=b$

   The sender stores $\theta _{i}^{A},\theta _{i}^{B},(k_{i}^{A},t_{i}^{A}),(k_{i}^{B},t_{i}^{B}),c_{i}^{A},CT_{i};$ and $z_{i}^{A}$ if $CT_{i}=a$ or $(d_{i}^{A},x_{i},a_{i},h_{i}^{A})$ and $y_{i}$ if $CT_{i}=b$

2. For every $i\in \{1,...,n\},$ the sender stores the variable $RT_{i}$ (round type), defined as follows:
   • if $CT_{i}=b$ and $\theta _{i}^{A}=\theta _{i}^{B}=$Hadamard, then $RT_{i}=$ Bell
   • else, set $RT_{i}=$ Product
3. For every $i\in \{1,...,n\},$ the sender chooses $T_{i}$, indicating a test round or generation round, as follows:
   • if $RT_{i}=$ Bell, choose $T_{i}\in$ {Test, Generate} uniformly at random
   • else, set $T_{i}=$ Test

   The sender sends ($T_{1},...,T_{n}$) to the receiver

   Testing:

4. The receiver sends the set of indices $I$ to the sender. The receiver publishes their output for all $T_{i}=$ Test rounds where $i\notin I$. 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 $\epsilon$, the protocol aborts

   Preparing data:

6. Let ${\tilde {I}}:=\{i:i\in I$ and $T_{i}=$ Generate} and $n^{\prime }=|{\tilde {I}}|$. The sender checks if there exists a $k>0$ such that $\gamma n^{\prime }\leq n^{\prime }/4-2l-kn^{\prime }$. If such a $k$ exists, the sender publishes ${\tilde {I}}$ and, for each $i\in {\tilde {I}}$, the trapdoor $t_{i}^{B}$ corresponding to the key Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k_{i}^{B}} (given by the sender in the execution of Protocol 2,Step 1); otherwise the protocol aborts.
7. For each $i\in {\tilde {I}},$ the sender calculates Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v_{i}^{\alpha }} and defines $w^{\alpha }$ by

   Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{i}^{\alpha }={\begin{cases}v_{i}^{\alpha },{\mbox{if }}x_{i}={\mbox{Hadamard}}\\0,{\mbox{if }}x_{i}={\mbox{Computational}}\end{cases}}}

   and the receiver calculates Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v_{i}^{\beta }} and defines $w^{\beta }$ by

   $w_{i}^{\beta }={\begin{cases}0,{\mbox{if }}y_{i}={\mbox{Hadamard}}\\v_{i}^{\beta },{\mbox{if }}y_{i}={\mbox{Computational}}\end{cases}}$

   Obtaining output:

8. The sender randomly picks two hash functions Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f_{0},f_{1}\in F} , announces $f_{0},f_{1}$ and $x_{i}$ for each $i\in {\tilde {I}}$, and outputs Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle s_{0}=f_{0}(a\oplus w^{\alpha }|_{{\tilde {I}}_{0}})} and $s_{1}=f_{1}(a\oplus w^{\alpha }|_{{\tilde {I}}_{1}})$, where ${\tilde {I}}_{r}:=\{i\in {\tilde {I}}:x_{i}=[$Computational,HadamardFailed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ]_{r}\}}
9. Receiver outputs $s_{c}=f_{c}(a\oplus w^{\beta }|_{{\tilde {I}}_{c}})$

Protocol 2: Self-testing with a single verifier

1. Alice chooses the state bases $\theta ^{A},\theta ^{B}\in$ {Computational,Hadamard} uniformly at random and generates key-trapdoor pairs Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (k^{A},t^{A}),(k^{B},t^{B})} , where the generation procedure for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k^{A}} and $t^{A}$ depends on Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \theta ^{A}} and a security parameter $\eta$, and likewise for Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k^{B}} and $t^{B}$. Alice supplies Bob with $k^{B}$. Alice and Bob then respectively send $k^{A},k^{B}$ to the device.
2. Alice and Bob receive strings $c^{A}$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle c^{B}} , respectively, from the device.
3. Alice chooses a challenge type Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle CT\in \{a,b\}} , uniformly at random and sends it to Bob. Alice and Bob then send Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle CT} to each component of their device.
4. If Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle CT=a} :
   1. Alice and Bob receive strings $z^{A}$ and $z^{B}$, respectively, from the device.
5. If $CT=b$:
   1. Alice and Bob receive strings Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d^{A}} and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d^{B}} , respectively, from the device.
   2. Alice chooses uniformly random measurement bases (questions) $x,y\in$ {Computational,Hadamard} and sends $y$ to Bob. Alice and Bob then, respectively, send $x$ and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} to the device.
   3. Alice and Bob receive answer bits Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} , respectively, from the device. Alice and Bob also receive bits Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h^A} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h^B} , respectively, from the device.

References

*contributed by Chirag Wadhwa