# Difference between revisions of "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

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

• ${\displaystyle S}$: The sender
• ${\displaystyle R}$: The receiver
• ${\displaystyle l}$: Length of the output strings
• ${\displaystyle s_{0},s_{1}}$: The strings output by the sender
• ${\displaystyle c}$: A bit denoting the receiver's choice
• For any bit ${\displaystyle r}$, [Computational, Hadamard]${\displaystyle _{r}={\begin{cases}{\mbox{Computational, if }}r=0\\{\mbox{Hadamard, if }}r=1\end{cases}}}$
• ${\displaystyle \sigma _{X}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$
• ${\displaystyle \sigma _{Z}={\begin{pmatrix}1&0\\0&-1\end{pmatrix}}}$
• For bits ${\displaystyle 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}}}}$
• An ENTCF family consists of two families of function pairs: ${\displaystyle F}$ and ${\displaystyle G}$. A function pair ${\displaystyle (f_{k,0},f_{k,1})}$is indexed by a public key ${\displaystyle k}$. If ${\displaystyle (f_{k,0},f_{k,1})\in F}$, then it is a claw-free pair; and if ${\displaystyle (f_{k,0},f_{k,1})\in G}$, then it is called an injective pair. ENTCF families satisfy the following properties:
1. For a fixed ${\displaystyle k\in K_{F},f_{k,0}}$ and ${\displaystyle f_{k,1}}$ are bijections with the same image; for every image ${\displaystyle y}$, there exists a unique pair ${\displaystyle (x_{0},x_{1})}$, called a claw, such that ${\displaystyle f_{k,0}(x_{0})=f_{k,1}(x_{1})=y}$
2. Given a key ${\displaystyle k\in K_{F}}$, for a claw-free pair, it is quantum-computationally intractable (without access to trapdoor information) to compute both a ${\displaystyle x_{i}}$ and a single generalized bit of ${\displaystyle x_{0}\oplus x_{1}}$, where ${\displaystyle (x_{0},x_{1})}$ forms a valid claw. This is known as the adaptive hardcore bit property.
3. For a fixed ${\displaystyle k\in K_{G},f_{k,0}}$ and ${\displaystyle f_{k_{1}}}$ are injunctive functions with disjoint images.
4. Given a key ${\displaystyle k\in K_{F}\cup K_{G}}$, it is quantum-computationally hard (without access to trapdoor information) to determine whether ${\displaystyle k}$ is a key for a claw-free or an injective pair. This property is known as injective invariance.
5. For every ${\displaystyle k\in K_{F}\cup K_{G}}$, there exists a trapdoor ${\displaystyle t_{k}}$ which can be sampled together with ${\displaystyle k}$ and with which 2 and 4 are computationally easy.

## Protocol Description

### Protocol 1: Rand 1-2 OT${\displaystyle ^{l}}$

1. A device prepares ${\displaystyle n}$ uniformly random Bell pairs ${\displaystyle |\phi ^{(v_{i}^{\alpha },v_{i}^{\beta })}\rangle ,i=1,...,n}$, where the first qubit of each pair goes to ${\displaystyle S}$ along with the string ${\displaystyle v^{\alpha }}$, and the second qubit of each pair goes to ${\displaystyle R}$ along with the string ${\displaystyle v^{\beta }}$.
2. R measures all qubits in the basis ${\displaystyle y=[}$Computational,Hadamard${\displaystyle ]_{c}}$ where ${\displaystyle c}$ is ${\displaystyle R}$'s choice bit. Let ${\displaystyle b\in \{0,1\}^{n}}$ be the outcome. ${\displaystyle R}$ then computes ${\displaystyle b\oplus w^{\beta }}$, where the ${\displaystyle i}$-th entry of ${\displaystyle w^{\beta }}$ is defined by
${\displaystyle w_{i}^{\beta }:={\begin{cases}0,{\mbox{if }}y={\mbox{ Hadamard}}\\v_{i}^{\beta },{\mbox{if }}y={\mbox{ Computational}}\end{cases}}}$
3. ${\displaystyle S}$ picks uniformly random ${\displaystyle x\in \{}$ Computational, Hadamard${\displaystyle \}^{n}}$, and measures the ${\displaystyle i}$-th qubit in basis ${\displaystyle x_{i}}$. Let ${\displaystyle a\in \{0,1\}^{n}}$ be the outcome. ${\displaystyle S}$ then computes ${\displaystyle a\oplus w^{\alpha }}$, where the ${\displaystyle i}$-th entry of ${\displaystyle w^{\alpha }}$ is defined by
${\displaystyle w_{i}^{\alpha }:={\begin{cases}v_{i}^{\alpha },{\mbox{if }}x_{i}={\mbox{ Hadamard}}\\0,{\mbox{if }}x_{i}={\mbox{ Computational}}\end{cases}}}$
4. ${\displaystyle S}$ picks two uniformly random hash functions ${\displaystyle f_{0},f_{1}\in F}$, announces ${\displaystyle x}$ and ${\displaystyle f_{0},f_{1}}$ to ${\displaystyle R}$ and outputs ${\displaystyle s_{0}:=f_{0}(a\oplus w^{\alpha }|_{I_{0}})}$ and ${\displaystyle s_{1}:=f_{1}(a\oplus w^{\alpha }|_{I_{1}})}$ where ${\displaystyle I_{r}:=\{i\in I:x_{i}=[}$Computational,Hadamard${\displaystyle ]_{r}\}}$
5. ${\displaystyle R}$ outputs ${\displaystyle s_{c}=f_{c}(b\oplus w^{\beta }|_{I_{c}})}$

### Protocol 2: Self-testing with a single verifier

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

### Protocol 3: DI Rand 1-2 OT${\displaystyle ^{l}}$

