SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Algorithms on Lattices - NMMB411
Title: Algoritmy na mřížích
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023 to 2023
Semester: winter
E-Credits: 4
Hours per week, examination: winter s.:2/1, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information:
Guarantor: doc. Mgr. Pavel Růžička, Ph.D.
Class: M Mgr. MMIB
M Mgr. MMIB > Povinné
Classification: Mathematics > Algebra
Annotation -
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.
Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (11.12.2018)
Course completion requirements -

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

part of the homework is of implementational character.

Last update: Příhoda Pavel, doc. Mgr., Ph.D. (11.10.2022)
Literature -

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

C. Peikert: A Decade of Lattice Cryptography, internet, 2016.

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

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (15.05.2020)
Requirements to the exam -

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

Last update: Příhoda Pavel, doc. Mgr., Ph.D. (30.10.2020)
Syllabus -

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)

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (15.05.2020)
Charles University | Information system of Charles University |