Ilan Komargodski

Distributed agreement is a general name for the task of ensuring consensus among non-faulty nodes in the presence of faulty or malicious behavior. Well-known instances of agreement tasks are Byzantine Agreement, Broadcast, and Committee or Leader Election. Since agreement tasks lie at the heart of many modern distributed applications, there has been an increased interest in designing scalable protocols for these tasks. Specifically, we want protocols where the per-party communication complexity scales sublinearly with the number of parties. With unconditional security, the state of the art protocols have $${\tilde{O}}(\sqrt{n})$$ O ~ ( n ) per-party communication and $${\tilde{O}}(1)$$ O ~ ( 1 ) rounds, where n stands for the number of parties, tolerating $$1/3-\epsilon $$ 1 / 3 - ϵ fraction of corruptions for any $$\epsilon >0$$ ϵ > 0 . There are matching lower bounds showing that these protocols are essentially optimal among a large class of protocols. Recently, Boyle-Cohen-Goel (PODC ’21, Journal of Cryptology ’24) relaxed the attacker to be computationally bounded and using strong cryptographic assumptions showed a protocol with $${\tilde{O}}(1)$$ O ~ ( 1 ) per-party communication and rounds (similarly, tolerating $$1/3-\epsilon $$ 1 / 3 - ϵ fraction of corruptions). The security of their protocol relies on SNARKs for NP with linear-time extraction, a somewhat strong and non-standard assumption. Their protocols further rely on a public-key infrastructure (PKI) and a common-reference-string (CRS). In this work, we present a new synchronous protocol with $${\tilde{O}}(1)$$ O ~ ( 1 ) per-party communication and rounds but relying only on the standard Learning With Errors (LWE) assumption. Our protocol also relies on a PKI and a CRS, and tolerates $$1/3-\epsilon $$ 1 / 3 - ϵ fraction of corruptions, similarly to Boyle et al. Technically, we leverage (multi-hop) BARGs for NP directly and in a generic manner that significantly deviates from the framework of Boyle et al.

Sponge hashing is a novel alternative to the popular Merkle-Damgård hashing design. The sponge construction has become increasingly popular in various applications, perhaps most notably, it underlies the SHA-3 hashing standard. Sponge hashing is parametrized by two numbers, r and c (bitrate and capacity, respectively), and by a fixed-size permutation on $$r+c$$ r + c bits. In this work, we study the collision resistance of sponge hashing instantiated with a random permutation by adversaries with arbitrary S -bit auxiliary advice input about the random permutation that make T online queries. Recent work by Coretti et al. (CRYPTO ’18) showed that such adversaries can find collisions (with respect to a random c -bit initialization vector) with advantage $$\Theta (ST^2/2^c + T^2/ 2^{r})$$ Θ ( S T 2 / 2 c + T 2 / 2 r ) . Although the above attack formally breaks collision resistance in some range of parameters, its practical relevance is limited since the resulting collision is very long (on the order of T blocks). Focusing on the task of finding short collisions, we study the complexity of finding a B -block collision for a given parameter $$B\ge 1$$ B ≥ 1 . We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage $$\begin{aligned} \Omega \left( \left( \frac{S^{2}T}{2^{2c}}\right) ^{2/3} + \frac{T^2}{2^r}\right) . \end{aligned}$$ Ω S 2 T 2 2 c 2 / 3 + T 2 2 r . In certain range of parameters (e.g., $$ST^2>2^c$$ S T 2 > 2 c ), our attack outperforms the previously-known best attack. To the best of our knowledge, this is the first natural application for which sponge hashing is provably less secure than the corresponding instance of Merkle-Damgård hashing. Our attack relies on a novel connection between single-block collision finding in sponge hashing and the well-studied function inversion problem. We also give a general attack that works for any $$B\ge 2$$ B ≥ 2 and has advantage $$\Omega ({STB}/{2^{c}} + {T^2}/{2^{\min \{r,c\}}})$$ Ω ( STB / 2 c + T 2 / 2 min { r , c } ) , adapting an idea of Akshima et al. (CRYPTO ’20). We complement the above attacks with bounds on the best possible attacks. Specifically, we prove that there is a qualitative jump in the advantage of best possible attacks for finding unbounded-length collisions and those for finding very short collisions. Most notably, we prove (via a highly non-trivial compression argument) that the above attack is optimal for $$B=2$$ B = 2 in some range of parameters.

We study the complexity of memory checkers with computational security and prove the first general tight lower bound. Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS ’91, Algorithmica ’94), allow a user to store and maintain a large memory on a remote and unreliable server by using small trusted local storage. The user can issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. The main complexity measure of interest is the size of the local storage and the number of queries the memory checker makes upon every logical instruction. The most efficient known construction has query complexity \(O(\log n/\log \log n)\) and local space proportional to a computational security parameter, assuming one-way functions, where n is the logical memory size. Dwork, Naor, Rothblum, and Vaikuntanathan (TCC ’09) showed that for a restricted class of “deterministic and non-adaptive” memory checkers, this construction is optimal, up to constant factors. However, going beyond the small class of deterministic and non-adaptive constructions has remained a major open problem. In this work, we fully resolve the complexity of memory checkers by showing that any construction with local space p and query complexity q must satisfy \(\begin{equation*} p \ge \frac{n}{(\log n)^{O(q)}} \;. \end{equation*}\) This implies, as a special case, that \(q\ge \Omega (\log n/\log \log n)\) in any scheme, assuming that \(p\le n^{1-\varepsilon }\) for \(\varepsilon \gt 0\) . The bound applies to any scheme with computational security, completeness \(2/3\) , and inverse polynomial in n soundness (all of which make our lower bound only stronger). We further extend the lower bound to schemes where the read complexity \(q_r\) and write complexity \(q_w\) differ. For instance, we show the tight bound that if \(q_r=O(1)\) and \(p\le n^{1-\varepsilon }\) for \(\varepsilon \gt 0\) , then \(q_w\ge n^{\Omega (1)}\) . This is the first lower bound, for any non-trivial class of constructions, showing a read-write query complexity trade-off. Our proof is via a delicate compression argument showing that a “too good to be true” memory checker can be used to compress random bits of information. We draw inspiration from tools recently developed for lower bounds for relaxed locally decodable codes. However, our proof itself significantly departs from these works, necessitated by the differences between settings.