CryptoDB
On Sequential Functions and FineGrained Cryptography
Authors: 


Download: 

Presentation:  Slides 
Conference:  CRYPTO 2024 
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 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(k, x) = g^k (x) 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 functionessentially a sequential function that can be computed in sequence to get the same output in two different waysand show that it implies finegrained key exchange. 
BibTeX
@inproceedings{crypto202434209, title={On Sequential Functions and FineGrained Cryptography}, publisher={SpringerVerlag}, doi={10.1007/9783031683886_14}, author={Jiaxin Guan and Hart Montgomery}, year=2024 }