On the power of public-key encryption in secure computation

Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran

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


We qualitatively separate semi-honest secure computation of nontrivial secure-function evaluation (SFE) functionalities from existence of keyagreement protocols. Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any SFE which can be securely performed relative to this oracle can also be securely performed in the plain model. Our main result has following consequences. There exists an oracle which is useful for some 3-party deterministic SFE; but useless for semi-honest secure realization of any general 2-party (deterministic finite) SFE. With respect to semi-honest, standalone or UC security, existence of keyagreement protocols (if used in black-box manner) is only as useful as the commitment-hybrid for general 2-party (deterministic finite) SFE functionalities. This work advances (and conceptually simplifies) several state-of-the-art techniques in the field of black-box separations: 1 We introduce a general common-information learning algorithm (CIL) which extends the "eavesdropper" in prior work [1,2,3], to protocols whose message can depend on information gathered by the CIL so far. 2 With the help of this CIL, we show that in a secure 2-party protocol using an idealized PKE oracle, surprisingly, decryption queries are useless. 3 The idealized PKE oracle with its decryption facility removed can be modeled as a collection of image-testable random-oracles. We extend the analysis approaches of prior work on random oracle [1,2,4,5,3] to apply to this class of oracles. This shows that these oracles are useless for semi-honest 2-party SFE (as well as for key-agreement). These information theoretic impossibility results can be naturally extended to yield black-box separation results (cf. [6]).

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, Proceedings
Number of pages25
ISBN (Print)9783642542411
StatePublished - 2014
Event11th Theory of Cryptography Conference on Theory of Cryptography, TCC 2014 - San Diego, CA, United States
Duration: Feb 24 2014Feb 26 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8349 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th Theory of Cryptography Conference on Theory of Cryptography, TCC 2014
Country/TerritoryUnited States
CitySan Diego, CA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the power of public-key encryption in secure computation'. Together they form a unique fingerprint.

Cite this