Completeness for Symmetric Two-Party Functionalities - Revisited

Understanding the minimal assumptions required for carrying out cryptographic tasks is one of the fundamental goals of theoretical cryptography. A rich body of work has been dedicated to understanding the complexity of cryptographic tasks in the context of (semi-honest) secure two-party computation. Much of this work has focused on the characterization of trivial and complete functionalities (resp., functionalities that can be securely implemented unconditionally, and functionalities that can be used to securely compute all functionalities).

All previous works define reductions via an ideal implementation of the functionality; i.e.,

f

reduces to

g

if one can implement

f

using an ideal box (or oracle) that computes the function

g

and returns the output to both parties. Such a reduction models the computation of

f

as an

atomic operation

. However, in the real-world, protocols proceed in rounds, and the output is not learned by the parties simultaneously. In this paper we show that this distinction is significant. Specifically, we show that there exist symmetric functionalities (where both parties receive the same outcome), that are neither trivial nor complete under “ideal-box reductions”, and yet the existence of a constant-round protocol for securely computing such a functionality implies infinitely-often oblivious transfer (meaning that it is secure for infinitely-many

n

’s). In light of the above, we propose an alternative definitional infrastructure for studying the triviality and completeness of functionalities.