On the Power of Public-Key Encryption in Secure Computation

We qualitatively separate semi-honest secure computation of nontrivial secure-function evaluation (SFE) functionalities from existence of keyagreement protocols. Technically, we 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.

Our main result has following consequences.

There exists an oracle which is useful for some 3-party deterministic SFE; but useless for semi-honest secure realization of any general 2-party (deterministic finite) SFE.

With respect to semi-honest, standalone or UC security, existence of keyagreement protocols (if used in black-box manner) is only as useful as the commitment-hybrid for general 2-party (deterministic finite) SFE functionalities.

This work advances (and conceptually simplifies) several state-of-the-art techniques in the field of black-box separations:

1

We introduce a general

common-information learning

algorithm (CIL) which extends the “eavesdropper” in prior work [1,2,3], to protocols whose message can depend on information gathered by the CIL so far.

2

With the help of this CIL, we show that in a secure 2-party protocol using an idealized PKE oracle, surprisingly, decryption queries are useless.

3

The idealized PKE oracle with its decryption facility removed can be modeled as a collection of

image-testable random-oracles

. We extend the analysis approaches of prior work on random oracle [1,2,4,5,3] to apply to this class of oracles. This shows that these oracles are useless for semi-honest 2-party SFE (as well as for key-agreement).

These information theoretic impossibility results can be naturally extended to yield black-box separation results (cf. [6]).