## CryptoDB

### Cody Freitag

#### Publications

**Year**

**Venue**

**Title**

2023

EUROCRYPT

Optimal Security for Keyed Hash Functions: Avoiding Time-Space Tradeoffs for Finding Collisions
Abstract

Cryptographic hash functions map data of arbitrary size to a fixed size digest, and are one of the most commonly used cryptographic objects. As it is infeasible to design an individual hash function for every input size, variable-input length hash functions are built by designing and bootstrapping a single fixed-input length function that looks sufficiently random.
To prevent trivial preprocessing attacks, applications often require not just a single hash function but rather a family of keyed hash functions.
The most well-known methods for designing variable-input length hash function families from a fixed idealized function are the Merkle-Damgård and Sponge designs. The former underlies the SHA-1 and SHA-2 constructions and the latter underlies SHA-3. Unfortunately, recent works (Coretti et al. EUROCRYPT 2018, Coretti et al. CRYPTO 2018)
show non-trivial time-space tradeoff attacks for finding collisions for both. Thus, this forces a parameter blowup (i.e., efficiency loss) for reaching a certain desired level of security. We ask whether it is possible to build families of keyed hash functions which are \emph{provably} resistant to any non-trivial time-space tradeoff attacks for finding collisions, without incurring significant efficiency costs.
We present several new constructions of keyed hash functions that are provably resistant to any non-trivial time-space tradeoff attacks for finding collisions. Our constructions provide various tradeoffs between their efficiency and the range of parameters where they achieve optimal security for collision resistance. Our main technical contribution is proving optimal security bounds for converting a hash function with a fixed-sized input to a keyed hash function with (potentially larger) fixed-size input. We then use this keyed function as the underlying primitive inside the standard MD and Merkle tree constructions. We strongly believe that this paradigm of using a keyed inner hash function in these constructions is the right one, for which non-uniform security has not been analyzed prior to this work. The most well-known methods for designing variable-input length hash function families from a fixed idealized function are the Merkle-Damgård and Sponge designs. The former underlies the SHA-1 and SHA-2 constructions and the latter underlies SHA-3. Unfortunately, recent works (Coretti et al. EUROCRYPT 2018, Coretti et al. CRYPTO 2018) show non-trivial time-space tradeoffs for both schemes. Thus, this forces a parameter blowup (i.e., efficiency loss) for reaching a certain desired level of security. We ask whether it is possible to build families of keyed hash functions which are \emph{provably} resistant to any non-trivial time-space tradeoff attacks, without a significant cost in efficiency.
We give several new constructions of keyed hash functions that are provably resistant to any non-trivial time-space tradeoffs attacks. Our constructions provide various tradeoffs between their efficiency and the range of parameters where they achieve optimal security. Our main technical contribution is proving optimal security bounds for converting a hash function with a fixed-sized input to a keyed hash function with (potentially larger) fixed-size input. We then use this keyed function as the underlying primitive inside the standard Merkle-Damgård and Merkle tree constructions. We strongly believe that this paradigm of using a keyed inner hash function in these constructions is the right one, for which non-uniform security has not been analyzed prior to this work.

2022

CRYPTO

Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions
📺
Abstract

Sponge hashing is a novel alternative to the popular Merkle-Damg\aa 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$ bits. In this work, we study the collision resistance of sponge hashing instantiated with a random permutation by adversaries with an arbitrary $S$-bit auxiliary advice input about the random permutation and $T$ queries. Recent work by Coretti et al.\ (CRYPTO '18) showed that such adversaries can find collisions (with respect to a random IV) with advantage $\Theta(ST^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 \emph{short} collisions, we study the complexity of finding a $B$-block collision for a given parameter $B\ge 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{align*}
\Omega \left(\left(\frac{S^{2}T}{2^{2c}}\right)^{2/3} + \frac{T^2}{2^r}\right).
\end{align*}
In some range of parameters, our attack has constant advantage of winning while the previously-known best attack has exponentially small advantage. To the best of our knowledge, this is the first natural application for which sponge hashing is \emph{provably less secure} than the corresponding instance of Merkle-Damg\aa 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$ and has advantage $\Omega({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$ and in some range of parameters.

2022

TCC

Universal Reductions: Reductions Relative to Stateful Oracles
Abstract

We define a framework for analyzing the security of cryptographic protocols that makes minimal assumptions about what a ``realistic model of computation is". In particular, whereas classical models assume that the attacker is a (perhaps non-uniform) probabilistic polynomial-time algorithm, and more recent definitional approaches also consider quantum polynomial-time algorithms, we consider an approach that is more agnostic to what computational model is physically realizable.
Our notion of \emph{universal reductions} models attackers as PPT algorithms having access to some arbitrary unbounded \emph{stateful} Nature that cannot be rewound or restarted when queried multiple times. We also consider a more relaxed notion of \emph{universal reductions w.r.t. time-evolving, $k$-window, Natures} that makes restrictions on Nature---roughly speaking, Nature's behavior may depend on number of messages it has received and the content of the last $k(\sec)$-messages (but not on ``older'' messages).
We present both impossibility results and general feasibility results for our notions, indicating to what extent the extended Church-Turing hypotheses are needed for a well-founded theory of Cryptography.

2022

TCC

Parallelizable Delegation from LWE
Abstract

We present the first non-interactive delegation scheme for P with time-tight parallel prover
efficiency based on standard hardness assumptions. More precisely, in a time-tight delegation
scheme—which we refer to as a SPARG (succinct parallelizable argument)—the prover’s parallel
running time is t + polylog(t), while using only polylog(t) processors and where t is the length
of the computation. (In other words, the proof is computed essentially in parallel with the
computation, with only some minimal additive overhead in terms of time).
Our main results show the existence of a publicly-verifiable, non-interactive, SPARG for P
assuming polynomial hardness of LWE. Our SPARG construction relies on the elegant recent
delegation construction of Choudhuri, Jain, and Jin (FOCS’21) and combines it with techniques
from Ephraim et al (EuroCrypt’20).
We next demonstrate how to make our SPARG time-independent—where the prover and
verifier do not need to known the running-time t in advance; as far as we know, this yields
the first construction of a time-tight delegation scheme with time-independence based on any
hardness assumption.
We finally present applications of SPARGs to the constructions of VDFs (Boneh et al,
Crypto’18), resulting in the first VDF construction from standard polynomial hardness assumptions (namely LWE and the minimal assumption of a sequentially hard
function).

2021

TCC

Non-Malleable Time-Lock Puzzles and Applications
📺
Abstract

Time-lock puzzles are a mechanism for sending messages "to the future", by allowing a sender to quickly generate a puzzle with an underlying message that remains hidden until a receiver spends a moderately large amount of time solving it. We introduce and construct a variant of a time-lock puzzle which is non-malleable, which roughly guarantees that it is impossible to "maul" a puzzle into one for a related message without solving it.
Using non-malleable time-lock puzzles, we achieve the following applications:
- The first fair non-interactive multi-party protocols for coin flipping and auctions in the plain model without setup.
- Practically efficient fair multi-party protocols for coin flipping and auctions proven secure in the (auxiliary-input) random oracle model.
As a key step towards proving the security of our protocols, we introduce the notion of functional non-malleability, which protects against tampering attacks that affect a specific function of the related messages. To support an unbounded number of participants in our protocols, our time-lock puzzles satisfy functional non-malleability in the fully concurrent setting. We additionally show that standard (non-functional) non-malleability is impossible to achieve in the concurrent setting (even in the random oracle model).

2020

EUROCRYPT

Continuous Verifiable Delay Functions
📺
Abstract

We introduce the notion of a continuous verifiable delay function (cVDF): a function g which is (a) iteratively sequential---meaning that evaluating the iteration $g^{(t)}$ of g (on a random input) takes time roughly t times the time to evaluate g, even with many parallel processors, and (b) (iteratively) verifiable---the output of $g^{(t)}$ can be efficiently verified (in time that is essentially independent of t). In other words, the iterated function $g^{(t)}$ is a verifiable delay function (VDF) (Boneh et al., CRYPTO '18), having the property that intermediate steps of the computation (i.e., $g^{(t')}$ for t'<t) are publicly and continuously verifiable.
We demonstrate that cVDFs have intriguing applications: (a) they can be used to construct public randomness beacons that only require an initial random seed (and no further unpredictable sources of randomness), (b) enable outsourceable VDFs where any part of the VDF computation can be verifiably outsourced, and (c) have deep complexity-theoretic consequences: in particular, they imply the existence of depth-robust moderately-hard Nash equilibrium problem instances, i.e. instances that can be solved in polynomial time yet require a high sequential running time.
Our main result is the construction of a cVDF based on the repeated squaring assumption and the soundness of the Fiat-Shamir (FS) heuristic for constant-round proofs.
We highlight that when viewed as a (plain) VDF, our construction requires a weaker FS assumption than previous ones (earlier constructions require the FS heuristic for either super-logarithmic round proofs, or for arguments).

2020

EUROCRYPT

SPARKs: Succinct Parallelizable Arguments of Knowledge
📺
Abstract

We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument system with the following three properties for computing and proving a time T (non-deterministic) computation:
- The prover's (parallel) running time is T + polylog T. (In other words, the prover's running time is essentially T for large computation times!)
- The prover uses at most polylog T processors.
- The communication complexity and verifier complexity are both polylog T.
While the third property is standard in succinct arguments, the combination of all three is desirable as it gives a way to leverage moderate 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 results are the following, all for non-deterministic polynomial-time RAM computation. We construct (1) an (interactive) SPARK based solely on the existence of collision-resistant hash functions, and (2) a non-interactive SPARK based on any collision-resistant hash function and any SNARK with quasi-linear overhead (as satisfied by recent SNARK constructions).

2019

CRYPTO

Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge
📺
Abstract

We introduce the notion of non-uniformly sound certificates: succinct single-message (unidirectional) argument systems that satisfy a “best-possible security” against non-uniform polynomial-time attackers. In particular, no polynomial-time attacker with s bits of non-uniform advice can find significantly more than s accepting proofs for false statements. Our first result is a construction of non-uniformly sound certificates for all $$\mathbf{NP }$$ in the random oracle model, where the attacker’s advice can depend arbitrarily on the random oracle.We next show that the existence of non-uniformly sound certificates for $$\mathbf{P }$$ (and collision resistant hash functions) yields a public-coin constant-round fully concurrent zero-knowledge argument for $$\mathbf{NP } $$.

#### Coauthors

- Benjamin Chan (1)
- Naomi Ephraim (2)
- Ashrujit Ghoshal (2)
- Ilan Komargodski (6)
- Rafael Pass (6)
- Naomi Sirkin (2)