Cody Freitag

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 introduce the notion of aSuccinct Parallelizable Argument of Knowledge(SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel timeTwith at mostpprocessors: —The prover’s (parallel) running time is \( T + \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) . (In other words, the prover’s running time is essentiallyTfor large computation times!) —The prover uses at most \( p \cdot \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) processors. —The communication and verifier complexity are both \( \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) . The combination of all three is desirable, as it gives a way to leverage a moderate increase in parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed.Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time is \( T \cdot \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \) when usingpprocessors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK foranyparallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinctnon-interactiveargument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to \( \mathrm{poly}\hspace{-2.0pt}\log (T\cdot p) \) factors.We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF.