The first part will be 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 me where ever I am:
e-mail:tanja@hyperelliptic.org


The second part will be taught by Marc Stevens.
The webpage for the second part is http://homepages.cwi.nl/~stevens/mastermath/2017/

We will cover only the very basics of quantum algorithms. I recommend you take Ronald de Wolf's Quantum Computing course (also Mastermat) for much more information. That coure runs Monday afternoon at UvA.

Details are filled in as time permits. The official home page is here.
The spring term runs week 6 until week 21, i.e. the first lecture takes place on February 7. The course takes place Tuesdays at the University of Utrecht; the room has changed. We are now in KBG and RUPP with the following schedule:

• KBG Pangea in week 8, 9, 13, 14,16
• KBG Atlas in week 10, 15
• RUPP A en D week 11, 12

• Rupp Paars week 17
• BBG 065 week 18, 19, 20, 21

Note that these are calendar weeks. Tanja's lectures go until March 21 (included) and Marc's start on April 4. There will be no lectures on March 28; Tanja will post reading material.

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

Announcements

Examination

There will be a written exam on June 13, 13:30-16:30, Educatorium Beta (at University of Utrecht). The retake will either be a written exam on July 4 or an oral exam.

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.

Literature

There are a few books covering topics we touch in class but there is no 'textbook' that covers everything. The following list will be updated as the course proceeds. 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.
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.
It is not necessary to purchase any book to follow the course.

Class notes

07 Feb 2017
General introduction to cryptography; concepts public key and symmetric key cryptography, interactive example of m-RSA, real RSA.
If you didn't take any crypto lectures before please check out my course on Cryptology. All lectures are online as videos in relatively good quality.
Here are photos and videos from the lecture.

14 Feb 2017
RSA is brpken if we can factor; Pollard-rho attack for factoring. How to decide whether a number is prime or not? Compositeness test based on Fermat's little theorem, Miller-Rabin test. Exercise to factor 403 using Pollard rho and to test whether it might be prime using Miller-Rabin.

Shor's algorithm uses a quantum computer to find the period of the function f(x)=c^x modulo n for some c. The smallest non-zero period is the order o of c mod n. If o is even, compute c^o/2 mod n. If that's not -1 compute gcd(c^o/2 -1,n). Remember that the gcd computation computes the first argument modulo the second, so you only need to compute the exponentiation once. This gives a factor of n. If o is odd, repeat with a different choice of c.

Here are photos and videos from the lecture.

21 Feb 2017
Much slower explanation of operations one can do on a quantum computer (NOT, XOR, Toffoli gates) and Hadamard operations. Then Simon's algorithm in detail (see slides from last time).
Correction to Shor's algorithm: if the order of a is odd, restart, if it even, i.e. 2*s then compute a^s. If that's not -1 we can factor.
Grover's algorithm (see slides). Grover's algorithm finds a root of a function with n-bit input in 2^(n/2) steps; classical algorithms would need 2^n steps. This reduces the security of block and stream ciphers. It does not seem to affect the security of information-theoretically secure MACs. For hash functions finding pre-images get faster. Note that these are 2^(n/2) quantum operations, which are likely slower than normal bit operations; e.g. at PQCrypto 2016 a paper was presented showing that Grover's algorithm applied to a AES-128 (a block cipher with 128 bits) takes 2^96 steps because of the complication of the algorithm.
One answer in the search for alternatives is to use quantum crypto (well, it also has 'quantum' in the name, so this must help ;-) ). I gave a short explanation and a short rant on quantum crypto. For a very positive view see the Everything you need to know about Quantum Cryptography by a company dealing in quantum crypto. A general-audience article on what goes wrong in practice appeared in Wired.
Finally I briefly explained the Diffie-Hellman key exchange because by name QKD is often misunderstood to achieve the same functionality as DH. DH in finite fields or on (hyper-)elliptic curves is broken by Shor's algorithms, so we only need to understand it in order to know what is currently used. If you haven't seen it before, read up on DH in the course from last year or in the reference books.

Here are photos and videos from the lecture.

Some people asked about homeworks. There won't be any exercise sheets but I expect you to read up on the material we cover in class. E.g. for this week we covered quantum algorithms and DH, so please read about that. The class notes from Ronald the Wolf are freely available, even if you didn't sign up for the course on Monday.

28 Feb 2017
This course is about post-quantum crypto, we cover 4 types of public-key systems for which no efficient application of Shor's algorithm is known: code-based crypto, hash-based signatures, lattice-based crypto, and signatures based on multivariate-quadratic equations.
Short introduction to coding theory and code-based crypto (linear block codes, length n, dimension k, minimum distance d=2t+1, Hamming weight, Hamming distance, generator matrix, parity check matrix, c=mG+e, H(c+e)=He).
General decoding problem is NP-complete; this seems to hold also on average (but no proof there). McEliece crypto system (1978) uses this to encrypt. Public key is generator matrix G, encrypt m as mG+e using some random error e of weight t, decryption is some secret way of decoding. Do avoid leaking information, we don't use this to encrypt messages but use it to transmit a key, Hash(m), which is then used with a symmetric cipher to encrypt the actual message.
Niederreiter's system uses the parity-check matrix instead of a generator matrix. Instead of using the parity-check matrix H of the easy-to-decode code we pick a random invertible (n-k)x(n-k) matrix S, and nxn permutation matrix P and put K=SHP. K is the public key and S and P together with a decoding algorithm for H form the private key. For codes that are suitable for code-based crypto, K looks like a random matrix. Given the syndrome s=Ke a user knowing S computes S^-1s=S^-1(SHP)e=H(Pe). Pe has the same weight as e (because P is a permutation matrix) so this can be decoded by the efficient decoding algorithm for H. Then applying P^-1 gives e.
A detailed description of how Goppa codes work and why they have dimension at least n-tm and minimum distance at least 2t+1 is on the slides. Note that for the XGCD we use that in computing gcd(v,g)=f*v+l*g we start with g=0*v+1*g and v=1*v+0*g and slowly decrease the left-hand side while increasing the coefficients on the right-hand side. In the algorithm we stop once we reach a state of a=b*v+h*g with a and b of degree bounded by t/2 and (t-1)/2; taken modulo g this gives the desired equation and thus σ.
I started explaining how attacks using information-set decoding work. The slides were missing a drawing which I made on the board; it is now included in the slides.

Here are photos and videos from the lecture and here are the slides.
For further reading take the overview chapter by Overbeck and Sendier 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 library account.

07 March 2017
Lecture given by Andreas Hülsing.
Hash-based singnatures require only a hash function that is resistant against preimage and second-preimage attacks. It is easy to build a one-time signature from these functions. To extend to multiple signatures use Merkle trees and trees of trees. Andy made his slides available so that you can check back what he covered.
He did not video tape this lecture but gave a similar one at the PQCrypto winter school last year; the video of that is available online on YouTube.

• In December 2014 I gave a short presentation on hash-based signatures. The first part contains some pictures of mathematical trees illustrating the text above.
• Together with a bunch of people we designed SPHINCS: practical stateless hash-based signatures dealing with the most annoying part of hash-based signatures, namely that the signer needs to keep state to know which leaf-level signature has been used. The design uses Winternitz signatures instead of Lamport signatures.
• Adam Langley from Google wrote a blog post giving more motivation for hash-based signatures ... should you need any.

14 March 2017
Finding words of small weight in a code -- algorithms by Lee-Brickel, Leon, and Stern. We didn't do the running time analysis, 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.
Further reading

• Henk van Tilborg made his book Coding Theory
• In 2009 Paulo Barreto gave a nice introductory lecture on code-based cryptography.
• 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.
• In 2012 I helped organize a workshop on post-quantum cryptography at the Lorentz Center in Leiden. Slides from the talks are available, in particular Nicolas Sendrier gave a tutorial on code-based cryptography.

The second part of the lecture covered lattices. A lattice is a discrete subgroup of R^n, usually given by some basis B={b1, b2, ..., bn}. Then L={Σ aibi | ai in Z}. In cryptography one is usually given a very skewed basis and the computational task is to find a nice basis in which the vectors are close to orthogonal. If the coefficients were in R rather than in Z we could do this easily with the Gram-Schmidt orthonormalization algorithm, but for lattices of sufficiently high dimension it is even hard to find the shortest vector in a lattice. This Shortest-Vector Problem (SVP) or the related problem of finding the closest lattice point to a given point in R^n, the Closest Vector Problem (CVP) form the basis of several lattice-based cryptosystems. See the slides (link below) for pictures.

Goldreich, Goldwasser, and Halevi showed how to build an ecryption and a signature system on top of CVP. Each signature leaks a bit of information on the secret (good) basis; with enough signatures one can easily see the fundamental parallelopiped (the elements in Σ (-0.5,0.5] b_i).

One of the oldest methods to find shortest vectors is LLL, named after H. Lenstra, A. Lenstra, and L. Lovasz. The algorithm finds a short vector that is at most a factor d longer than the shortest. This approximation factor d is important when checking whether a system is secure. The shortest vector must be such that there are other vectors more likely to be found.

