On the Power of Public-Key Encryption in Secure Computation
Public-Key Encryption (PKE) is an important security primitive in a system involving more than two parties. In this paper, the authors ask if PKE could be useful for protecting two mutually distrusting parties against each other, if there is no other party involved. They qualitatively separate semi-honest secure computation of non-trivial Secure-Function Evaluation (SFE) functionalities from existence of key-agreement protocols. Technically, they show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any SFE which can be securely performed relative to this oracle can also be securely performed in the plain model.