Verifiable Delay Functions z Lucasových posloupností

• Název práce v češtině: Verifiable Delay Functions z Lucasových posloupností
• Název v anglickém jazyce: Verifiable Delay Functions from Lucas Sequences
• Klíčová slova: Lucasovy posloupnosti|ověřitelné zpožďovací funkce|modulární mocnění|silná prvočísla
• Klíčová slova anglicky: Lucas sequences|verifiable delay function|modular squaring|strong primes
• Akademický rok vypsání: 2019/2020
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: Mgr. Pavel Hubáček, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 22.09.2020
• Datum zadání: 22.09.2020
• Datum potvrzení stud. oddělením: 10.05.2022
• Datum a čas obhajoby: 09.06.2022 09:00
• Datum odevzdání elektronické podoby: 05.05.2022
• Datum odevzdání tištěné podoby: 09.05.2022
• Datum proběhlé obhajoby: 09.06.2022
• Oponenti: doc. Mgr. Pavel Příhoda, Ph.D.

Zásady pro vypracování

Student nastuduje konstrukce Verifiable Delay Functions (VDFs) založené na sekvencialitě iterovaného modulárního mocnění na druhou [1,2,3]. Cílem práce je zobecnění technik z literatury pro konstrukce VDFs založených na sekvencialitě modulárních Lucasových posloupností a studium jejich vlastností.

Seznam odborné literatury

[1] Krzysztof Pietrzak. "Simple verifiable delay functions." In 10th Innovations in Theoretical Computer Science conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[2] Benjamin Wesolowski. "Efficient verifiable delay functions." Journal of Cryptology (2020): 1-35.
[3] Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. "Verifiable delay functions." In Annual international cryptology conference (CRYPTO 2018), pp. 757-788. Springer, Cham, 2018.

Předběžná náplň práce

Lucasovy posloupnosti jsou konstantní rekurzivní celočíselné posloupnosti s dlouhou historií aplikací v kryptografii - používané jak pro návrh kryptografických schémat, tak při kryptoanalýze. V této práci představujeme ověřitelné zpožďovací funkce založené na sekvenční náročnosti výpočtu Lucasových posloupností v RSA grupě.

Zaprvé ukážeme, že modulární Lucasovy poslopnosti jsou alespoň tak sekvenční, jako jsou klasické zpožďovací funkce založené na iterovaném modulárním mocnění představené Rivestem, Shamirem, and Wagnerem v kontextu tzv. time-lock puzzles. Navíc nenacházíme žádnou očividnou opačnou redukci, což nás přivádí k domněnce, že počítání modulárních Lucasových poslopností je ostře složitější než modulární iterované mocnění. Jinými slovy, námi kostruovaná zpoždovací funkce si zachová svoji sekvenčnost i v případě nalezení nového efektivnějšího algoritmu pro modulární iterováné mocnění.

Zadruhé představíme praktickou konstrukci ověřitelné zpožďovací funkce založené na modulárních Lucasových posloupnostech. Naše konstrukce vychází z nedávné práce Pietrzaka (ITCS 2019) a využívá souvislost mezi problémem výpočtu modulárních Lucasových posloupností a mocněním v příslušném tělesovém rozšíření.

Předběžná náplň práce v anglickém jazyce

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 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.