International Association
for Cryptologic Research

The leader election problem requires a set of $n$ parties, out of which up to $t$ can be Byzantine, to elect a leader uniformly at random such that no two parties disagree on the elected leader and an honest leader is elected with constant probability. The Scalable Leader Election protocol published in SODA'2006 is an important breakthrough in solving this problem efficiently for all but $o(1)$ of the parties. They achieve a protocol for $t < (\frac{1}{3} - \epsilon)n$ (for $\epsilon = o(1)$) in the full-information setting such that every party only sends $\polylog(n)$ bits. In this paper, we revisit their work and show that there are subtleties in the protocol that are not dealt with in the analysis. In particular, two mechanisms related to ``silencing'' parties and dealing with ``bad nodes'' are at odds with each other, which is why the existing analysis is insufficient. We present these concerns in detail and subsequently present a modification to their protocol with a corresponding analysis to solve leader election with the desired metrics.

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing succinct arguments. In this work, we study the limitations of IOPs, as well as their relation to those of PCPs. We present a versatile toolbox of IOP-to-IOP transformations containing tools for: (i) length and round reduction; (ii) improving completeness; and (iii) derandomization. We use this toolbox to establish several barriers for IOPs: \begin{itemize} \item Low-error IOPs can be transformed into low-error PCPs. In other words, interaction can be used to construct low-error PCPs; alternatively, low-error IOPs are as hard to construct as low-error PCPs. This relates IOPs to PCPs in the regime of the sliding scale conjecture for inverse-polynomial soundness error. \item Limitations of quasilinear-size IOPs for 3SAT with small soundness error. \item Limitations of IOPs where query complexity is much smaller than round complexity. \item Limitations of binary-alphabet constant-query IOPs. \end{itemize} We believe that our toolbox will prove useful to establish additional barriers beyond our work.

We investigate the communication complexity of Byzantine agreement protocols for long messages against an adaptive adversary. In this setting, prior $n$-party protocols either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages and security parameter $\kappa$. We improve the state of the art by presenting protocols with communication complexity $O(nl + n \cdot \poly(\kappa))$ in both the synchronous and asynchronous communication models. The synchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{2}$ corruptions and assumes a VRF setup, while the asynchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{3}$ corruptions under further cryptographic assumptions. Our protocols are very simple and combine subcommittee election with the recent approach of Nayak et al. (DISC'20). Surprisingly, the analysis of our protocols is 'all but simple' and involves an interesting new application of Mc Diarmid's inequality to obtain 'almost optimal' corruption thresholds.