Multi party computations
Published 1 January 1997
Shafi Goldwasser
Citations238
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
Cryptography is traditionally concerned with two users, Alice and Bob, who want to communicate privately and authentically over an insecure channel, and in modern times engage in protocols such as coin flipping over the telephone, contract signing, and interactive zero-knowledge proofs.
Abstract
Article Multi party computations: past and present Share on Author: Shafi Goldwasser MIT Laboratory for Computer Science, 545 Technology, Square, Cambridge, MA and The Weizmann, Institute MIT Laboratory for Computer Science, 545 Technology, Square, Cambridge, MA and The Weizmann, InstituteView Profile Authors Info & Claims PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computingAugust 1997 Pages 1–6https://doi.org/10.1145/259380.259405Online:01 August 1997Publication History 128citation1,742DownloadsMetricsTotal Citations128Total Downloads1,742Last 12 Months70Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Keywords
Computer Science
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
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.
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.
SIAM Journal on ComputingThe Knowledge Complexity of Interactive Proof Systems
3,186 Citations1989Shafi Goldwasser, Silvio Micali +1 more
A computational complexity theory of the “knowledge” contained in a proof is developed and examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity.
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!
Lecture notes in computer scienceEntity Authentication and Key Distribution
1,735 Citations2007Mihir Bellare, Phillip Rogaway
This work provides the first formal treatment of entity authentication and authenticated key distribution appropriate to the distributed environment and presents a definition, protocol, and proof that the protocol meets its goal, assuming only the existence of a pseudorandom function.
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.
Non-malleable cryptography
992 Citations1991Danny Dolev, Cynthia Dwork +1 more
Non-malleable schemes for each of the contexts of string commitment and zero-knowledge proofs of possession of knowledge, where a user need not know anything about the number or identity of other system users are presented.
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.
Verifiable secret sharing and multiparty protocols with honest majority
930 Citations1989Tal Rabin, Michael Ben-Or
A verifiable secret sharing protocol is presented, and it is shown that any multiparty protocol, or game with incomplete information, can be achieved if a majority of the players are honest.
Lecture notes in computer scienceProactive Secret Sharing Or: How to Cope With Perpetual Leakage
718 Citations1995Amir Herzberg, Stanisław Jarecki +2 more
In order to guarantee the availability and integrity of the secret, this work provides mechanisms to detect maliciously (or accidentally) corrupted shares, as well as mechanisms to secretly recover the correct shares when modification is detected.
Adaptively secure multi-party computation
546 Citations1996Ran Canetti, Uri Feige +2 more
This work proposes a novel property of encryption protocols and shows that if an encryption protocol enjoying this property is used, instead of a standard encryption scheme, then known constructions become adaptively secure.
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.
How to withstand mobile virus attacks (extended abstract)
453 Citations1991Rafail Ostrovsky, Moti Yung
It is shown how local computations (at each processor) and global computations can be made robust using a constant factor resilience and a polynomial factor redundancy in the computation.
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.
Lecture notes in computer scienceReceipt-Free Mix-Type Voting Scheme
320 Citations1995Kazue Sako, Joe Kilian
This work presents a receipt-free voting scheme based on a mixtype anonymous channel, where the sole physical assumption is the existence of a private channel through which the center can send the voter a message without fear of eavesdropping.
Fast asynchronous Byzantine agreement with optimal resilience
299 Citations1993Ran Canetti, Tal Rabin
Symposium on the Theory of ComputingReceipt-Free Secret-Ballot Elections
282 Citations1994Josh Cohen Benaloh
Lecture notes in computer scienceFoundations of Secure Interactive Computing
280 Citations2007Donald Beaver
Relative resilience provides modular proof techniques that other approaches lack: one may compare a sequence of protocols ranging from the real-world protocol to the ideal protocol, proving the relative resilience of each successive protocol with greater clarity and less complexity.
Achieving oblivious transfer using weakened security assumptions
270 Citations1988Claude Crépeau, Joe Kilian
The authors present some general techniques for establishing the cryptographic strength of a wide variety of games and show that a noisy telephone line is in fact a very sophisticated cryptographic device.
Communication complexity of secure computation (extended abstract)
262 Citations1992Matthew Franklin, Moti Yung
This paper begins the investigation of the communication complexity of unconditionally secure multi-party computation, and its relation with various fault-tolerance models, and presents upper and lower bounds on communication, as well as tradeoffs among resources.
Lecture notes in computer scienceDeniable Encryption
255 Citations1997Rein Canetti, Cynthia Dwork +2 more
Simple constructions that transform sender-deniable schemes into receiver-deniability schemes and vice-versa are described, with respect to schemes that encrypt only one bit at a time.
Optimal algorithms for Byzantine agreement
250 Citations1988Paul Feldman, Silvio Micali
For both synchronous and asynchronous networks whose lines do not guarantee private communication, the authors may use cryptography to obtain algorithms optimal both in fault tolerance and running time against computationally bounded adversaries.
Asynchronous secure computation
220 Citations1993Michael Ben-Or, Ran Canetti +1 more
A study of security in asynchronous networks considers a completely asynchronous network where every two parties are connected via a private channel, and some of the parties may be faulty, and defines secure computation in this model, which adapts the underlying principles of defining security to the asynchronous model.
Asynchronous secure computations with optimal resilience (extended abstract)
180 Citations1994Michael Ben-Or, Boaz Kelmer +1 more
This work describes an ( [~1 – I)-resilient protocol that securely computes any function F, and introduces a new secret sharing scheme called Ultimate Secret Sharing that guarantees that all the honest players will obtain their share of the secret, and it enables the players to verify that the shares are genuine.
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...
Lecture notes in computer scienceCryptographic Protocols Provably Secure Against Dynamic Adversaries
135 Citations2007Donald Beaver, Stuart Haber
It is proved that this protocol is secure against the malicious actions of any adversary, limited to feasible computation, but with the power to eavesdrop on all messages and to corrupt any dynamically chosen minority of the parties.
Lecture notes in computer scienceMaintaining Security in the Presence of Transient Faults
105 Citations2007Ran Canetti, Amir Herzberg
A scheme which, using randomness only at the beginning of the computation, supplies each party with a new pseudorandom number at each round of communication, which is unpredictable by an adversary controlling the viruses, even if the party was infected in previous rounds.
Journal of the ACMRobust sharing of secrets when the dealer is honest or cheating
98 Citations1994Tal Rabin
The problem of Verifiable Secret Sharing is the following: A dealer, who may be honest or cheating, can share a secret s, among n ≥ 2t + 1 players, where t players at most are cheaters.
Solvability in asynchronous environments
35 Citations1989Benny Chor, Lior Moscovici
The authors present necessary and sufficient combinatorial conditions that determine membership in SM/ sub t/ (respectively, MP/sub t/), the class of distributed decision tasks that are solvable in the shared memory model by a t-resilient randomized protocol, which never errs and works in the presence of a strong adversary.
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).