Secure multi-party computation tolerating faulty majority
Jonathan Katz, Rafail Ostrovsky, Adam Smith
Abstract:
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