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

## Contents

## 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. - Following the generation rounds, the honest sender outputs two randomly generated strings of equal length, and the honest receiver outputs their chosen string out of the two.

## Notation

- : The sender
- : The receiver
- : Length of the output strings
- : The strings output by the sender
- : A bit denoting the receiver's choice
- For any bit , [
**Computational, Hadamard**]

- For bits
- An ENTCF family consists of two families of function pairs: and . A function pair is indexed by a public key . If , then it is a
*claw-free pair*; and if , then it is called an*injective pair*. ENTCF families satisfy the following properties:- For a fixed and are bijections with the same image; for every image , there exists a unique pair , called a
*claw*, such that - Given a
*key*, for a claw-free pair, it is quantum-computationally intractable (without access to*trapdoor*information) to compute both a and a single generalized bit of , where forms a valid claw. This is known as the*adaptive hardcore bit*property. - For a fixed and are injunctive functions with disjoint images.
- Given a key , it is quantum-computationally hard (without access to
*trapdoor*information) to determine whether is a key for a claw-free or an injective pair. This property is known as*injective invariance*. - For every , there exists a trapdoor which can be sampled together with and with which 2 and 4 are computationally easy.

- For a fixed and are bijections with the same image; for every image , there exists a unique pair , called a

## Protocol Description

### Protocol 1: Rand 1-2 OT

- 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 .
- 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 - 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 - picks two uniformly random hash functions , announces and to and outputs and where
**Computational,Hadamard** - outputs

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

- 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. - Alice and Bob receive strings and , respectively, from the device.
- Alice chooses a
*challenge type*, uniformly at random and sends it to Bob. Alice and Bob then send to each component of their device. - If :
- Alice and Bob receive strings and , respectively, from the device.

- If :
- Alice and Bob receive strings and , respectively, from the device.
- Alice chooses uniformly random
*measurement bases (questions)*{**Computational,Hadamard**} and sends to Bob. Alice and Bob then, respectively, send and to the device. - 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:**

- 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

- If , then with probability , the receiver does not use the measurement basis question supplied by the sender and instead inputs
- For every the sender stores the variable (round type), defined as follows:
- if and
**Hadamard**, then**Bell** - else, set
**Product**

- if and
- 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:**

- if
- 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. - 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:**

- 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. - For each the sender calculates and defines by
- and the receiver calculates and defines by
**Obtaining output:**

- The sender randomly picks two hash functions , announces and for each , and outputs and , where
**Computational,Hadamard** - Receiver outputs

## Properties

## Further Information

## References

**contributed by Chirag Wadhwa*