@inbook{25bbb849c8c144b396fb1c1b0a0be0c2,
title = "Round efficiency of multi-party computation with a dishonest majority",
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 [13]; the second requires a stronger hardness assumption (along with the non-black-box techniques of Barak [2]) and achieves O(1) round complexity.",
author = "Jonathan Katz and Rafail Ostrovsky and Adam Smith",
year = "2003",
doi = "10.1007/3-540-39200-9_36",
language = "English (US)",
isbn = "3540140395",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "578--595",
editor = "Eli Biham",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}