Computer Science Colloquium, 2002-2003

Kobbi Nissim
DIMACS, Rutgers University
December 18, 2002

Efficient Oblivious Computation

Assume Alice and Bob each holds an $n$ bit number. How may they decide whose value is larger in a way that leaks no other information? This problem is well known as the Millionaires Problem - one of the first problems to be considered in the context of secure function evaluation [Yao82].

Consider any function $f$ over the private inputs of Alice and Bob. A major plausibility result states that ``If $f$ may be computed using polynomial resources then it may be computed securely using polynomial resources''. This result follows by a transformation from a circuit computing $f$ to a secure protocol computing $f$, known as the garbled circuit transformation. However, the garbled circuit transformation usually yields very inefficient protocols, especially when compared with the non-secure version. E.g. for the Millionaires Problem it yields protocols with $\Omega(n)$ communication whereas the communication complexity of the non-secure computation is $O(polylog n)$.

The talk will focus on two improvements on the efficiency of secure protocols. First, we will present some new transformations, that unlike the garbled circuit transformation allow for sub-linear communication complexity. As an application, we get the first sub-linear protocols for the Millionairs Problem. Then, we consider one of the basic components of secure computation - Oblivious Transfer (OT) - that usually incures most of the computation/communication costs in protocols. We will present an efficient method of extending OTs. I.e. a way of implementing a large number of OTs given just a small number of them.

- M. Naor and K. Nissim, Communication Preserving Protocols for Secure Function Evaluation.
- J. Kilian, K. Nissim and E. Petrank, Extending Oblivious Transfers Efficienctly.


Shuly Wintner
Last modified: Thu Dec 5 11:16:46 IST 2002