Rafail Ostrovsky - Publications

Secure multi-party computation tolerating faulty majority

Jonathan Katz, Rafail Ostrovsky, Adam Smith


We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality and up to n-1 of these players may be arbitrarily malicious. Previous protocols for this setting (when a broadcast channel is available) require O(n) rounds. We present two protocols with improved round complexity: The first assumes only the existence of trapdoor permutations and dense cryptosystems, and achieves round complexity O(\log n) based on a proof scheduling technique of Chor and Rabin; the second requires a stronger hardness assumption (along with the non-black-box techniques of Barak) and achieves O(1) round complexity.

comment: Appeared in Proceedings of Advances in Cryptology, (EUROCRYPT-2003) Springer-Verlag/IACR Lecture Notes in Computer Science.

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to the Rafail Ostrovsky publication list or to the Rafail Ostrovsky main page.