Paper 2024/540
Lattice-Based Timed Cryptography
, Aalto University, Bocconi University, Max Planck Institute for Security and PrivacyAbstract
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
-
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},
note = {\url{https://eprint.iacr.org/2024/540}},
url = {https://eprint.iacr.org/2024/540}
}
