CryptoDB
Time/Space Tradeoffs for Generic Attacks on Delay Functions
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | Delay functions have the goal of being inherently slow to compute. They have been shown to be useful for generating public randomness in distributed systems in the presence of a dishonest majority of network participants; a task that is impossible to solve without such functions, due to Cleve's seminal impossibility result (STOC 1986). Currently, little is known on how to construct secure delay functions or how to analyze the security of newly proposed candidate constructions. In this work, we explore the time/space tradeoffs of generic attacks for a large class of potential delay function designs. We consider delay functions $F^T$, which are computed as \[ F^T := \underbrace{F(\dots F(F}_T(x)) \dots ), \] where $F : [N] \to [N]$ is some round function, in the presence of an adversary, who is given an advice string of some bounded size, has oracle access to $F$, and would like to compute $F^T$ on a random input $x$ using less than $T$ sequential oracle calls. We show that for both random and arbitrary functions $F$ there exist non-trivial adversaries, who successfully evaluate $F^T$ using only $T/4$ sequential calls to oracle $F$, when given a large enough advice string. We also show that there exist round functions $F$ for which the adversary cannot compute $F^T$ using less than $T/2$ sequential queries, unless they receive a large advice string or they can perform a large number of oracle queries to $F$ in parallel. |
BibTeX
@inproceedings{tcc-2025-36310,
title={Time/Space Tradeoffs for Generic Attacks on Delay Functions},
publisher={Springer-Verlag},
author={Kasper Green Larsen and Mark Simkin},
year=2025
}