Deterministic broadcast protocols among n parties tolerating t corruptions require \(\min \{f+2, t+1\}\) rounds, where \(f \le t\) is the actual number of corruptions in an execution of the protocol. We provide the first protocol which is optimally resilient, adaptively secure, and asymptotically matches this lower bound for any \(t<(1-\varepsilon )n\) . By contrast, the best known algorithm in this regime by Loss and Nielsen (EUROCRYPT’24) always requires \(O(\min \{f^2, t\})\) rounds. Our main technical tool is a generalization of the notion of polarizer introduced by Loss and Nielsen, which allows parties to obtain transferable cryptographic evidence of missing messages with fewer rounds of interaction.

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

Asymptotically Optimal Early Termination for Dishonest Majority Broadcast

  • Giovanni Deligios,
  • Ivana Klasovita,
  • Chen-Da Liu-Zhang

摘要

Deterministic broadcast protocols among n parties tolerating t corruptions require \(\min \{f+2, t+1\}\) rounds, where \(f \le t\) is the actual number of corruptions in an execution of the protocol. We provide the first protocol which is optimally resilient, adaptively secure, and asymptotically matches this lower bound for any \(t<(1-\varepsilon )n\) . By contrast, the best known algorithm in this regime by Loss and Nielsen (EUROCRYPT’24) always requires \(O(\min \{f^2, t\})\) rounds. Our main technical tool is a generalization of the notion of polarizer introduced by Loss and Nielsen, which allows parties to obtain transferable cryptographic evidence of missing messages with fewer rounds of interaction.