Algoritmy na mřížích - NMMB411

• Anglický název: Algorithms on Lattices
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• 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í
• Další informace: https://www2.karlin.mff.cuni.cz/~prihoda/mrize/
• Garant: doc. Mgr. Pavel Příhoda, Ph.D.
• Vyučující: Om Prakash; doc. Mgr. Pavel Příhoda, Ph.D.
• Třída: M Mgr. MMIB; M Mgr. MMIB > Povinné
• Kategorizace předmětu: Matematika > Algebra

Anotace

čeština

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)

angličtina

LLL algoritm and its application: Short vector problem is NP-hard, cryptosystem NTRU., constructions of hash functions, Coppersmith's attack on RSA, knapsack-based cryptosystems.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (11.12.2018)

Podmínky zakončení předmětu

čeština

Ú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)

angličtina

Oral exam and a homework posed at problem sessions. The essential

part of the homework is of implementational character.

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

Literatura

čeština

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

čeština

Ú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)

angličtina

Oral exams consists of two questions. It is possible to do it either in present or distant form.

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

Sylabus

čeština

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)

angličtina

LLL algoritm and its applications - factorization of polynomials over Z, Coppersmith's attack on RSA with small public exponent, cryptanalysis of some knapsack-based cryptosystems.

Hash functions, Ajtai's worst case to average case reduction and its application to security proving. Short vector problem is NP-hard.

Cryptosystem NTRU.

Dicrete Gaussians and LWE, fully homomorphic encryption (optional)

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (15.05.2020)