betaFeedback

WorksComputer Science

Optimal Subcubic Byzantine Agreement with Plain PKI

Abstract

We consider Byzantine Agreement (BA), where nn parties run a distributed protocol to agree on a common value, despite tt parties being byzantine. In the synchronous setting, a choice must be made between the weaker unauthenticated setting, which only allows t<n/3t < n/3 byzantine parties, and the stronger authenticated setting that allows up to t<n/2t < n/2 byzantine parties. For this latter setting, BA can be solved with optimal resiliency and optimal bit complexity. However, so far, all optimal solutions rely on the use of threshold signatures. This shows a gap compared to regular signatures, where only protocols with cubic complexity are known for optimal resiliency t<n/2t < n/2. We wonder whether this cubic complexity is required without the use of threshold signatures and show that this is not the case. More specifically, given κκ an upper bound on the size of a hash or signature, we describe a deterministic protocol solving BA with bit complexity O(κ(13−1)/2n(13+1)/2)≈O(κ1.303n2.303)\mathcal{O}(κ^{(\sqrt{13} - 1)/2} n^{(\sqrt{13} + 1)/2}) \approx \mathcal{O}(κ^{1.303}n^{2.303}) while having optimal resiliency t<n/2t<n/2 and round complexity O(n)\mathcal{O}(n).

Introduction

Byzantine Agreement is a fundamental problem in distributed computing, where a set of parties must agree on a single value even in the presence of some malicious parties. In its simplest form, we are given nn parties, of which at most tt can be byzantine. Without any kind of setup, this problem can only be solved if t<n/3t < n/3 [25]. However, if we assume the presence of a public key infrastructure (PKI), and more specifically that parties can sign messages, then we can solve the problem with t<n/2t < n/2.

Another important aspect of the problem is the complexity of the protocol. In 1982, Dolev and Reischuk [14] gave a quadratic lower bound for communication complexity. In the authenticated setting, this lower bound was only somewhat recently matched by Momose and Ren [24]. However, when considering optimal resiliency t<n/2t < n/2, their protocol relies on threshold signatures [5], which are a stronger cryptographic primitive, allowing parties, in certain cases, to compress nn signatures into one. Even though threshold signatures are used in practice, they have multiple drawbacks:

  • Threshold signatures require their keys to be correlated. A consequence is that a trusted dealer setup is needed. This is a strong assumption and requiring a trusted third party, even if only for the setup, for a decentralized protocol is not ideal. Another possible approach is to use a distributed key generation (DKG) protocol, but this is a complex protocol in itself.

  • Looking in the future, most common signature and threshold signature primitives are not quantum-safe. While regular signatures quantum-safe alternatives exist and have already been thoroughly studied [3, 15], quantum-safe threshold signatures [11, 19] are less mature and have been less studied.

  • In general, it is interesting to known the best we can do with the least amount of cryptographic assumptions.

For these reasons, we consider the problem of solving Byzantine Agreement with optimal resiliency t<n/2t < n/2 with only regular signatures. To the best of our knowledge, all existing protocols for this setting have cubic complexity. In this work, we show that this is not a requirement and give the following result:

Theorem 1. There exists a deterministic byzantine agreement protocol with round complexity RBA(n)=O(n)R_{\mathrm{BA}}(n) = O(n) and bit complexity BBA(n)=O(κ(13−1)/2n(13+1)/2)≈O(κ1.303n2.303)B_{\mathrm{BA}}(n) = O(\kappa^{(\sqrt{13}-1)/2}n^{(\sqrt{13}+1)/2}) \approx O(\kappa^{1.303}n^{2.303}).

Our work builds on the framework laid by Momose and Ren [24], and make use of numerous new techniques, including more refined recursive protocols, improved uses of dispersers and fault-tolerant expander graphs, as well as fair cake cutting theory to achieve a subcubic complexity.

