Mandatory free coffee at the coffee bar downstairs (“Academisch
Kwartier”). Please be on time!
9:00 - 9:30
Visual Cryptography — Lodewijk
9:30 - 10:00
Zero Knowledge — Femke
10:15 - 10:45
Multiparty Computation — Sarah
Thursday 8 December
10:30 - 11:00
Obfuscation — Max
11:00 - 11:30
Random Oracles — Demet
11:45 - 12:15
Quantum Cryptography — Jessica
12:15 - 12:45
Side-Channel Attacks — Maria
Procedure
The following procedure is meant as a help, it forces you to start
early enough with preparing and finishing your presentation.
You pick a subject from the list
below and inform us by email about your choice (the first to choose a subject gets it).
You study the material
and think about how you want to present the subject to your
fellow students in a 20-minute talk.
You make an appointment with Joachim or Christian in
week 46 (14 Nov to 18 Nov) or before.
For this meeting, you have thought about how to structure your talk and
prepared an outline of the talk on paper. We will discuss this outline and you can ask
questions about the studied material
(you are of course welcome to ask any questions at any time.)
In week 48 (28 Nov - 2 Dec) (or before) you email us your talk slides and we will
give you feedback in order to improve them.
On Tuesday, 6 December or Thursday, 8 December, you give a 20-minute
talk, followed by 10 minutes of questions from the audience. (Yes, we will be
asking questions.)
A presentation should make your fellow students care about the
subject and convey the main ideas of the topic/paper.
You should present the main result(s) with some precision, and it would be nice
to give some insight into the proofs (where appropriate - some proofs are nasty
and/or not interesting). Don't spend all your time putting up formula after
formula: make a presentation you would like to listen to.
Your grade for the final presentation will be determined by the
quality of the presentation and your ability to answer questions about
the subject. Your grade might be reduced if you do not follow the
timeline above. (This does not mean that you have to stick to the
indicated papers, if you find other articles or sources that are
relevant for the selected topic, you are welcome to use them.) The
final presentation counts 1/3 towards your final grade of the course
(the other 2/3 are determined by the exercises).
Presentation tools
LaTeX has several presentation packages available: powerdot and beamer are
probably the best choices. (Powerdot is more modern, but both are quite
powerful.) Powerpoint and Apple's Keynote can be used too.
Making slides is a lot of work, it usually takes me a few full days to
prepare well for a 20-minute talk. Don't spend too much time on making it pretty before
receiving our feedback.
Research tools
Cryptographic papers can be found via DBLP,
which has an index, BibTeX (citation) files and links to an electronic edition.
If the electronic edition requires payment, you can find almost any "modern"
paper online via Google or Google
Scholar. As an alternative, almost all universities have a
subscription to SpringerLink, allowing you to access these articles for free
from their computers. If neither works, feel free to contact us.
Suggested topics for final presentation:
You are very welcome to suggest a topic yourself.
Some subjects are far more challenging than others. A good talk about a
challenging subject is more impressive than a good talk about an easy subject,
and the grade will reflect that.
Composability
Intuitively, we would expect that, if F and G are "secure" in some sense,
the composition F(G(.)) is secure. This is not always the case, as shown
here
[dblp]. A
student at ETH has extended the result in a
semester thesis.
There are more results of this type.
Multi-Party Computation — Sarah
questions to Christian
Many bank vaults can only be opened by two or three employees.
Secret sharing allows you to do the same with digital secrets, and even to do (some)
calculations on these secrets.
Multi-party computation allows multiple parties to jointly compute a function
of each of their private inputs - for instance, to calculate their average
salary without having to reveal their own.
In many cases, the author may not want a program to be understandable.
As an example, multiplayer games generally try to protect themselves from cheaters.
There are also obvious applications in "Digital Rights Management": obfuscating the code verifying license key checking may help deter piracy.
Quantum computers, if ever built, will severely upset cryptography: most
importantly, breaking RSA and solving discrete logarithms can be done
efficiently on a quantum computer. Fortunately, quantum-mechanical effects can
also be used to construct new and more secure algorithms.
For a good overview, see
this
survey paper. For an introduction to quantum computing, see Ronald de Wolf's lecture notes or the standard text book by Nielsen and Chuang. This is Christian's main area of research, he can
point you to more specific subjects.
Random Oracle Model — Demet
questions to Joachim
The random oracle model is a formalization of intuitions like "the output of
DES is random". It is typically much easier to prove security in the random
oracle model, which often allows more efficient cryptography. On the other
hand, "security" now depends on a very strong assumption... and it's possible
to construct schemes that are secure only in the random oracle model.
The purpose of a robust combiner is to combine different candidate
implementations of a cryptographic primitive (e.g. a PRG) such that
the combined device is secure as long as at least one of the
ingredients is secure. Here is
the original paper and some nice
slides
about the topic.
Side-Channel Attacks — Maria
questions to Joachim
A mathematical proof of security is nice, but real-world implementations of
cryptographic algorithms are complicated programs and electronic devices. There
are many ways to attack the implementation, instead of the mathematical object.
For instance, the running time of a bad RSA implementation may depend on the
exact value of key, allowing key recovery via precise timing - an attack not
considered by the usual security proof, which deals in oracles and mathematical
functions.
Some understanding of real-world computers and chips is useful for this topic
(depending on the attack or attacks you choose to treat).
The Learning-With-Errors Problem and Light-Weight Authentication
Learning with errors is a linear algebra problem related to decoding random
error-correcting codes: let A be a random matrix and let e be "a little" noise;
now find s from A, A s + e (note that this is easy if e is the zero vector.)
This is an area of active research (papers are from 2011), and Joachim is doing
research based on subspace LWE.
Theoretical Constructions of Pseudorandom Objects
Since cryptography is eventually based on (so far) unprovable assumptions about
the hardness of certain problems, it is interesting to show that, for instance,
one-way functions ("hard to invert") can be used to construct pseudorandom
permutations.
This is primarily of theoretical interest - you can typically achieve more
efficient schemes using specialized constructions - but the results of this
form are also often applied in "new" families of security definitions, where no
standard PRFs may be known yet.
Zero-knowledge proofs allow you to prove that you know something, without
revealing what it is. This is a useful building block, e.g. if you want to do
password authentication without revealing your password to an untrusted server
(e.g. SRP protocol.)
Focus on the theory, it's usually quite elegant.
One of the best non-technical explanation of zero knowledge appears in
this paper (Naor, Naor and Reingold),
published in the prestigious Journal of Craptology. Another good introduction is
"How to explain zero-knowledge protocols to your children"
[dblp].
Consider also some more serious works: Damgård and Nielsen's "Commitment Schemes and Zero-Knowledge Protocols (2011)" (available here, for now) and Goldreich's tutorial.
There are a lot of zero-knowledge protocols, so you have plenty of
choice if you pick this topic.