Selected Areas in Cryptology - Spring 2023

Part II

Announcements Exam Literature Course notes Old exams

This second part is taught by
Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven

The easiest ways to reach Tanja is by e-mail: There will be two guest lectures, by Jolijn Cottaar and Andreas Hülsing; references to their pages will appear with the lectures they give. The MasterMath semester starts on February 6, 2023 and the lectures for this course are on Thursdays in the mornings, hence the first session is on February 09.
The second part will be taught by Marc Stevens.
The webpage for his part is

We will cover only the very basics of quantum algorithms. I recommend you take Ronald de Wolf's Quantum Computing course (also MasterMath) for much more information. There is also a complete set of videos for that course.

Details are filled in as time permits. The official home page is here.
The lectures take place Thursday 10:00 - 12:45 in room BBG 017 at Utrecht Univerity. This covers 2 time 45 min of lecture followed by 45 min of exercises.
If you prefer to learn by watching short videos – or want videos in addition to attending the live lectures – please take a look at the course page of this course from 2022.

The goal of this course is to provide insight into cryptography secure against quantum computers (post-quantum cryptography) as well as various methods for the mathematical cryptanalysis of cryptographic systems

Cryptology deals with mathematical techniques for design and analysis of algorithms and protocols for digital security in the presence of malicious adversaries. For example, encryption and digital signatures are used to construct private and authentic communication channels, which are instrumental to secure Internet transactions.
This course in cryptology consists of two main topics:
This second part focuses on post-quantum cryptography dealing with cryptographic systems that are secure even given the existence of quantum computers. The first part focuses on cryptanalysis, the analysis of the security of cryptographic systems.
The main contenders for post-quantum systems are code-based cryptography, hash-based signatures, isogeny-based cryptography, lattice-based cryptography, and multivariate-quadratic-based signatures. These systems are examples of public-key systems and this is the main area affected by quantum computers; symmetric-key systems, such as hash functions and block and stream ciphers) are used as building blocks inside them and for the transmission of data in bulk.


The first session will take place on 30 Mar, starting at 10:00.


The exam is planned for 8 June as a written exam and the retake for 29 June. If only very few people sign up we will offer the exam as oral exams instead. The same holds for the retake. Most likely the first exam will be written and the retake replaced by oral exams.

See below for old exams to practice.


There are a few books covering topics we touch in class but there is no 'textbook' that covers everything. For further reading on the individual topics see below.
It is not necessary to purchase any book to follow the course.

Class notes

To appear during the course.

30 Mar 2023
The uncertainty about strikes of the public tranportaion sector and definitely cancelled train travel between Eindhoven and Utrecht (badgers digging under the tracks) means that we will hold this first lecture online. I was hoping to return to normal lecturing plus exercise sessions but that's not going to happen for this week. We will do flipped classroom, meaning that you watch four videos before class to learn about the topic and then we meet for 2 hours (11:00 - 12:45) on to discuss some exercises. Jolijn Cottaar will be there with me, so we have plenty of capacity to answer all your questions &ndash bring them on!

The first video recalls some background on elliptic curves.

See also the slides.
I fixed the definitions of discriminant and j-invariant.

The second video recalls the Diffie-Hellman key-exchange and presents exponentiation as a walk on graphs, We will see similar walks for isogenies soon. For the graphs that multiply by G^2, g^4, and g^8 I assume that those values are precomputed. So, you can change the DH parameters to G, g, g^2, g^4, g^8, so have those as part of the system.

See also the slides.

This video gets to isogenies and shows how one can use the isogeny graph to get a DH-like structure.

See also the slides.

This video got a bit too long, but covers all the remaining math background that we need.

See also the slides.
To give proper credit:
Tate's theorem says that two curves over a field Fq are isogenous if and only if they have the same number of points,

This is all for preparation for this week, but if you want to get some motivation and understand why we do all of this and how to turn all this knoweledge into a cryptosystem, you can take a peak at this 5th video.

See also the slides.

I will post the exercise sheet on Thurday morning. You can find the link to the room on the mastermath elo environment and on zulip.

Here is the exercise sheet for the live session

For the 3rd exercise you probably want to use some computer algebra system. I recorded a video to demonstrate how to use Sage, covering basics of finite fields and elliptic curves.

I also wrote a short ``cheat sheet'' with commands for Sage, see here

06 Apr 2023
Topics today are a general introduction to PQC and the rest of isogeny-based crypto. If you're following the lecture by using the videos from 2021, you should watch the introduction video and the fifth isogeny video.

You can find photos of the blackboards here. If you want to get an idea how Fourier transforms help in breakig RSA note that they reveal the period of a function; Shor's algorithm uses quantum computation to find the period of f(x)=a^x mod n for some a. This period is the order of a mod n, hence a divisor of φ(n). If this order is even we can compute a square-root of 1 which has at least a 50% chance of not being 1 or -1 (higher probability if there are more than 2 factors of n). For details see this video. I also have some videos explaining Grover's algorithm and Simon's algorithm. I don't have one on Kuperberg's algorithm (which is the main attack on CSIDH).

For isogeny-based crypto, I showed a non-principal ideal for p=23. I also talked a bit more about the need for consistent definitions of what directions to choose to motivate the choices of (x,y) for the positive direction and (x,iy) for the negative direction. The slides I used were from a summer school in Bangkok earlier this year and cover isogeny-based crypto after the SIKE attack. Note that the 6th isogey video is no longer up to date as SIKE/SIDH was broken i July 2022. This warning also applied to all older material, such as the Isogeny Summer school in 2021. I wrote some lecture notes for my part, see (C)SIDH – Isogeny school week 3.
There is more happening in isogeny-based crypto. We don't cover SQIsign but there is a nice explanation available by Maria Corte-Real Santos and Giacomo Pope.. The upcoming Eurocrypt conference has several isogeny talks in the schedule including 3 talks on breaking SIKE. Online attendance is 25 USD for the IACR membership, so after that you can attend other conferences online for free.

Here is the exercise sheet for today.

13 Apr 2023
Today's topic is code-based cryptography.

You can find photos of the blackboards here. The lectures covered a general introduction to coding theory, the McEliece scheme (how and why it works), some basic information set-decoding (brute force and Prange) and Berson's attack.

Here is the exercise sheet for today.

20 Apr 2023
Today I had planned cover the rest of code-based cryptography but didn't manage to cover the attack side. If you're following via the vides that means everything apart from the last two video. I will not cover the last video as I'm skipping quantum algorithms (the videos are from a year with 8 weeks of PQC) but I'll show you the better ISD algorithms in the next lecture (after Kings day). If you want to get a glimse t the quantum algorithms part, watch the vidoe on Grover and then part VI of code-based crypto after I've covered ISD.

You can find photos of the blackboards here.

Here is the exercise sheet for today. This covers the same exercises as last week but I added exercise 2 on Goppa codes.

04 May 2023
I wasn't in a shape to write on the blackboard, so I only showed slides, namely

Here is the exercise sheet for today.

11 May 2023
This lecture will be given by Andreas Hülsing;. Andreas is the expert on hash-based signatures, so you'll get a better lecture than I could possibly pull off (though I know a thing or two about them, too). Andreas used slides which you can download

Here is the exercise sheet for today.

Further reading/watching:

25 May 2023
We coverd NTRU, a scheme based on lattices, and why it works and how to avoid decryption failures. One way to attack NTRU is to define a lattice related to the public key and find the private key as a short vector in the lattice. Hence the parameters are chosen in a way to protect against this attack (based on what we know about the complexity of the computation to find the short vector and the quality of the shortness). We also looked into combinatorial attacks and meet-in-the-middle attacks searching for the private key.
We did not cover but I commented on it and recommended to watch the video on reaction attacks on NTRU.

Here is the exercise sheet for today.

You can find photos of the blackboards here.

Further reading:

Other topics
We lost a day to King's day and thus skipped some topics. I chose not to cover multivariate cryptography as lots of things have changed since I recorded the videos and some students are following remotely.
Here is a short summary what happened:

In summary, take the first video with a grain of salt, and ignore the third video.

Old exams

Here are some test exercises.

The exercises for the first exam 2015 are here. I will not make solutions available for my part but you can email me what you think is the correct solution and I'll give you feedback.

The exercises for the second exam 2015 are here.

The exercises for the first exam 2017 are here.

The exercises for the second exam 2017 are here.

The exercises for the first exam 2019 are here.