PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Algoritmy na mřížích - NMMB411
Anglický název: Algorithms on Lattices
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2023 do 2023
Semestr: zimní
E-Kredity: 4
Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: https://www2.karlin.mff.cuni.cz/~prihoda/mrize/
Garant: doc. Mgr. Pavel Růžička, Ph.D.
Třída: M Mgr. MMIB
M Mgr. MMIB > Povinné
Kategorizace předmětu: Matematika > Algebra
Anotace -
Algoritmus LLL. NP-úplnost problému hledání krátkého vektoru v mříži. Aplikace v kryptografii (NTRU, konstrukce hashovacích funkcí) a kryptoanalýze (RSA, knapsack).
Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (07.12.2018)
Podmínky zakončení předmětu -

Ústní zkouška a vypracování domácích úkolů dle instrukcí cvičícího.

Podstatná část úkolu bude implementačního charakteru.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (11.10.2022)
Literatura -

D. Stanovský, L. Barto: Počítačová algebra, Matfyzpress, Praha 2011.

C. Peikert: A Decade of Lattice Cryptography, internet, 2016. https://web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf

D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, vol. 10, pp. 233-260, 1997.

M. Ajtai. Generating hard instances of lattice problems. Quaderni di Matematica, 13:1-32, 2004.

M. Ajtai. The shortest vector problem in L_2 is NP-hard for randomized reductions (extended abstract). In STOC, pages 10-19. 1998

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (15.05.2020)
Požadavky ke zkoušce -

Ústní zkouška formou prezenční nebo distanční. Student dostane dvě otázky z probrané teorie.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (30.10.2020)
Sylabus -

Algoritmus LLL. Aplikace LLL - faktorizace celočíselných polynomů, Coppersmithův útok na RSA s malým veřejným exponentem, útok na kryptosystém využívající složitost problému batohu.

Hashovací funkce, důkazy bezpečnosti převedením na výpočetní problémy v mřížkách. Složitost problém hledání krátkého vektoru v mříži.

Kryptosystém NTRU.

Diskrétní Gaussián a LWE, homomorfní šifrování (pokud bude čas).

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (15.05.2020)
 
Univerzita Karlova | Informační systém UK