This first 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 The MasterMath semester starts on February 7, 2022 and the lectures for this course are on Thursdays in the mornings, hence the first session is on February 10.
The second part will be taught by Bart Mennink.

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. Videos are already posted for that course.

Details are filled in as time permits. The official home page is here.
The official time slot is Thursday 10:15 - 13:00. Because of the pandemic situation I will run this first part online, using the inverted classroom method. Hence, for the first part the lectures are replaced by pre-recorded videos, see below, slides and recommendations for further reading. All material is already provided and we will go through it in the order in which it is listed. For each week I will specify which videos I expect you to have watched. We will have an interactive part, also online, in the form of instruction/discussion sessions where I provide exercises for you to solve live and to test your understanding from the video and material. This interactive session runs 11:00 - 12:00, with an option for extension by up to 60 min if there are more questions.

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 first part focuses on post-quantum cryptography dealing with cryptographic systems that are secure even given the existence of quantum computers and the second part focuses on cryptanalysis, the analysis of the security of cryptographic systems.
After a general introduction to cryptography (the constructive side of cryptology) and cryptanalysis the course introduces the main contenders for secure systems: lattice-based encryption, code-based encryption, hash-based signatures, 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 second part of the course will center around those symmetric-key cryptosystems. The course covers a description of the basic security properties and designs of such systems (such as authenticated schemes, encryption schemes, and primitives). It is demonstrated how security is argued generically and under which security assumptions. Finally, it is discussed how cryptographic primitives are designed that are supposed to meet these security assumptions.

Announcements

The first session will take place on 10 Feb, starting at 11:00.

Examination

Details of the exam format depend on the number of students taking the course for credits and the pandemic situation.

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.

Topics

This first part covers the following topics:

• Introduction
• Quantum computing
• Code-based crypto
• Hash-based signatures
• Isogeny-based crypto
• Lattice-based crypto
• Multi-variate-quadratics-based crypto

Introduction

This video motivates the topic of post-quantum cryptography

See also the slides.

If you are taking this course without having prior knowledge in cryptology, please watch the following videos as preparation:

• 
  which covers basic concepts of cryptology. See also the slides.
• 
  to understand public-key cryptography. You can find the slides here.
• As a first public-key system we look at RSA. Warning: do not use schoolbook RSA in practice
  
  The slides are here.
• Diffie–Hellman key exchange
  
  The slides are here.
• 
  The slides are here
  KEM (Key Encapsulation mechanism) is a more modern security notion than public-key encryption, using the public-key part only to generate a shared secret for use in symmetric-key cryptography, then called DEM (Data Encapsulation Mechanism). The video shows how to turn a PKE into a KEM and gives RSA and DH as examples.
• We will also need formal security notions
  
  The slides are here

These videos were prepared for a bachelor course on cryptography. If you want to see more, check out the YouTube channel for it and its course page

Quantum computing

This video shows how period finding can be used to break RSA.

See also the slides.

This video shows how to represent qubits using normal bits. This representation can be used to verify algorithms and will be used in the following videos.

See also the slides.

Watch this video

to learn about quantum gates and basic circuits. See also the slides.

This video covers Simon's algorithm.

See also the slides.

Finally we cover Grover's algorithm,

see also the slides.

Further reading:

• A nice discussion of Simon's algorithm in the usual Dirac notation can be found here.
• Simon's algorithm can be used to break secret key cryptography if we run the cryptography on a quantum computer (see this paper). Note, this is a far stronger model than post-quantum cryptography where we assume honest users use conventional computers. However, it nicely demonstrates the power of quantum algorithms.

Code-based crypto

This video explains basic notions of coding-theory and the McEliece scheme.

See also the slides.

This video covers Niederreiter's version, statements about their equivalence, and attacks on the schoolbook versions.

See also the slides.
If the security notions on the last slide do not make sense to you, watch the last video in the introduction section.

