Abstract
Gordon et al. recently showed that certain (non-trivial) functions can be computed with complete fairness in the two-party setting. Motivated by their results, we initiate a study of complete fairness in the multi-party case and demonstrate the first completely-fair protocols for non-trivial functions in this setting. We also provide evidence that achieving fairness is “harder” in the multi-party setting, at least with regard to round complexity.
The original version of the book was revised: The copyright line was incorrect. The Erratum to the book is available at DOI: 10.1007/978-3-642-00457-5_36
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: Proc. 18th Annual ACM Symposium on Theory of Computing (STOC), pp. 364–369 (1986)
Gordon, D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. In: Proc. 40th Annual ACM Symposium on Theory of Computing (STOC) (2008)
Chor, B., Ishai, Y.: On privacy and partition arguments. Inf. Comput. 167(1), 2–9 (2001)
Kilian, J., Kushilevitz, E., Micali, S., Ostrovsky, R.: Reducibility and completeness in private computations. SIAM J. Computing 29(4), 1189–1208 (2000)
Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy. SIAM Journal of Discrete Math 4(1), 36–47 (1991)
Ishai, Y., Kushilevitz, E., Lindell, Y., Petrank, E.: On combining privacy with guaranteed output delivery in secure multiparty computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 483–500. Springer, Heidelberg (2006)
Gordon, S.D., Katz, J.: Complete fairness in multi-party computation without an honest majority. In: 6th Theory of Cryptography Conference, TCC (2009), http://eprint.iacr.org/2008/458
Goldreich, O.: Foundations of Cryptography, Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gordon, S.D., Katz, J. (2009). Complete Fairness in Multi-party Computation without an Honest Majority. In: Reingold, O. (eds) Theory of Cryptography. TCC 2009. Lecture Notes in Computer Science, vol 5444. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00457-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-00457-5_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00456-8
Online ISBN: 978-3-642-00457-5
eBook Packages: Computer ScienceComputer Science (R0)