A Zero-One Law for Deterministic 2-Party Secure Computation

Manoj M Prabhakaran


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.

Time and Place

Apr 20 2009 (Monday) at 1630 hrs
Gates 4B (opposite 490)