Multi-Party Computation | MIT CSAIL Theory of Computation

Multiparty computation allows a group of players to perform a given task as correctly and as privately as if a trusted third party has performed the computation on a players behalf. In fundamental papers by Goldreich, Micali and Wigderson [GMW87] and Ben-Or, Goldwasser and Wigderson [BGW88] it was shown that any probabilistic (polynomial-time) function can be securely computed in the computational and in the information-theoretic settings. Ever since, many papers have been produced and a lot of research is still going on in this fundamental area. In particular, the following issues are of critical importance: ability to compose secure protocols (e.g., sequential/parallel/concurrent reducibility), round and communication complexity, the network structure (e.g., existence of private channels, broadcast, limited connectivity), adversary structure that can be tolerated (e.g., thereshold adversaries), types of adversary (e.g., active/passive/fail, adaptive/non-adaptive) and some others.

ARTICLES IN REFEREED CONFERENCES OR JOURNALS

Micciancio, D., and Tessaro, S. "An Equational Approach to Secure Multi-Party Computation." Innovations in Theoretical Computer Science (ITCS2013).

Boyle, E., Goldwasser, S., Tessaro, S. “Communication Locality in Secure Multi-party Computation - How to Run Sublinear Algorithms in a Distributed Setting.” TCC 2013.

Akavia, A., Goldwasser, S., and Hazay, C. “Distributed Public Key Schemes Secure against Continual Leakage.” Proceedings of the 31th Annual ACM Symposium on Principles of Distributed Computing (PODC 2012), Funchal, Madeira, Portugal, pages 155-164, July 2012.

Boyle, E., Goldwasser, S., Jain, A., and Tauman Kalai, Y. “Multiparty Computation Secure Against Continual Memory Leakage.” Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), New York, NY, May 2012.

Boyle, E., Goldwasser, S., and Tauman Kalai, Y. “Coin Tossing with Leakage.” Proceedings of the 25th International Symposium on DIStributed Computing, Rome, Italy, September 20-22, 2011.

Canetti, R., Eiger, D., Goldwasser, G., and Lim, D.Y. “How to Protect Yourself without Perfect Shredding.” 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), pages 511-523, Reykjavik, Iceland, July 2008.

Chen, H., Cramer, R., Goldwasser, S., de Haan, R., and Vaikuntanathan, V. “Secure Computation from Random Error Correcting Codes.” EUROCRYPT 2007, Barcelona, Spain, pages 291-310, May 2007.

Goldwasser, S., Pavlov, E., and Vaikuntanathan, V. “Fault-Tolerant Distributed Computing in Full-Information Networks.” Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, CA, October 2006.

Goldwasser, S. and Lindell, Y. “Secure Multi-Party Computation without Agreement.” J. Cryptology 18(3):247-287, 2005.

Goldwasser, S., Sudan, M., and Vaikuntanathan, V. “Distributed Computing with Imperfect Randomness.” 19th International Symposim on Distributed Computing (DISC 2005), Cracow, Poland, pages 288-302, September 2005.

Goldwasser, S. and Lindell, Y. “Secure Computation without Agreement.” Proceedings of the 16th Int’l Symposium on DIStributed Computing (DISC 2002), pages 17-32, Toulouse, France, October 2002.

Gertner Y., Goldwasser S., and Malkin T. “A Random Server Model for Private Information Retrieval (or How to Achieve Information Theoretic PIR Avoiding Database Replication).” 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 1998), Barcelona, Spain, October 1998.

Goldwasser, S. “Multi-Party Computations: Past and Present.” Invited paper to Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing (PODC 1997), Santa Barbara, California, USA, August 21-24, 1997.

Goldreich, O., Goldwasser S., and Linial N. “Fault Tolerant Distributed Computation in the Full Information Model.” Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), Puerto Rico, October 1991.

Goldwasser, S. and Levin L. “Fair Computation of General Functions in Presence of Immoral Majority.” A. Menezes, S. Vanstone, editors Advances in Cryptology (Proceedings of CRYPTO90, Santa Barbara, CA, August 1990), volume 537 of Lecture Notes in Computer Science,1991. Springer.

Beaver, D. and Goldwasser, S. “Multi Party Fault Tolerant Computation with Faulty Majority Based on Oblivious Transfer.” Proceedings of 30th Annual Symposium on Foundations of Computer Science (FOCS89), Duke, NC, October 1989.

Beaver, D. and Goldwasser, S. “Multi Party Fault Tolerant Computation with Faulty Majority.” G. Brassard, editor, Advances in Cryptology - Proceedings of 9th Annual Intl. Cryptology Conference (Crypto89), volume 435 of Lecture Notes in Computer Science, pages 589-590, 1989. Springer.

Ben-Or, M., Goldwasser S., Kilian J., and Wigderson A. “Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions.” Proceedings of 20th Annual ACM Symposium on Theory of Computing (STOC 1988), Chicago, Illinois, pages 113-122, May 1988.

Chor, B., Goldwasser S., Micali S., and Awerbuch B. “Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults.” Proceedings of 26th Annual Symposium on the Foundations of Computer Science (FOCS 1985), pages 383-395, October 1985.