|
Computer Sciences Seminar Efficient Oblivious Computation
Kobbi Nissin Abstract 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]. A major plausibility result answers this positively for any feasible function $f$ over the private inputs of Alice and Bob: ``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, comparing $n$-bit numbers, it yields protocols with $\Omega(n)$ communication whereas the communication complexity of the non-secure computation is $O(polylog n)$. In the talk we will explore several approaches to achieving efficient secure function evaluation protocols, including (i) Private approximations, where one is willing to approximate $f$ without leaking information or with a controled amount of leakage, (ii) New communication preserving transformations from insecure computation to secure protocols and (iii) an efficient protocol for oblivious transfer - one of the building blocks of secure computation. Among other results, we get the first sub-linear protocol for the Millionaires Problem. Bio |