Introduction to Modern Cryptography 2014 - Final Exam

General Procedure

For the final exam of the course, every student will pick a cryptographic subject from the list below and study that. Every student has to prepare and give a 15-minute talk followed by 10 minutes of questions about the chosen topic, as well as prepare a hand-out of maximal 2 A4 pages.

Detailed Procedure

• Look through the list of topic below. By Wednesday, 8 October, 14:00, send us by email on ordered list of your top 5 preferences. Note that you are welcome to add your own topic of choice, see below. Let us know as well if you have any constraints for the presentation slots during the exam week (Mo 20 Oct, Wed 22 Oct, Fri 24 Oct, all 13:00-15:00).
• Study the material and think about how you want to present the subject to your fellow students in a 15-minute talk.
• Write down in a few bullet points how you want to structure your talk.
• Prepare a written hand-out about the chosen topic, consisting of maximally two A4 pages. That hand-out will be handed out to the audience right before or after your talk (so you cannot assume the talk audience has studied your hand-out beforehand). Send a preliminary version of your handout and the talk structure to Christian and Malvin by Wednesday, 15 October 2014, 14:00. We will then use the lecture slot on Thursday, 16 October 2014 from 9:00-11:00 to give you individual feedback.
• In this meeting, we will discuss your talk outline and hand-out and you can ask questions about the studied material (you are of course welcome to ask any questions at any time.)
• Send us a PDF version of your handout until 11:00 of the day of your talk, we will print them and hand them out, the electronic version will be put on the course webpage.
• We will create the presentation schedule, you give a 15-minute talk, followed by 10 minutes of questions from the audience. (Yes, we will be asking questions.)

Presentation

A presentation should make your fellow students care about the subject and convey the main ideas of the topic/paper. Try to show how your topic connects to something we have learned in class. You should present the main result(s) with some precision, and it would be nice to give some key ingredients of proofs (where appropriate - some proofs are nasty and/or not interesting). Do not spend all your time putting up formula after formula: prepare a presentation you would like to listen to. It is important to stay on time, you leave a bad impression if your 15-minute talk lasts for 20 minutes or more. Here are a few general tips:

• Keep it simple! The talk is only 15 minutes and the goal is really not to impress anybody with technical details, but instead to convey the main message to your fellow students who do not know anything about your topic.
• Use at least some slides, 15 minutes are not enough for a blackboard-only talk. Presenting from slides comes with the danger of going (way) too fast. Make sure everybody in the room can follow you. A rough average of 1min per slide tends to be reasonable.
• Practice your talk in order to get an estimate of the right timing!

Handout

The handout consists of maximal 2 A4 pages giving an overview of the selected topic. A proper handout contains at least the title of the chosen subject, a general description of it, a high-level overview of the main ideas, and references to scientific articles and other resources you have used (please insert hyperlinks for very reference). The handout is not a means to help people understanding your talk. To the contrary, it is unrelated to your talk, and simply gives a quick two-page overview of the presented topic. Keep it accessible for the target audience of your fellow students. Make it look more attractive by putting one or more pictures or figures. Do not put too many formulas, it should be light to read and easy to digest. Send us a PDF version of your handout until 11:00 of the day of your talk, we will print them and hand them out.

Grades

Your grade for the final presentation will be determined by the quality of the presentation, your ability to answer questions about the subject (we will use this list for the evaluation), and the quality of the hand-out. Your grade might be reduced if you do not follow the "detailed procedure" 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 homework exercises).

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:

Note that you are very welcome to suggest a topic yourself. In that case, send us (at least) one link to an academic paper about the subject. We will let you know quickly if that subject is appropriate.

Some subjects are far more challenging than others. The following list if roughly ordered in decreasing difficulty of topics. A good talk about a challenging subject is more impressive than a good talk about an easy subject, and the grade will reflect that.

Obfuscation (Thijmen)

This is the new "hot topic" in theoretical cryptography since 2013. In many cases, an 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.

There is an impossibility result from 2001 (see informal introduction and a paper), but since last year, there are also positive results, see for instance Shai Halevi's presentations on the topic.

Fully Homomorphic Encryption (Merel)

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.

Quantum Cryptography (Filipos)

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.

Zero Knowledge (Joost)

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: Damgaard and Nielsen's "Commitment Schemes and Zero-Knowledge Protocols (2011)" (available here) and Goldreich's tutorial.

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

The Cramer-Shoup encryption system (Eileen)

R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Advances in Cryptology: CRYPTO'98, Lecture Notes in Computer Science, 1998. You can also check Boaz Barak's lecture notes on it.

Theoretical Constructions of Pseudorandom Objects (Leanne)

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.

Identity-Based Encryption

Check https://en.wikipedia.org/wiki/ID-based_encryption and D. Boneh et M. Franklin (2001). Identity-based encryption from the Weil pairing, Advances in Cryptology:CRYPTO'01, Lecture Notes in Computer Science, Springer, pp. 213-229, 2001.

Secret-Key Agreement by public discussion from common information

U. Maurer, Secret key agreement by public discussion from common information, IEEE Transactions on Information Theory, 1993.

Yao's garbled circuits (Konstantinos)

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

Multi-Party Computation

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.

You may then look at the first chapter of a draft of a book on multiparty computation (by Cramer, Damgaard 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".

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 tutorial slides by Krzysztof Pietrzak about the topic.

Elliptic Curve Cryptography (Eli)

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

Dolev-Yao Models

The Dolev-Yao model is a formal model used to prove properties of interactive cryptographic protocols. Check wikipedia and the original article Dolev, D.; Yao, A. C. (1983), On the security of public key protocols, IEEE trans. on Information Theory, IT-29: 198–208

Paillier Encryption

Section 11.3.2 in [KL] or P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Advances in Cryptology: EUROCRYPT'99. Lecture Notes in Computer Science, Springer, pp. 223-238. 1999

Position-Based Cryptography

In standard cryptography, one uses a password or biometric features to identify a cryptographic player. In position-based cryptography, one uses the geographic location of a player as cryptographic credential. The following paper gives some (im-)possibility results in the classical setting: Chandran, N., Goyal, V., Moriarty, R., and Ostrovsky, R. (2009). Position based cryptography. Lecture Notes in Computer Science, 5677:391–407. Also check this report of a recent student project.

Secret Sharing (Arianna)

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.

Start with understanding the key tool of secret sharing, proposed in "How to share a secret" [dblp].

Then dive deeper into more recent literature.

Rainbow Tables

This news article talks about password cracking and Rainbow tables. See Hellmann: A cryptanalytic time-memory trade-off [dblp] for the basic idea and Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off [dblp] for the rainbow part.

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" Methodology, Revisited" [dblp].

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

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.

Tor Project (Remi)

Using so-called onion routing, Tor employs cryptography to allow anonymous usage of the internet.

CPA-security of padded RSA (Tingxiang)

There is a proof of CPA-security of padded RSA with l(n)=O(log n). Why does it not work for l(n)=O(n)?

Last update:     CWI DISCLAIMER