Extending Oblivious Transfers Efficiently Yuval Ishai Technion Joe Kilian NEC Kobbi Nissim Erez Petrank Microsoft Technion Motivation x y f(x,y) How (in)efficient is generic secure computation? myth dont even think about it garbled circuit method THIS WORK O(|x|) pub. O(|f|) sym.

k pub. O(|f|+|x|) sym. sftp f.txt Road Map Extending OTs Extending primitives Reductions Cryptographic primitives A Taxonomy of Primitives Symmetric encryption Public-key encryption Commitment Key agreement PRG Oblivious transfer Collision resistant hashing Secure function evaluation here you go r u kidding?

check this out nice try check this out r u kidding? crack this!!! hmmm crack this!!! r u kidding? here you go r u kidding? Symmetric encryption Public-key encryption Commitment Key agreement PRG Oblivious transfer Collision resistant hashing Secure function evaluation easy to implement heuristically

(numerous candidates, may rely on structureless functions) hard to implement heuristically (few candidates, rely on specific algebraic structures) very cheap in practice more expensive by orders of magnitude Major challenge: bridge efficiency gap Reductions in Cryptography Motivated by minimizing assumptions gaining efficiency Reduction from Y to X: a mapping f such that if A implements X then f(A) implements Y. Cannot be ruled out when Y is believed to exist. Black-box reduction: f(A) makes a black-box use of A; Black-box proof of security: Adversary breaking f(A) can be used as a black box to break A. Almost all known reductions are black-box. Non-black-box reductions are inefficient in practice. Can

be reduced to ? Impagliazzo-Rudich [IR89]: No black-box reduction exists. In fact, even a random oracle unlikely to yield Extending Primitives [IR] ? Extending Y using X: Realizing n instances of Y by making k (black-box) calls to Y, k

mn + m1 m2 mn Extending PKE is easy Huge impact on our everyday use of encryption. Symmetric encryption Public-key encryption Commitment Key agreement PRG Oblivious transfer Collision resistant hashing Secure function evaluation This work: Establish a similar result for remaining tasks. Oblivious Transfer (OT) Several equivalent flavors [Rab81,EGL86,BCR87] 2 1 -OT:

Receiver r {0,1} Sender x0,x1 {0,1}l xr ??? Formally defined as an instance of secure 2-party computation: OT(r, ) = (xr , ) Extensively used in general secure computation protocols [Yao86,GV87,Kil88,GMW88] Yaos protocol: # of OTs = # of input bits special-purpose protocols Auctions [NPS99], shared RSA [BF97,Gil99], information retrieval [NP99], data mining [LP00,CIKRRW01], Cost of OT OT is at least as expensive as key-agreement. OTs form the efficiency bottleneck in many protocols. OT count has become a common efficiency measure. Some amortization was obtained in [NP01]. Cost of OT is pretty much insensitive to l Most direct OT implementations give l = security parameter for free Handle larger l via use of a PRG r x0

x1 efficient, black-box r s0 s1 + G(s0) x0 G(s1) x1 Extending Oblivious Transfers OT OT OT OT OT OT OT OT

OT OT OT OT OT OT OT OT OT OT OT OT OT OT OT OT OT OT OT

OT OT OT OT OT OT OT OT OT OT ? OT OT OT OT OT + Beaver 96: OT can be extended using a PRG!! Thm. If PRG exists, then k OTs can be extended to n=kc OTs. However:

Extension makes a non-black-box use of underlying PRG. Numerous PRG invocations Huge communication complexity Unlikely to be better than direct OT implementations Can OT be extended via a black-box reduction? Our Result OT OT OT OT OT OT OT OT OT OT OT OT OT OT

OT OT OT OT OT OT efficient, black-box OT OT OT OT OT OT OT OT OT OT OT

OT OT OT OT OT OT OT OT OT OT OT + = random oracle or = new type of hash function Strategy s1 r1 r2 r3 s2

sk x1,0 x1,1 s1 x2,0 x2,1 x3,0 n ... x3,1 ... . rn xn,0 s2 sk ... + O(n)H

Already saw xn,1 + O(n)H Notation k mi n mj M The Basic Protocol Receiver picks T R {0,1}nk Sender picks s R {0,1}k Sender obtains Q {0,1}nk ri=0 1 1 0 0 1

1 qi= ti ri=1 1 0 0 1 1 0 qi= ti s t1 t1 r s1 t2 t2

... tk tk t1 r r r s2 t2 ... tk r sk qi qi) i,0 = xi,0 i,0 H(i,

For 1 i n, Sender sends yi,0 yi,1 qiqis s) i,1 = xi,1 i,1 H(i, For 1 i n, Receiver outputs zi= yi,r i H(i, ti ti)i Security Receiver picks T R {0,1}nk Sender picks s R {0,1}k Sender learns nothing Q is uniformly random Sender obtains Q {0,1}nk ri=0 qi= ti ri=1 qi= ti s Receiver learns no additional info except w/neg prob. Must query H on (i, ti s) For 1 i n, Sender sends yi,0 = xi,0 H(i, qi) yi,1 = xi,1 H(i, qi s) For 1 i n, Receiver outputs zi= yi,r i H(i, ti)i Attack by a Malicious Receiver

0 0 0 0 0 0 0 1 0 0 0 0 0 0 s1 0 0 0 0 0 0 0 0 1 0 0 0 0 0

s2 ... 0 0 0 0 0 0 0 0 0 0 1 0 0 0 sk qi = { 0 , si=0 ei, si=1 Receiver can easily learn si given a-priori knowledge of xi,0 Recover mask H(i,qi) = yi,0 xi,0 Find si by querying H Handling Malicious Receivers Call Receiver well-behaved if each pair of rows are either identical or complementary. Security proof goes through as long as Receiver is well-behaved. Good behavior can be easily enforced via a cut-andchoose technique:

Run copies of the protocol using random inputs Sender challenges Receiver to reveal the pairs it used in /2 of the executions. Aborts if inconsistency is found. Remaining executions are combined. Efficiency Basic protocol is extremely efficient Seed of k OTs Very few invocations of H per OT. Cut-and-choose procedure multiplies costs by Receiver gets away with cheating w/prob 2-/2 very small suffices if some penalty is associated with cheating Optimizations Different cut-and-choose approach eliminates factor overhead to seed. Online version, where the number n of OTs is not known in advance. Eliminating the Random Oracle h:{0,1}k{0,1}l is correlation robust if fs(t) : h(s t) is a weak PRF. (t1, ,tn, h(s t1), , h(s tn)) is pseudorandom. s s s h s h h

s h s h h s h s h s s h h Correlation robust h can be used to instantiate H. Is this a reasonable primitive? simple definition satisfied by a random function many efficient candidates (SHA1, MD5, AES, ) Conclusions OTs can be efficiently extended by making an efficient

black-box use of a symmetric primitive. Theoretical significance Advances our understanding of relations between primitives Practical significance Amortized cost of OT can be made much lower than previously thought. Significant even if OT did not exist: Initial seed of OTs can be implemented by physical means, or using multi-party computation. Big potential impact on efficiency of secure computations Further Research Assumptions Can OT be extended using OWF as a black-box? Study correlation robustness Efficiency Improve efficiency in malicious case Scope Obtain similar results for primitives which do not efficiently reduce to OT Practical implications Has generic secure computation come to term?