A Zero-One Law for Deterministic 2-Party Secure Computation
Manoj M Prabhakaran
Abstract:
A Zero-One Law for Deterministic 2-Party Secure Computation We use security in the Universal Composition framework to study the ``cryptographic complexity'' of 2-party functionalities, in a computationally bounded setting. It is well-known that (no matter what complexity assumptions are made), many 2-party functionalities are not UC-securely realizable given just communication channels: i.e., there exist non-trivial functionalities. It is also known that some 2-party functionalities are {\em complete} --- namely any functionality can be UC-securely realized given ideal access to this functionality. We give a {\em necessary and sufficient} complexity assumption under which the following {\bf zero-one law} holds: {\em In the probabilistic polynomial time setting, every finite, deterministic 2-party (non-reactive and reactive) functionality is either trivial or complete.} The complexity assumption referred to above is that there exists a protocol that securely realizes oblivious transfer against semi-honest corruption. An important contribution in this work is to initiate an ``automata-theoretic'' study of {\em reactive} functionalities. Our work is the first in any security model to investigate completeness for arbitrary {\em reactive} functionalities, while almost all previous results classifying multi-party functionalities have been restricted to the case of secure function evaluation. This is joint work with Hemanta Maji and Mike Rosulek.