|
|
Security of Trapdoor Permutations under Preimage Leakage
Sedláček, Petr ; Hubáček, Pavel (vedoucí práce) ; Göloglu, Faruk (oponent)
Tato diplomová práce se zabývá jednosměrnými permutacemi s padacími dvířky odol- nými vůči útočníkům s částečnou znalostí předobrazu (PLR-TDPs) a jejich aplikacemi pro důkazy replikovaného uložení dat a nekomprimovatelná kódování. Samotná práce je roz- dělena do tří kapitol, které popisují jednosměrné permutace s padacími dvířky, formální definici PLR-TDPs a analýzu bezpečnosti PLR-TDPs. V první kapitole připomínáme definici jednosměrných permutací s padacími dvířky (TDPs) a ukazujeme jejich vlastnosti a aplikace pro důkazy replikovaného uložení dat. Naše výsledky jsou popsány ve druhé a třetí kapitole. Ve druhé kapitole formálně definu- jeme PLR-TDPs a s jejich pomocí konstruujeme jednoduché nekomprimovatelné kódo- vání v modelu náhodného orákula. Ve třetí kapitole studujeme, zda PLR-TDPs existují. V idealizovaném modelu náhodných TDPs ukazujeme jejich odolnost vůči útočníkům s částečnou znalostí předobrazu. Jako první tak předkládáme částečné formální opodstat- nění domněnky, že i praktické TDPs, jako například RSA či Rabinova permutace, jsou odolné vůči útočníkům s částečnou znalostí předobrazu.
|
|
|
Analýza blockchainu používaného pro Bitcoin
Surma, David ; Hartman, David (vedoucí práce) ; Hubáček, Pavel (oponent)
Tato práce se zabývá analýzou blockchainu používaného pro Bitcoin. Blockchain je distribuovaná databáze všech uskutečněných transakcí s touto kryptoměnou. Její veřejná dostupnost představuje možnost zkoumání přesunů prostředků mezi veškerými uživateli. Ti však v transakcích vystupují pod anonymními adresami, jejichž počet je prakticky ne- omezený. Hlavním cílem naší práce je nalézt klastrování adres odpovídající jejich přísluš- nosti k reálným uživatelům. V práci navrhujeme nové heuristiky, které lze při klastrování využít. Hlavním přínosem je metoda, která využívá vlastnosti velmi rychle po sobě vytvo- řených transakcí. Dále analyzujeme problém vzniku superklastru obsahujícího neúměrně velkou část adres a navrhujeme způsob, jakým lze klastr vhodně rozdělit. 1
|
|
|
Multivariate polynomial commitment schemes
Bžatková, Kateřina ; Hubáček, Pavel (vedoucí práce) ; Žemlička, Jan (oponent)
Tato diplomová práce se zabývá schématy polynomiálních závazků, což jsou schémata umožňující vytvářet polynomiální závazky a následně pomocí spuštění navrženého protokolu důvěryhodně vyhodnocovat polynomy v požadovaných bodech. Jako náš hlavní výsledek navrhujeme nové schéma, které umožňuje pracovat s polynomy více proměnných a efektivně dokazovat korektnost vyhodnocení polynomu ve více bodech. Vytvoření našeho schématu vedlo k využití poznatků z teorie algebry, především zabývající se vlastnostmi ideálů v polynomiálních okruzích a grupovými vlastnostmi. V porovnání s jiným schématem, které je též navrženo pro polynomy více proměnných, se nám podařilo zlepšit komunikační složitost během protokolu.
|
|
|
On the Complexity of Search Problems with a Unique Solution
Králová, Veronika ; Hubáček, Pavel (vedoucí práce) ; Brzuska, Christopher (oponent) ; Bitansky, Nir (oponent)
Meggido a Papadimitriou [Theor. Comput. Sci., 1991] definovali třídu TFNP, která je tvořena vyhledávacími problémy, pro které řešení vždy existuje a lze je testovat v polynomiálním čase. V této práci studujeme, zdali lze různé problémy redukovat na problémy z TFNP. Problémy, jejichž redukovatelnost do TFNP studujeme, mají společnou vlastnost, že všechny jejich instance mají jednoznačné řešení (pokud nějaké řešení vůbec existuje). V první části této práce studujeme problém zvaný ARRIVAL, který se poprvé ob- jevil v článku Dohrau, Gärtner, Kohler, Matoušek a Welzl [A Journey Through Discrete Mathemathics: A tribute to Jiří Matoušek, 2017]. ARRIVAL je následující rozhodovací problém: Máme dán orientovaný graf, po kterém se pohybuje vláček podle předepsaných pravidel, a ptáme se, jestli vláček někdy dojede do předem určeného vrcholu. Prvně vylepšíme výsledek Dohrau a kol., kteří ukázali, že tento problém je v NP ∩ coNP. Ukážeme, že existuje jednoznačný certifikát pro náležení do jazyka a tedy dokážeme, že ARRIVAL je v UP ∩ coUP. Dále budeme studovat vyhledávací variantu problému ARRIVAL, při které máme určit kolikrát vláček projel po každé hraně grafu. Jak ukázal Karthik C. S. [Inf. Process. Lett., 2017], vyhledávací varianta ARRIVAL je ve třídě PLS. My tento výsledek vylepšíme a ukážeme redukci z problému...
|
|
|
Verifiable Delay Functions z Lucasových posloupností
Krňák, Tomáš ; Hubáček, Pavel (vedoucí práce) ; Příhoda, Pavel (oponent)
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 ne- nachá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 Lu- casových posloupností a mocněním v příslušném tělesovém rozšíření. 1
|
|
| |
|
|
Gröbnerovy báze v kryptografii
Hubáček, Pavel ; Stanovský, David (vedoucí práce) ; Šťovíček, Jan (oponent)
Předložené práce studuje využití Grobnerových bází v kryptografii, a to speciálně při kryptoanalýze blokový šifer. Nejprve seznamujeme se základními pojmy teorie Grobnerových bází a metodou pro jejich nalezení, kterou je Buchbergerův algoritmus. Je vysvětlen princip řešení soustav polynomiálních rovnic pomocí vhodných Grobrenových bází. Následně je věnována pozornost moderním algoritmům pro nalezení Grobnerovy báze, jež Buchbergerův algoritmus vylepšují. V poslední části jsou shrnuty dosavadní výsledky dosažené v kryptografii pomocí metod založených na Grobnerových bázích a je představen pojem algebraické kryptoanalýzy. Ta převádí problém prolomení kryptosystému na problém nalezení řešení soustavy polynomiálních rovnic nad konečným tělesem. Na příkladech je vysvětleno jak konstruovat soustavy polynomů více proměnných popisující blokové šifry a jsou prezentovány výsledky praktických pokusů s takovými soustavami.
|
|
|
Effectivity and Limitations of Homomorphic Secret Sharing Schemes
Jančová, Ľubica ; Hubáček, Pavel (vedoucí práce) ; Holub, Štěpán (oponent)
Táto práca sa zameriava na konštrukcie homomorfných schém na zdieľanie tajomstva (HSS), o ktorých nie je známe, že by implikovali plne homomorfné šifrovanie. Efektivita týchto konštrukcií závisí na zložitosti problému distribuovaného diskrétneho logaritmu (DDLog) v odpovedajúcich grupách. Tento problém detailne popisujeme, zameriava- júc sa na možnosť využitia predspracovania v grupách prvočíselného rádu a na odvo- denie horných medzí pre pravdepodobnosť úspechu pre DDLog problém s predspracov- aním v generickom grupovom modeli. Ďalej predstavujeme novú konštrukciu HSS. Našu konštrukciu zakladáme na Joye-Libert šifrovacej schéme, ktorú prispôsobíme tak, aby podporovala efektívny protokol pre distribuovaný diskrétny logaritmus. Naša modifiko- vaná Joye-Libertova schéma vyžaduje novú množinu bezpečnostných predpokladov, ktoré uvedieme, dokazujúc IND-CPA bezpečnosť našej schémy za týchto predpokladov. 1
|
|
|
Kvantové programovací jazyky
Čížková, Josefína ; Mareš, Martin (vedoucí práce) ; Hubáček, Pavel (oponent)
Kvantové programovací jazyky Abstrakt Popisujeme základní principy a vlastnosti kvantového systému a jeho následné využití pro Shorův algoritmus pro faktorizaci celých čísel, který na kvantovém počítači slibuje lepší časovou složitost. Následně je zahrnut popis Shorova algoritmu v programovacím jazyce Q#, který umožňuje simulovat kvantový algoritmus na klasickém počítači. Nakonec je poukázáno na další dva kvantové programovací jazyky, a to na Qiskit a QCL, a jejich využití pro faktorizaci.
|
|
|
Limitations of Incompressible Encodings
Sedláček, Petr ; Hubáček, Pavel (vedoucí práce) ; Mareš, Martin (oponent)
Tato práce se zabývá limitacemi nekomprimovatelných kódování s nepodmíněnou bezpečností. Představujeme trhliny v existujícím důkazu nemožnosti konstrukce nekomprimovatelných kódování bez výpočetních omezení na útočníka. Naším hlavním přínosem je nový kompletní důkaz tohoto negativního výsledku. V první části práce představujeme základy teorie nekomprimovatelných kódování včetně nutných definic. Dále prezentujeme nedostatky v původním důkazu a konstruujeme protipříklady. Zbývající část práce tvoří důkaz nemožnosti existence netriviálních nekomprimova- telných kódování bez výpočetních omezení kladených na útočníka. Ten budujeme v několika krocích, kde v každém kroku zahrnujeme více kódování. Na konci práce představujeme útočníka, který je schopný prolomit libovolné netriviální nekompri- movatelné kódování. 1
|
host ::
RSS.