Papercraft: Lattice-based Verifiable Delay Function Implemented

Michał Osadnik; Darya Kaviani; Valerio Cini; Russell W. F. Lai; Giulio Malavolta

Paper 2025/879

Papercraft: Lattice-based Verifiable Delay Function Implemented

Michał Osadnik

, Aalto University, Finland

Darya Kaviani

, UC Berkeley, United States

Valerio Cini, Bocconi University, Italy

Russell W. F. Lai

, Aalto University, Finland

Giulio Malavolta

, Bocconi University, Italy

Abstract

A verifiable delay function (VDF) requires a specified number of sequential steps to compute, yet the validity of its output can be verified efficiently, much faster than recomputing the function from scratch. VDFs are a versatile cryptographic tool, with many industrial applications, such as blockchain consensus protocols, lotteries and verifiable randomness. Unfortunately, without exceptions, all known practical VDF constructions are broken by quantum algorithms. In this work, we investigate the practicality of VDFs with plausible post-quantum security. We propose Papercraft, a working implementation of a VDF based entirely on lattice techniques and thus plausibly post-quantum secure. Our VDF is based on new observations on lattice-based succinct argument systems with many low-level optimisations, yielding the first lattice-based VDF that is implementable on today's hardware. As an example, our Papercraft implementation can verify a computation of almost 6 minutes in just 7 seconds. Overall, our work demonstrates that lattice-based VDFs are not just a theoretical construct, paving the way for their practical deployment.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. S&P 2025
DOI: 10.1109/SP61157.2025.00159
Keywords: VDF time-based cryptography lattice-bases cryptography SNARK
Contact author(s): michal osadnik @ aalto fi
daryakaviani @ berkeley edu
valerio cini @ unibocconi it
russell lai @ aalto fi
giulio malavolta @ unibocconi it
History: 2025-05-19: approved; 2025-05-17: received; See all versions
Short URL: https://ia.cr/2025/879
License: CC BY

BibTeX

@misc{cryptoeprint:2025/879,
      author = {Michał Osadnik and Darya Kaviani and Valerio Cini and Russell W. F. Lai and Giulio Malavolta},
      title = {Papercraft: Lattice-based Verifiable Delay Function Implemented},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/879},
      year = {2025},
      doi = {10.1109/SP61157.2025.00159},
      url = {https://eprint.iacr.org/2025/879}
}