bakalářská práce

Grafy složitosti a praktické experimenty v postkvantové kryptografii

Text práce 3.03 MB Příloha 10.25 MB

Autor práce: Bc. Lucia Hirnerová

Ak. rok: 2025/2026

Vedoucí: M.Sc. Sara Ricci, Ph.D.

Oponent: Ing. Petr Dzurenda, Ph.D.

Abstrakt:

Táto práca skúma matematické problémy, ktoré tvoria základ algoritmov v súčasnej postkvantovej kryptografii, a vzťahy medzi nimi. Kvantové počítanie predstavuje hrozbu pre súčasné šifrovacie systémy, a preto je téma postkvantovej kryptografie čoraz relevantnejšia. Národný inštitút pre štandardy a technológie (NIST) a Kórejská postkvantová kryptografia (KpqC) už štandardizovali niekoľko protokolov, ktoré využívajú rôzne techniky na zabezpečenie bezpečnej komunikácie. Väčšina týchto protokolov je založená na kódovaní alebo mriežke, ale zvažujú sa aj iné možnosti. Tieto problémy je dôležité preskúmať a pochopiť ich vzájomné súvislosti. Potom môžeme
predpokladať ich NP-zložitosť. Zistené vzťahy sme zmapovali v grafe a roztriedili do sekcií podľa typu problému, na ktorom sú založené. Tento graf sme spolu s SVP simulátorom následne zreplikovali v Python webovej aplikácií, aby bol prístupný bežnému používateľovi.

Klíčová slova:

Post-kvantová kryptografia, zložitosť, NP-zložitosť, kryptografia založená na mriežkach, kryptografia založená na kódovaní, kryptografia založená na hashovaní, PQC protokoly

Termín obhajoby

16.06.2026

Výsledek obhajoby

obhájeno (práce byla úspěšně obhájena)

znamkaAznamka

Klasifikace

A

Průběh obhajoby

Studentka prezentovala výsledky své práce a komise byla seznámena s posudky. Studentka obhájila bakalářskou práci a odpověděla na otázky členů komise a oponenta. Otázky oponenta: Jaké hlavní závěry přineslo vytvoření grafu vzájemných vztahů mezi problémy a jejich klasifikace podle typu základního problému? Popište metodiku vytváření grafu vzájemných vztahů mezi algoritmy a složitostními problémy. Jaké jsou hlavní důvody vzniku PQC standardů KpqC vedle standardů NIST a jaké jsou hlavní rozdíly mezi jednotlivými standardizovanými algoritmy?

Jazyk práce

angličtina

Fakulta

Ústav

Studijní program

Informační bezpečnost (BPC-IBE)

Složení komise

prof. Ing. Jiří Mekyska, Ph.D. (předseda)
Ing. Petr Dzurenda, Ph.D. (člen)
Ing. Tomáš Mácha, Ph.D. (člen)
Ing. Radim Dvořák (člen)
Ing. Ondřej Dohnal (člen)
JUDr. Pavel Loutocký, BA (Hons), Ph.D. (místopředseda)
Ing. Viet Anh Phan (člen)

Posudek vedoucího
M.Sc. Sara Ricci, Ph.D.

Práce se zaměřuje na analýzu vztahů mezi standardizovanými postkvantovými kryptografickými schématy a jejich základními předpoklady výpočetní obtížnosti napříč různými rodinami postkvantové kryptografie. Studentka vytvořila graf závislostí propojující algoritmy postkvantové kryptografie, standardy a problémy výpočetní obtížnosti, což umožnilo strukturální analýzu vzájemných vazeb v ekosystému postkvantové kryptografie. Dále studentka vyvinula interaktivní aplikaci pro vizuální prozkoumávání grafu závislostí a implementovala demonstrační řešič problému SVP, který ukazuje útoky na malé instance mřížových problémů. Studentka splnila zadání. Rozsah práce odpovídá očekávanému rozsahu bakalářské práce. Zpracování vyžadovalo studium a propojení teoretických konceptů z několika výzkumných oblastí. Za zmínku stojí, že práce vedla ke vzniku dvou publikací, jedna byla přijata na konferenci EEICT a druhá byla přijata na workshopu ARES-SP2I mezinárodní konference. Text práce je na dobré úrovni a obsahuje pouze drobné formální nedostatky. Oceňuji také, že práce je napsána v anglickém jazyce. Využití odborné literatury je na velmi dobré úrovni. Studentka byla po celý semestr aktivní a svou práci pravidelně konzultovala. Velmi oceňuji její iniciativu a úsilí věnované jak teoretické, tak praktické části práce, které jsou na velmi dobré úrovni. Celkově hodnotím práci i dosažené výsledky jako velmi kvalitní a doporučuji ji k obhajobě s hodnocením A / 92 bodů. Výsledný počet bodů navržený vedoucím: 92

Známka navržená vedoucím: A

Posudek oponenta
Ing. Petr Dzurenda, Ph.D.

Prezentační úroveň práce i její rozsah jsou na dobré úrovni. Některé věty jsou však formulovány nejasně a mohou působit zmateně. Studentka také volně překládá některé anglické termíny, například „technika viacstranného výpočtu v hlave (angl. MPC in the Head)“, což není zcela správné. Rozšířený abstrakt navíc není psán v trpném rodě. Z formálního hlediska práce obsahuje několik nedostatků. Některé zkratky nejsou definovány při svém prvním výskytu, některé obrázky mají nedostatečné rozlišení a popisky tabulek jsou uváděny pod tabulkami. Práce s odbornou literaturou je na dobré úrovni, avšak některé kapitoly či formální definice postrádají odkazy na použité zdroje, případně není zcela jasné, ke které části textu se daná reference vztahuje. Po odborné stránce je práce na dobré úrovni, avšak praktická část působí z velké části velmi teoreticky, vzhledem k tomu, že se jedná o analýzu vztahů mezi PQC protokoly. V této části jsou popsány výsledné grafy vztahů mezi PQC algoritmy a složitostními problémy, avšak metodologie jejich vytváření není dostatečně popsána. Stejně tak postrádám rozsáhlejší diskusi dosažených výsledků a jejich významu. Výsledné grafy byly dále implementovány do dynamické webové aplikace PQC Explorer. Kladně hodnotím také fakt, že studentka publikovala své výsledky na dvou vědeckých konferencích (EEICT a ARES). Celkově hodnotím práci známkou B, 85 bodů. Otázky k obhajobě:
  1. Jaké hlavní závěry přineslo vytvoření grafu vzájemných vztahů mezi problémy a jejich klasifikace podle typu základního problému?
  2. Popište metodiku vytváření grafu vzájemných vztahů mezi algoritmy a složitostními problémy.
  3. Jaké jsou hlavní důvody vzniku PQC standardů KpqC vedle standardů NIST a jaké jsou hlavní rozdíly mezi jednotlivými standardizovanými algoritmy?
Výsledný počet bodů navržený oponentem: 85

Známka navržená oponentem: B

Odpovědnost: Mgr. et Mgr. Hana Odstrčilová