Welcome to the resource topic for 2023/1757
Title:
Adaptively Secure Consensus with Linear Complexity (and Constant Round) under Honest Majority in the Bare PKI Model, and Separation Bounds from the Idealized Message-Authentication Model
Authors: Matthieu Rambaud
Abstract: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<n(1/2-\epsilon), with an expected bit complexity of communications which is {linear} in n, and tolerance to an {adaptive} rushing adversary (but which unavoidably cannot remove messages sent). As [BCG’21], they have constant expected latency. All previous BAs or VBAs achieving the same metrics as our upper bound, are either in the static adversary model: Sleepy [Pass-Shi, Asiacrypt’17], Snow White [Daian-Pass-Shi, FC’19], or assume more than a bare PKI setup: (i) The model of Thunderella [Pass-Shi, EC’17], Algorand [Gilad et al, SOSP’17], Praos [David et al, EC’18], [Goyal et al, FC’21] and [Momose et al, CCS’22 and CCS’23] assumes a public random seed which is unpredictable until strictly after all players published on the bulletin board; (ii) [Abraham et al, Podc’19] assume a trusted entity which honestly samples the keys of all players; (iii) All known implementations of the setups (i) and (ii), as well as the setup of [Blum et al, TCC’20], require interactions, furthermore in the form of BAs. (iv) [Garay-Kiayas-Shen '23] assume that honest players work more than the adversary, or, [Eckey-Faust-Loss et al '17 '22] at least as fast.
Of independent interest, our tool is a very simple non-interactive mechanism which {sets-up any self-sortition function from one publication on the bulletin board}, and still, guarantees an honest majority in every committee up to probability exponentially small in both \epsilon and in the multicast complexity.
We provide the following further results:
{- Optimality.} We show that resilience up to a tight honest majority f<n/2 is impossible for any multicast-based adaptively secure BA with subquadratic communication, whatever the setup.
{- 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<n(1/3-\epsilon) resilience. On the other hand, we show that any partially-synchronous BA in the messages-authentication model and linear message complexity, has necessarily latency {logarithmic in f}. Of independent interest, our baseline technique provides a simpler proof of the unauthenticated quadratic lower bound of [Blum et al, TCC’20].
{- 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<n/3, whatever the setup; whereas VBA is feasible under synchrony up to f=n-1 (contrary to BA).
ePrint: https://eprint.iacr.org/2023/1757
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .