Paper 2025/141

Space-Lock Puzzles and Verifiable Space-Hard Functions from Root-Finding in Sparse Polynomials

Nico Döttling, Helmholtz Center for Information Security
Jesko Dujmovic, Helmholtz Center for Information Security, Saarland University
Antoine Joux, Helmholtz Center for Information Security
Abstract

Timed cryptography has initiated a paradigm shift in the design of cryptographic protocols: Using timed cryptography we can realize tasks fairly, which is provably out of range of standard cryptographic concepts. To a certain degree, the success of timed cryptography is rooted in the existence of efficient protocols based on the sequential squaring assumption. In this work, we consider space analogues of timed cryptographic primitives, which we refer to as space-hard primitives. Roughly speaking, these notions require honest protocol parties to invest a certain amount of space and provide security against space constrained adversaries. While inefficient generic constructions of timed-primitives from strong assumptions such as indistinguishability obfuscation can be adapted to the space-hard setting, we currently lack concrete and versatile algebraically structured assumptions for space-hard cryptography. In this work, we initiate the study of space-hard primitives from concrete algebraic assumptions relating to the problem of root-finding of sparse polynomials. Our motivation to study this problem is a candidate construction of VDFs by Boneh et al. (CRYPTO 2018) which are based on the hardness of inverting permutation polynomials. Somewhat anticlimactically, our first contribution is a full break of this candidate. However, we then revise this hardness assumption by dropping the permutation requirement and considering arbitrary sparse high degree polynomials. We argue that this type of assumption is much better suited for space-hardness rather than timed cryptography. We then proceed to construct both space-lock puzzles and verifiable space-hard functions from this assumption.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2024
DOI
10.1007/978-3-031-78020-2_15
Keywords
Spack-Lock PuzzleVerifiable Space-Hard FunctionSLPVSHFSparse PolynomialsRoot Finding
Contact author(s)
doettling @ cispa de
jesko dujmovic @ cispa de
joux @ cispa de
History
2025-01-31: approved
2025-01-29: received
See all versions
Short URL
https://ia.cr/2025/141
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/141,
      author = {Nico Döttling and Jesko Dujmovic and Antoine Joux},
      title = {Space-Lock Puzzles and Verifiable Space-Hard Functions from Root-Finding in Sparse Polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/141},
      year = {2025},
      doi = {10.1007/978-3-031-78020-2_15},
      url = {https://eprint.iacr.org/2025/141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.