  The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box
separation between one-way functions and public-key encryption: informally, a
public-key encryption scheme cannot be constructed using one-way functions as
the sole source of computational hardness. In addition, this implied a
black-box separation between one-way functions and protocols for certain Secure
Function Evaluation (SFE) functionalities (in particular, Oblivious Transfer).
Surprisingly, however, {\em since then there has been no further progress in
separating one-way functions and SFE functionalities} (though several other
black-box separation results were shown). In this work, we present the complete
picture for deterministic 2-party SFE functionalities. We show that one-way
functions are black-box separated from {\em all such SFE functionalities},
except the ones which have unconditionally secure protocols (and hence do not
rely on any computational hardness), when secure computation against
semi-honest adversaries is considered. In the case of security against active
adversaries, a black-box one-way function is indeed useful for SFE, but we show
that it is useful only as much as access to an ideal commitment functionality
is useful.
  Technically, our main result establishes the limitations of random oracles
for secure computation.
