Welcome to the resource topic for 2024/1601
Title:
Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
Authors: Daniel Collins, Yuval Efron, Jovan Komatovic
Abstract:It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of t2 corruptions, bypassing the setup-free t3 barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher corruption resilience (n/2 instead of n/3) for the price of increased assumptions. Is this trade-off necessary?
We further the study of crypto-agnostic Byzantine agreement among n parties that answers this question in the negative. Specifically, let t_s and t_i denote two parameters such that (1) 2t_i + t_s < n, and (2) t_i \leq t_s < n/2. Crypto-agnostic Byzantine agreement ensures agreement among honest parties if (1) the adversary is computationally bounded and corrupts up to t_s parties, or (2) the adversary is computationally unbounded and corrupts up to t_i parties, and is moreover given all secrets of all parties established during the setup. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols in the authenticated and information-theoretic setting into one that is crypto-agnostic. Our compiler has several attractive qualities, including using only O(\lambda n^2) bits over the two underlying Byzantine agreement protocols, and preserving round and communication complexity in the authenticated setting. In particular, our results improve the state-of-the-art in bit complexity by at least two factors of n and provide either early stopping (deterministic) or expected constant round complexity (randomized). We therefore provide fallback security for authenticated Byzantine agreement for free for t_i \leq n/4.
ePrint: https://eprint.iacr.org/2024/1601
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 .