Paper 2014/018

Completeness for Symmetric Two-Party Functionalities - Revisited

Yehuda Lindell, Eran Omri, and Hila Zarosim


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; \ie $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 \emph{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.

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2012
Contact author(s)
hila zarosim @ gmail com
2014-01-07: received
Short URL
Creative Commons Attribution


      author = {Yehuda Lindell and Eran Omri and Hila Zarosim},
      title = {Completeness for Symmetric Two-Party Functionalities - Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2014/018},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.