Scholarlink

<p>Broadcast protocols enable a set of <i>n</i> parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP ’83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="446_2024_473_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="35" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega (n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform “after the fact” removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple sub-quadratic broadcast protocol showing near tightness of our first bound.</p>

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

Communication lower bounds for cryptographic broadcast protocols

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年1月7日

查看全文
  • Erica Blum,
  • Elette Boyle,
  • Ran Cohen,
  • Chen-Da Liu-Zhang

摘要

Broadcast protocols enable a set of n parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP ’83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial \(\omega (n)\) ω ( n ) communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform “after the fact” removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple sub-quadratic broadcast protocol showing near tightness of our first bound.