@conference {15140, title = {Round efficiency of multi-party computation with a dishonest majority}, booktitle = {Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques}, series = {EUROCRYPT{\textquoteright}03}, year = {2003}, month = {2003///}, pages = {578 - 595}, publisher = {Springer-Verlag}, organization = {Springer-Verlag}, address = {Berlin, Heidelberg}, 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.}, isbn = {3-540-14039-5}, url = {http://dl.acm.org/citation.cfm?id=1766171.1766222}, author = {Katz, Jonathan and Ostrovsky,Rafail and Smith,Adam} }