2025/02/04 by Mose Mizrahi Erbes, Roger Wattenhofer, Erbes, Mose Mizrahi +1 · 1 citation
Computer Science · Social Sciences · #Access Control and Trust #Cryptography and Data Security #Cryptography and Security (cs.CR) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Information Theory (cs.IT) #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2502.02320
openalex publication_date 2025/02/04 · openalex created_date 2025/02/06 · openalex updated_date 2026/07/28
In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of n parties where up to t < (n)/(3) parties are byzantine. We present a new reduction from multivalued BA to binary BA. It allows one to achieve BA on ℓ-bit inputs with one instance of binary BA, one instance of crusader agreement (CA) on ℓ-bit inputs and Θ(ℓ n + n2) bits of additional communication. As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for ℓ-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability 1 - 2-λ against t < (n)/(3) faults with Θ(ℓ n + n2(λ+ log n)) bits of communication. Following this, we replace the hashes with error correcting code symbols and add a preliminary step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain a second, perfectly secure CA protocol that can for any ε > 0 be set to tolerate t ≤ (n)/(3 + ε) faults with O((ℓ n)/(min(1, ε2)) + n2max(1, log (1)/(ε)) ) bits of communication. Our CA protocols allow one to extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-n communication overhead, and information-theoretic security.