How to play any mental game, or a completeness theorem for protocols with honest majority

By O. Goldreich, Silvio Micali, Avi Wigderson. Providing Sound Foundations for Cryptography, 2019

667 citations recorded by the source corpus.

Permission to copy without fee all or part of this material is granted provided that the copies are not made or Idistributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machimery. To copy otherwise, or to republish, requires a fee and/or specfic permission. correctly run a given Turing machine hi on these 2;‘s while keeping the maximum possible pniracy about them. That is, they want to compute Y~(~l,..., 2,) without revealing more about the Zi’s than it is already contained in the value y itself. For instance, if M computes the sum of the q’s, every single player should not be able to learn more than the sum of the inputs of the other parties. Here A4 ma.y very well be a probabilistic Turing machine. In this case, all playen want to agree on a single string y, selected with the right probability distribution, as M’s output.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/0104b5d5bcf4356939c5dd0c8df0018216b0030d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

SPD Z 2 k : Eﬃcient MPC mod 2 k for Dishonest Majority (2018, result): “7, is similar to that in other secret sharing-based protocols like GMW, BeDOZa, SPDZ and MASCOT [11,2,9,14].”
SPDℤ2k: Efficient MPC mod 2k for Dishonest Majority (2018, neutral): “Over the integers modulo 232, the overhead reduces to around 50% more than MASCOT, although here the statistical security parameters of 26 and 32 bits may be too low for some applications.”
Universally Composable Two-Party and Multi-party Secure Computation (neutral): “(This notion was implicitly present in the work of Goldreich, Micali, and Wigderson [33], and explicitly proposed by Kilian [37].”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, background): “The GMW compiler relies on standard zero-knowledge proofs, which apply to public statements.”
New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning (2019, background): “A typical choice of algebraic structure is the ﬁnite ﬁeld 2 [5], [6], [7], [ ?”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, background): “Secure multi-party computation (MPC) [69, 36] is concerned with privacy of the users’ input from a dierent perspective.”