Scholarlink

Byzantine Agreement is a fundamental primitive in cryptography and distributed computing, and minimizing its round complexity is of paramount importance. The seminal works of Karlin and Yao [Manuscript’84] and Chor, Merritt and Shmoys [JACM’89] showed that any randomized r-round protocol must fail with probability at least \((c\cdot r)^{-r}\) , for some constant c, when the number of corruptions is linear in the number of parties, \(t = \theta (n)\) . The work of Ghinea, Goyal and Liu-Zhang [Eurocrypt’22] introduced the first round-optimal BA protocol matching this lower bound. However, the protocol requires a trusted setup for unique threshold signatures and random oracles. In this work, we present the first round-optimal BA protocols without trusted setup: a protocol for \(t&lt;n with="" statistical="" security_="" and="" a="" protocol="" for="" _t_1-_epsilon="" _n="" any="" constant="" _epsilon=""&gt; 0\) , assuming a bulletin-board PKI for signatures.</n>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Round-Optimal Byzantine Agreement Without Trusted Setup

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Diana Ghinea,
  • Ivana Klasovitá,
  • Chen-Da Liu-Zhang

摘要

Byzantine Agreement is a fundamental primitive in cryptography and distributed computing, and minimizing its round complexity is of paramount importance. The seminal works of Karlin and Yao [Manuscript’84] and Chor, Merritt and Shmoys [JACM’89] showed that any randomized r-round protocol must fail with probability at least \((c\cdot r)^{-r}\) , for some constant c, when the number of corruptions is linear in the number of parties, \(t = \theta (n)\) . The work of Ghinea, Goyal and Liu-Zhang [Eurocrypt’22] introduced the first round-optimal BA protocol matching this lower bound. However, the protocol requires a trusted setup for unique threshold signatures and random oracles. In this work, we present the first round-optimal BA protocols without trusted setup: a protocol for \(t<n with="" statistical="" security_="" and="" a="" protocol="" for="" _t_1-_epsilon="" _n="" any="" constant="" _epsilon=""> 0\) , assuming a bulletin-board PKI for signatures.