To illustrate the working of LLL I showed slides by Thijs Laarhoven, a former PhD student at TU/e. Thijs made his slides available on his webpage. Open the slides in acroread and click on the arrors to play.

Finally I explained the set up of NTRU and how finding the secret key is related to finding a short vector. I will start next week with NTRU.

Here are photos and videos from the lecture.

21 March 2017
I used slides made by Thijs Laarhoven to explain the main algorithms for computing shortest vectors (not just short vectors as in LLL); covering both enumeration algorithms and sieving algorithms. The latter brings you all the way to research results (by him) from a paper that appeared at Crypto 2015. There are some more improvements in more recent papers.

On the constructive side I explained how NTRU works. The NTRU system has three general public parameters: namely positive integers n, p, and q where gcd(p,q)=1 and q is much larger than p. Toy parameters are p=3, q=64, N=107; the low end of reasonable is p=3, q=128, and N=503. For hand calculations you can use p=3, q=101, and N=7. If you want something more challenging, try the NTRU challenge; they do offer cash prizes!

All computations take place in the ring R=Z[x]/(x^N-1), i.e. all elements are represented by polynomials of degree <N. Some computations additionally reduce modulo p or modulo q. I used p=3 in my explanation.

The private key of user Alice is a polynomial f(x) in R which satisfies that f is invertible in R/p=(Z/p)[x]/(x^N-1) and in R/q=(Z/q)[x]/(x^N-1).

To generate her public key, Alice picks a polynomial g(x)in R and computes f_p=f^{-1} in R/p, f_q=f^{-1} in R/q and h=f_q* pg in R/q. Alice's public key is h along with the public parameters p,q, and N.

To encrypt message m(x) which is an element of R with coefficients in the smaller interval [-(p-1)/2,(p-1)/2] to a user with public key h take a random polynomial φ(x)\in R$ and compute c=φ * h +m in R/q.

To decrypt ciphertext c in R/q use private key f and compute a=f * c in R/q, choosing coefficients in [-(q-1)/2,(q-1)/2]. [If you're a mathematician, lift a to R, i.e. forget about the reduction modulo q]. Then compute m'=a* f_p in R/p, taking coefficients from [-(p-1)/2,(p-1)/2].

The idea here is that the computation modulo p removes the first part, so that we are left with f*f_p*m which is congruent to m modulo p, because f_p is the inverse of f modulo p. However, this mixes computations modulo q and p, which usually is a bad idea. The reason that this is still likely to work is that the first part is not just some multiple of p but that h=f_q*pg and thus the first part of a(x) equals f*φ*h=φf*f_q*pg which is equivalent to φ*pg modulo q. Now, if φ and g are sparse (have very few nonzero coefficient), the existing coefficients are small and p is small (all relative to q) then is is very likely that φ*pg in R (i.e. without reduction) equals φ*pg with reduction to coefficients in [-(q-1)/2,(q-1)/2], which means that all coefficients are indeed divisible by p and thus the first part vanishes.

NTRU chooses to have all random polynomials have coefficients in {-1,0,1} and to limit the number of non-zero coefficients. Let Lf be the set of polynomials in R with df coefficients equal to 1, df-1 coefficients equals to -1, and the remaining coefficients equal to 0. The secret key f is chosen to be an element of Lf. Similarly let Lg (and Lφ) be the sets of polynomials with exactly dg (and dφ) coefficients equal to 1, the same number equal to -1 and the rest equal to 0. For the parameters with N=107 choose df=15, dg=12, and dφ=5; for N=503 choose df=216, dg=72 and dφ=55.

I showed how to estimate sizes so that one knows how likely decryption failures are andthat this is usually OK for the proposed parameters. Last week we already discussed why f cannot have the same number of -1 and +1 coefficients (else it is divisible by x-1 and thus cannot be invertible).

We showed how turn finding g and f into a lattice problem; this means that all the lattice attacks from this and last week apply. We also considered Odlyzko's man-in-the-middle attack and hybrid attacsk.

Finally I showed how the lattice-based signature system BLISS works. I've fixed up the slides in the meantime and combined NTRU and BLISS into one slide set.

Further reading: I mentioned 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.

I took pictures and one student was so nice to handle the recording. All files are here.

28 Mar 2017
No lectures today. Please read up on signatures based on multivariate quadratic equations. For that you might be interested in watching Jintai Ding's talk from the Winter School on Post-Quantum Crypto 2016. His slides are also posted there.

A slightly older summary by Jintai Ding and Bo-Yin Yang "Multivariate Public Key Cryptography" in the book on post-quantum cryptography.