(Verifiable) delay functions from Lucas sequences

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F23%3A00579718" target="_blank" >RIV/67985840:_____/23:00579718 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-031-48624-1_13" target="_blank" >https://doi.org/10.1007/978-3-031-48624-1_13</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-48624-1_13" target="_blank" >10.1007/978-3-031-48624-1_13</a>

Result language

angličtina

Original language name

(Verifiable) delay functions from Lucas sequences

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Theory of Cryptography: 21st International Conference, TCC 2023, Taipei, Taiwan, November 29–December 2, 2023, Proceedings, Part IV

ISBN

978-3-031-48623-4

ISSN

0302-9743

e-ISSN

—

Number of pages

27

Pages from-to

336-362

Publisher name

Springer

Place of publication

Cham

Event location

Taipei

Event date

Nov 29, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001160733700013