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.
Category / Keywords: foundations / Foundations, Secure 2-party Randomized Function Evaluation, Completeness Characterization, Standalone Security, UC Security, Information-theoretic Reduction Original Publication (with major differences): IACR-EUROCRYPT-2014 Date: received 4 Feb 2014, last revised 5 Feb 2014 Contact author: hemanta maji at gmail com Available format(s): PDF | BibTeX Citation Note: This is a FULL VERSION of the paper appearing in Eurocrypt-2014. Version: 20140205:170113 (All versions of this report) Short URL: ia.cr/2014/080