In a setting with n parties and an adversary controlling at most t parties in Byzantine fashion, we present BB and BA extension protocols with and without trusted set-up assumption that are simultaneously optimal in multiple complexity measures. The best communication that an extension protocol can achieve in any setting is O(l n) bits for a message of length l bits. The best achievable seed round complexity is one. The best achievable round complexity is O(n) for the setting t< n and constant otherwise. We now summarize our results below:
Without set-up assumption: In this setting t<n/3 is necessary. We present the first extension protocol that is simultaneously communication, round and seed round optimal. Both the round complexity and seed round complexity of the best known communication optimal extension protocol in this setting is $\Omega(n^3)$ that is neither round optimal nor seed round optimal.
With set-up assumption: With t< n/2, we present the first extension protocol that is simultaneously communication, round and seed round optimal. The round complexity and the seed round complexity of the best known protocol in this setting, though constant, are more than that of our protocol. In the most challenging setting of t<n, we present the first extension protocol that is simultaneously communication and round optimal. The best known protocol in this setting is only communication optimal.Category / Keywords: cryptographic protocols / Byzantine Broadcast, Byzantine Agreement, Round complexity, Communication Complexity Original Publication (with minor differences): PODC 2016, OPODIS 2011 Date: received 29 Jan 2017, last revised 1 Feb 2017 Contact author: chaya ganesh at gmail com, arpitapatra10@gmail com Available format(s): PDF | BibTeX Citation Version: 20170202:035348 (All versions of this report) Short URL: ia.cr/2017/063 Discussion forum: Show discussion | Start new discussion