# oblivious-transfer: An implementation of the Oblivious Transfer protocol in Haskell

[ cryptography, library ] [ Propose Tags ]

## Modules

[Index] [Quick Jump]

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

#### Maintainer's Corner

For package maintainers and hackage trustees

[back to package description]

Oblivious Transfer (OT) is a cryptographic primitive in which a sender transfers some of potentially many pieces of information to a receiver. The sender doesn't know which pieces of information have been transferred.

# 1-out-of-2 OT

Oblivious transfer is central to many of the constructions for secure multiparty computation. In its most basic form, the sender has two secret messages as inputs, m<sub>0</sub> and m<sub>1</sub>; the receiver has a choice bit c as input. At the end of the 1-out-of-2 OT protocol, the receiver should only learn message M<sub>c</sub>, while the sender should not learn the value of the receiver's input c.

The protocol is defined for elliptic curves over finite fields E(F<sub>q</sub>). The set of points E(F<sub>q</sub>) is a finite abelian group. It works as follows:

1. Alice samples a random a and computes A = aG. Sends A to Bob

2. Bob has a choice c. He samples a random b.

• If c is 0, then he computes B = bG.
• If c is 1, then he computes B = A + bG.

Sends B to Alice

3. Alice derives two keys:

• K<sub>0</sub> = aB
• K<sub>1</sub> = a(B - A)

It's easy to check that Bob can derive the key K<sub>c</sub> corresponding to his choice bit, but cannot compute the other one.

# 1-out-of-N OT

The 1-out-of-N oblivious transfer protocol is a natural generalization of the 1-out-of-2 OT protocol, in which the sender has a vector of messages (M<sub>0</sub>, ..., M<sub>n-1</sub>). The receiver only has a choice c.

We implement a protocol for random OT, where the sender, Alice, outputs n random keys and the receiver, Bob, only learns one of them. It consists on three parts:

Setup

Alice samples a ∈ Z<sub>p</sub> and computes A = aG and T = aA, where G and p are the generator and the order of the curve, respectively. She sends A to Bob, who aborts if A is not a valid point in the curve.

Choose

Bob takes his choice c ∈ Z<sub>n</sub>, samples b ∈ Z<sub>p</sub> and replies R = cA + bG. Alice aborts if R is not a valid point in the curve.

Key derivation

1. For all e ∈ Z<sub>n</sub>, Alice computes k<sub>e</sub> = aR - eT. She now has a vector of keys (k<sub>0</sub>, ..., k<sub>n-1</sub>).

2. Bob computes k<sub>R</sub> = bA.

We can see that the key k<sub>e</sub> = aR - eT = abG + (c - e)T. If e = c, then k<sub>c</sub> = abG = bA = k<sub>R</sub>. Therefore, k<sub>R</sub> = k<sub>c</sub> if both parties are honest.

testOT :: ECC.Curve -> Integer -> IO Bool
testOT curve n = do

-- Alice sets up the procotol
(sPrivKey, sPubKey, t) <- OT.setup curve

-- Bob picks a choice bit 'c'
(rPrivKey, response, c) <- OT.choose curve n sPubKey

-- Alice computes a set of n keys
let senderKeys = OT.deriveSenderKeys curve n sPrivKey response t

-- Bob only gets to know one out of n keys. Alice doesn't know which one

pure \$ receiverKey == (senderKeys !! fromInteger c)


# k-out-of-N OT

1-out-of-N oblivious transfer can be generalised one step further into k-out-of-N. This is very similar in structure to the methods above comprising the same 3 parts:

Setup As above, Alice samples a ∈ Z<sub>p</sub> and computes A = aG and T = aA, where G and p are the generator and the order of the curve, respectively. She sends A to Bob, who aborts if A is not a valid point in the curve.

Choose Bob takes his choices c<sup>i</sup> ∈ Z<sub>n</sub>, samples b<sup>i</sup> ∈ Z<sub>p</sub> and replies R<sup>i</sup> = c<sup>i</sup>A + b<sup>i</sup>G. Alice aborts if R<sup>i</sup> is not a valid point in the curve.

Key derivation

1. For all e<sup>i</sup> ∈ Z<sub>n</sub>, Alice computes k<sub>e</sub><sup>i</sup> = aR<sup>i</sup> - e<sup>i</sup>T. She now has a vector of vectors of keys (k<sub>0</sub><sup>i</sup>, ..., k<sub>n-1</sub><sup>i</sup>).

2. Bob computes k<sub>R</sub><sup>i</sup> = b<sup>i</sup>A.

We can see that the key k<sub>e</sub><sup>i</sup> = aR<sup>i</sup> - e<sup>i</sup>T = ab<sup>i</sup>G + (c<sup>i</sup> - e<sup>i</sup>)T. If e = c, then k<sub>c</sub><sup>i</sup> = ab<sup>i</sup>G = b<sup>i</sup>A = k<sub>R</sub><sup>i</sup>. Therefore, k<sub>R</sub><sup>i</sup> = k<sub>c</sub><sup>i</sup> if both parties are honest.

References:

1. Chou, T. and Orlandi, C. "The Simplest Protocol for Oblivious Transfer" Technische Universiteit Eindhoven and Aarhus University

Notation:

k: Lower-case letters are scalars. <br /> P: Upper-case letters are points in an elliptic curve. <br /> kP: Multiplication of a point P with a scalar k over an elliptic curve defined over a finite field modulo a prime number.

Copyright 2018 Adjoint Inc