MIT cypher talk

[Alan Wexelblat <wex@media.mit.edu>]

[email joanne@theory.lcs.mit.edu for more info]

>                        Thursday, May 19, 1994
>          Refreshments at 4:00pm, Talk at 4:15pm in NE43-518
>
>              ``A Minimal Model for Secure Computation''
>                           by Uriel Feige
>                         Weizmann Institute
>
>                              ABSTRACT
>
>We consider a minimal scenario for secure computation: Parties $A$ and
>$B$ have private inputs $x$ and $y$ and a shared random string $r$.
>$A$ and $B$ are each allowed to send a single message to a third party
>$C$, from which $C$ is to learn the value of $f(x,y)$ for some
>function $f$, but nothing else.  We show that this model is
>surprisingly powerful: every function $f$ can be securely computed in
>this fashion.  If the messages are required to be of polynomial size,
>then we exhibit an efficient protocol for any function $f$ computable
>in nondeterministic logspace.  Using a computational notion of
>security, we exhibit efficient protocols for any polynomial-time
>computable function $f$, assuming the existence of one-way functions.
>The above results generalize to the case where there are more than two
>parties with private inputs.
>
>The minimalistic nature of our model makes it easy to transform
>positive results achieved in our model to other more general models of
>secure computation.  It also gives hope for lower-bound proofs.  We
>give an alternative characterization of our model in terms of graph
>embeddings, and use this to show that for most Boolean functions on
>$\{0,1\}^n\times\{0,1\}^n$, the need to hide just one of the input
>bits from $C$ requires a communication overhead of $n$ bits.  \medskip
>
>Joint work with Joe Kilian and Moni Naor.
>
>Host:  Michel Goemans