Search

In the standard general-adversary model for multi-party protocols, a global adversary structure is given, and every party must trust in this particular structure. We introduce a more general model, the asymmetric-trust model, wherein every party is allowed to trust in a different, personally customized adversary structure. We have two main contributions. First, we present non-trivial lower and upper bounds for broadcast, verifiable secret sharing, and general multi-party computation in different variations of this new model. The obtained bounds demonstrate that the new model is strictly more powerful than the standard general-adversary model. Second, we propose a framework for expressing and analyzing asymmetric trust in the usual simulation paradigm for defining security of protocols, and in particular show a general composition theorem for protocols with asymmetric trust. [ABSTRACT FROM AUTHOR]

Perfectly secure message transmission (PSMT), a problem formulated by Dolev, Dwork, Waarts and Yung, involves a sender ${\cal S}$ and a recipient ${\cal R}$ who are connected by n synchronous channels of which up to t may be corrupted by an active adversary. The goal is to transmit, with perfect security, a message from ${\cal S}$ to ${\cal R}$. PSMT is achievable if and only if n > 2t. For the case n > 2t, the lower bound on the number of communication rounds between ${\cal S}$ and ${\cal R}$ required for PSMT is 2, and the only known efficient (i.e., polynomial in n) two-round protocol involves a communication complexity of O(n3ℓ) bits, where ℓ is the length of the message. A recent solution by Agarwal, Cramer and de Haan is provably communication-optimal by achieving an asymptotic communication complexity of O(nℓ) bits; however, it requires the messages to be exponentially large, i.e., ℓ = Ω(2n). In this paper we present an efficient communication-optimal two-round PSMT protocol for messages of length polynomial in n that is almost optimally resilient in that it requires a number of channels n ≥ (2 + ε)t, for any arbitrarily small constant ε > 0. In this case, optimal communication complexity is O(ℓ) bits. [ABSTRACT FROM AUTHOR]

We consider perfect verifiable secret sharing (VSS) in a synchronous network of n processors (players) where a designated player called the dealer wishes to distribute a secret s among the players in a way that no t of them obtain any information, but any t + 1 players obtain full information about the secret. The round complexity of a VSS protocol is defined as the number of rounds performed in the sharing phase. Gennaro, Ishai, Kushilevitz and Rabin showed that three rounds are necessary and sufficient when n > 3t. Sufficiency, however, was only demonstrated by means of an inefficient (i.e., exponential-time) protocol, and the construction of an efficient three-round protocol was left as an open problem. In this paper, we present an efficient three-round protocol for VSS. The solution is based on a three-round solution of so-called weak verifiable secret sharing (WSS), for which we also prove that three rounds is a lower bound. Furthermore, we also demonstrate that one round is sufficient for WSS when n > 4t, and that VSS can be achieved in 1 + ε amortized rounds (for any ε > 0 ) when n>3t. [ABSTRACT FROM AUTHOR]

We show that if a set of players hold shares of a value for some prime p (where the set of shares is written [a]p), it is possible to compute, in constant rounds and with unconditional security, sharings of the bits of a, i.e., compute sharings [a0]p..., [aℓ-1]p such that ℓ = ⌈ log2p ⌉, and a = ∑i=0ℓ-1ai 2i. Our protocol is secure against active adversaries and works for any linear secret sharing scheme with a multiplication protocol. The complexity of our protocol is invocations of the multiplication protocol for the underlying secret sharing scheme, carried out in rounds. This result immediately implies solutions to other long-standing open problems such as constant-rounds and unconditionally secure protocols for deciding whether a shared number is zero, comparing shared numbers, raising a shared number to a shared exponent and reducing a shared number modulo a shared modulus. [ABSTRACT FROM AUTHOR]

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, privacy can be guaranteed against every minority, thus tolerating additional tp ≤ n/6 passively corrupted players. These protocols require no broadcast and have an exponentially small failure probability. When zero failure probability is required, privacy can be maintained against any minority, but one can even tolerate ta ≤ n/4 of these players to be corrupted actively. We further show that the bound t < n/2 for passive corruption holds even if the adversary is additionally allowed to make the passively corrupted players fail. Moreover, we characterize completely the achievable thresholds ta, tp and tf for four scenarios. Zero failure probability is achievable if and only if 2ta + 2tp + tf < n and 3ta + tp + tf < n; this holds whether or not a broadcast channel is available. Exponentially small failure probability with a broadcast channel is achievable if and only if 2ta + 2tp + tf

This paper presents protocols for Byzantine agreement, i.e. for reliable broadcast, among a set of n players, some of which may be controlled by an adversary. It is well-known that Byzantine agreement is possible if and only if the number of cheaters is less than n/3. In this paper we consider a general adversary that is specified by a set of subsets of the player set (the adversary structure), and any one of these subsets may be corrupted by the adversary. The only condition we need is that no three of these subsets cover the full player set. A result of Hirt and Maurer implies that this condition is necessary and sufficient for the existence of a Byzantine agreement protocol, but the complexity of their protocols is generally exponential in the number of players. The purpose of this paper is to present the first protocol with polynomial message and computation complexity for any (even exponentially large) specification of the adversary structure. This closes a gap in a recent result of Cramer, Damgård and Maurer on applying span programs to secure multi-party computation. [ABSTRACT FROM AUTHOR]