AI Disclosure: ChatGPT-6 Astra was used to improve and refine ideas in § 9 and § 11.1. ChatGPT-6 Astra was also used to provide an initial draft, which the authors based their proof of Theorems 9 and 10. Apart of the uses mentioned above, LLMs were only used for grammar and spelling checks.

Related work

Deterministic synchronous protocols In the deterministic synchronous setting, the Dolev-Reischuk [14] lower bound shows that a quadratic amount of communication is necessary to solve byzantine agreement. Dolev and Strong [13] also show that t+1t+1 rounds are necessary to solve deterministic byzantine agreement. In the unauthenticated setting, Berman, Garay and Perry [2] were the first to give a protocol with optimal resiliency t<n/3t < n/3 and optimal bit complexity O(n2)\mathcal{O}(n^2). It took until 2020 for Momose and Ren [24] to match this result in the unauthenticated setting. More precisely, they give a protocol with optimal resiliency t<n/2t < n/2 and quadratic bit complexity O(κn2)\mathcal{O}(\kappa n^2) using threshold signatures. When considering only regular signatures, they provide a protocol with resiliency t<n/(2+ε)t < n/(2 + \varepsilon) and bit complexity O(κε−1n2)\mathcal{O}(\kappa\varepsilon^{-1}n^2), which results in a cubic complexity for t<n/2t < n/2.

Randomized protocols We note that all the previous lower bounds only apply to deterministic algorithms. In the randomized settings, more efficient protocols exist, concerning both round and bit complexity [18]. In particular, even in the much weaker asynchronous setting, when properties are only required to hold with high probability, byzantine agreement can be solved with expected near-linear complexity [4, 9].

Bypassing the lower bound There have been multiple attempts to bypass the deterministic lower bounds by using additional assumptions. Some of them rely on using adaptive algorithms which depend on the actual number of byzantine parties [6, 10]. Others rely on amortizing the cost of byzantine agreement over multiple instances [7, 16]. However, all approaches with resiliency t≥n/3t \ge n/3 rely on threshold signatures. A notable exception is [16] which can be used to solve Θ(n)\Theta(n) concurrent instances of byzantine agreement with an amortized near-linear cost per instance while only using regular signatures. However, this is only achieved with resiliency t<n/(2+ε)t < n/(2 + \varepsilon).

Overview

Our main contribution is a new weak agreement protocol using plain PKI with subcubic message complexity. This protocol consists of 2 main parts:

  • Proof Gathering: In the first part, parties exchange signed messages between themselves to get a proof that either 0 or 1 can be voted. We note that because of the lack of threshold signatures, a proof must contains at least t+1t + 1 signatures so that byzantine parties cannot forge it. In our protocol it is the case: a proof is made of exactly t+1t + 1 threshold signatures and thus has size Θ(κn)\Theta(\kappa n). At the end of this part, we require that at least n/10n/10 honest parties have a proof for either 0 or 1. Additionally, if every honest party has the same input, then every honest party will get a proof for this input by the end of the proof gathering.

  • Validated Dispersion: From the first part, at least n/10n/10 honest parties have a proof. Our goal in this part is to make every honest party hold the same proof, i.e that there is a specific proofvproof_v with v∈{0,1}v \in\{0,1\} such that every honest party has received proofvproof_v by the end of this part.

After running consecutively these two parts, if a party has a proof for both 0 and 1, it will decide ⊥\bot. Otherwise, it will decide the value matching the proof it received (validated dispersion ensures at least one proof will be received). Although these two sections sound simple to explain, obtaining a subcubic protocol for both of them is the main difficulty of this paper and requires multiple complex ideas. An overview is given below:

Proof construction

