A full characterization of completeness for two-party randomized function evaluation

Daniel Kraschewski, Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai

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

Abstract

We settle a long standing open problem which has pursued a full characterization of completeness of (potentially randomized) finite functions for 2-party computation that is secure against active adversaries. Since the first such complete function was discovered [Kilian, FOCS 1988], the question of which finite 2-party functions are complete has been studied extensively, leading to characterization in many special cases. In this work, we completely settle this problem. We provide a polynomial time algorithm to test whether a 2-party finite secure function evaluation (SFE) functionality (possibly randomized) is complete or not. The main tools in our solution include: - A formal linear algebraic notion of redundancy in a general 2-party randomized function. - A notion of statistically testable games. A kind of interactive proof in the information-theoretic setting where both parties are computationally unbounded but differ in their knowledge of a secret. - An extension of the (weak) converse of Shannon's channel coding theorem, where an adversary can adaptively choose the channel based on its view. We show that any function f, if complete, can implement any (randomized) circuit C using only O(|C| + κ) calls to f, where κ is the statistical security parameter. In particular, for any two-party functionality g, this establishes a universal notion of its quantitative "cryptographic complexity" independent of the setup and has close connections to circuit complexity.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology, EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
PublisherSpringer-Verlag
Pages659-676
Number of pages18
ISBN (Print)9783642552199
DOIs
StatePublished - Jan 1 2014
Event33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014 - Copenhagen, Denmark
Duration: May 11 2014May 15 2014

Publication series

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

Other

Other33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014
CountryDenmark
CityCopenhagen
Period5/11/145/15/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A full characterization of completeness for two-party randomized function evaluation'. Together they form a unique fingerprint.

  • Cite this

    Kraschewski, D., Maji, H. K., Prabhakaran, M., & Sahai, A. (2014). A full characterization of completeness for two-party randomized function evaluation. In Advances in Cryptology, EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 659-676). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8441 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-642-55220-5_36