Pictures and slides | Announcements | Exam | Literature | Course |

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

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:

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

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.

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.

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