In the random oracle model, the parties are given oracle access to a random member of
a (typically huge) function family, and are assumed to have unbounded computational power
(though they can only make a bounded number of oracle queries). This model provides powerful
properties that allow proving the security of many protocols, even such that cannot be proved
secure in the standard model (under any hardness assumption). The random oracle model is also
used to show that a given cryptographic primitive cannot be used in a black-box way to construct
another primitive; in their seminal work, Impagliazzo and Rudich [STOC \'89] showed that in the
random function model - when the function family is the set of all functions - it is impossible
to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box
reduced to one-way functions. Their work has a long line of followup works (Simon [EC \'98],
Gertner et al. [STOC \'00] and Gennaro et al. [SICOMP \'05], to name a few), showing that given
oracle access to a certain type of function family (e.g., the family that \"implements\" public-key
encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer).
Yet, in the more general sense, the following fundamental question remained open:
What is the exact power of the random oracle model, and more specifically, of the
random function model?
We make progress towards answering the above question, showing that any (no private input)
semi-honest two-party functionality that can be securely implemented in the random function
model, can be securely implemented information theoretically (where parties are assumed to be
all powerful, and no oracle is given). We further generalize the above result to function families
that provide some natural combinatorial property.
To exhibit the power of our result, we use the recent information theoretic impossibility result
of McGregor et al. [FOCS \'10], to show the existence of functionalities (e.g., inner product) that
cannot be computed both accurately and in a differentially private manner in the random
function model; yielding that protocols for computing these functionalities cannot be black-box
reduced to the existence of one-way functions.