References to Secure Multiparty Computation Literature

Secure Multiparty Computation


In “distributed computing” a number of networked players carry out a joint computation of a function on their inputs. The aim of secure multiparty computation (or simply, multiparty computation), in contrast, is to enable players to carry out distributed computing tasks on their private information while under attack by an external entity (“the adversary”) and/or by a subset of malicious players (“the colluding players”). The purpose of the attack is to learn the private information of non-colluding, honest players or to cause the computation to be incorrect. As a result, there are two important requirements of a multiparty computation protocol: privacy and correctness. Below is a list of key and a list of supporting publications found in the computer science literature. (If you have an additional citation you deem essential to this collection, please let us know.)


Application Areas: distributed sueveillance, privacy-preserving data mining


Key References

  1. W. Diffie and M. Hellman. New directions in cryptography. Information Theory, IEEE Transactions on, 22(6):644-654, 1976. [.pdf ] A ground breaking paper in the area of computational cryptography that set the stage for much of the work in secure multi-party computation that followed. A secure protocol for key exchange is presented based on the computational difficulty of inverting the discrete logarithm function.

  2. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979. [ .pdf ] Introduces the problem of secret sharing (SS) which becomes an important application domain for multiparty computation in the future.

  3. D. Chaum. Blind signatures for untraceable payments. In Proceedings of Advances in Cryptology, pages 199-203. Plenum Press, 1982. [ .pdf ] Introduces the idea of blind signatures as a form of multi-party computation that can be applied to one of the key problem domains: protocols for privacy preserving electronic cash.

  4. A. Yao. Protocols for secure computations. In Proceedings of the twenty-third annual IEEE Symposium on Foundations of Computer Science, pages 160-164. IEEE Computer Society, 1982. Builds the foundations for general secure multi-party computation. The millionaire problem is introduced: Alice and Bob are two millionaires who want to know which is richer, but without revealing the precise amount of their wealth. Proposes a solution allowing Alice and Bob to satisfy their curiosity while respecting the constraints.

  5. Manuel Blum. Coin flipping by telephone a protocol for solving impossible problems. SIGACT News, 15(1):23-27, 1983. [ .pdf ] Extends the Diffie-Hellman key exchange protocol to arbitrary multi-party compuations. A method for ensuring that a random coin-flip (or bit choice) is accurately computed by multiple parties via an insecure phone line is presented. Theoretical analysis garauntees that the outcome of the coin-flip will be random.

  6. A. Yao. How to generate and exchange secrets. In Proceedings of the twenty-seventh annual IEEE Symposium on Foundations of Computer Science, pages 162-167. IEEE Computer Society, 1986. An extension of earlier work that formalizes the notion of secure multiparty protocols for secret sharing.

  7. O. Goldreich, S. Micali, and A. Wigderson. How to play ANY mental game. In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 218-229. ACM Press, 1987. [ .pdf ] Provides an algorithm for converting any game with incomplete information to a multi-party protocol which leaks no partial information as long as a majority of players is honest.

  8. Michael Ben-Or and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 1-10. ACM Press, 1988. [ .pdf ] Proves completeness theorems about multi-party protocols in the information theoretic sense. More than half of the players must collaborate to ever learn information other than the final output, if everyone plays honestly. More than one third of the players must collaborate if there are Byzantine faults in the system.

  9. David Chaum, Claude Cropeau, and Ivan Damgard. Multiparty unconditionally secure protocols. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 11-19. ACM Press, 1988. [ .pdf ] Proves completeness theorems for secure multiparty protocols regardless of computational power. More than one third of the players must collaborate to break any reasonable multiparty protocol.

  10. Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 52-61. ACM Press, 1993. [ .pdf ] Introduces the notion of asynchronous multiparty computation and examines security issues surrounding it.

  11. Josh Cohen Benaloh and Michael de Mare. One-way accumulators: A decentralized alternative to digital signatures. Lecture Notes in Computer Science, 765:274-286, 1994. [.pdf ] Presents a protocol for securely accumulating the results of computation accross multiple parties using a quasi-commutative one way hash function. One-way accumulators are desirable because they allow secure multi-party computation to take place without the need for a trusted third party.

  12. Ran Canetti, Uri Feige, Oded Goldreich, and Moni Naor. Adaptively secure multi-party computation. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 639-648. ACM Press, 1996. [ .pdf ] Identifies flaws in previous multi-party computation work arrising from the introduction of adaptive adversarys, who choose to corrupt involved parties dynamically during the computation. Introduces the notion of a semi-honest party, who appears to be honest from an outside persepective, but deviates from the protocol in some way. Presents a secure protocol, using a trusted third party, to avoid the adaptive adversarial pitfalls.

  13. Victor Shoup. On formal models for secure key exchange. Technical Report RZ 3120 (#93166), 1999. [ .pdf ] A good survey of formal models and methods used for secure multi-party computation.

  14. Ronald Cramer, Ivan Damgard, and Stefan Dziembowski. On the complexity of verifiable secret sharing and multiparty computation. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 325-334. ACM Press, 2000. [ .pdf ] Theoretical discussion of complexity constraints on secure multiparty protocols, specifically for the secret sharing problem.


Supporting References

  1. Ran Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, 1996. [ .html ]

  2. Moni Naor, Benny Pinkas, and Omer Reingold. Distributed pseudo-random functions and KDCs. Lecture Notes in Computer Science, 1592:327-??, 1999. [ .html ]

  3. Yehuda Lindell and Benny Pinkas. Privacy preserving data mining. Lecture Notes in Computer Science, 1880:36-??, 2000. [ .html ]

  4. N. Hopper, J. Langford, and L. von Ahn. Provably secure steganography, 2002. [ .html ]

  5. Paul Beame and Erik Vee. Time-space tradeoffs, multiparty communication complexity and nearest-neighbor problems. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 688-697. ACM Press, 2002. [ https ]

  6. S. Micali, M. Rabin, and J. Kilian. Zero-knowledge sets, 2003. [ .html ]

  7. Joseph Halpern and Vanessa Teague. Rational secret sharing and multiparty computation: extended abstract. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 623-632. ACM Press, 2004. [ .pdf ]

  8. B. Malin, E. Airoldi, S. Edoho-Eket, and Y. Li. Configurable security protocols for multi-party data analysis with malicious participants. In Proceedings of the 21st IEEE International Conference on Data Engineering, 2005. [ .pdf ]

  9. L. Sweeney and M. Shamos. A Multiparty Computation for Randomly Ordering Players and Making Random Selections. Carnegie Mellon University, School of Computer Science, Technical Report, CMU-ISRI-04-126. Pittsburgh: July 2004. [ .pdf ]


Related Links

This list was compiled in part by Michael Benisch. For additions or changes, please contact us.

Copyright © 2011. President and Fellows Harvard University.   |   IQSS   |    Data Privacy Lab   |    [info@dataprivacylab.org]