Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Theory of Computing (STOC)

More general completeness theorems for secure two-party computation

Joe Kilian

Published May 1, 2000• 116 citations
Publisher

Abstract

We consider the power of cryptographic primitives, denoted f-cryptogates, defined as follows: Alice and Bob have inputs x and y, respectively.Given a possibly probabilistic function, f(x,y), the f-cryptogate computes z +--f(x,y) and either broadcasts z to both parties (the symmetric case) or sends z exclusively to Bob (the asymmetric case); neither party learns more than what is provided by the fcryptogate.We say that an f-cryptogate is complete if, using information-theoretic notions of reductions, security and privacy, one can use the cryptogate to perform secure two-party computation.We give a number of characterizations of the complete fcryptogates, depending on the adversary model, whether the output of f is probabilistic or deterministic, and whether the cryptogate is symmetric or asymmetric.For active adversaries, who may violate the protocol, we characterize the complete asymmetric f-cryptogates for deterministic f.For passive adversaries, who always follow the protocol, we characterize the complete symmetric and asymmetric f-cryptogates for all deterministic and probabilistic f.Our characterizations for asymmetric cryptogates generalizes a recent theorem of Beimel, Malkin and Micali.abilistic) function f(x, y), the goal of secure function evaluation is to provide Bob with the value of z +--f(x, y) (for

DOI
10.1145/335305.335342

Related papers

Completeness Theorems for All Finite Stateless 2-Party Primitives.

Daniel Kraschewski

Since Kilian showed in 1988 that oblivious transfer (OT) is complete in the sense that every secure multi-party computation can be realized from this primitive, cryptographers are working on reductions of OT to various other primitives. A long-standing open question in this context is the classification of finite stateless 2-party primitives (so-called “cryptogates”), i.e. trusted black boxes that can be jointly queried by two parties, have finite input and output alphabets, and do not change behavior depending on time or input history. Over the decades, completeness criteria have been found for deterministic cryptogates (i.e. primitives without internal randomness), noisy channels, and symmetric (i.e., both parties receive the same output) or asymmetric (i.e., only one party receives any output at all) randomized cryptogates. However, the known criteria for randomized primitives other than noisy channels only hold in presence of passive adversaries (i.e., even corrupted parties still follow the protocol). We complete this line of research by providing simple but comprehensive combinatorial completeness criteria for all finite stateless 2-party primitives. I.e., for the first time there are completeness criteria for randomized primitives that are neither symmetric nor asymmetric (but

•Jan 1, 2013•1 citation

Completeness Theorems with Constructive Proofs for Finite Deterministic 2-Party Functions (full version).

Daniel Kraschewski, Jörn Müller‐Quade

In this paper we present simple but comprehensive combinatorial criteria for completeness of finite deterministic 2-party functions with respect to information-theoretic security. We give a general protocol construction for efficient and statistically secure reduction of oblivious transfer to any finite deterministic 2-party function that fulfills our criteria. For the resulting protocols we prove universal composability. Our results are tight in the sense that our criteria still are necessary for any finite deterministic 2-party function to allow for implementation of oblivious transfer with statistical privacy and correctness. We unify and generalize results of Joe Kilian (1991, 2000) in two ways. Firstly, we show that his completeness criteria also hold in the UC framework. Secondly, what is our main contribution, our criteria also cover a wide class of primitives that are not subject of previous criteria. We show that there are non-trivial examples of finite deterministic 2-party functions that are neither symmetric nor asymmetric and therefore have not been covered by existing completeness criteria so far. As a corollary of our work, every finite deterministic 2-party function is either complete or can be considered equivalent to a non-complete symmetric 2-party function—this assertion holds true with respect to active adversaries as well as passive adversaries. Thereby known results on non-complete symmetric 2-party functions are strengthened.

•Jan 1, 2010•2 citations

An elementary completeness proof for secure two-party computation primitives

Ye Wang, Prakash Ishwar, Shantanu D. Rane

In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noise-less communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are “complete” primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.

arXiv:1402.4360•IEEE Information Theory Workshop (ITW)•Nov 1, 2014•0 citations

Completeness for Symmetric Two-Party Functionalities - Revisited.

Yehuda Lindell, Eran Omri, Hila Zarosim

Abstract. 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. 1

•Jan 1, 2014•0 citations

Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation.

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

In symmetric secure function evaluation (SSFE), Alice has an input x, Bob has an input y, and both parties wish to securely compute f(x, y). We show several new results classifying the feasibility of securely implementing these functions in several security settings. Namely, we give new alternate characterizations of the functions that have (statistically) secure protocols against passive and active (standalone), computationally unbounded adversaries. We also show a strict, infinite hierarchy of complexity for SSFE functions with respect to universally composable security against unbounded adversaries. That is, there exists a sequence of functions f1, f2,... such that there exists a UC-secure protocol for fi in the fj-hybrid world if and only if i ≤ j. The main new technical tool that unifies our unrealizability results is a powerful protocol simulation theorem, which may be of independent interest. Essentially, in any adversarial setting (UC, standalone, or passive), f is securely realizable if and only if a very simple (deterministic) “canonical ” protocol for f achieves the desired security. Thus, to show that f is unrealizable, one need simply demonstrate a single attack on a single simple protocol. 1

•Jan 1, 2008•1 citation

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

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

We use security in the Universal Composition framework as a means to study the “cryptographic complexity ” of 2-party secure computation tasks (functionalities). We say that a functionality F reduces to another functionality G if there is a UC-secure protocol for F using ideal access to G. This reduction is a natural and fine-grained way to compare the relative complexities of cryptographic tasks. There are two natural “extremes ” of complexity under the reduction: the trivial functionalities, which can be reduced to any other functionality; and the complete functionalities, to which any other functionality can be reduced. In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semi-honest adversaries), there is a zero-one law for the cryptographic complexity of 2-party deterministic functionalities. Namely, every such functionality is either trivial or complete. No other qualitative distinctions exist among functionalities, under this computational assumption. While nearly all previous work classifying multi-party computation functionalities has been restricted to the case of secure function evaluation, our results are the first to consider completeness of arbitrary reactive functionalities, which receive input and give output repeatedly throughout several rounds of interaction. One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality.

•Jan 1, 2010•1 citation
We consider the power of cryptographic primitives, denoted f-cryptogates, defined as follows: Alice and Bob have inputs x and y, respectively.Given a possibly probabilistic function, f(x,y), the f-cryptogate computes z +--f(x,y) and either broadcasts z to both parties (the symmetric case) or sends z exclusively to Bob (the asymmetric case); neither party learns more than what is provided by the fcryptogate.We say that an f-cryptogate is complete if, using information-theoretic notions of reductions, security and privacy, one can use the cryptogate to perform secure two-party computation.We give a number of characterizations of the complete fcryptogates, depending on the adversary model, whether the output of f is probabilistic or deterministic, and whether the cryptogate is symmetric or asymmetric.For active adversaries, who may violate the protocol, we characterize the complete asymmetric f-cryptogates for deterministic f.For passive adversaries, who always follow the protocol, we characterize the complete symmetric and asymmetric f-cryptogates for all deterministic and probabilistic f.Our characterizations for asymmetric cryptogates generalizes a recent theorem of Beimel, Malkin and Micali.abilistic) function f(x, y), the goal of secure function evaluation is to provide Bob with the value of z +--f(x, y) (for
Since Kilian showed in 1988 that oblivious transfer (OT) is complete in the sense that every secure multi-party computation can be realized from this primitive, cryptographers are working on reductions of OT to various other primitives. A long-standing open question in this context is the classification of finite stateless 2-party primitives (so-called “cryptogates”), i.e. trusted black boxes that can be jointly queried by two parties, have finite input and output alphabets, and do not change behavior depending on time or input history. Over the decades, completeness criteria have been found for deterministic cryptogates (i.e. primitives without internal randomness), noisy channels, and symmetric (i.e., both parties receive the same output) or asymmetric (i.e., only one party receives any output at all) randomized cryptogates. However, the known criteria for randomized primitives other than noisy channels only hold in presence of passive adversaries (i.e., even corrupted parties still follow the protocol). We complete this line of research by providing simple but comprehensive combinatorial completeness criteria for all finite stateless 2-party primitives. I.e., for the first time there are completeness criteria for randomized primitives that are neither symmetric nor asymmetric (but
In this paper we present simple but comprehensive combinatorial criteria for completeness of finite deterministic 2-party functions with respect to information-theoretic security. We give a general protocol construction for efficient and statistically secure reduction of oblivious transfer to any finite deterministic 2-party function that fulfills our criteria. For the resulting protocols we prove universal composability. Our results are tight in the sense that our criteria still are necessary for any finite deterministic 2-party function to allow for implementation of oblivious transfer with statistical privacy and correctness. We unify and generalize results of Joe Kilian (1991, 2000) in two ways. Firstly, we show that his completeness criteria also hold in the UC framework. Secondly, what is our main contribution, our criteria also cover a wide class of primitives that are not subject of previous criteria. We show that there are non-trivial examples of finite deterministic 2-party functions that are neither symmetric nor asymmetric and therefore have not been covered by existing completeness criteria so far. As a corollary of our work, every finite deterministic 2-party function is either complete or can be considered equivalent to a non-complete symmetric 2-party function—this assertion holds true with respect to active adversaries as well as passive adversaries. Thereby known results on non-complete symmetric 2-party functions are strengthened.
In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noise-less communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are “complete” primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.
Abstract. 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. 1
In symmetric secure function evaluation (SSFE), Alice has an input x, Bob has an input y, and both parties wish to securely compute f(x, y). We show several new results classifying the feasibility of securely implementing these functions in several security settings. Namely, we give new alternate characterizations of the functions that have (statistically) secure protocols against passive and active (standalone), computationally unbounded adversaries. We also show a strict, infinite hierarchy of complexity for SSFE functions with respect to universally composable security against unbounded adversaries. That is, there exists a sequence of functions f1, f2,... such that there exists a UC-secure protocol for fi in the fj-hybrid world if and only if i ≤ j. The main new technical tool that unifies our unrealizability results is a powerful protocol simulation theorem, which may be of independent interest. Essentially, in any adversarial setting (UC, standalone, or passive), f is securely realizable if and only if a very simple (deterministic) “canonical ” protocol for f achieves the desired security. Thus, to show that f is unrealizable, one need simply demonstrate a single attack on a single simple protocol. 1
We use security in the Universal Composition framework as a means to study the “cryptographic complexity ” of 2-party secure computation tasks (functionalities). We say that a functionality F reduces to another functionality G if there is a UC-secure protocol for F using ideal access to G. This reduction is a natural and fine-grained way to compare the relative complexities of cryptographic tasks. There are two natural “extremes ” of complexity under the reduction: the trivial functionalities, which can be reduced to any other functionality; and the complete functionalities, to which any other functionality can be reduced. In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semi-honest adversaries), there is a zero-one law for the cryptographic complexity of 2-party deterministic functionalities. Namely, every such functionality is either trivial or complete. No other qualitative distinctions exist among functionalities, under this computational assumption. While nearly all previous work classifying multi-party computation functionalities has been restricted to the case of secure function evaluation, our results are the first to consider completeness of arbitrary reactive functionalities, which receive input and give output repeatedly throughout several rounds of interaction. One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality.