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

Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek. Submitted.

Abstract

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 complete --- namely any functionality can be UC-securely realized given ideal access to this functionality.

We give a necessary and sufficient complexity assumption under which the following zero-one law holds:

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.

Our work is the first in any security model to investigate completeness for arbitrary reactive functionalities, while almost all previous results classifying multi-party functionalities have been restricted to the case of secure function evaluation. An important contribution in this work is to initiate an "automata-theoretic" study of reactive functionalities.

Downloads