This example protocol achieves the task of device-independent oblivious transfer in the bounded quantum storage model using a computational assumption.
Assumptions[edit]
- 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
Requirements[edit]
- Network Stage: Entanglement Distribution
- Classical communication between the parties
- Extended noisy trapdoor claw-free (ENTCF) function family
Outline[edit]
- 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[edit]
: 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.
Protocol Description[edit]
Protocol 1: Rand 1-2 OT
[edit]
Requirements: Entanglement distribution, classical communication
Input: Receiver - a bit
Output: Sender outputs randomly generated
, Receiver outputs
- 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![{\displaystyle ]_{r}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/844bdee236aa3442b189aec0adc9b394fa79f344)
outputs 
Protocol 2: Self-testing with a single verifier[edit]
Requirements: ENTCF function family, classical communication
- 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
[edit]
Requirements: Entanglement distribution, ENTCF function family, classical communication
Input: Receiver - a bit
Output: Sender outputs randomly generated
, Receiver outputs
- 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 
- For every
the sender stores the variable
(round type), defined as follows:
- if
and
Hadamard, then
Bell
- else, set
Product
- 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:
- 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![{\displaystyle ]_{r}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/844bdee236aa3442b189aec0adc9b394fa79f344)
- Receiver outputs

Properties[edit]
-Receiver security: If
is honest, then for any
, there exist random variables
such that Pr[
and
- Protocol 3 is perfectly receiver secure, i.e.
= 0
-Sender security: If S is honest, then for any
, there exist a random variable
such that
- Protocol 3 is
-sender secure, where
can be made negligible in certain conditions.
References[edit]
*contributed by Chirag Wadhwa