Time-Lock Puzzles with Preprocessing: an Instantiation from Average-Case Hardness Assumptions on Graphs and Lattices

Abstract

Sequential functions are computable functions that admit no asymptotic speedup, even in the presence of massive parallel computational resources. Although extensively studied within complexity theory, they have received less attention in cryptographic applications. This situation changed with the recent introduction of verifiable delay functions, which found practical use in decentralized cryptographic payment systems and renewed the practical interest in sequential functions. In particular, the closely-related notion of time-lock puzzles (TLP), in which a secret can be recovered only after a prescribed amount of sequential computation, have re-emerged as a fundamental primitive. Post-quantum secure TLPs based solely on standard cryptographic assumptions are unknown. A relaxed variant – TLPs with preprocessing, which allow for an expensive setup phase – can be obtained using randomized encodings and the existence of worst-case non-parallelizing languages (NPL). In this work, we introduce a new post-quantum secure TLP with preprocessing. Our construction combines (i) cryptographic evaluation over encrypted data with (ii) a well-studied averagecase hardness assumption in graph theory: refuting cliques in Erdős–Rényi graphs using (resolution-based) proof systems. Sequentiality is proven by relating this task to the problem of deciding, in quasipolynomial time, whether an Erdős–Rényi graph contains a planted clique of appropriate size. Building on a result of Atserias, Bonacina, de Rezende, Lauria, Nordström, and Razborov, which shows that clique refutation requires at least $n^{\Omega(k)}$ steps – where n denotes the number of vertices and k is related to the clique size – we identify clique refutation as a natural candidate for sequential computation. Moreover, such refutation proofs can be equivalently represented as read-once branching programs of comparable depth. Leveraging this correspondence, we construct a time-lock puzzle in which the clique refutation instance is not revealed in the clear, but instead encrypted using an attribute-based encryption scheme. This approach securely encodes the graph structure while allowing holders of appropriate attribute-keys to evaluate the branching program. To ensure efficiency, we require attribute-based encryption schemes whose parameter growth is logarithmic in the size of the evaluated function; existing constructions are known to satisfy this requirement.