Abstract
A secure function evaluation protocol allows two parties to jointly compute a function $f(x,y)$ of their inputs in a manner not leaking more information than necessary. A major result in this field is: ``any function $f$ that can be computed using polynomial resources can be computed {\em securely} using polynomial resources'' (where `resources' refers to communication and computation). This result follows by a general transformation from any circuit for $f$ to a secure protocol that evaluates $f$. Although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of $f$.

We propose a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of $f$. We start with an efficient (insecure) protocol for $f$ and transform it into a secure protocol. In other words, ``any function $f$ that can be computed using communication complexity $c$ can be can be computed securely using communication complexity that is polynomial in $c$ and a security parameter''. We show several simple applications of this new methodology resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the ``millionaires problem", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.