Fault-tolerant computation in the full information model
Published 9 December 2002
Oded Goldreich, S. Goldwasser, Nathan Linial
Citations23
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is proved for these protocols that for most functions, the influence of any t dishonest players on the outcome of the protocol is the minimum one possible (up to polylogarithmic factors).
Abstract
Efficient two-party protocols for fault-tolerant computation of any two-argument function are presented. It is proved that the influence of a dishonest player in these protocols is the minimum one possible (up to polylogarithmic factors). Also presented are efficient m-party fault-tolerant protocols for sampling a general distribution (m>or=2). Efficient m-party protocols for computation of any m-argument function are given, and it is proved for these protocols that for most functions, the influence of any t dishonest players on the outcome of the protocol is the minimum one possible (up to polylogarithmic factors).>
Keywords
Computer Science
How to generate and exchange secrets
3,712 Citations1986Andrew Chi-Chih Yao
It is shown how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors, is hidden from either party individually but is recoverable jointly if desired.
How to play ANY mental game
3,541 Citations1987Oded Goldreich, Silvio Micali +1 more
This work presents a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest.
Protocols for secure computations
3,014 Citations1982Andrew Chi-Chih Yao
Foundations of Computer ScienceProtocols for secure computations
2,715 Citations1982Andrew Chi-Chih Yao
The author gives a precise formulation of this general problem and describes three ways of solving it by use of one-way functions, which have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc.
Completeness theorems for non-cryptographic fault-tolerant distributed computation
2,515 Citations1988Michael Ben-Or, Avi Wigderson
The above bounds on t, where t is the number of players in actors, are tight!
Multiparty unconditionally secure protocols
1,515 Citations1988David Chaum, Claude Crépeau +1 more
It is shown that any reasonable multiparty protocol can be achieved if at least 2n/3 of the participants are honest and the secrecy achieved is unconditional.
Founding crytpography on oblivious transfer
1,029 Citations1988Joe Kilian
It is shown that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol,known as oblivious circuit evaluation([Y], and that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in NP.
The influence of variables on Boolean functions
618 Citations1988J. Kahn, Gil Kalai +1 more
Methods from harmonic analysis are used to prove some general theorems on Boolean functions and enable them to prove theorem on the rapid mixing of the random walk on the cube and in the extremal theory of finite sets.
SIAM Journal on ComputingUnbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
554 Citations1988Benny Chor, Oded Goldreich
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
544 Citations1986Oded Goldreich, Silvio Micali +1 more
This paper demonstrates the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff that efficiently demonstrate membership in the language without conveying any additional knowledge.
Lecture notes in computer scienceFair Computation of General Functions in Presence of Immoral Majority
355 Citations2007Shafi Goldwasser, Leonid A. Levin
A method for n players to compute correctly, privately, and fairly any computable function f(x1,...,xn) where xi, is the input of the i-th player, and proposes a simpler definition of security for multi-player protocols which still implies previous definitions of privacy and correctness.
SIAM Journal on Discrete MathematicsA Zero-One Law for Boolean Privacy
148 Citations1991Benny Chor, Eyal Kushilevitz
An interesting “zero-one” law for private distributed computation of Boolean functions is derived: every Boolean function defined over a finite domain is either n-private, or it is $\lfloor ( n - 1 )/2 \rfloor $-private but not $\lceil n/ 2 \rceil $-p...
Foundations in signal processing, communications and networkingFounding Cryptography on Oblivious Transfer
119 Citations2016Rudolf Ahlswede
In cryptography, an oblivious transfer protocol (abbreviated OT) is a fundamental protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious to what piece has been transferred.
Generating Quasi-Random Sequences From Slightly-Random Sources
99 Citations2005Miklós Sántha, Umesh Vazirani
It is proved that quasi-random sequences can be used in place of truly random ones for applications such as seeds for pseudo-random number generators, randomizing algorithms, and stochastic simulation experiments.
Random polynomial time is equal to slightly-random polynomial time
91 Citations1985Umesh Vazirani, Vijay V. Vazirani
This paper gives an affirmative answer to the question "is Rp = SRp?" and shows how to obtain an SRp algorithm for it, which is a more realistic definition of a tractable computational problem.
Lecture notes in computer sciencePerfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions
61 Citations2007Moni Naor, Rafail Ostrovsky +2 more
A general construction of zero-knowledge arguments, which can be based on any one-way permutation, is shown, which is efficient both players can execute only polynomial-time programs during the protocol and the security achieved is on-line.
Fair Games Against an All-Powerful Adversary
57 Citations1993Rafail Ostrovsky, Ramarathnam Venkatesan +1 more
SIAM Journal on ComputingCoin-Flipping Games Immune against Linear-Sized Coalitions
56 Citations1993Noga Alon, Moni Naor
Fault-tolerant computation in the full information model
23 Citations2002Oded Goldreich, S. Goldwasser +1 more
It is proved for these protocols that for most functions, the influence of any t dishonest players on the outcome of the protocol is the minimum one possible (up to polylogarithmic factors).