Announcements | Exam | Literature | Topics | Course notes | Old exams |
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 8, 2021 and the lectures
for this course are on Thursdays in the mornings, hence the first
session is on February 11.
The second part will be taught by Marc Stevens.
The webpage for his part is
https://homepages.cwi.nl/~stevens/mastermath/2021/.
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. For the first
part the lectures are replaced by pre-recorded videos. The
exercise session runs 11:00 - 12:00, with an option for extension
by 30 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 cover various generic attacks
against common cryptographic primitives (e.g., block ciphers, hash
functions) and cover important cryptanalytic attack techniques like
time-memory tradeoffs, linear cryptanalysis, differential
cryptanalysis and algebraic cryptanalysis.
The first lecture will take place on 11 Feb, starting at 11:00.
The exam is planned for 17 June but as we will offer the exam as oral exams
we are more flexible with the dates. The same holds for the retake.
Each exam will take 30 min and will have Marc and Tanja both asking some questions. These cover general concepts as well as showing some expam-type exercises and asking the student to explain how they would solve it, without doing any of the computational steps.
After the quesstioning part they will retreat to discuss the grade and return to the student to announce the grade.
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.
This first part covers the following topics:
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:
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
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:
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.
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 and last video covers stateless hash-based signatures
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:
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:
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:
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 is a new recording.
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:
11 Feb 2021
Here is the exercise sheet for the live session
The videos for today are posted. 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.
If you are taking this course without background in cryptography, please see the extra videos in the Introduction section.
18 Feb 2021
Please watch the last 3 videos on quantum computing as preparation for
the live session. You should also watch the first video on code-based
crypto as part of today's videos.
Here is the exercise sheet for the live
session.
Note: I have updated the exercise sheet to include an exercise on
Grover's algorithm.
25 Feb 2021
Please watch the remaining videos on code-based cryptography in
preparation.
Here is the exercise sheet for the live session. Note that I have updated the sheet to clarify that n=q in exercise 2 and that exercise 4 uses the public key K as parity-check matrix.
04 Mar 2021
If you haven't done so, yet, finish watching the videos on code-based
cryptography. The topic for this week is hash-based signatures, so
watch the first 3 videos in preparation. The 4th video is now also
released to round off this unit.
Here is the exercise sheet for the live session.
11 Mar 2021
We'll cover isogeny-based crypto this lecture and half of thee next.
Sorry for being slow on the videos. You can solve these
exercises with the information from
the videos. I've extended exercise 3 since the firs posting.
18 Mar 2021
All videos for isogeny-based crypto are now posted. Next up are
lattices. This week's sheet is all about isogenies.
Here is the exercise sheet for the live session.
25 Mar 2021
The topic today is lattice-based cryptography.
Here is the exercise sheet for the live session.
01 Apr 2021
The topics today are lattice-based
cryptography and multivariate quadratic systems.
This is the last lecture on post-quantum crypto in this course,
next week Marc Stevens will continue.
Here is the exercise sheet for the live session.
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.