A Full Characterization of Completeness for Two-party Randomized Function Evaluation

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

Paper 2014/080

A Full Characterization of Completeness for Two-party Randomized Function Evaluation

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

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 it view. We show that any function f, if complete, can implement any (randomized) circuit C using only O(|C| + k) calls to f, where k 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.

Note: This is a FULL VERSION of the paper appearing in Eurocrypt-2014.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in Eurocrypt 2014
Keywords: Foundations Completeness Characterization Standalone Security UC Security Information-theoretic Reduction
Contact author(s): hemanta maji @ gmail com
History: 2014-02-05: revised; 2014-02-05: received; See all versions
Short URL: https://ia.cr/2014/080
License: CC BY

BibTeX

@misc{cryptoeprint:2014/080,
      author = {Daniel Kraschewski and Hemanta K.  Maji and Manoj Prabhakaran and Amit Sahai},
      title = {A Full Characterization of Completeness for Two-party Randomized Function Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/080},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/080}},
      url = {https://eprint.iacr.org/2014/080}
}