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
Netherlands

The easiest ways to reach Tanja is by e-mail: tanja@hyperelliptic.org 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 https://homepages.cwi.nl/~stevens/mastermath/2023/.

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.

Goal
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

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

Announcements

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

Examination

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.

Literature

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.

• For general background on cryptography the Handbook of Applied Cryptography by Menezes, van Oorshot, and Vanstone has everything you wanted to know (and more); you can download the chapters freely from the web.
• A more modern take on cryptography is Boneh and Shoup's A Graduate Course in Applied Cryptography.
• Steven Galbraith gives a nice overview of public-key crypto and coves some post-quantum schemes in Mathematics of Public Key Cryptography
• Lots of references on post-quantum cryptography are collected at pqcrypto.org.
• A (only slightly outdated) reference on post-quantum crypto is Post-Quantum Cryptography by Bernstein, Buchmann and Dahmen as editors. Some sample pages are available on the Springer page and the authors of the chapters are free to host their chapters on their personal webpages. You should also have access to this book via the online library of your university.

Class notes

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 wonder.me 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 F_q 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 wonder.me 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 https://www.sagemath.org/, 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

• CBC lecture 5 on information-set decoding attacks on code-based cryptography,
• lattice lecture 1 introducing lattices incl. LLL,
• Thijs Laarhoven's nice slides lec1.pdf (for the visualization of LLL and the GGH encryption and signature systems), and
• lattice lecture 2 showing the attack landscape on lattices in general and enumeration as a way to instantiate the SVP in the block-size beta blocks in BKZ in particular.

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

• in ppts
• in pdf

Here is the exercise sheet for today.

• Andy also lectured on hash-based signatures at the 2017 summer school. Follow the link for the video, slides, and exercises.
• For the NIST competition we submitted an improved version of SPHINCS which we called SPHINCS+. On the website you can also find the original SPHINCS publication. SPHINCS+ is now in the third round of the NIST competition.
• Adam Langley from Google wrote a blog post giving more motivation for stateless hash-based signatures ... should you need any.

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:

• If you want to see the current records in lattice attacks check out the page on Lattice challenges including a page on SVP challenge.
• The lattices used in cryptography are often not general lattices but carry more structure. E.g. the lattice in NTRU comes from computing in the polynomial ring modulo x^N-1. Such ideal lattices might be easier to break than general lattices and there is a separate ideal lattice challenge.
• Daniel J. Bernstein, Nadia Heninger, and I gave an introductory talk about lattices at 34C3. You can find the material including lots of Sage snippets at https://latticehacks.cr.yp.to.
  There is also a video for the talk; I suggest stopping many times while watching to do some examples with Sage.
• For details on an optimized version of the attack see Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures by Phong Nguyen and Oded Regev.
• Lyubashevsky introduced rejection sampling on signatures to avoid the attacker learning information about the good basis, see lattice-based signature scheme.
• NTRU was a round-3 candidate in NIST's post-quantum crypto competition. The system works essentially as described in the slides, with some improvements, e.g. to avoid evaluation-at-1 attacks. While NTRU didn't win the competition, it is now used by Google to secure their internal communications.
  Our entry, NTRU Prime, in the NIST competition shares many elements with NTRU but makes different choices for the ring R and q. Like NTRU is didn't win, but it's seeing real-wold usage, in this case in OpenSSH, a common system for logging into remoe computers.
• The PQCRYPTO summer school produced lots of slides, videos (6 long sessions!) and exercises on lattices. Take a look here.

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:

• GeMSS and HFEv-, the examples I mentioned for hidden large fields got weakened by Tao, Petzold, and Ding at Crypto 2021, see Efficient Key Recovery for all HFE Signature Variants.
• Rainbow, the NIST submission based on UOV, got broken by Beullens at Crypto 2022, see Breaking Rainbow Takes a Weekend on a Laptop.
  While this knocked out Rainbow, the general concept of UOV seems OK and submissions based on it are announced for NIST's new competition on signatures.
• MQDSS, the NIST submission based on using the Fiat-Shamir transform from a random system of multivariate equations, had chosen too small parameters but the approach is generally fine. Hence, video II is still OK.

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.