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