The goal of proof gathering is that, by the end of it, at least n/10n/10 honest parties have a proof showing that either 0 or 1 can be decided. We first give an initial idea for the proof. A proof for v∈{0,1}v \in\{0,1\} allows a party to confirm it can decide vv without any additional communication. In particular, if all honest parties have input vv, a proof for 1−v1-v cannot exist. A common construction for such a proof is to have every party sign and send its input. If a party gets t+1t+1 distinct signatures for v∈{0,1}v \in\{0,1\}, it shows that at least one honest party had input vv and thus that this value can be decided.

Using threshold signatures, such a proof can be encoded using O(κ)\mathcal{O}(\kappa) bits. Here, because only plain signatures are available, such a proof will require (t+1)κ=O(κn)(t+1)\kappa= \mathcal{O}(\kappa n) bits. As such, a protocol should be careful when sending this proof to avoid having a cubic complexity. We present the different ideas used to achieve proof gathering with O~(κn2)\widetilde{\mathcal{O}}(\kappa n^2) bit complexity and O(log⁡n)\mathcal{O}(\log n) rounds complexity:

I know that I can’t know: As said before, we consider a first round where every party votes for its input and sends its (signed) vote to every other party. Given a party vv, this can results in two outcomes for vv:

  • vv gets enough votes for 0 or 1 to get a proof for either 0 or 1

  • vv is not able to get a proof for either 0 or 1. However, in this case, we make the observation that vv still gained information from this step: it learned that all honest parties don’t hold the same value (otherwise it would have received n−t≥t+1n-t \ge t+1 votes for this value), and therefore both 0 and 1 are ”fine” to decide. To symbolize this, it sets its input to ⊥\perp. A downside of this approach is that vv has no way to prove this observation to other parties. But we show that this simple remark is powerful enough to always get a proof afterward. We note that this approach was already used to obtain optimal adaptive byzantine agreement protocol using threshold signatures [10, 17].

Let nb⊥nb_{\perp} be the number of honest parties which set their input to ⊥\perp (they know that both values are fine). We remark that if nb⊥≤4n/10nb_{\perp} \le4n/10, then at least n−t−nb⊥≥n/10n-t-nb_{\perp} \ge n/10 honest parties have a proof and therefore this step is already done.

In the case where nb⊥>4n/10nb_{\perp} > 4n/10, we perform a second round of input (which can now be 0, 1 or ⊥\perp) signing and sending. We now observe that byzantine parties can only behave in two different ways.

If byzantine parties behave as honest: We consider the first case, where multiple byzantine will send their vote to an honest party, as a way to appear as honest from this party’s point of view. More specifically, we consider the case when any honest party receives at least 7n/107n/10 votes. In this case, we use a disperser to disperse the votes received. Every vote is forwarded to a constant (different for each vote) number of parties. This ensures that any set of 4n/104n/10 honest parties holds enough information together to produce a proof. Afterwards, we give and use the following fault-tolerant expander, which we believe to be of independent interest:

Theorem 2. For any α∈]0,1[\alpha\in]0,1[, β>1\beta> 1, there exists D>0D > 0 such that for any n>0n > 0, there exists an explicit graph G=(V,E)G = (V,E) on nn vertices of bounded degree DD. Additionally, for any C⊂VC \subset V such that ∣C∣≤α⋅n|C| \le\alpha\cdot n, there exists S⊆VS \subseteq V such that S∩C=∅S \cap C = \emptyset, ∣S∣≥n−β⋅∣C∣|S| \ge n - \beta\cdot|C|, and the induced subgraph G[S]G[S] is connected and has diameter O(log⁡n)\mathcal{O}(\log n).

We note that this is a generalization and stronger version of [26]’s result, which had fixed α=1/72\alpha= 1/72 and β=6\beta= 6. Using this graph, we ensure that a subset of 4n/104n/10 honest parties will be able to communicate and all get a proof in O(log⁡n)O(\log n) rounds.

If byzantine parties behave as malicious: If the previous case is not reached, it implies that all honest parties received less than 7n/107n/10 votes and thus each honest party can identify at least 3n/103n/10 byzantine parties. We note that in this case, votes only may not be enough to get a proof. Therefore, we combine votes with our next ”trick”: accusations. An honest party can only accuse another party if it is byzantine. Thus, given a signed accusation from pip_i to pjp_j, we know that either pip_i or pjp_j is byzantine. This approach is inspired by the work done for repeated agreement [7] and relies on the insight formalized by [21]: instead of trying to determine whether pip_i or pjp_j is byzantine, we can just discard the two parties.

This is implemented by adding accusations into a proof. For example, with n=5n = 5 and t=2t = 2, assume the proof consists of: {vote⁡p1(0),vote⁡p2(⊥),accuse⁡(p3,p4)}\{\operatorname{vote}_{p_1}(0), \operatorname{vote}_{p_2}(\perp), \operatorname{accuse}(p_3,p_4)\}, we know that either p3p_3 or p4p_4 is byzantine, so at most one party among p1p_1 and p2p_2 is byzantine and thus 0 is a valid value. We note that for this to work, votes and accusations must be disjoint, and in particular, accusations must form a matching.

From accusations to fair cake-cutting: In this setting, each honest party wants to get ”rid of” up to 3n/103n/10 non-⊥\perp votes, and each honest party can accuse at least 3n/103n/10 byzantine parties. We view this in another way: consider the set of nn parties to be a cake. Each party knows at least 3n/103n/10 byzantine parties which we identify as delicious slices. The goal becomes for a party to split the cake such that each relevant party is given a range which contains what it considers to be a delicious slice: this is fair cake-cutting theory. We adapt an existing algorithm to our setting and show that such an assignment can always be obtained by asking each party to cut a range of the cake into 2 equal parts ⌈log⁡n⌉\lceil\log n\rceil times. This approach has bit complexity O(n2log⁡2n)O(n^2\log^2 n) and round complexity O(log⁡n)O(\log n).

Validated dispersal

Using proof construction, we can guarantee that at least n/10n/10 honest parties hold a proof (possibly not for the same value). Each party running the proof dispersal algorithm will get a set of proofs in return. The main property of proof dispersal is that there exists a proof which is in every set returned by an honest party. This implies that every party will either get a proof for 0 or every party will get a proof for 1. Because a proof for vv can only exist if vv satisfies weak validity (i.e if all honest party don’t have input 1−v1-v), we show that deciding vv if a party only receives proofs for vv or otherwise deciding ⊥\perp satisfies weak agreement.

Validated dispersal in its definition does not consider proofs, it consider any LL-bit input which satisfies some external validity predicate (where in our case, the validity predicate is that the value is a valid proof). We note that a really simple implementation of validated dispersal can be to have every party send its input (if it has one) to every other party, then return the set of inputs received. This works and can be done in one round, however, it has cubic complexity.

Divide-And-Conquer: The approach we took to improve the complexity in this paper is based on a divide-and-conquer approach (and later recursive calls). We divide the nn parties into m:=m(n)m := m(n) groups of similar size (where mm is decided later) and make two key remarks. The first remark is that by sending messages using a disperser pattern, we can make it so at most n/(10m)n/(10m) honest parties do not have an input, with a bit cost of O(n2m)O(n^2m). The second insight is that if one of the groups has a byzantine minority (which we are guaranteed at least one has), and all honest parties in this group agree on the same value, then, using standard erasure coding techniques, all parties can learn this value using only O(n2)O(n^2) communication. Summing this over all mm groups, we get the same O(n2m)O(n^2m) bit cost.

Validated Agreement: Using the previous idea, we can effectively reduce Validated dispersal to mm parallel calls to agreement on a valid value within a group of smaller size n/mn/m. We note that this problem is not exactly regular Validated Byzantine Agreement, as some honest parties may not have an input. We call this problem Partial Validated Agreement. Nevertheless, we show that Partial Validated Agreement can be implemented using O(log⁡n)O(\log n) calls to regular Validated Agreement.

Our setting is now Validated Byzantine Agreement with a byzantine minority. An easy way to solve this would be to have every party send its input using Byzantine Broadcast (for example the Dolev-Strong protocol). Although this simple approach would be enough to achieve a subcubic complexity for the overall protocol, there exists better approaches.

A first improvement would be to implement Byzantine Broadcast using our own Byzantine Agreement protocol, effectively making our protocol recursive. This is more efficient, but requires nn recursive calls in total and also has a high bit-complexity due to multiple inputs sharings.

Dynamic Programming approach When considering the previous Validated Agreement running with nn parties and input size LL, it requires O(κn)O(\kappa n) recursive binary agreement calls and its dependency on LL is O(n2L)O(n^2L). To reduce the dependency on LL to O(nL)O(nL), we take a dynamic programming approach: for a set SS of parties, we keep track of a tuple (d,H)(d, H) where dd is the Merkel root of a valid value and HH is a set of parties that know the value associated with HH. One key invariant we keep is that S∖HS \setminus H has a byzantine majority (i.e at least half of its parties are byzantine). We show how to merge two disjoint sets SS and S′S' where we have a tuple satisfying these properties to obtain a new tuple for S∪S′S \cup S' using only ∣S′∣|S'| byzantine agreement calls with an additional O(L∣S′∣)O(L|S'|) bit complexity. When merging sets in the correct order, this allows the protocol to only have an O(nL)O(nL) dependency on LL.

Batching Our dynamic programming approach relies on running multiple independent byzantine broadcast procedures. Each broadcast requires one recursive call to our byzantine agreement protocol, which is expensive. To work around this issue, we show how to use batching to improve the overall bit complexity. Let b:=b(n)b := b(n), we consider bb independent instances of byzantine broadcast from a set of broadcasters SS. We rely on a committee-based broadcast protocol, based on the Dolev-Strong protocol, which is more efficient, but only guarantees agreement if at least one party in the committee is honest. Using SS as the committee, each party tries to broadcast its value using the committee-based protocol. Afterwards, a single multi-valued byzantine protocol (implemented on top of our binary BA protocol) is run to check the consistency of all bb instances at once. This decreases the number of recursive calls needed from O(κn)O(\kappa n) to O(κn/b)O(\kappa n/b).

Parallel execution A point we did not mention up to now is round complexity. Byzantine Agreement requires Ω(n)\Omega(n) rounds and our goal is for our algorithm to be optimal in this regard. When implementing the ideas presented above naively while optimizing mm and bb to minimize the bit complexity, the resulting algorithm would end up with a super-linear round complexity. To solve this, we make a more efficient use of the batching approach above, in particular by batching byzantine broadcasts from multiple independent merges together. This, together with running independent subprotocols in parallel whenever possible, allows the final round complexity to be linear.

Overall Complexity As said before, our algorithm is recursive: it recursively calls itself on smaller groups. When computing the bit complexity, we show that the per-party bit complexity BBA(n)B_{BA}(n), while optimizing the parameters mm and nn is:

BBA(n)=2BBA(n/2)+O~(κn)+min⁡1≤b≤n/m<nO~(nm+κnb2m+κnb2m+κnmbBBA(n/m))B_{BA}(n) = 2B_{BA}(n/2) + \widetilde{O}(\kappa n) + \min_{1 \le b \le n/m < n} \widetilde{O}\left(nm + \frac{\kappa n b^2}{m} + \frac{\kappa n}{b^2m} + \frac{\kappa n}{mb}B_{BA}(n/m)\right)

We get the optimal value by choosing b=m=Θ~((κn)(13−3)/2)b=m=\widetilde{\Theta}\left((\kappa n)^{(\sqrt{13}-3)/2}\right) which leads to the algorithm per-party bit complexity BBA(n)=O~(n(13−1)/2)B_{BA}(n)=\widetilde{O}\left(n^{(\sqrt{13}-1)/2}\right).

