Paper 2023/1404

(Verifiable) Delay Functions from Lucas Sequences

Charlotte Hoffmann, Institute of Science and Technology Austria
Pavel Hubáček, Czech Academy of Sciences, Charles University
Chethan Kamath, Tel Aviv University
Tomáš Krňák, Charles University

Lucas sequences are constant-recursive integer sequences with a long history of applications in cryptography, both in the design of cryptographic schemes and cryptanalysis. In this work, we study the sequential hardness of computing Lucas sequences over an RSA modulus. First, we show that modular Lucas sequences are at least as sequentially hard as the classical delay function given by iterated modular squaring proposed by Rivest, Shamir, and Wagner (MIT Tech. Rep. 1996) in the context of time-lock puzzles. Moreover, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring. In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring. Moreover, we note that modular Lucas sequences also yield a time-lock puzzle, similar to the classical construction of Rivest, Shamir and Wagner. Second, we demonstrate the feasibility of constructing practically-efficient verifiable delay functions based on the sequential hardness of modular Lucas sequences. Our construction builds on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connection between the problem of computing modular Lucas sequences and exponentiation in an appropriate extension field.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2023
Delay functionsVerifiable delay functionsLucas sequences
Contact author(s)
charlotte hoffmann @ ist ac at
hubacek @ iuuk mff cuni cz
ckamath @ protonmail com
tomas @ krnak cz
2023-09-24: approved
2023-09-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charlotte Hoffmann and Pavel Hubáček and Chethan Kamath and Tomáš Krňák},
      title = {(Verifiable) Delay Functions from Lucas Sequences},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1404},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.