Wednesday, 19 December 2012, 13:00 - 16:00, in SP B0.208
13:00 - 13:40
Multi-Party Computation — Iva
13:40 - 14:20
Fully-Homomorphic Encryption — Ignas
14:20 - 14:40
14:40 - 15:20
Elliptic Curves — Frank
15:20 - 16:00
Rainbow Tables — Malvin
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 25-minute talk.
You make an appointment with Maria and Christian before
Thursday, December 13. Malvin: Wed 12/12/12, 13:00, Iva: Thu
13/12/12 11:00, Frank: Thu 13/12/12 12:00, Ignas: Thu 13/12/12 13:00
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.)
On Wednesday, 19 December 2012, between 13:00 and 16:00, you give a 25-minute
talk, followed by 10 minutes of questions from the audience. (Yes, we will be
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. It is important to stay on time, you leave a bad impression if your
25-minute talk lasts for 30 minutes or more.
Your grade for the final presentation will be determined by the
quality of the presentation and your ability to answer questions about
the subject (we will use this list for the evaluation). 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/2 towards your final grade of the course
(the other 1/2 are determined by the exercises).
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 25-minute talk. Don't spend too much time on making it pretty before
receiving our feedback.
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.
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
student at ETH has extended the result in a
There are more results of this type.
Achieving fully homomorphic encryption, under any kind of reasonable
computational assumptions was a holy grail of cryptography for many
years until finally achieved by Craig Gentry in 2009. Since then, the
schemes have been improved and simplified, but this remains a very
challenging topic. Try to start with Boaz
Barak's notes from an Advanced
Crypto class at MIT. A complete overview of the papers can be
but watching one of Shai
Halevi's presentations on the topic (e.g. from CRYPTO 2011) might be more useful.
Multi-Party Computation — Iva
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
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.
Rainbow Tables — Malvin
article talks talks about password cracking and Rainbow
tables. More details follow...
Random Oracle Model
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
about the topic.
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
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).
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
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.