Regarding round complexity, the recurrence relation is:

RBA(n)=2RBA(n/2)+O(log⁡n)+m1/3RBA(n/m)R_{BA}(n) = 2R_{BA}(n/2) + O(\log n) + m^{1/3}R_{BA}(n/m)

For our optimal choice of mm, the resulting round complexity is the expected optimal RBA(n)=O(n)R_{BA}(n)=O(n).

Preliminaries

We consider a set P\mathcal{P} of nn parties, out of which up to tt can be byzantine. We focus on fully deterministic protocols. The network is fully connected and channels are authenticated: any party can send a message to any other party, and the receiver will know who the sender is.

Model: We consider a synchronous model, where parties communicate in rounds. In each round, parties can send messages to other parties, and all messages will be received by the beginning of the next round.

Hashes: We assume the existence of a cryptographic hash function that is collision-resistant: it is computationally infeasible to find two distinct inputs that hash to the same output. We assume that the output of the hash function is κ\kappa bits long. Because byzantine parties should not be able to brute force a hash, we assume that κ=Ω(log⁡n)\kappa=\Omega(\log n). Another assumption made in this work is that κ=polylog⁡(n)\kappa=\operatorname{polylog}(n).

Signatures: Each party has a public-private key pair, where the public key is known to all parties, and can sign messages with its private key. We assume that signatures are unforgeable: it is computationally infeasible for a party to forge a signature of another party. The signature size is κ\kappa bits.

Erasure Coding: Erasure coding allows a message to be split into multiple shares, such that a subset of the shares can be used to reconstruct the original message. We use classical Reed-Solomon codes [27]:

Definition 1. An LL-bit value can be split into mm shares, such that any subset of m/2m/2 shares can be used to reconstruct the original value. Each share has size O(L/m+log⁡m)O(L/m+\log m) bits.

