What is the exact power of the random oracle model?
We make progress towards answering the above question, showing that, essentially, any no private input, semi-honest two-party functionality that can be securely implemented in the random oracle 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.
Our result immediately yields essentially that the only no-input functionalities that can be securely realized in the random oracle model (in the sense of secure function evaluation), are the trivial ones (ones that can be securely realized information theoretically). In addition, 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 oracle model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.Category / Keywords: foundations / random oracles; black-box separations; one-way functions; differential privacy; key agreement Date: received 9 Oct 2012, last revised 14 Jan 2013 Contact author: iftachh at cs tau ac il, omrier@gmail com, zarosih@cs biu ac il Available formats: PDF | BibTeX Citation Note: The name of the paper was changed from ``On the Power of Random Oracles" to ``Limits on the Usefulness of Random Oracles" Version: 20130114:212507 (All versions of this report) Discussion forum: Show discussion | Start new discussion