Completeness theorems for non-cryptographic fault-tolerant distributed computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Completeness theorems for non-cryptographic fault-tolerant distributed computation

Full text

Pdf (1.05 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 1 - 10

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Michael Ben-Or	Hebrew University
Shafi Goldwasser	MIT
Avi Wigderson	Hebrew University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 31, Downloads (12 Months): 204, Citation Count: 148

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/62212.62213 What is a DOI?

ABSTRACT

Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that: If no faults occur, no set of size t < n/2 of players gets any additional information (other than the function value), Even if Byzantine faults are allowed, no set of size t < n/3 can either disrupt the computation or get additional information. Furthermore, the above bounds on t are tight!

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BL	M. Ben-Or and N. Linial, Collective coin flipping, FOCS86.
	CCD	David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
	DH	W. Diffie and M. E. Helman, New directions in cryptography, iEEE Trt~ns. Inform. Theory, VoI.IT-22,pp.644-654, 1976.
	DS	Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
	FM	P. Fcldlllan and S. Micali, Opt. inlal algoritllrns for Byzantine agreement, These proceediligs.
	GMW1	O. Goldriech, S. Micali and A. Wigderson, Proofs that yield nothing but the validity of the assertion, and a methodology of cryptographic protocol design, FOCS86, pp. 174-187.
	GMW2	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
	GMR	S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
	PSL	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
	PW	W. W. Peterson and E. J. Weldon, Error correcting codes, Second Ed., MiT Press, (1972).
	Sh	Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
	Y1	A. C. Yao, How to generate and exchange secrets~ STOC86.
	Y2	A. (2. Yao, On the succession problem for Byzantine Generals, manuscript, (1983).

CITED BY 149

	Matthew Franklin , Moti Yung, Communication complexity of secure computation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.699-710, May 04-06, 1992, Victoria, British Columbia, Canada
	Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece
	Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Yair Frankel , Philip D. MacKenzie , Moti Yung, Robust efficient distributed RSA-key generation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.663-672, May 24-26, 1998, Dallas, Texas, United States
	Ronald Fagin , Moni Naor , Peter Winkler, Comparing information without leaking it, Communications of the ACM, v.39 n.5, p.77-85, May 1996
	Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States
	Shlomi Dolev , Rafail Ostrobsky, Xor-trees for efficient anonymous multicast and reception, ACM Transactions on Information and System Security (TISSEC), v.3 n.2, p.63-84, May 2000
	Josh Benaloh , Dwight Tuinstra, Receipt-free secret-ballot elections (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.544-553, May 23-25, 1994, Montreal, Quebec, Canada
	Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States
	David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States
	Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States
	Harry Buhrman , Matthew Franklin , Juan A. Garay , Jaap-Henk Hoepman , John Tromp , Paul Vitányi, Mutual search, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.481-489, January 25-27, 1998, San Francisco, California, United States
	J. Bar-Ilan , D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.201-209, June 1989, Edmonton, Alberta, Canada
	Mihir Bellare , Juan A. Garay , Tal Rabin, Distributed pseudo-random bit generators—a new way to speed-up shared coin tossing, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.191-200, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Benny Chor, On privacy and partition arguments, Information and Computation, v.167 n.1, p.2-9, 5/25/2001
	Harry Buhrman , Matthew Franklin , Juan A. Garay , Jaap-Henk Hoepman , John Tromp , Paul Vitányi, Mutual search, Journal of the ACM (JACM), v.46 n.4, p.517-536, July 1999
	Yaron Minsky , Robbert van Renesse , Fred B. Schneider , Scott D. Stoller, Cryptographic support for fault-tolerant distributed computing, Proceedings of the 7th workshop on ACM SIGOPS European workshop: Systems support for worldwide applications, September 09-11, 1996, Connemara, Ireland
	Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Amortizing randomness in private multiparty computations, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.81-90, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Characterizing linear size circuits in terms of privacy, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.541-550, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Michael Ben-Or , Boaz Kelmer , Tal Rabin, Asynchronous secure computations with optimal resilience (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.183-192, August 14-17, 1994, Los Angeles, California, United States
	Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada
	Dan Boneh , Matthew Franklin, Efficient generation of shared RSA keys, Journal of the ACM (JACM), v.48 n.4, p.702-722, July 2001
	Ronald Cramer , Ivan Damgård , Stefan Dziembowski, On the complexity of verifiable secret sharing and multiparty computation, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.325-334, May 21-23, 2000, Portland, Oregon, United States
	Donald Beaver, Adaptive zero knowledge and computational equivocation (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.629-638, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Makoto Yokoo , Koutarou Suzuki, Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States
	Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States
	Anne Condon, Space-bounded probabilistic game automata, Journal of the ACM (JACM), v.38 n.2, p.472-494, April 1991
	B. Chor , E. Kushilevitz, A zero-one law for Boolean privacy, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.62-72, May 14-17, 1989, Seattle, Washington, United States
	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States
	Martin Hirt , Ueli Maurer, Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.25-34, August 21-24, 1997, Santa Barbara, California, United States
	Ran Canetti , Rafail Ostrovsky, Secure computation with honest-looking parties (extended abstract): what if nobody is truly honest?, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.255-264, May 01-04, 1999, Atlanta, Georgia, United States
	Tal Rabin, Robust sharing of secrets when the dealer is honest or cheating, Journal of the ACM (JACM), v.41 n.6, p.1089-1109, Nov. 1994
	Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States
	Claude Crépeau , Daniel Gottesman , Adam Smith, Secure multi-party quantum computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Matthew Franklin , Moti Yung, Secure hypergraphs: privacy from partial broadcast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.36-44, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Anna Gál , Adi Rosén, A theorem on sensitivity and applications in private computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.348-357, May 01-04, 1999, Atlanta, Georgia, United States
	Baruch Awerbuch , Israel Cidon , Shay Kutten , Yishay Mansour , David Peleg, Broadcast with partial knowledge (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.153-163, August 19-21, 1991, Montreal, Quebec, Canada
	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991
	Rosario Gennaro , Michael O. Rabin , Tal Rabin, Simplified VSS and fast-track multiparty computations with applications to threshold cryptography, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.101-111, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Shafi Goldwasser, Multi party computations: past and present, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.1-6, August 21-24, 1997, Santa Barbara, California, United States
	Donald Beaver, Commodity-based cryptography (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.446-455, May 04-06, 1997, El Paso, Texas, United States
	Uri Feige , Joe Killian , Moni Naor, A minimal model for secure computation (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.554-563, May 23-25, 1994, Montreal, Quebec, Canada
	Rafail Ostrovsky , Sridhar Rajagopalan , Umesh Vazirani, Simple and efficient leader election in the full information model, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.234-242, May 23-25, 1994, Montreal, Quebec, Canada
	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States
	Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002
	Christian Cachin, Efficient private bidding and auctions with an oblivious third party, Proceedings of the 6th ACM conference on Computer and communications security, p.120-127, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	Eyal Kushilevitz , Yishay Mansour, Randomness in private computations, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.181-190, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Mattias Fitzi , Ueli Maurer, From partial consistency to global broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.494-503, May 21-23, 2000, Portland, Oregon, United States
	D. Aharonov , M. Ben-Or, Fault-tolerant quantum computation with constant error, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.176-188, May 04-06, 1997, El Paso, Texas, United States
	Rei Safavi-Naini , Huaxiong Wang, Secret sharing schemes with partial broadcast channels, Designs, Codes and Cryptography, v.41 n.1, p.5-22, October 2006
	Matthew Franklin , Zvi Galil , Moti Yung, Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, Journal of the ACM (JACM), v.47 n.2, p.225-243, March 2000
	Chin-Chen Chang , Chi-Yien Chung, An efficient protocol for anonymous multicast and reception, Information Processing Letters, v.85 n.2, p.99-103, 31 January 2003
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Anna Gal , Adi Rosen, Lower bounds on the amount of randomness in private computation, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Robert McGrew , Ryan Porter , Yoav Shoham, Towards a general theory of non-cooperative computation, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana
	Matthias Fitzi , Juan A. Garay, Efficient player-optimal protocols for strong and differential consensus, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.211-220, July 13-16, 2003, Boston, Massachusetts
	Ueli Maurer, The role of cryptography in database security, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Ran Canetti , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Randomness vs. fault-tolerance, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.35-44, August 21-24, 1997, Santa Barbara, California, United States
	Donald Beaver, Server-assisted cryptography, Proceedings of the 1998 workshop on New security paradigms, p.92-106, September 22-26, 1998, Charlottesville, Virginia, United States
	Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin, The round complexity of verifiable secret sharing and secure multicast, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.580-589, July 2001, Hersonissos, Greece
	Mihir Bellare , Ran Canetti , Hugo Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.419-428, May 24-26, 1998, Dallas, Texas, United States
	Ran Canetti , Shai Halevi , Amir Herzberg, Maintaining authenticated communication in the presence of break-ins, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.15-24, August 21-24, 1997, Santa Barbara, California, United States
	Giovanni Di-Crescenzo , Yuval Ishai , Rafail Ostrovsky, Universal service-providers for database private information retrieval (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.91-100, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Silvio Micali , Kazuo Ohta , Leonid Reyzin, Accountable-subgroup multisignatures: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA
	W. G. Tzeng, A Secure Fault-Tolerant Conference-Key Agreement Protocol, IEEE Transactions on Computers, v.51 n.4, p.373-379, April 2002
	Bogdan S. Chlebus , Leszek Gasieniec , Andrzej Pelc, Deterministic computations on a PRAM with static processor and memory faults, Fundamenta Informaticae, v.55 n.3-4, p.285-306, June 2003
	M V N Ashwin Kumar , Pranava R. Goundan , K Srinathan , C. Pandu Rangan, On perfectly secure communication over arbitrary networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Danny Harnik , Moni Naor , Omer Reingold , Alon Rosen, Completeness in two-party secure computation: a computational view, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Matt Lepinski , Silvio Micali , Chris Peikert , Abhi Shelat, Completely fair SFE and coalition-safe cheap talk, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Alejandro Hevia , Marcos Kiwi, Electronic jury voting protocols, Theoretical Computer Science, v.321 n.1, p.73-94, June 16, 2004
	Moni Naor, Cryptography and mechanism design, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	Keith B. Frikken , Mikhail J. Atallah, Privacy preserving route planning, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA
	Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Journal of the ACM (JACM), v.51 n.6, p.851-898, November 2004
	József Balogh , János A. Csirik , Yuval Ishai , Eyal Kushilevitz, Private computation using a PEZ dispenser, Theoretical Computer Science, v.306 n.1-3, p.69-84, 5 September 2003
	Wen-Guey Tzeng, Efficient 1-Out-of-n Oblivious Transfer Schemes with Universally Usable Parameters, IEEE Transactions on Computers, v.53 n.2, p.232-240, February 2004
	Matt Lepinksi , Silvio Micali , abhi shelat, Collusion-free protocols, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Keith Frikken , Mikhail Atallah , Chen Zhang, Privacy-preserving credit checking, Proceedings of the 6th ACM conference on Electronic commerce, p.147-154, June 05-08, 2005, Vancouver, BC, Canada
	Alejandro Hevia , Daniele Micciancio, Simultaneous broadcast revisited, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Benny Pinkas, Cryptographic techniques for privacy-preserving data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.12-19, December 2002
	Michael Ben-Or , Ran El-Yaniv, Resilient-optimal interactive consistency in constant time, Distributed Computing, v.16 n.4, p.249-262, December 2003
	Yael Tauman Kalai , Yehuda Lindell , Manoj Prabhakaran, Concurrent general composition of secure protocols in the timing model, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Felix Brandt , Tuomas Sandholm, Decentralized voting with unconditional privacy, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
	Christian Scheideler, How to spread adversarial nodes?: rotate!, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Rosario Gennaro , Mario Di Raimondo, Secure multiplication of shared secrets in the exponent, Information Processing Letters, v.96 n.2, p.71-79, 31 October 2005
	Felix Brandt , Tuomas Sandholm, Unconditional privacy in social choice, Proceedings of the 10th conference on Theoretical aspects of rationality and knowledge, June 10-12, 2005, Singapore
	Makoto Yokoo , Koutarou Suzuki , Katsutoshi Hirayama, Secure distributed constraint satisfaction: reaching agreement without revealing private information, Artificial Intelligence, v.161 n.1-2, p.229-245, January 2005
	Joseph Halpern , Vanessa Teague, Rational secret sharing and multiparty computation: extended abstract, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Bella Dubrov , Yuval Ishai, On the randomness complexity of efficient sampling, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Marius Calin Silaghi, Meeting Scheduling Guaranteeing n/2-Privacy and Resistant to Statistical Analysis (Applicable to any DisCSP), Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.711-715, September 20-24, 2004
	Ran Canetti, Security and composition of cryptographic protocols: a tutorial (part I), ACM SIGACT News, v.37 n.3, September 2006
	Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin J. Strauss , Rebecca N. Wright, Secure multiparty computation of approximations, ACM Transactions on Algorithms (TALG), v.2 n.3, p.435-472, July 2006
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Ueli Maurer, Secure multi-party computation made simple, Discrete Applied Mathematics, v.154 n.2, p.370-381, 1 February 2006
	Steven S. Seiden , Peter P. Chen , R. F. Lax , J. Chen , Guoli Ding, New bounds for randomized busing, Theoretical Computer Science, v.332 n.1-3, p.63-81, 28 February 2005
	Paolo D'Arco , Wataru Kishimoto , Douglas R. Stinson, Properties and constraints of cheating-immune secret sharing schemes, Discrete Applied Mathematics, v.154 n.2, p.219-233, 1 February 2006
	Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Yuval Ishai , Eyal Kushilevitz , Yehuda Lindell , Erez Petrank, Black-box constructions for secure computation, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Eyal Kushilevitz , Yehuda Lindell , Tal Rabin, Information-theoretically secure protocols and security under composition, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ashwin Machanavajjhala , Daniel Kifer , Johannes Gehrke , Muthuramakrishnan Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.3-es, March 2007
	Jaimee Brown , Juan M. Gonzalez Nieto , Colin Boyd, Efficient and secure self-escrowed public-key infrastructures, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore
	Sergio Rajsbaum, ACM SIGACT news distributed computing column 24, ACM SIGACT News, v.37 n.4, December 2006
	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated Byzantine Agreement, Journal of the ACM (JACM), v.53 n.6, p.881-917, November 2006
	Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
	Michael Harkavy , J. D. Tygar , Hiroaki Kikuchi, Electronic auctions with private bids, Proceedings of the 3rd conference on USENIX Workshop on Electronic Commerce, p.6-6, August 31-September 03, 1998, Boston, Massachusetts
	Joan Boyar , René Peralta, Tight bounds for the multiplicative complexity of symmetric functions, Theoretical Computer Science, v.396 n.1-3, p.223-246, May, 2008
	Felix Brandt , Tuomas Sandholm, On the Existence of Unconditionally Privacy-Preserving Auction Protocols, ACM Transactions on Information and System Security (TISSEC), v.11 n.2, p.1-21, March 2008
	Dov S. Gordon , Hazay Carmit , Jonathan Katz , Yehuda Lindell, Complete fairness in secure two-party computation, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Zero-knowledge from secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Jonathan Katz, On achieving the "best of both worlds" in secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Sébastien Gambs , Balázs Kégl , Esma Aïmeur, Privacy-preserving boosting, Data Mining and Knowledge Discovery, v.14 n.1, p.131-170, February 2007
	S.-C. S. Samson Cheung , Thinh Nguyen, Secure multiparty computation between distrusted networks terminals, European Journal of Information Systems, v.2007 n.1, p.1-11, January 2007
	Marius Calin Silaghi, Framework for Modeling Reordering Heuristics for Asynchronous Backtracking, Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, p.529-536, December 18-22, 2006
	Felix Brandt , Tuomas Sandholm, (Im)Possibility of Unconditionally Privacy-Preserving Auctions, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.810-817, July 19-23, 2004, New York, New York
	Josiane Nzouonta , Marius-Calin Silaghi , Makoto Yokoo, Secure Computation for Combinatorial Auctions and Market Exchanges, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1398-1399, July 19-23, 2004, New York, New York
	D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States
	Mahir Can Doganay , Thomas B. Pedersen , Yücel Saygin , Erkay Savaş , Albert Levi, Distributed privacy preserving k-means clustering with additive secret sharing, Proceedings of the 2008 international workshop on Privacy and anonymity in information society, March 29-29, 2008, Nantes, France
	Paul Bunn , Rafail Ostrovsky, Secure two-party k-means clustering, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA
	Markus Hinkelmann , Andreas Jakoby, Communications in unknown networks: Preserving the secret of topology, Theoretical Computer Science, v.384 n.2-3, p.184-200, October, 2007
	Florian Kerschbaum , Rafael J. Deitos, Security against the business partner, Proceedings of the 2008 ACM workshop on Secure web services, p.1-10, October 31-31, 2008, Alexandria, Virginia, USA
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Cryptography with constant computational overhead, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Ittai Abraham , Danny Dolev , Joseph Y. Halpern, An almost-surely terminating polynomial protocol forasynchronous byzantine agreement with optimal resilience, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Assaf Ben-David , Noam Nisan , Benny Pinkas, FairplayMP: a system for secure multi-party computation, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA
	Roy Friedman , Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Asynchronous Agreement and Its Relation with Error-Correcting Codes, IEEE Transactions on Computers, v.56 n.7, p.865-875, July 2007
	Danfeng Yao , Keith B. Frikken , Mikhail J. Atallah , Roberto Tamassia, Private Information: To Reveal or not to Reveal, ACM Transactions on Information and System Security (TISSEC), v.12 n.1, p.1-27, October 2008
	Carmit Hazay , Yehuda Lindell, Constructions of truly practical secure protocols using standardsmartcards, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA
	Florian Kerschbaum , Andreas Schaad, Privacy-preserving social network analysis for criminal investigations, Proceedings of the 7th ACM workshop on Privacy in the electronic society, October 27-27, 2008, Alexandria, Virginia, USA
	Jonathan Katz , Chiu-Yuen Koo, On expected constant-round protocols for Byzantine agreement, Journal of Computer and System Sciences, v.75 n.2, p.91-112, February, 2009
	Jonathan Katz , Chiu-Yuen Koo , Ranjit Kumaresan, Improving the round complexity of VSS in point-to-point networks, Information and Computation, v.207 n.8, p.889-899, August, 2009
	Arpita Patra , Ashish Choudhary , C. Pandu Rangan , Kannan Srinathan , Prasad Raghavendra, Perfectly reliable and secure message transmission tolerating mobile adversary, International Journal of Applied Cryptography, v.1 n.3, p.200-224, February 2009
	Amos Beimel, On private computation in incomplete networks, Distributed Computing, v.19 n.3, p.237-252, January 2007
	Florian Kerschbaum , Daniel Dahlmeier , Axel Schröpfer , Debmalya Biswas, On the practical importance of communication complexity for secure multi-party computation protocols, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Jaideep Vaidya, Privacy-preserving linear programming, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Kannan Srinathan , Arpita Patra , Ashish Choudhary , C. Pandu Rangan, Unconditionally secure message transmission in arbitrary directed synchronous networks tolerating generalized mixed adversary, Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, March 10-12, 2009, Sydney, Australia
	Takashi Nishide , Kazuo Ohta, Constant-Round Multiparty Computation for Interval Test, Equality Test, and Comparison, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.5, p.960-968, May 2007
	Prahladh Harsha , Yuval Ishai , Joe Kilian , Kobbi Nissim , S. Venkatesh, Communication vs. Computation, Computational Complexity, v.16 n.1, p.1-33, May 2007
	I-Cheng Wang , Chih-hao Shen , Justin Zhan , Tsan-sheng Hsu , Churn-Jung Liau , Da-Wei Wang, Toward empirical aspects of secure scalar product, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, v.39 n.4, p.440-447, July 2009
	Arpita Patra , Ashish Choudhary , Chandrasekharan Pandu Rangan, Simple and efficient asynchronous byzantine agreement with optimal resilience, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Alptekin Küpçü , Anna Lysyanskaya , James W. Mickens, Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Li Bai , XuKai Zou, A Proactive Secret Sharing Scheme in matrix projection method, International Journal of Security and Networks, v.4 n.4, p.201-209, September 2009
	Mark Gondree , Payman Mohassel, Longest common subsequence as private search, Proceedings of the 8th ACM workshop on Privacy in the electronic society, November 09-09, 2009, Chicago, Illinois, USA
	Thomas B. Pedersen , Erkay Savaş, Impossibility of unconditionally secure scalar products, Data & Knowledge Engineering, v.68 n.10, p.1059-1070, October, 2009
	Florian Kerschbaum, A verifiable, centralized, coercion-free reputation system, Proceedings of the 8th ACM workshop on Privacy in the electronic society, November 09-09, 2009, Chicago, Illinois, USA
	Makoto Yokoo , Koutarou Suzuki , Katsutoshi Hirayama, Secure distributed constraint satisfaction: reaching agreement without revealing private information, Artificial Intelligence, v.161 n.1-2, p.229-245, January 2005
	Florian Kerschbaum , Andreas Schaad , Debmalya Biswas, Practical privacy-preserving protocols for criminal investigations, Proceedings of the 2009 IEEE international conference on Intelligence and security informatics, p.197-199, June 08-11, 2009, Richardson, Texas, USA
	Nitesh Saxena , Jeong Hyun Yi, Noninteractive self-certification for long-lived mobile ad hoc networks, IEEE Transactions on Information Forensics and Security, v.4 n.4, p.946-955, December 2009