Paper 2024/540

Lattice-Based Timed Cryptography

Russell W. F. Lai, Aalto University
Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy
Abstract

Timed cryptography studies primitives that retain their security only for a predetermined amount of time, such as proofs of sequential work and time-lock puzzles. This feature has proven to be useful in a large number of practical applications, e.g. randomness generation, sealed-bid auctions, and fair multi-party computation. However, the current state of affairs in timed cryptography is unsatisfactory: Virtually all efficient constructions rely on a single sequentiality assumption, namely that repeated squaring in unknown order groups cannot be parallelised. This is a single point of failure in the classical setting and is even false against quantum adversaries. In this work we put forward a new sequentiality assumption, which essentially says that a repeated application of the standard lattice-based hash function cannot be parallelised. We provide concrete evidence of the validity of this assumption and perform some initial cryptanalysis. We also propose a new template to construct proofs of sequential work, based on lattice techniques.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
DOI
https://doi.org/10.1007/978-3-031-38554-4_25
Keywords
timed cryptographyproof of sequential worklattice-based
Contact author(s)
russell lai @ aalto fi
History
2024-04-08: approved
2024-04-07: received
See all versions
Short URL
https://ia.cr/2024/540
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/540,
      author = {Russell W. F. Lai and Giulio Malavolta},
      title = {Lattice-Based Timed Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/540},
      year = {2024},
      doi = {https://doi.org/10.1007/978-3-031-38554-4_25},
      url = {https://eprint.iacr.org/2024/540}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.