• Calendar

December 24, Tuesday
12:00 – 14:00

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(poly\log 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.