Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation.

Yehuda Lindell

Published Jan 1, 2001• 0 citations

Abstract

Abstract. In this paper we show that any two-party functionality can be securely computed in a constant number of rounds, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao’s constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds. In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round perfect coin-tossing protocol, where by “perfect ” we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom). 1

Related papers

A constant-round perfect parallel coin-tossing protocol

Xiaolan Zhang, Hong-xiang Sun, Hua Zhang +2 more

A coin-tossing protocol lets two parties decide on a string that should be a random (or at least pseudorandom) string. In this paper, we focus on taking advantage of the perfectly hiding commitment scheme, constant-round perfect zero-knowledge arguments and arguments of knowledge to construct a two-party constant-round perfect protocol for secure coin-tossing, where both of two parties can obtain the common resulting coins and the resulting coins are guaranteed to be statistically close to uniform. The security of our protocol is obtained against malicious non-uniform adversaries that may arbitrarily deviate from the protocol specification. Comparing with the Barak's protocol, we utilize the black-box reduction in the process of security proof and the rounds of our protocol decrease obviously.

IEEE International Conference on Progress in Informatics and ComputingDec 1, 20100 citations

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries.

Yehuda Lindell, Benny Pinkas B

Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1

Jan 1, 20080 citations

Protocols for Multiparty Coin Toss With Dishonest Majority.

Amos Beimel, Eran Omri, Ilan Orlov

Abstract. Coin-tossing protocols are protocols that generate a random bit with uniform distribution. These protocols are used as a building block in many cryptographic protocols. Cleve [STOC 1986] has shown that if at least half of the parties can be malicious, then, in any r-round coin-tossing protocol, the malicious parties can cause a bias of Ω(1/r) to the bit that the honest parties output. However, for more than two t, where t is the number

Jan 1, 20122 citations

A Proof of Yao's Protocol for Secure Two-Party Computation

Yehuda Lindell, Benny Pinkas B

In the mid 1980’s, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao’s protocol, along with a rigorous proof of security. Despite the importance of Yao’s protocol to the field of secure computation, to the best of our knowledge, this is the first time that a proof of security has been published. 1

Electronic colloquium on computational complexityJan 1, 2004150 citations

On the Computational Complexity of Coin Flipping

Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai

Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.

Annual Symposium on Foundations of Computer ScienceOct 1, 201029 citations

An Optimally Fair Coin Toss.

Tal Moran, Moni Naor, Gil Segev

We address one of the foundational problems in cryptography: the bias of coin-\nipping pro-tocols. Coin-\nipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot signicantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party r-round coin-\nipping protocol there exists an efficient adversary that can bias the output of the honest party by Ω(1=r). However, the best previously known protocol only guarantees O(1= p r) bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years. In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-\nipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an r-round protocol with bias O(1=r).

Jan 1, 20090 citations