Data generation:
1. The sender and receiver execute ${\displaystyle n}$ rounds of Protocol 2 (Self-testing) with the sender as Alice and receiver as Bob, and with the following modification:
If ${\displaystyle CT_{i}=b}$, then with probability ${\displaystyle p}$, the receiver does not use the measurement basis question supplied by the sender and instead inputs ${\displaystyle y_{i}=[}$Computational, Hadamard${\displaystyle ]_{c}}$ where ${\displaystyle c}$ is the receiver's choice bit. Let ${\displaystyle I}$ be the set of indices marking the rounds where this has been done.
For each round ${\displaystyle i\in \{1,...,n\}}$, the receiver stores:
• ${\displaystyle c_{i}^{B}}$
• ${\displaystyle z_{i}^{B}}$ if ${\displaystyle CT_{i}=a}$
• or ${\displaystyle (d_{i}^{B},y_{i},b_{i},h_{i}^{B})}$ if ${\displaystyle CT_{i}=b}$
The sender stores ${\displaystyle \theta _{i}^{A},\theta _{i}^{B},(k_{i}^{A},t_{i}^{A}),(k_{i}^{B},t_{i}^{B}),c_{i}^{A},CT_{i};}$ and ${\displaystyle z_{i}^{A}}$ if ${\displaystyle CT_{i}=a}$ or ${\displaystyle (d_{i}^{A},x_{i},a_{i},h_{i}^{A})}$ and ${\displaystyle y_{i}}$ if ${\displaystyle CT_{i}=b}$
2. For every ${\displaystyle i\in \{1,...,n\},}$ the sender stores the variable ${\displaystyle RT_{i}}$ (round type), defined as follows:
• if ${\displaystyle CT_{i}=b}$ and ${\displaystyle \theta _{i}^{A}=\theta _{i}^{B}=}$Hadamard, then ${\displaystyle RT_{i}=}$ Bell
• else, set ${\displaystyle RT_{i}=}$ Product
3. For every ${\displaystyle i\in \{1,...,n\},}$ the sender chooses ${\displaystyle T_{i}}$, indicating a test round or generation round, as follows:
• if ${\displaystyle RT_{i}=}$ Bell, choose ${\displaystyle T_{i}\in }$ {Test, Generate} uniformly at random
• else, set ${\displaystyle T_{i}=}$ Test
The sender sends (${\displaystyle T_{1},...,T_{n}}$) to the receiver
Testing:
4. The receiver sends the set of indices ${\displaystyle I}$ to the sender. The receiver publishes their output for all ${\displaystyle T_{i}=}$ Test rounds where ${\displaystyle 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 ${\displaystyle \epsilon }$, the protocol aborts
Preparing data:
6. Let ${\displaystyle {\tilde {I}}:=\{i:i\in I}$ and ${\displaystyle T_{i}=}$ Generate} and ${\displaystyle n^{\prime }=|{\tilde {I}}|}$. The sender checks if there exists a ${\displaystyle k>0}$ such that ${\displaystyle \gamma n^{\prime }\leq n^{\prime }/4-2l-kn^{\prime }}$. If such a ${\displaystyle k}$ exists, the sender publishes ${\displaystyle {\tilde {I}}}$ and, for each ${\displaystyle i\in {\tilde {I}}}$, the trapdoor ${\displaystyle t_{i}^{B}}$ corresponding to the key ${\displaystyle k_{i}^{B}}$ (given by the sender in the execution of Protocol 2,Step 1); otherwise the protocol aborts.
7. For each ${\displaystyle i\in {\tilde {I}},}$ the sender calculates ${\displaystyle v_{i}^{\alpha }=d_{i}^{A}.(x_{i,0}^{A}\oplus x_{i,1}^{A})}$ and defines ${\displaystyle w^{\alpha }}$ by
${\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 ${\displaystyle v_{i}^{\beta }==d_{i}^{B}.(x_{i,0}^{B}\oplus x_{i,1}^{B})}$ and defines ${\displaystyle w^{\beta }}$ by
${\displaystyle 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 ${\displaystyle f_{0},f_{1}\in F}$, announces ${\displaystyle f_{0},f_{1}}$ and ${\displaystyle x_{i}}$ for each ${\displaystyle i\in {\tilde {I}}}$, and outputs ${\displaystyle s_{0}=f_{0}(a\oplus w^{\alpha }|_{{\tilde {I}}_{0}})}$ and ${\displaystyle s_{1}=f_{1}(a\oplus w^{\alpha }|_{{\tilde {I}}_{1}})}$, where ${\displaystyle {\tilde {I}}_{r}:=\{i\in {\tilde {I}}:x_{i}=[}$Computational,Hadamard${\displaystyle ]_{r}\}}$
9. Receiver outputs ${\displaystyle s_{c}=f_{c}(a\oplus w^{\beta }|_{{\tilde {I}}_{c}})}$

## Properties

• ${\displaystyle \epsilon }$-Receiver security: If ${\displaystyle R}$ is honest, then for any ${\displaystyle {\tilde {S}}}$, there exist random variables ${\displaystyle S_{0}^{\prime },S_{1}^{\prime }}$ such that Pr[${\displaystyle Y=S_{c}^{\prime }]\geq 1-\epsilon }$ and ${\displaystyle 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 }$
Protocol 3 is perfectly receiver secure, i.e. ${\displaystyle \epsilon }$ = 0
• ${\displaystyle \epsilon }$-Sender security: If S is honest, then for any ${\displaystyle {\tilde {R}}}$, there exist a random variable ${\displaystyle c^{\prime }}$ such that ${\displaystyle 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 }$
Protocol 3 is ${\displaystyle \epsilon ^{\prime }}$-sender secure, where ${\displaystyle \epsilon ^{\prime }}$ can be made negligible in certain conditions.