## 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.

### Time and Place

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