List of Topics for Final Presentation

Introduction to Modern Cryptography
University of Amsterdam course, Fall 2012; part of Master of Logic

Preliminary Schedule for Final Presentations

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	break
14:40 - 15:20	Elliptic Curves — Frank
15:20 - 16:00	Rainbow Tables — Malvin

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

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

Elliptic Curve Cryptography — Frank

See the wikipedia article for an overview and check this page for a list of references.

Fully Homomorphic Encryption — Ignas

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 found here, 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.

Start with understanding the key tool of secret sharing, proposed in "How to share a secret" [dblp]. You may then look at the first chapter of a draft of a book on multiparty computation (by Cramer, Damgård and Nielsen) to get an overview of the topic and then look more closely at a specific topic like "Secure Multiparty Computation for Privacy-Preserving Data Mining".

Obfuscation

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.

Start with an informal introduction and a paper on this topic. If you want, you can also say something about watermarking, another way to fight piracy.

Quantum Cryptography

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.

Rainbow Tables — Malvin

This recent news 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.

This is treated in chapter 13 of [KL]. Also read "The Random Oracle Methodology, Revisited" [dblp].

Robust Combiners

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

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.

There is a large collection of such attacks. Start with the original paper by Kocher [dblp]. There are many other papers, e.g. on timing attacks over networks [dblp] and attacks on disk encryption keys in computer memory [dblp] (very readable and has nice images, but rather different from other attacks.)

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

Some classic results are in this paper.

Subspace LWE is a new and more flexible form of this problem. Present subspace LWE, and possibly its applications [dblp].

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

Chapter 6 of [KL] has a good treatment.

Visual Cryptography

Visual cryptography is about cryptosystems that can be decrypted "by hand", or rather "by eye". Not too challenging, and comes with nice images. Introduction at Wikipedia, the paper introducing visual cryptography [dblp]. Browse through the more recent papers on Doug Stinson's visual-cryptography page.

Yao's garbled circuits

Yao's garbled circuit is an important building block for multiparty computation. Simple and cute idea, but it took 20 years to provide a full proof. See "A Proof of Yao's Protocol for Secure Two-Party Computation".

Zero Knowledge

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.