conference paper yes Charlotte Hoffmann author 0f78d746-dc7d-11ea-9b2f-83f92091afe70000-0003-2027-5549 Pavel Hubáček author Chethan Kamath author Tomáš Krňák author KrPi department TCC: Theory of Cryptography 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. 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. Springer Nature2023Taipei, Taiwan eng 0302-9743 1611-3349 9783031486234 00116073370001310.1007/978-3-031-48624-1_13 14372336-362 C. Hoffmann, P. Hubáček, C. Kamath, T. Krňák, in:, 21st International Conference on Theory of Cryptography, Springer Nature, 2023, pp. 336–362. Hoffmann C, Hubáček P, Kamath C, Krňák T. (Verifiable) delay functions from Lucas sequences. In: <i>21st International Conference on Theory of Cryptography</i>. Vol 14372. Springer Nature; 2023:336-362. doi:<a href="https://doi.org/10.1007/978-3-031-48624-1_13">10.1007/978-3-031-48624-1_13</a> Hoffmann, Charlotte, et al. “(Verifiable) Delay Functions from Lucas Sequences.” <i>21st International Conference on Theory of Cryptography</i>, vol. 14372, Springer Nature, 2023, pp. 336–62, doi:<a href="https://doi.org/10.1007/978-3-031-48624-1_13">10.1007/978-3-031-48624-1_13</a>. Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, and Tomáš Krňák. “(Verifiable) Delay Functions from Lucas Sequences.” In <i>21st International Conference on Theory of Cryptography</i>, 14372:336–62. Springer Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-48624-1_13">https://doi.org/10.1007/978-3-031-48624-1_13</a>. C. Hoffmann, P. Hubáček, C. Kamath, and T. Krňák, “(Verifiable) delay functions from Lucas sequences,” in <i>21st International Conference on Theory of Cryptography</i>, Taipei, Taiwan, 2023, vol. 14372, pp. 336–362. Hoffmann, C., Hubáček, P., Kamath, C., &#38; Krňák, T. (2023). (Verifiable) delay functions from Lucas sequences. In <i>21st International Conference on Theory of Cryptography</i> (Vol. 14372, pp. 336–362). Taipei, Taiwan: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-48624-1_13">https://doi.org/10.1007/978-3-031-48624-1_13</a> Hoffmann C, Hubáček P, Kamath C, Krňák T. 2023. (Verifiable) delay functions from Lucas sequences. 21st International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 14372, 336–362. 146932023-12-17T23:00:54Z2025-09-09T14:01:23Z