TY - GEN
T1 - Limits of random oracles in secure computation
AU - Mahmoody, Mohammad
AU - Maji, Hemanta K.
AU - Prabhakaran, Manoj
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893254760&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893254760&partnerID=8YFLogxK
U2 - 10.1145/2554797.2554801
DO - 10.1145/2554797.2554801
M3 - Conference contribution
AN - SCOPUS:84893254760
SN - 9781450322430
T3 - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
SP - 23
EP - 33
BT - ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PB - Association for Computing Machinery
T2 - 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
Y2 - 12 January 2014 through 14 January 2014
ER -