]> Cryptography - Oblivious Transfer (OT)

1-out-of-n Oblivious Transfer

Suppose A has a list (x 1 ,...,x n), B has i{1 ,...,n}.

We want a SFE protocol where F A=0 ,F B=x i, that is,

  1. B learns x i and nothing else

  2. A learns nothing about i

Theorem: [Kilian'87] 1-out-of-2 OT is universal for 2-party SFE

In other words, given a 1-out-of-2 OT protocol, one can do any 2-party SFE. (Yao's construction requires a block cipher in addition to a 1-out-of-2 OT protocol.)

Note that oblivious transfer implies 2-party SFE, which implies key exchange, and hence 1-out-of-2 OT cannot be built from a blackbox one-way function. Instead, we build one using the DDH assumption [Bellare-Micali'92].

Bellare-Micali Construction

Let G be a group of prime order p, and let gG be a generator, and H:G{0,1 } n be a hash function.

Suppose A has x 0 ,x 1 {0,1 } n, and B has b{0,1 }.

  1. A publishes a random cG, B picks k p, sets PK b=g K,PK 1 b=c/g k and sends PK 0 ,PK 1 to A. A checks PK 0 PK 1 =c.

  2. A encrypts x 0 with El Gamal using PK 0 , i.e. sets C 0 =[g r 0 ,H(PK 0 r 0 )x 0 ], encrypts x 1 using PK 1 , and sends C 0 ,C 1 to B.

  3. B decrypts C b using K, i.e. if C b=[V 1 ,V 2 ], B computes X b=H(V 1 K)V 2 .

Security: A cannot learn anything about b (information theoretic result).

If B is honest-but-curious, then assuming DDH, B can only decrypt one of C 0 or C 1 .

If B is malicious, then assuming DDH is not enough: conceivably B could generate PK 0 ,PK 1 in such a way that B knows partial information about their corresponding private keys, and perhaps B can then learn partial information about both x 0 and x 1 . However, if H is a random oracle, then the protocol is secure under CDH.

Naor-Pinkas Construction

[Naor, Pinkas '00] Let G be a group of prime order q and let gG be a generator. Suppose A has m 0 ,m 1 and B has V{0,1 }.

  1. B sends the tuple (g,x=g a,y=g b,z 0 =g c 0 ,z 1 =g c 1 to A, where a,b q, c v=ab and c 1 v q.

  2. A verifies that z 0 z 1 and applies a partial DDH random self-reduction: (g,x,y,z 0 ) becomes T 0 =(g,x,y 0 ,z 0 ), and (g,x,y,z 1 ) becomes T 1 =(g,x,y 1 ,z 1 ).

  3. A encrypts m 0 using T 0 and m 1 using T 1 , that is, A sends to B the ciphertexts (CT 0 =(y 0 ,mz 0 ),CT 1 =(y 1 ,mz 1 )).

  4. B decrypts CT v.

This protocol is information theoretically secure against B, and DDH secure against A. The random self-reduction destroys any partial information in the message B sends to A. Note that this construction also generalizes to a 1-out-of-n protocol.

DDH Random Self-Reduction

Suppose we have a tuple g,g x,g y,g z. Then to perform a random self-reduction, pick random a,b p *, and output g,g (x+b)a,g y,g (z+by)a.

Note that this transformation takes DH-tuples to DH-tuples, and non-DH-tuples to non-DH-tuples. Furthermore, the new exponents are independent of the originals. This is easy to see if we start with a DH tuple. On the other hand, if the tuple is not DH, then given any x,z, there exists a unique a,b such that (x+b)a=x,(z+by)a=z (we can solve to get a=(zxy)/(zxy) and b can be easily determined from a). As expected, these solutions are not well defined if z=xy, i.e. the original tuple is DH.

1-out-of-n From 1-out-of-2

We show how to construct a 1-out-of-n OT protocol from any 1-out-of-2 OT protocol.

Suppose A has m 0 ,...,m N{0,1 } n and B has t{0 ,...,N}. Assume N=2 l1 for some l.

  1. A prepares 2 l keys (K 1 0 ,K 1 1 ),...,(K l 0 ,K l 1 ).

  2. Let F k:{0,1 } l{0,1 } n be a PRF. A sends to B the tuple (C 0 ,...,C N): view the message index as a bit string I=I 1 ...I l{0,1 } l, and encrypt using

    C I=m I i=1 lF K i I i(I)

    Note A sends O(N) bits to B.

  3. Let t=t 1 ...t l{0,1 } l. Then l 1-out-of-2 OT's are performed where during the jth OT, A has (K j 0 ,K j 1 ) and B has t j{0,1 }.

  4. B now has K 1 t 1 ,...,K l t l and can decrypt C t to get m t.

Thus with logN 1-out-of-2 OT's, a single 1-out-of-N OT can be constructed, that has O(N) communication complexity.