Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement

• URL: http://arxiv.org/abs/2502.02320v2
• Date: Mon, 10 Feb 2025 14:06:17 GMT
• Title: Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement
• Authors: Mose Mizrahi Erbes, Roger Wattenhofer,
• Abstract summary: We present a novel reduction from multivalued BA to binary BA. As our reduction uses multivalued WA, we design two new efficient WA protocols for $ell$-bit inputs. Our WA protocols extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and near-optimal security.
• Score: 23.27199615640474
• License:
• Abstract: In this work, we study multivalued byzantine agreement (BA) in an asynchronous network of $n$ parties where up to $t < \frac{n}{3}$ parties are byzantine. In this setting, we present a novel reduction from multivalued BA to binary BA. This reduction allows one to achieve BA on $\ell$-bit inputs with one instance of binary BA, one instance of weak agreement (WA) on $\ell$-bit inputs and $\Theta(\ell n + n^2)$ bits of additional communication. Afterwards, as our reduction uses multivalued WA, we design two new efficient WA protocols for $\ell$-bit inputs. In the first one, we use almost-universal hashing to achieve statistical security with probability $1 - 2^{-\lambda}$ against $t < \frac{n}{3}$ failures with $\Theta(n^2(\lambda + \log n + \log \ell))$ bits of communication. Then, we replace the hashes with error correcting code symbols and add a step based on the synchronous multivalued BA protocol COOL [DISC '21] to obtain our second protocol, which for any fixed $\varepsilon > 0$ achieves perfect security against $t \leq \frac{n}{3 + \varepsilon}$ failures with $\Theta(\ell n + n^2)$ bits of communication. Used in our reduction, our WA protocols extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and near-optimal security.

Related papers

• OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement [15.464948077412021]
  We propose an error-free, information-theoretically secure multi-valued asynchronous Byzantine agreement protocol, called OciorABA. In our protocol design, we introduce a new primitive: asynchronous partial vector agreement (APVA)
  arXiv  Detail & Related papers  (2025-01-20T23:36:11Z)
• Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement [1.77513002450736]
  It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $tn/2$ corruptions. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols into one that is crypto-agnostic. 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)
  arXiv  Detail & Related papers  (2024-10-15T23:44:29Z)
• Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
  We consider an asynchronous network of $n$ message-sending parties, up to $t$ of which are byzantine. We study approximate agreement, where the parties obtain approximately equal outputs in the convex hull of their inputs. This takes $Theta(n2)$ messages per reliable broadcast, or $Theta(n3)$ messages per iteration.
  arXiv  Detail & Related papers  (2024-08-10T09:03:06Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
  arXiv  Detail & Related papers  (2024-04-16T00:56:36Z)
• SwiftAgg+: Achieving Asymptotically Optimal Communication Load in Secure Aggregation for Federated Learning [83.94234859890402]
  SwiftAgg+ is a novel secure aggregation protocol for federated learning systems. A central server aggregates local models of $NinmathbbN$ distributed users, each of size $L in mathbbN$, trained on their local data, in a privacy-preserving manner.
  arXiv  Detail & Related papers  (2022-03-24T13:12:23Z)
• Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms [75.17357040707347]
  Motivated by online recommendation systems, we propose the problem of finding the optimal policy in contextual bandits. The goal is to robustly learn the policy that maximizes rewards for good users with as few user interactions as possible. We show we can achieve an $tildeO(min(S,A)cdot alpha/epsilon2)$ upper-bound, by employing efficient robust mean estimators.
  arXiv  Detail & Related papers  (2022-01-30T01:45:13Z)
• Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error [1.6522364074260811]
  We investigate the randomized and quantum communication complexities of the Equality function with small error probability $epsilon$. We show that any $log(n/epsilon)-loglog(sqrtn/epsilon)+3$ protocol communicates at least $log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubits.
  arXiv  Detail & Related papers  (2021-07-25T13:52:42Z)
• An Efficient Simulation of Quantum Secret Sharing [7.195824023358536]
  We propose a secure $d$-level $QSS$ protocol for sharing a secret with efficient simulation. It does not disclose any information about the secret to players. Its security analysis shows that the intercept-resend, intercept, entangle-measure, forgery, collision and collusion attacks are not possible in this protocol.
  arXiv  Detail & Related papers  (2021-03-20T16:42:02Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.