Multiparty unconditionally secure protocols
Published 1 January 1988
David Chaum, Claude Crépeau, Ivan Damgård
Citations1,515
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 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.
Abstract
Under the assumption that each pair of participants em communieatc secretly, we show that any reasonable multiparty protwol can be achieved if at least Q of the Participants am honest.The secrecy achieved is unconditional, It does not rely on any assumption about computational intractability.
Keywords
Computer Science
Communications of the ACMHow to share a secret
13,453 Citations1979Adi Shamir
This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.
ACM Transactions on Programming Languages and SystemsThe Byzantine Generals Problem
5,966 Citations1982Leslie Lamport, Robert E. Shostak +1 more
It is shown that, using only oral messages, the problem of a group of generals camped with their troops around an enemy city is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals.
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!
Association for Computing Machinery eBooksThe Byzantine generals problem
1,019 Citations2019Leslie Lamport, Robert E. Shostak +4 more
Journal of Computer and System SciencesMinimum disclosure proofs of knowledge
956 Citations1988Gilles Brassard, David Chaum +1 more
This paper unifies and extends models and techniques previously put forward by the authors, and compares some independent related work.
Communications of the ACMOn sharing secrets and Reed-Solomon codes
634 Citations1981Robert J. McEliece, D.V. Sarwate
Decoding algorithms for Reed-Solomon codes provide extensions and generalizations of Shamir's method, which is closely related to Reed- Solomon coding schemes.
Polynomial algorithms for multiple processor agreement
149 Citations1982Danny Dolev, H. Raymond Strong
It is proved that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.
Association for Computing Machinery eBooksCompleteness theorems for non-cryptographic fault-tolerant distributed computation
97 Citations2019Michael Ben-Or, Shafi Goldwasser +2 more
Lecture notes in computer scienceZero-Knowledge Simulation of Boolean Circuits
72 Citations2007Gilles Brassard, Claude Crépeau
A zero-knowledge interactive proof is a protocol by which Alice can convince a polynomially-bounded Bob of the truth of some theorem without giving him any hint as to how the proof might proceed.
Information and ControlMental poker with three or more players
30 Citations1983Imre Bárány, Zoltán Füredi
A protocol is given which deals cards to three or more players in a fair way and some related questions are also discussed.
Security Proofs for Information Protection Systems
21 Citations1981G. R. Blakley, L. Swanson
The purpose is to put a rigorous foundation under the intuitive security arguments these papers adduce, and produce a distinctive style of proof of security, a rigorous argument involving product measures as a conceptual basis for justifying intuitively plausible probabilistic statement of the sort C. E. Shannon used to describe the security of the one-time pad.