Welcome to the resource topic for 2011/313
Title:
Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity
Authors: Arpita Patra
Abstract:In this paper we present first ever error-free, asynchronous broadcast (called as A-cast) and Byzantine Agreement (called as ABA) protocols with optimal communication complexity and fault tolerance. Our protocols are multi-valued, meaning that they deal with \ell bit input and achieve communication complexity of O(n\ell) bits for large enough \ell for a set of n \geq 3t+1 parties in which at most t can be Byzantine corrupted. In synchronous settings, Fitzi and Hirt (PODC’06) proposed probabilistically correct multi-valued broadcast (BC) and Byzantine Agreement (BA) protocols with optimal complexity of O(n\ell) bits. Recently, Liang and Vaidya (PODC’11) achieved the same deterministically, i.e. without error probability. In asynchronous settings, Patra and Rangan (Latincrypt’10, ICITS’11) reported similar protocols with error probability. Here we achieve optimal complexity of O(n\ell) bits for asynchronous error-free case. Following all the previous works on multi-valued protocols, we too follow reduction-based approach for our protocols, meaning that our multi-valued protocols are designed given existing A-cast and ABA protocols for small message (possibly for single bit). However compared to existing reductions, our reductions are simple and elegant. More importantly, our reductions run in constant expected time, in contrast to O(n) of Patra and Rangan (ICITS’11). Furthermore our reductions invoke less or equal number of instances of protocols for single bit in comparison to the reductions of Patra and Rangan. In synchronous settings, while the reduction of Fitzi and Hirt is constant-round and invokes O(n(n+\kappa)) (\kappa is the error parameter) instances of protocols for single bit, the reduction of Liang and Vaidya calls for round complexity and number instances that are in fact function of the message size, O(\sqrt{\ell} + n^2) and \calO(n^2\sqrt{\ell} + n^4), respectively where \ell = \Omega(n^6). By adapting our techniques from asynchronous settings, we present new {\it error-free} reduction in synchronous world that is constant-round and calls for only O(n^2) instances of protocols for single bit which is at least as good as Fitzi and Hirt.
ePrint: https://eprint.iacr.org/2011/313
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .