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.
Category / Keywords: Original Publication (with minor differences): IACR-ASIACRYPT-2012 Date: received 7 Jan 2014 Contact author: hila zarosim at gmail com Available format(s): PDF | BibTeX Citation Version: 20140107:094654 (All versions of this report) Short URL: ia.cr/2014/018 Discussion forum: Show discussion | Start new discussion