International Association
for Cryptologic Research

We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It assumes that players can broadcast once and non-interactively before they receive their inputs and start the execution. We consider both the problems of consensus with strong unanimity, also known as ``Byzantine agreement'' (BA), and of ``Validated Byzantine agreement'' [CKPS, Crypto'01] (VBA, also known as MVBA). Most works on BA use a bulletin-board PKI setup only for the purpose of publishing verification keys. This implements the {messages-authentication model}, i.e., when $P$ is forwarded a message issued by $R$, it is convinced that $R$ is the author. Without messages-authentication, it is known since [Lamport et al, 82] that BA under honest majority is impossible, let alone secure computation. Thus, since the bare PKI setup and the messages-authentication model seem close, this raizes the question whether there is a separation between the two. In the bare PKI setup, the most communication-efficient synchronous BA is the one of [Boyle-Cohen-Goel, Podc'21 \& J. Cryptol.'24], which has $O(n.\text{polylog}(n))$ bit complexity, $f
{- Optimality.} We show that resilience up to a tight honest majority $f
{- Separation.} We show impossibility of subquadratic multicast-based BA in the messages-authentication model. Our model for this lower bound is even stronger, since it onboards other assumptions at least as strong as all popular implications of a bulletin-board PKI setup: {secure channels}, {a (possibly structured) random string}, {NIZK}.

{- Partial synchrony.} We then show that the separation also holds under partial synchrony. On the one hand, our upper-bound also holds, with $f
{- Extension to VBA.} We extend to VBA the logarithmic latency lower bound. This is the first communication lower bound for adaptively secure VBA to our knowledge. It shows that the separation under partial synchrony also holds for VBA. Along the way, we close the categorization of [Civit et al, Podc'23] of validity conditions in authenticated consensus, by apparently new results on VBA: both BA and VBA are infeasible under partial synchrony beyond $f