References

  1. [2]Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Bit Optimal Distributed Consensus, pages 313–321. Springer US, Boston, MA, 1992. doi:10.1007/978-1-4615-3422-8_27.DOI
  2. [3]Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The sphincs+ signature framework. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS ’19, page 2129–2146, 2019. doi:10.1145/3319535.3363229.DOI
  3. [4]Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part I, volume 12550 of LNCS, pages 353–380. Springer, Cham, November 2020. doi:10.1007/978-3-030-64375-1_13.DOI
  4. [5]Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. Journal of Cryptology, 17(4):297–319, September 2004. doi:10.1007/s00145-004-0314-9.
  5. [6]Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. DARE to agree: Byzantine agreement with optimal resilience and adaptive communication. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, 43rd ACM PODC, pages 145–156. ACM, June 2024. doi:10.1145/3662158.3662792.DOI
  6. [7]Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. Repeated agreement is cheap! On weak accountability and multishot byzantine agreement. In Balliu and Kuhn [1], pages 15–27. doi:10.1145/3732772.3733520.DOI
  7. [8]Michael B. Cohen. Ramanujan graphs in polynomial time. In Irit Dinur, editor, 57th FOCS, pages 276–281. IEEE Computer Society Press, October 2016. doi:10.1109/FOCS.2016.37.DOI
  8. [9]Shir Cohen, Idit Keidar, and Alexander Spiegelman. Brief announcement: Not a CO-Incidence: Sub-quadratic asynchronous byzantine agreement WHP. In Yuval Emek and Christian Cachin, editors, 39th ACM PODC, pages 175–177. ACM, August 2020. doi: 10.1145/3382734.3405708.DOI
  9. [10]Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Wattenhofer. From few to many faults: Optimal adaptive byzantine agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’26, page 177–187, 2026. doi:10.1145/3796701.3815964.DOI
  10. [11]Rafạel Del Pino, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, and Markku-Juhani O. Saarinen. Threshold raccoon: Practical threshold signatures from standard lattice assumptions. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part II, volume 14652 of LNCS, pages 219–248. Springer, Cham, May 2024. doi:10.1007/978-3-031-58723-8_8.DOI
  11. [12]David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In Kaisa Nyberg, editor, Topics in Cryptology — CT-RSA 2015, pages 127–144, Cham, 2015. doi:10.1007/978-3-319-16715-2_7.DOI
  12. [13]D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666, 1983. doi:10.1137/0212045.DOI
  13. [14]Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. In Robert L. Probert, Michael J. Fischer, and Nicola Santoro, editors, 1st ACM PODC, pages 132–140. ACM, August 1982. doi:10.1145/800220.806690.DOI
  14. [15]Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR TCHES, 2018(1):238–268, 2018. URL: https://tches.iacr.org/index.php/TCHES/article/view/839, doi:10.13154/tches.v2018.i1.238-268.
  15. [16]Marc Dufay, Diana Ghinea, and Anton Paramonov. General Convex Agreement with Near-Optimal Communication. In William K. Moses Jr. and Keren Censor-Hillel, editors, 40th International Symposium on Distributed Computing (DISC 2026), volume 397, pages 35:1–35:25, 2026. doi:10.4230/LIPIcs.DISC.2026.35.arxiv.org/abs/2602.21411
  16. [17]Marc Dufay, Anton Paramonov, and Roger Wattenhofer. Brief Announcement: Optimal Adaptive Multi-Valued Byzantine Agreement. In William K. Moses Jr. and Keren Censor-Hillel, editors, 40th International Symposium on Distributed Computing (DISC 2026), volume 397, pages 63:1–63:7, 2026. doi:10.4230/LIPIcs.DISC.2026.63.arxiv.org/abs/2608.17552
  17. [18]Fabien Dufoulon and Gopal Pandurangan. Improved byzantine agreement under an adaptive adversary. In Balliu and Kuhn [1], pages 173–180. doi:10.1145/3732772.3733553.
  18. [19]Thomas Espitau, Guilhem Niot, and Thomas Prest. Flood and submerse: Distributed key generation and robust threshold signature from lattices. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VII, volume 14926 of LNCS, pages 425–458. Springer, Cham, August 2024. doi:10.1007/978-3-031-68394-7_14.DOI
  19. [20]S. Even and A. Paz. A note on cake cutting. Discrete Applied Mathematics, 7(3):285–296, 1984. doi:10.1016/0166-218X(84)90005-2.DOI
  20. [21]Martin Hirt, Ueli M. Maurer, and Bartosz Przydatek. Efficient secure multi-party computation. In Tatsuaki Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 143–161. Springer, Berlin, Heidelberg, December 2000. doi:10.1007/3-540-44448-3_12.DOI
  21. [22]Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraete. Hypergraph ramsey numbers: Triangles versus cliques. Journal of Combinatorial Theory, Series A, 120(7):1491–1507, 2013. doi:10.1016/j.jcta.2013.04.009.DOI
  22. [23]Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, Advances in Cryptology — CRYPTO ’87, pages 369–378, 1988. doi:10.1007/3-540-48184-2_32.DOI
  23. [24]Atsuki Momose and Ling Ren. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209, pages 32:1–32:16, 2021. doi:10.4230/LIPIcs.DISC.2021.32.DOI
  24. [25]M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234, 1980. doi:10.1145/322186.322188.DOI
  25. [26]Eli Upfal. Tolerating linear number of faults in networks of bounded degree. In Norman C. Hutchinson, editor, 11th ACM PODC, pages 83–89. ACM, August 1992. doi:10.1145/135419.135437.DOI
  26. [27]Stephen B. Wicker and Vijay K. Bhargava, editors. Reed-Solomon Codes and Their Applications. John Wiley & Sons, Inc., USA, 1999.DOI

Paper details

vlnc:W_qdyxz973
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents