International Association
for Cryptologic Research

In this paper, we present two \textit{early stopping} Byzantine agreement protocols in the authenticated setting against a corrupt minority $t < n/2$, where $t$ represents the maximum number of malicious parties. Early stopping protocols ensure termination within a number of rounds determined solely by the actual number of malicious nodes $f$ present during execution, irrespective of $t$. Our first protocol is deterministic and ensures early stopping termination in $ (d+5) \cdot (\lfloor f/d \rfloor +3)$ rounds, where $d$ is a fixed constant. For example, for all $d\ge 6$, our protocol runs in at most $(1+\epsilon )\cdot f$ rounds (where $0<\epsilon<1$), improving (for large $f$) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg~\cite{Perry}, which terminates in $2f+4$ rounds. Additionally, our second protocol is randomized, ensuring termination in an expected constant number of rounds and achieving early stopping in $(d+9) \cdot (\lfloor f/d \rfloor +2)$ rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank.~\cite{GOLDREICH199045}, which \emph{always} requires an expected constant number of rounds and $O(t)$ rounds in the worst case, i.e., does not have the early stopping property.

Time-lock puzzles (TLP) are a fascinating type of cryptographic problem that is easy to generate, but takes a certain time to solve, even when arbitrary parallel speedup is allowed. TLPs have wide-ranging applications including fairness, round efficient computation, and more. To reduce the effort needed to solve large numbers of TLPs, prior work has proposed batching techniques to reduce the cost of solving. However, these proposals either require: (1) a trusted setup or (2) the puzzle size be linear in the maximum batch size, which implies setting an a priori bound on the maximum size of the batch. Any of these limitations restrict the utility of TLPs in decentralized and dynamic settings like permissionless blockchains. In this work, we demonstrate the feasibility and usefulness of a TLP that overcomes all the above limitations using indistinguishability obfuscation to show that there are no fundamental barriers to achieving such a TLP construction. As a main application of our TLP, we show how to improve the resilience of consensus protocols toward network-level adversaries in the following settings: (1) We show a generic compiler that boosts the resilience of a Byzantine broadcast protocol $\Pi$ as follows: if $\Pi$ is secure against $t<n$ weakly adaptive corruptions, then the compiled protocol is secure against $t<n$ strongly adaptive corruptions. Here, `strong' refers to adaptively corrupting a party and deleting messages that it sent while still honest. Our compiler is round and communication preserving, and gives the first expected constant-round Byzantine broadcast protocol against a strongly adaptive adversary for the dishonest majority setting. (2) We adapt the Nakamoto consensus protocol to a weak model of synchrony where the adversary can adaptively create minority partitions in the network. Unlike prior works, we do not assume that all honest messages are delivered within a known upper bound on the message delay. This is the first work to show that it is possible to achieve consensus in the permissionless setting even after relaxing the standard synchrony assumption.

In Private Information Retrieval (PIR), a client wishes to retrieve the value of an index $i$ from a public database of $N$ values without leaking any information about $i$. In their recent seminal work, Corrigan-Gibbs and Kogan (EUROCRYPT 2020) introduced the first two-server PIR protocol with sublinear amortized server time and sublinear $O(\sqrt{N} \log N)$ bandwidth. In a followup work, Shi et al. (CRYPTO 2021) reduced the bandwidth to polylogarithmic by proposing a construction based on privately puncturable pseudorandom functions, a primitive whose only construction known to date is based on heavy cryptographic primitives such as LWE. Partly because of this, their PIR protocol does not achieve concrete efficiency. In this paper we propose TreePIR, a two-server PIR protocol with sublinear amortized server time and polylogarithmic bandwidth whose security can be based on just the DDH assumption. TreePIR can be partitioned in two phases that are both sublinear: The first phase is remarkably simple and only requires pseudorandom generators. The second phase is a single-server PIR protocol on \emph{only} $\sqrt{N}$ indices, for which we can use the protocol by D\"ottling et al. (CRYPTO 2019) based on DDH, or, for practical purposes, the most concretely efficient single-server PIR protocol. Not only does TreePIR achieve better asymptotics than previous approaches while resting on weaker cryptographic assumptions, it also outperforms existing two-server PIR protocols in practice. The crux of our protocol is a new cryptographic primitive that we call weak privately puncturable pseudorandom functions, which we believe can have further applications.

In Private Information Retrieval (PIR), a client wishes to access an index $i$ from a public $n$-bit database without revealing any information about $i$. Recently, a series of works starting with the seminal paper of Corrigan-Gibbs and Kogan (EUROCRYPT 2020) considered PIR with \emph{client preprocessing} and \emph{no additional server storage}. In this setting, we now have protocols that achieve $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ (amortized) server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(1)$ (amortized) bandwidth in the two-server model (Shi et al., CRYPTO 2021) as well as $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ bandwidth in the single-server model (Corrigan-Gibbs et al., EUROCRYPT 2022). Given existing lower bounds, a single-server PIR scheme with $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ (amortized) server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(1)$ (amortized) bandwidth is still feasible, however, to date, no known protocol achieves such complexities. In this paper we fill this gap by constructing the first single-server PIR scheme with $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(\sqrt{n})$ (amortized) server time and $\stackrel{\sim}{\smash{O}\rule{0pt}{1.0ex}}$$(1)$ (amortized) bandwidth. Our scheme achieves near-optimal (optimal up to polylogarithmic factors) asymptotics in every relevant dimension. Central to our approach is a new cryptographic primitive that we call an \emph{adaptable pseudorandom set}: With an adaptable pseudorandom set, one can represent a large pseudorandom set with a succinct fixed-size key $k$, and can both add to and remove from the set a constant number of elements by manipulating the key $k$, while maintaining its concise description as well as its pseudorandomness (under a certain security definition).

Byzantine Broadcast is crucial for many cryptographic protocols such as secret sharing, multiparty computation and blockchain consensus. In this paper we apply \emph{gossiping} (propagating a message by sending to a few random parties who in turn do the same, until the message is delivered) and propose new communication-efficient protocols, under dishonest majority, for Single-Sender Broadcast (BC) and Parallel Broadcast (PBC), improving the state-of-the-art in several ways. As our first warm-up result, we give a randomized protocol for BC which achieves $O(n^2\kappa^2)$ communication complexity from plain public key setup assumptions. This is the first protocol with subcubic communication in this setting, but does so only against static adversaries. Using some ideas from our BC protocol, we then move to our central contribution and present two protocols for PBC that are secure against adaptive adversaries. To the best of our knowledge we are the first to study PBC \emph{specifically}: All previous approaches for parallel BC (PBC) naively run $n$ instances of single-sender Broadcast, increasing the communication complexity by an undesirable factor of $n$. Our insight of avoiding black-box invocations of BC is particularly crucial for achieving our asymptotic improvements. In particular: \begin{enumerate} \item Our first PBC protocol achieves $\tilde{O}(n^3\kappa^2)$ communication complexity and relies only on plain public key setup assumptions. \item Our second PBC protocol uses trusted setup and achieves nearly optimal communication complexity $\tilde{O}(n^2\kappa^4)$. \end{enumerate} Both PBC protocols yield an almost linear improvement over the best known solutions involving $n$ parallel invocations of the respective BC protocols such as those of Dolev and Strong (SIAM Journal on Computing, 1983) and Chan et al. (Public Key Cryptography, 2020). Central to our PBC protocols is a new problem that we define and solve, that we call ``{Converge}''. In {Converge}, parties must run an adaptively-secure and \emph{efficient} protocol such that by the end of the protocol, the honest parties that remain possess a superset of the union of the inputs of the initial honest parties.

We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both $$O(d\log C)$$ for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 s to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.

Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely access untrusted memory, such that the access patterns reveal nothing about sensitive data. ORAM is known to have broad applications in secure processor design and secure multiparty computation for big data. Unfortunately, due to a logarithmic lower bound by Goldreich and Ostrovsky (J ACM 43(3):431–473, 1996 ), ORAM is bound to incur a moderate cost in practice. In particular, with the latest developments in ORAM constructions, we are quickly approaching this limit, and the room for performance improvement is small. In this paper, we consider new models of computation in which the cost of obliviousness can be fundamentally reduced in comparison with the standard ORAM model. We propose the oblivious network RAM model of computation, where a CPU communicates with multiple memory banks, such that the adversary observes only which bank the CPU is communicating with, but not the address offset within each memory bank. In other words, obliviousness within each bank comes for free—either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank—and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the network RAM model. We describe applications of our new model in distributed storage applications with a network adversary.

We propose the first linear-space searchable encryption scheme with constant locality and sublogarithmic read efficiency, strictly improving the previously best known read efficiency bound (Asharov et al., STOC 2016) from $$\varTheta (\log N \log \log N)$$Θ(logNloglogN) to $$O(\log ^{\gamma } N)$$O(logγN) where $$\gamma =\frac{2}{3}+\delta $$γ=23+δ for any fixed $$\delta >0$$δ>0 and where N is the number of keyword-document pairs. Our scheme employs four different allocation algorithms for storing the keyword lists, depending on the size of the list considered each time. For our construction we develop (i) new probability bounds for the offline two-choice allocation problem; (ii) and a new I/O-efficient oblivious RAM with $$\tilde{O}(n^{1/3})$$O~(n1/3) bandwidth overhead and zero failure probability, both of which can be of independent interest.