Description:

Students will gain deeper knowledge of algebraic procedures solving the most important mathematical problems concerning the security of ciphers. In particular, the course focuses on the problem of solving a system of polynomial equations over a finite field, the problem of factorization of large numbers and the problem of discrete logarithm. The problem of factorization will also be solved on elliptic curves. Students will further become familiar with modern encryption systems based on lattices.

Contents:

1. Groups - basic properties
2. Factor groups, cyclic groups
3. Ideals in rings
4. Factor rings
5. Polynomial rings
6. Extension of finite fields
7. Solving algebraic equations over finite bodies: relinearization, XL and XSL algorithms
8. Gröbner's bases, Buchberger's algorithm
9. Factorization: Pollard's rho method, p-1 method, Fermat factorization.
10. Factorization: network methods.
11. Discrete logarithm: Pohlig-Hellman algorithm, Babystep-giantstep algorithm, Pollard's rho method.
12. Discrete logarithm: Index calculus.
13. Elliptic curves - basic properties
14. Elliptic curves over real numbers and Galois fields.
15. ECDLP, factorization using elliptic curves.
16. Menezes-Okamoto-Vanston algorithm
17. Latice-based cryptography, GGH encryption system.
18. Orthogonalization and reduction, NTRU encryption system.

Seminar contents:

Examples of various mathematical structures,, and algorithms will be discussed.

Recommended literature:

1. Katz, J. - Lindell, Y. : Introduction to modern cryptography. CRC press, 2014. ISBN 978-1466570269.
2. Hoffstein, J. - Pipher, J. - Silverman, J. H. : An Introduction to Mathematical Cryptography. Springer, 2008. ISBN 978-1441926746.
3. Lidl, R. - Niederreiter, H. : Finite Fields. Cambridge University Press, 2008. ISBN 978-0521065672.
4. Menezes, A. J. - van Oorschot, P. C. - Vanstone, S. A. : Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7.

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar