We qualitatively separate semi-honest secure computation of non-trivial secure-function evaluation (SFE) functionalities from existence of key-agreement 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.
1) 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.
2) With respect to semi-honest, standalone or UC security, existence of key-agreement 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 {\em common-information learning} algorithm (CIL) which extends the ``eavesdropper'' in prior work Impagliazzo and Rudich (1989), Barak and Mahmoody (2009) and Haitner et. al (2013), 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 {\em image-testable random-oracles}. We extend the analysis approaches of prior work on random oracle Impagliazzo and Rudich (1989), Barak and Mahmoody (2009), Dachman et. al (2011), Mahmoody et. al (2012) and Haitner et. al (2013) 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 (c.f. Reingold et. al (2004)).
