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.