Metraipolis › archive › dc_a2d42d71c6fc

Optimal Subcubic Byzantine Agreement with Plain PKI — arXiv:2611.06479

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.06479
License (as archived)
CC0-1.0
Archived
2026-11-05T18:19:23.115Z
SHA-256 of the archived text
99aebbe95046afab833f9503c8597a917b641840fd8d526fc5cb100e2c5af1f5
Stable URL of this page
https://metraipolis.com/documento/dc_a2d42d71c6fc

How to cite

Optimal Subcubic Byzantine Agreement with Plain PKI — arXiv:2611.06479 — arXiv (en), https://arxiv.org/abs/2611.06479 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a2d42d71c6fc (Metraipolis archive dc_a2d42d71c6fc, sha256 99aebbe95046afab833f9503c8597a917b641840fd8d526fc5cb100e2c5af1f5)
BibTeX
@misc{dca2d42d71c6fc,
  title = {Optimal Subcubic Byzantine Agreement with Plain PKI — arXiv:2611.06479},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06479},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a2d42d71c6fc; sha256 99aebbe95046afab833f9503c8597a917b641840fd8d526fc5cb100e2c5af1f5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06479. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We consider Byzantine Agreement (BA), where $n$ parties run a distributed protocol to agree on a common value, despite $t$ parties being byzantine. In the synchronous setting, a choice must be made between the weaker unauthenticated setting, which only allows $t < n/3$ byzantine parties, and the stronger authenticated setting that allows up to $t < n/2$ byzantine parties. For this latter setting, BA can be solved with optimal resiliency and optimal bit complexity. However, so far, all optimal solutions rely on the use of threshold signatures. This shows a gap compared to regular signatures, where only protocols with cubic complexity are known for optimal resiliency $t < n/2$. We wonder whether this cubic complexity is required without the use of threshold signatures and show that this is not the case. More specifically, given $\kappa$ an upper bound on the size of a hash or signature, we describe a deterministic protocol solving BA with bit complexity $\mathcal{O}(\kappa^{(\sqrt{13} - 1)/2} n^{(\sqrt{13} + 1)/2}) \approx \mathcal{O}(\kappa^{1.303}n^{2.303})$ while having optimal resiliency $t<n/2$ and round complexity $\mathcal{O}(n)$.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2611.06479 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:13:18.989Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).