The reliable broadcast protocol with the best communication complexity for long messages to date is the MiniCast protocol of Locher & Shoup (2024). To reliably broadcast a message m to n parties, MiniCast has communication complexity ~ 1.5|m|n when the size |m| of m is large. However, the round complexity of MiniCast is 4, which is worse than the 3 rounds of the classical protocol of Bracha. We give a new reliable broadcast protocol whose communication complexity is essentially the same as that of MiniCast, but whose round complexity is just 3. For large |m|, the communication complexity of our new protocol is essentially optimal (for 3-round protocols with somewhat balanced communication). Like MiniCast, our new protocol does not rely on any cryptography other than hash functions. We also give two new 2-round protocols that rely on signatures. The communication complexity of the first protocol is also ~ 1.5|m|n, unless the sender provably misbehaves, in which case its communication complexity may degrade to ~ 2|m|n. The communication complexity of the second protocol is ~ 1.5|m|n, even in the worst case, but (unlike our other protocols) the communication is unbalanced.

We present Kudzu, a high-throughput atomic broadcast protocol with an integrated fast path. Our contribution is based on the combination of two lines of work. Firstly, our protocol achieves finality in just two rounds of communication if all but p out of n = 3f + 2p + 1 participating replicas behave correctly, where f is the number of Byzantine faults that are tolerated. Due to the seamless integration of the fast path, even in the presence of more than p faults, our protocol maintains state-of-the-art characteristics. Secondly, our protocol utilizes the bandwidth of participating replicas in a balanced way, alleviating the bottleneck at the leader, and thus enabling high throughput. This is achieved by disseminating blocks using erasure codes. Despite combining a novel set of advantages, Kudzu is remarkably simple: intricacies such as "progress certificates", complex view changes, and speculative execution are avoided.

BoLD is a new dispute resolution protocol that is designed to replace the originally deployed Arbitrum dispute resolution protocol. Unlike that protocol, BoLD is resistant to delay attacks. It achieves this resistance without a significant increase in onchain computation costs and with reduced staking costs.

Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on cryptographic hash functions modeled as a random oracle. Our protocol has O(κn3) total communication and runs in expected O(1) rounds. The fact that we use only cryptographic hash functions also means that our protocol is post-quantum secure. The minimal use of cryptography and the small number of rounds make our protocol practical. We implement our protocol and evaluate it in a geo-distributed setting with up to 128 machines. Our experimental evaluation shows that our protocol is more efficient than the only other setup-free consensus protocol that has been implemented to date. En route to our asynchronous consensus protocols, we also introduce new primitives called asynchronous secret key sharing and cover gather, which may be of independent interest.

This paper explores the problem good-case latency of Byzantine fault-tolerant broadcast, motivated by the real-world latency and performance of practical state machine replication protocols. The good-case latency measures the time it takes for all non-faulty parties to commit when the designated broadcaster is non-faulty. We provide a complete characterization of tight bounds on good-case latency, in the authenticated setting under synchrony, partial synchrony and asynchrony. Some of our new results may be surprising, e.g., 2-round PBFT-style partially synchronous Byzantine broadcast is possible if and only if $n\geq 5f-1$, and a tight bound for good-case latency under $n/3

Abstract We present new protocols for Asynchronous Verifiable Secret Sharing for Shamir (i.e., threshold $$t t < n ) sharing of secrets. Our protocols: Use only “lightweight” cryptographic primitives, such as hash functions; Can share secrets over rings such as $${\mathbb {Z}}/(p^k)$$ Z / ( p k ) as well as finite fields $$\mathbb {F}_q$$ F q ; Provide optimal resilience, in the sense that they tolerate up to $$t < n/3$$ t < n / 3 corruptions, where n is the total number of parties; Are complete, in the sense that they guarantee that if any honest party receives their share then all honest parties receive their shares; Employ batching techniques, whereby a dealer shares many secrets in parallel and achieves an amortized communication complexity that is linear in n, at least on the “happy path”, where no party provably misbehaves.

We present the Internet Computer Consensus (ICC) family of protocols for atomic broadcast (a.k.a., consensus), which underpin the Byzantine fault-tolerant replicated state machines of the Internet Computer. The ICC protocols are leader-based protocols that assume partial synchrony, and that are fully integrated with a blockchain. The leader changes probabilistically in every round. These protocols are simple and robust: in any round where the leader is corrupt (which itself happens with probability less than 1/3) or the network is asynchronous, each ICC protocol will effectively allow other parties to step in and propose blocks for that round and to move the protocol forward to the next round. In case there was no agreement on a single block in a round, a decision for this round will be taken in a later round with synchronous network behavior and an honest leader. The task of reliably disseminating the blocks to all parties is an integral part the protocol. We present three different protocols, along with various minor variations on each. The first of these protocols (ICC0) illustrates the combination of the main building blocks in a simplified manner for an easier presentation and analysis. Protocol ICC1 is designed to be integrated with a peer-to-peer gossip sub-layer, which reduces the bottleneck created at the leader for disseminating large blocks, a problem that all leader-based protocols must address. Our Protocol ICC2 addresses the same problem by substituting a lowcommunication reliable broadcast subprotocol (which may be of independent interest) for the gossip sub-layer.

We implemented (a simplified version of) the branching-program obfuscator due to Gentry et al. (GGH15), which is itself a variation of the first obfuscation candidate by Garg et al. (GGHRSW13). To keep within the realm of feasibility, we had to give up on some aspects of the construction, specifically the "multiplicative bundling" factors that protect against mixed-input attacks. Hence our implementation can only support read-once branching programs.

Secure identity tokens such as Electronic Identity (eID) cards are emerging everywhere. At the same time user-centric identity management gains acceptance. Anonymous credential schemes are the optimal realization of user-centricity. However, on inexpensive hardware platforms, typically used for eID cards, these schemes could not be made to meet the necessary requirements such as future-proof key lengths and transaction times on the order of 10 seconds. The reasons for this is the need for the hardware platform to be standardized and certified. Therefore an implementation is only possible as a Java Card applet. This results in severe restrictions: little memory (transient and persistent), an 8-bit CPU, and access to hardware acceleration for cryptographic operations only by defined interfaces such as RSA encryption operations.

We show how to significantly speed-up the encryption portion of some public-key cryptosystems by the simple expedient of allowing a sender to maintain state that is re-used across different encryptions.In particular we present stateful versions of the DHIES and Kurosawa-Desmedt schemes that each use only 1 exponentiation to encrypt, as opposed to 2 and 3 respectively in the original schemes, yielding the fastest discrete-log based public-key encryption schemes known in the random-oracle and standard models respectively. The schemes are proven to meet an appropriate extension of the standard definition of IND-CCA security that takes into account novel types of attacks possible in the stateful setting.

A new public-key encryption scheme, along with several variants, is proposed and analyzed. The scheme and its variants are quite practical and are proved secure against adaptive chosen ciphertext attack under standard intractability assumptions. These appear to be the first public-key encryption schemes in the literature that are simultaneously practical and provably secure.

In this paper we describe ideas used to accelerate the Searching Phase of the Berlekamp—Zassenhaus algorithm, the algorithm most widely used for computing factorizations in Z[x]. Our ideas do not alter the theoretical worst-case complexity, but they do have a significant effect in practice: especially in those cases where the cost of the Searching Phase completely dominates the rest of the algorithm. A complete implementation of the ideas in this paper is publicly available in the library NTL [16]. We give timings of this implementation on some difficult factorization problems.

Byzantine agreement requires a set of parties in a distributed system to agree on a value even if some parties are corrupted. A new protocol for Byzantine agreement in a completely asynchronous network is presented that makes use of cryptography, specifically of threshold signatures and coin-tossing protocols. These cryptographic protocols have practical and provably secure implementations in the “random oracle” model. In particular, a coin-tossing protocol based on the Diffie-Hellman problem is presented and analyzed.

We present a new protocol that allows two players to exchange digital signatures over the Internet in a fair way, so that either each player gets the other's signature, or neither player does. The obvious application is where the signatures represent items of value, for example, an electronic check or airline ticket. The protocol can also be adapted to exchange encrypted data. It relies on a trusted third party, but is "optimistic," in that the third party is only needed in cases where one player crashes or attempts to cheat. A key feature of our protocol is that a player can always force a timely and fair termination, without the cooperation of the other player, even in a completely asynchronous network. A specialization of our protocol can be used for contract signing; this specialization is not only more efficient, but also has the important property that the third party can be held accountable for its actions: if it ever cheats, this can be detected and proven.

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called strong RSA assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA assumption.

We describe and analyze a new digital signature scheme. The new scheme is quite efficient, does not require the the signer to maintain any state, and can be proven secure against adaptive chosen message attack under a reasonable intractability assumption, the so-called strong RSA assumption. Moreover, a hash function can be incorporated into the scheme in such a way that it is also secure in the random oracle model under the standard RSA assumption.

New algorithms are presented for computing the minimal polynomial over a finite field K of a given element in an algebraic extension of K of the form K[ff] or K[ff][fi]. The new algorithms are explicit and can be implemented rather easily in terms of polynomial multiplication, and are much more efficient than other algorithms in the literature. 1 Introduction In this paper, we consider the problem of computing the minimal polynomial over a finite field K of a given element oe in an algebraic extension of K of the form K[ff] or K[ff][fi]. The minimal polynomial of oe is defined to be the unique monic polynomial OE oe=K 2 K[x] of least degree such that OE oe=K (oe) = 0. In the first case, we assume that the ring K[ff] is given as K[x]=(f) where f 2 K[x] is a monic polynomial of degree n, and that elements in K[ff] are represented in the natural way as elements of K[x] !n (the set of polynomials of degree less than n). Similarly, in the second case, we assume that K[ff] is given as a...

