Paper 2024/1050
On Sequential Functions and FineGrained Cryptography
Abstract
A sequential function is, informally speaking, a function $f$ for which a massively parallel adversary cannot compute "substantially" faster than an honest user with limited parallel computation power. Sequential functions form the backbone of many primitives that are extensively used in blockchains such as verifiable delay functions (VDFs) and timelock puzzles. Despite this widespread practical use, there has been little work studying the complexity or theory of sequential functions. Our main result is a blackbox oracle separation between sequential functions and oneway functions: in particular, we show the existence of an oracle $\mathcal{O}$ that implies a sequential function but not a oneway function. This seems surprising since sequential functions are typically constructed from very strong assumptions that imply oneway functions and also since timelock puzzles are known to imply oneway functions (Bitansky et al., ITCS '16). We continue our exploration of the theory of sequential functions. We show that, informally speaking, the decisional, worstcase variant of a certain class of sequential function called a continuous iterative sequential function (CISF) is PSPACEcomplete. A CISF is, in a nutshell, a sequential function $f$ that can be written in the form $f \left(k, x \right) = g^{k} \left(x \right)$ for some function $g$ where $k$ is an input determining the number of "rounds" the function is evaluated. We then show that more general forms of sequential functions are not contained in PSPACE relative to a random oracle. Given these results, we then ask if it is possible to build any interesting cryptographic primitives from sequential functions that are not oneway. It turns out that even if we assume just the existence of a CISF that is not oneway, we can build certain "finegrained" cryptographic primitives where security is defined similarly to traditional primitives with the exception that it is only guaranteed for some (generally polynomial) amount of time. In particular, we show how to build "finegrained" symmetric key encryption and "finegrained" MACs from a CISF. We also show how to build finegrained publickey encryption from a VDF with a few extra natural properties and indistinguishability obfucsation (iO) for null circuits. We do not assume oneway functions. Finally, we define a primitive that we call a commutative sequential function  essentially a sequential function that can be computed in sequence to get the same output in two different ways  and show that it implies finegrained key exchange.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2024
 Keywords
 Sequential FunctionVerifiable Delay FunctionIdealized ModelLower BoundBlockchainBlackBox Separation
 Contact author(s)

jiaxin @ guan io
hart montgomery @ gmail com  History
 20240630: approved
 20240628: received
 See all versions
 Short URL
 https://ia.cr/2024/1050
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1050, author = {Jiaxin Guan and Hart Montgomery}, title = {On Sequential Functions and FineGrained Cryptography}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1050}, year = {2024}, url = {https://eprint.iacr.org/2024/1050} }