Limits of random oracles in secure computation

Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: a public-key encryption scheme cannot be constructed using one-way functions in a black-box way. In addition, their result implied black-box separations between one-way functions and protocols for certain Secure Function Evaluation (SFE) functionalities (in particular, Oblivious Transfer). Surprisingly, however, since then there has been no further progress in separating one- way functions and SFE functionalities. In this work, we present the complete picture for finite deterministic 2-party SFE functionalities, vis a vis one-way functions. We show that in case of semi-honest adversaries, one-way functions are black-box separated from all such SFE functionalities, except the ones which have unconditionally secure protocols (and hence do not rely on any computational hardness). In the case of active adversaries, a black-box one-way function is indeed useful for SFE, but we so 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. We show that a twoparty deterministic functionality f has a secure protocol in the random oracle model that is (statistically) secure against semi-honest adversaries if and only if f has a protocol in the plain model that is (perfectly) secure against semi-honest adversaries. Further, in the case of active adversaries, a deterministic SFE functionality f has a (UC or standalone) statistically secure protocol in the random oracle model if and only if f has a (UC or standalone) statistically secure protocol in the commitment-hybrid model. Our proof is based on a "frontier analysis" of two-party protocols, combining it with (extensions of) the "independence learners"of Impagliazzo-Rudich/Barak-Mahmoody. We make essential use of a combinatorial property, originally discovered by Kushilevitz (FOCS 1989), of junctions that have semi-honest secure protocols in the plain model (and hence our analysis applies only to functions of polynomialsized domains, for which such a characterization is known). Our result could be seen as a first step towards proving a conjecture that we put forth in this work and call it the Many-Worlds Conjecture. For every 2-party SFE functionality f, one can consider a "world"where f can be semi-honest securely realized in the computational setting. Many-Worlds Conjecture states that there are infinitely many "distinct worlds" between minicrypt and cryptomania in the universe of Impagliazzo's Worlds.

Original languageEnglish (US)
Title of host publicationITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery
Pages23-33
Number of pages11
ISBN (Print)9781450322430
DOIs
StatePublished - Jan 1 2014
Event2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States
Duration: Jan 12 2014Jan 14 2014

Publication series

NameITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

Other

Other2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
CountryUnited States
CityPrinceton, NJ
Period1/12/141/14/14

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Limits of random oracles in secure computation'. Together they form a unique fingerprint.

  • Cite this

    Mahmoody, M., Maji, H. K., & Prabhakaran, M. (2014). Limits of random oracles in secure computation. In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (pp. 23-33). (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery. https://doi.org/10.1145/2554797.2554801