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

Information-Theoretically Secure Three-Party Computation with One Active Adversary

Ye Wang, Prakash Ishwar, Shantanu D. Rane

Published Jun 12, 2012• 2 citations
OpenAlex

Abstract

The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated through the BGW protocol for computing quadratic and Hamming distances; this protocol is secure under the passive model, but is shown to be not secure under the active model.

Related papers

Information-theoretically secure three-party computation with One corrupted party

Ye Wang, Prakash Ishwar, Shantanu D. Rane

The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated by examining a protocol for computing quadratic and Hamming distances that is secure under the passive model, but is insecure under the active model.

arXiv:1206.2669•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•1 citation

Information theory and secure multi-party computation

Ueli M. Maurer

Two types of generalizations in secure multi-party computation are described. First, we report on a new general adversary model: while previous protocols were designed to tolerate misbehavior of one of two types (active or passive adversaries) the new protocols tolerate mixed types of adversaries, i.e. an adversary that can corrupt players actively, passively, or can let them crash (i.e. stop execution). We derive the necessary and sufficient conditions under which such a general adversary can be tolerated. Second, we present a generic protocol framework that unifies previous approaches achieving unconditional (or information-theoretic) security and cryptographic security (i.e. security based on a cryptographic intractability assumption). This is achieved by introducing secret sharing schemes with an additional property called the multiplication property and a new type of homomorphic commitment scheme, and by generalizing the concept of commitments.

IEEE Information Theory Workshop (ITW)•Nov 27, 2002•0 citations

Trading Correctness for Privacy in Unconditional Multi-Party Computation

Matthias Fitzi, Martin Hirt, Ueli M. Maurer

. This paper improves on the classical results in unconditionally secure multi-party computation among a set of n players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the computation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf = 0) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp ! n=2. In the active case, every function can be computed securely if and only if ta ! n=3; when a broadcast channel is available, then this bound is ta ! n=2. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating ta ! n=3 actively corrupted players, pr...

•Jan 1, 1998•5 citations

Study on Commitment Schemes of Secure Multi-party Computation

Xiaoqiang Guo, Yan Yan, Lihong Li +1 more

The problem of secure multi-party computation(SMPC) is one of the most fundamental problems in information security. First, we introduce the basic concept of SMPC and four SMPC basic agreement: key distribution,oblivious transfer, bit commitment and zero knowledge proof. Secondly, we separately illustrate commitment schemes  commitment transfer protocol, commitment sharing protocol and commitment multiplication protocol. Finally, we present unconditionally secure multi-party computation with a passive adversary, an active adversary, general adversary structures.

Indonesian Journal of Electrical Engineering and Computer Science•Oct 1, 2014•0 citations

Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract)

Martin Hirt, Ueli M. Maurer

The classical results in unconditional multi-party computation among a set of n players state that less than n/2 passive or Iess than n/3 active adversaries can be tolerated; assuming a broadcast channel the threshold for active adversaries is ta/2.Strictly generalizing these results we specify the set of potential y misbehaving players as an arbitrary set of subsets of the player set.We prove the necessary and sufficient conditions for the existence of secure multi-party protocols in terms of the potentially misbehaving player sets.For every function there exists a protocol secure against a set of potential passive collusions if and only if no two of these collusions add up to the full player set.The same condition applies for active adversaries when assuming a broadcast chzmnel.Without broadcast channels, for every function there exists a protocol secure against a set of potential active adverse player sets if and only if no three of these sets add up to the full player set.The complexities of the protocols not using a broadcast channel are polynomial, that of the protocol with broadcast is only slightly higher.

ACM Symposium on Principles of Distributed Computing (PODC)•Jan 1, 1997•165 citations

A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation.

Gilad Asharov, Yehuda Lindell

In the setting of secure multiparty computation, a set of n parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full detailed proof of these results was never given. In this paper, we remedy this situation and provide a full proof of security of the BGW protocol. We also derive corollaries for security in the presence of adaptive adversaries and under concurrent general composition (equivalently, universal composability). In addition, we give a full specification of the protocol for the malicious setting. This includes one new step

Electronic colloquium on computational complexity•Jan 1, 2011•23 citations
The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated through the BGW protocol for computing quadratic and Hamming distances; this protocol is secure under the passive model, but is shown to be not secure under the active model.
The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated by examining a protocol for computing quadratic and Hamming distances that is secure under the passive model, but is insecure under the active model.
Two types of generalizations in secure multi-party computation are described. First, we report on a new general adversary model: while previous protocols were designed to tolerate misbehavior of one of two types (active or passive adversaries) the new protocols tolerate mixed types of adversaries, i.e. an adversary that can corrupt players actively, passively, or can let them crash (i.e. stop execution). We derive the necessary and sufficient conditions under which such a general adversary can be tolerated. Second, we present a generic protocol framework that unifies previous approaches achieving unconditional (or information-theoretic) security and cryptographic security (i.e. security based on a cryptographic intractability assumption). This is achieved by introducing secret sharing schemes with an additional property called the multiplication property and a new type of homomorphic commitment scheme, and by generalizing the concept of commitments.
. This paper improves on the classical results in unconditionally secure multi-party computation among a set of n players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the computation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf = 0) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp ! n=2. In the active case, every function can be computed securely if and only if ta ! n=3; when a broadcast channel is available, then this bound is ta ! n=2. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating ta ! n=3 actively corrupted players, pr...
The problem of secure multi-party computation(SMPC) is one of the most fundamental problems in information security. First, we introduce the basic concept of SMPC and four SMPC basic agreement: key distribution,oblivious transfer, bit commitment and zero knowledge proof. Secondly, we separately illustrate commitment schemes  commitment transfer protocol, commitment sharing protocol and commitment multiplication protocol. Finally, we present unconditionally secure multi-party computation with a passive adversary, an active adversary, general adversary structures.
The classical results in unconditional multi-party computation among a set of n players state that less than n/2 passive or Iess than n/3 active adversaries can be tolerated; assuming a broadcast channel the threshold for active adversaries is ta/2.Strictly generalizing these results we specify the set of potential y misbehaving players as an arbitrary set of subsets of the player set.We prove the necessary and sufficient conditions for the existence of secure multi-party protocols in terms of the potentially misbehaving player sets.For every function there exists a protocol secure against a set of potential passive collusions if and only if no two of these collusions add up to the full player set.The same condition applies for active adversaries when assuming a broadcast chzmnel.Without broadcast channels, for every function there exists a protocol secure against a set of potential active adverse player sets if and only if no three of these sets add up to the full player set.The complexities of the protocols not using a broadcast channel are polynomial, that of the protocol with broadcast is only slightly higher.
In the setting of secure multiparty computation, a set of n parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full detailed proof of these results was never given. In this paper, we remedy this situation and provide a full proof of security of the BGW protocol. We also derive corollaries for security in the presence of adaptive adversaries and under concurrent general composition (equivalently, universal composability). In addition, we give a full specification of the protocol for the malicious setting. This includes one new step