A unified characterization of completeness and triviality for secure function evaluation

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

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

Abstract

We present unified combinatorial characterizations of completeness for 2-party secure function evaluation (SFE) against passive and active corruptions in the information-theoretic setting, so that all known characterizations appear as special cases. In doing so we develop new technical concepts. We define several notions of isomorphism of SFE functionalities and define the "kernel" of an SFE functionality. An SFE functionality is then said to be "simple" if and only if it is strongly isomorphic to its kernel. An SFE functionality ℱ′ is a core of an SFE functionality ℱ if it is "redundancy free" and is weakly isomorphic to ℱ. Then: - An SFE functionality is complete for security against passive corruptions if and only if it is not simple. - A deterministic SFE functionality is complete for security against active corruptions if and only if it has a core that is not simple. We conjecture that this characterization extends to randomized SFE as well. We further give explicit combinatorial characterizations of simple SFE functionalities. Finally, we apply our new notions of isomorphism to reduce the problem of characterization of trivial functionalities (i.e., those securely realizable without setups) for the case of general SFE to the same problem for the case of simple symmetric SFE.

Original languageEnglish (US)
Title of host publicationProgress in Cryptology, INDOCRYPT 2012 - 13th International Conference on Cryptology in India, Proceedings
Pages40-59
Number of pages20
DOIs
StatePublished - Dec 31 2012
Event13th International Conference on Cryptology in India, INDOCRYPT 2012 - Kolkata, India
Duration: Dec 9 2012Dec 12 2012

Publication series

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

Other

Other13th International Conference on Cryptology in India, INDOCRYPT 2012
CountryIndia
CityKolkata
Period12/9/1212/12/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A unified characterization of completeness and triviality for secure function evaluation'. Together they form a unique fingerprint.

Cite this