Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Algorithms on Lattices - NMMB411

Title:	Algoritmy na mřížích
Guaranteed by:	Department of Algebra (32-KA)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2024
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
Additional information:	https://www2.karlin.mff.cuni.cz/~prihoda/mrize/

Guarantor:	doc. Mgr. Pavel Příhoda, Ph.D.
Teacher(s):	Om Prakash doc. Mgr. Pavel Příhoda, Ph.D.
Class:	M Mgr. MMIB M Mgr. MMIB > Povinné
Classification:	Mathematics > Algebra

Opinion survey results Examination dates WS schedule Noticeboard

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. 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

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)