This video defines binary Goppa codes and how to use them in code-based crypto

See also the slides.

This video proves two bounds on the minimum distance of Goppa codes and shows how to decode.

See also the slides.

This video covers information-set decoding, which are generic attacks on code-based cryptography.

See also the slides.

This last video covers quantum attacks on code-based cryptography

See also the slides.

We didn't do the running time analysis for Leon or Stern. I gave some motivation why the improvements are improvements but didn't trace all the binomial coefficients. Here is a taste of this. I will denote the binomial coefficient n choose k by C(n,k) to save my sanity in typing this.
There are n choose t ways the t error positions can be distributed over the n positions. When we select the n-k columns to make a left-right split and to transform the right hand side into the identity matrix we determine, whether step 2 can be successful. On that level, the likelihood of a selection to work changes from C(k,p)*C(n-k,t-p)/C(n,t) for Lee-Brickel to C(k,p)*C(n-k-z,t-p)/C(n,t) for Leon (because there are p columns chosen out of the k columns on the left, and t-p of those on the right; for Leon in addition we insist on having z positions to be zero in return for a cheaper step). For Stern the probability is (C(k/2,p))^2*C(n-k-z,t-2p)/C(n,t). Take a look at the original Stern paper or our paper reporting on our 2008 attack.

• Henk van Tilborg made his book Coding Theory available.
• Miichiel Marcus has kindly agreed to make his report available which gives a nicely worked out explanation of Goppa codes and the McEliece system. He also wrote a Jupyter notebook which you can download and use in Sage.
• Christiane Peters wrote her PhD thesis on curves (not post-quantum) and code-based crypto in 2011. You can download her thesis from her publications page.
• For further reading take the overview chapter by Overbeck and Sendrier on coding theory from the book on post-quantum crypto. The pdf is available here. You should also be able to download the full Springer version via your university account.
• Sendrier also lectured in a summer school at TU/e, you can find the slides and exercises at the PQCRYPTO Summer School on Post-Quantum Cryptography 2017.

Hash-based signatures

This video introduces hash-based signatures and shows how to sign messages with up to 4 bits.

See also the slides.

This video introduces Lamport and Winternitz one-time signatures.

See also the slides.

In this video we generalize from one-time signatures to schemes that can sign a fixed number of messages and cover general stateful hash-based signatures.

See also the slides.

The fourth video covers stateless hash-based signatures

See also the slides.

The fifth video describes some ingredients to few-times signates and defines r-subset resilience.

See also the slides.

You can find the python code snippets from the slides here.

Andreas Hülsing gave a lecture on hash-based signatures in the 2019 edition of this course and covered also security reductions. His slides available.
Further reading/watching:

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

Isogeny-based crypto

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 video gives the full description of the CSIDH system. You need the previous video to really understand why this works, but you can also watch this one first for motivation.

See also the slides.

SIDH is a different system based on isogenies. It is a bit harder to understand but we now have all material necessary to do so.

See also the slides.

Further reading/watching:

• For a lot mor information on isogeny-based cryptography visit the page of the Summer school on this topic. I contributed a unit on SIDH and CSIDH. The videos are the same as above but I also added a writeup and more references, see (C)SIDH – Isogeny school week 3.
• Chloe Martindale gave a lecture on isogeny-based cryptography at the PQCRYPTO summerschool in 2017. Note that that was before the CSIDH system was invented, so she covers only the math background and SIDH.
  For that school we have videos (Long form) as well as slides and exercises.
• Lorenz Panny gave a lecture on isogeny-based cryptography at the Executive School on Post-Quantum Cryptography 2019, where he does cover CSIDH as well.
• Luca de Feo wrote a nice overview paper Mathematics of Isogeny Based Cryptography in 2017.
• Take a look at https://csidh.isogeny.org for more information on CSIDH.

Lattice-based crypto

This video introduces lattices and shows the LLL algorithm to reduce lattices bases.

See also the slides.

