TMA4160 Cryptography - Fall 2016

Lecturer: Kristian Gjøsteen
Assistant: Herman Galteland
Schedule Room
Lectures: Tuesday 12.15-14.00 R60
Friday 12.15-14.00 B2 (map) (except for October 14 which will be in B22) MA23
Exercises: Wednesday 13.15-14.00 Usually in K26, sometimes in Nullrommet (380A)
Visiting hours: Tuesday 14.15-15.00 848 in SBII
Exam: December 7

What you should know before taking the course

You should be familiar with basic abstract algebra such as groups, rings and fields.

It is helpful, but not required, to know something about computational complexity and the analysis of algorithms. Using a computer algebra system (or equivalent) is required for some of the exercises. Previous experience with computer algebra systems is helpful, but not required.

Reference group


Course material

Lecture notes:

  • These notes follow the lectures fairly closely, but will be updated throughout the course.

Main book:


You should be able to get by with just the lecture notes (and possibly the supplements), but many of you will find Stinson useful.

The curriculum is defined to be the material covered by the lecture notes, the lectures (except lattice-based cryptography) and the exercises.


3/1: The results are in. Statistics: A - 11, B - 12, C - 8, D - 6, E - 3, F - 4. The problem set was perhaps too easy, but some problems were obviously unexpected and unfamiliar for those who had skipped certain exercises.

  • Obviously, some people made calculating mistakes in Problem 1 or 2a.
  • Almost everyone understood elliptic curve arithmetic in 2a, which is good. Some people forgot to explain why the curve was cyclic, which is bad.
  • For 5a, the key point is not that the sequences are the same, but that they stop at the same point.
  • For 5b, many forgot to mention that the exponent arithmetic should happen modulo the group order. This is important, since otherwise exponents can become very big, which means that arithmetic with these numbers becomes expensive.
  • For 5c, very few realised that you were also supposed to explain how to find the relevant triples. While many covered this in 5d, very few covered it in sufficient detail. This is important, since the naive method requires m^2 time, while a sorting-based approach will be much faster. In some situations, this may make the difference between feasible and infeasible.
  • As expected, 5e was difficult.

8/12: The exam with a solution sketch is now available.

2016-12-03, Kristian Gjøsteen