The optimistic approach of involving a third party only in the case of exceptions is a useful technique to build secure, yet practical fair exchange protocols. Previous solutions using this approach implicitly assumed that players had reliable communication channels to the third party. We present a set of optimistic fair exchange protocols which tolerate temporary failures in the communication channels to the third party. A central feature of the protocols is that either player can asynchronously and unilaterally bring a protocol run to completion.

New algorithms are presented for factoring polynomials of degree n over the finite field of q elements, where q is a power of 2. When log q = n 1+a , where a ? 0 is constant, these algorithms are asymptotically faster than previous known algorithms, the fastest of which required time \\Omega\\Gamma n(log q) 2 ), y or \\Omega\\Gamma n 3+2a ) in this case, which corresponds to the cost of computing x q modulo an n degree polynomial. The new algorithms factor an arbitrary polynomial in time O(n 3+a+o(1) + n 2:69+1:69a ). All measures are in fixed precision operations, that is in bit complexity. Moreover, in the special case where all the irreducible factors have the same degree, the new algorithms run in time O(n 2:69+1:69a ). In particular, one may test a polynomial for irreducibility in O(n 2:69+1:69a ) bit operations. These results generalize to the case where q = p k , where p is a small, fixed prime. 1 Introduction The expected running time of randomized algorithms...

) Rafail Ostrovsky Victor Shoup y Bellcore Bellcore, IBM May 1997 Abstract This paper deals with the problem of efficiently and privately storing and retrieving information that is distributively maintained in several databases that do not communicate with one another. The goal is to minimize the communication complexity while maintaining privacy (i.e., so that individual databases do not get any information about the data or the nature of the users' queries). The question of private retrieval from multiple databases was introduced in a very nice paper of Chor, Goldreich, Kushilevitz and Sudan (FOCS '95), but the question whether it is possible to perform both reading and writing in a communication-efficient manner remained open. In this paper, we answer this question in the affirmative, and show that efficient read/write schemes are indeed possible. In fact, we show a general informationtheoretic reduction from reading and writing to any read-only scheme that preserves the comm...

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields.The algorithms factor a polynomial of de reen over afinite field of constant cardi-#8,5 nality in time O(n ).Previous algorithms required time @(n2+0(1)).Thenew algorithms rely on fast matrix multiplacation techniques.More generally, to factor a polynomial of degree noverthe finite field F~with q elements, the algo-1 Sl.510gqJ ~ithmetic operations in J?9. rithms use O(n The new "baby step/giant step" techniques used in our algorithms also yield new fast practical algorithms at superquadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields. 1

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over Fq, the algorithm uses O((n2 + n log q)•(log n)2 log log n) arithmetic operations in Fq. The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.

It is shown that there is a set of points p/sub 1/, p/sub 2/,. . .,p/sub n/ such that any algebraic program of depth d for polynomial evaluation (or interpolation) at these points has size Omega (n log n/log d). Moreover, if d is a constant, then a lower bound of Omega (n/sup 1+1/d/) is obtained.>

We present a new algorithm for factoring polynomials over finite fields. Our algorithm is deterministic, and its running time is "almost" quadratic when the characteristic is a small fixed prime. As such, our algorithm is asymptotically faster than previously known deterministic algorithms for factoring polynomials over finite fields of small characteristic. Appeared in Proc. 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 14--21, 1991. 1. Introduction Consider the problem of factoring a univariate polynomial f of degree n over the finite field F q , where q = p k and p is a small, fixed prime. We assume that F q is represented as F p (`), where ` is the root of an irreducible polynomial over F p of degree k. We present a new deterministic algorithm for this problem whose asymptotic complexity is less than that of previous deterministic algorithms. In discussing running times of algorithms, for expositional purposes we treat p as a constant in Sec...

We describe a new deterministic algorithm for the problem of constructing k-th power nonresidues in finite fields GF(pn), where p is prime and k is a prime divisor of pn -1.We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed n and p + m, our algorithm runs in polynomial time.Unlike previous algorithms for this problem, this polynomial time bound holds even if k is very large.More generally, assuming the ERH, in time (log p)"(n) we can construct a set of elements that generates GF(pn)*.

Let GF(p ~) be the finite field with p'~ elements where p is prime.We consider the problem of how to deterministically generate in polynomial time a subset of GF(p n) that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in GF(pn).We present three results.First, we present a solution to this problem for the case where p is small, i.e., p = n °(1).Second, we present a solution to this problem under the assumption of the Extended Riemann Hypothesis (ERH) for the case where p is large and n = 2. Third, we give a quantitative improvement of a theorem of Wang on the least primitive root for GF(p) assuming the ERH.

An algorithm is presented for finding an irreducible polynomial of specified degree over a finite field. It is deterministic and runs in polynomial time for fields of small characteristics. A proof is given of the stronger result, that the problem of finding irreducible polynomials of specified degree over a finite field K is deterministic-polynomial-time reducible to the problem of factoring polynomials over the prime field of K.>