Better lattice attacks are the topic of this video.

See also the slides.

The Goldreich, Goldwasser, Halevi systems have the advantage that you can see lattices at work. Note that the signature system is not secure, and this talks shows why.

I used slides by Thijs Laarhoven for this video.

NTRU is one of the oldest lattice-based encryption systems and one of the finalists in the NIST competition

See also the slides.
Note, I fixed a sign error in the definition of R_q.

This video discussed attacks on NTRU.

See also the slides.

The 6th and last video discusses reaction attacks on NTRU.

See also the slides.

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 is 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.
  Our entry, NTRU Prime, in the NIST competition shares many elements with NTRU but makes different choices for the ring R and q.
• The PQCRYPTO summer school produced lots of slides, videos (6 long sessions!) and exercises on lattices. Take a look here.

Multi-variate-quadratics-based crypto

This video defines how multivariate systems work and what the hard problem is.

See also the slides.

This video explains the Sakumoto–Shirai–Hiwatari identification scheme which is the basis of MQDSS.

iee also the slides.

This video explains how one can hide structure in the system of multivariate equations.

See also the slides.
I know that this video has terrible quality, haven't been able to fix it.

Further reading:

• If you want to learn more about multivariate signatures take a look at Albrecht Petzoldt's presentation at the 2017 summer school and solve the exercises.
• For a shorter version check out Bo-YinYang's talk at the PQC Minischool including videos (links from the schedule)
• Ding, Petzold, and Schmidt have published a book Multivariate Public Key Cryptosystems which you can download via your university library.
• The recent attacks I mention at the end of the last video are Improved Cryptanalysis of UOV and Rainbow by Ward Beullens and Improved Key Recovery of the HFEv- Signature Scheme by Chengdong Tao, Albrecht Petzoldt, and Jintai Ding.
• Since recording the videos in spring 2021 even more has happened on the attack front. Ward Beullens showed a practical attack on the level-I parameters in Breaking Rainbow Takes a Weekend on a Laptop.

Class notes and links to videos

10 Feb 2022
Please watch the introduction to post-quantum cryptography as well as Shor vs. RSA in preparation for the live session. The third video for today is Quantum computing for cryptographers I. This year the semester has one lecture less. I will skip the rest of the quantum computing videos, but feel free to ask questions about those, too.

If you are taking this course without background in cryptography, please see the extra videos in the Introduction section.

For this session we'll use a big-blue button server. Please see the Zulip chat for the link.

Here is the exercise sheet for the live session

17 Feb 2022
Please watch the first 5 videos on code-based crypto in preparation for today's session. This time we will meet on wonder, please see the Zulip chat for the URL.
Here is the exercise sheet for the live session.

24 Feb 2022
Please watch video IV on quantum computig (Grover's algorithm), video VI on quantum-attacks on code-based cryptography, and the first 3 videos (I-III) on hash-based signatures in preparation.

Here is the exercise sheet for the live session.

03 Mar 2022
The topics for this week are hash-based signatures and isogeny-based cryptography. I'm still working on recording a 5th vidoe on hash-basehd signatures. Please watch the remaiing video on hash-based signatures and the first 3 videos on isogeny-based cryptography.

Here is the exercise sheet for the live session.

10 Mar 2022
Please watch the remaining 3 videos on isogeny-based crypto (IV-VI) and the first video on lattice-based crypto.

Here is the exercise sheet for the live session.

17 Mar 2022
The topic today is lattice-based cryptography. Please watch the first five lectures (I-V) on this topic, i.e., the one from last week and 4 more..

Here is the exercise sheet for the live session.

24 Mar 2022
The topics today are lattice-based cryptography and multivariate quadratic systems. Please watch the remaining video (VI) on lattice-based crypto and the three videos on multivariate-quadratic signatures.
This is the last session on post-quantum crypto in this course, next week Bart Mennink will continue.

Here is the exercise sheet for the live session.

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.