The Taub Faculty of Computer Science Events and Talks

Suppose two parties, Alice and Bob, have access to a trusted third party that can do some \emph{simple} computation for them. How can we find out whether the trusted third party's functionality is sufficient to implement arbitrary secure computation from it?

The oblivious transfer (OT) functionality just takes as input a tuple of bits $(b_0,b_1)$ from Alice and a choice bit $c$ from Bob and then outputs $b_c$ to Bob. Joe Kilian showed in 1988 that OT is complete in the sense that every secure multi-party computation can be realized from it. Since then, cryptographers are working on reductions of OT to various other primitives. In this context, it has been a long-standing open problem to find efficiently checkable completeness criteria for a class of primitives called ``cryptogates''. These are stateless black boxes with fixed (but not necessarily deterministic) functionality of constant size that can be jointly queried by two parties. Examples are OT itself or noisy channels.

Over the decades, completeness criteria have been found for symmetric (i.e., both parties receive the same output) and asymmetric (i.e., only one party receives any output at all) \emph{deterministic} cryptogates and noisy channels. For \emph{randomized} cryptogates more complex than noisy channels only a classification in the semi-honest model was known, until recently this whole line of research was completed by two independent works. I present one of these approaches, which uses real algebraic geometry to reduce the completeness question to a problem of game-theoretic flavor.

The talk requires no mathematical knowledge other than some basic probability theory.