Seminars on Theoretical Computer Science, semteo11

This year the topic of the course is cryptography and Johan Håstad is the lecturer. The lectures might be given in English or Swedish depending on the audience but all written material in connection with the course will be in English.

Relation to DD2448

There may be some overlap between this course and DD2448 , but this is kept to a minimum. This course is meant to give a more in-depth treatment of some topics introduced in DD2448 and/or to introduce more advanced notions and concepts. It is possible to get full credit for both DD2448 and this course.

News

• 110418: The second homework is now published.

Schedule

F	ti	13-15	v 14,17,18,19		1537
F	ti	13-15	v 15		4523
F	to	13-15	v 14,15		1537
F	mo	13-15	v 20		1537

Content of the Course

The precise set of topics covered in this course is negotiated in class. Examples of possible topics are listed below, but students may also propose topics of their own. As the lectures for the first three topics are already prepared and the topics are important for the course, these topics are likely to be covered.

Previous version of the course

A similar course was given in 2002/03. The old course page contains information that might be useful also for this version of the course.

Course Material

Some lectures will follow a similar path to lectures the of the course in 2002/03.

For some lectures there will be supporting material in the form of research papers.

The current course will take a more theoretical approach to cryptography than is taken by the book of Stinson used in DD2448. The books by Goldreich are more in the style that we expect of the current course but we will cover a small part of these books and be a on slightly less formal level. The material on Goldreich's homepage can, however, be very useful and is worth investigating for the student interested in a more in depth treatment.

Course Requirements

To be decided with the course participants but there will be a mix of homeworks and presentations (oral or written) of reasearch paper(s) with some component of both.

Grading

To appear.

Possible Topics

1. The definition of a good pseudorandom generator. Construction of such a generator from any one-way permutation.
2. The definition of a good pseudorandom function. Construction of such a generator from any good pseudorandom generator.
3. Zero-knowledge proofs. Proofs for some of the following: graph-isomorphism, graph-colorability or even PSPACE-complete problems. Perfect, statistical and computational flavors. Proofs of knowledge.
4. Zero-knowledge arguments. Arguments are proofs whose soundness depends on computational assumptions while the zero-knowledge property usually is perfect.
5. Cryptographic assumptions, examples, discussions and comparisons.
6. Security of encryption. Semantic security (no information is leaked) and non-malleability (cannot produce encryptions of related messages). Possibly a system by Cramer and Shoup.
7. Factorization and discrete logarithms. (7a) A study of the best algorithms on classical computers (quadratic sieve, number field sieve). (7b) A discussion of algorithms for the problems on quantum computers.
8. Multi-party computation. Joint computation of a function on secret inputs. Possibly only in the model of honest and curious participants.
9. Quantum cryptography. How to establish a common random string over a public channel in the quantum world.
10. Integer lattices. (10a) The algorithm of LLL with some application to cryptanalysis, possibly breaking knapsack cryptosystems. (10b) Using hardness assumptions on the computation of shortest vector to create cryptosystems.
11. Cryptanalysis of some symmetric crypto scheme. Possibly the details of linear cryptanalysis of DES.