Structural Complexity II: Advanced Topics

Monday, 16:00, Fontanka 27, room 203

Pre-requisites can be learned from my previous course.

Lecture notes (in Russian) for Spring 2003 course (updated in April 2005):

• defs.tex (you need this file to compile .tex sources).
  
  
• Lecture 1: TeX source, Postscript file, compressed Postscript file, PDF file.
  (Worst-case) one-way functions and permutations. Trapdoor permutations. Public-key encryption. RSA.
• Lecture 2: TeX source, Postscript file, compressed Postscript file, PDF file.
  Security of encryption (semantics security vs indistinguishability).
• Lecture 3: TeX source, Postscript file, compressed Postscript file, PDF file.
  Strongly one-way functions and trapdoor permutations. Hardcore predicates. A cryptosystem that encrypts just one bit.
• Lecture 4: TeX source, Postscript file, compressed Postscript file, PDF file.
  Pseudorandom generators. A more efficient cryptosystem.
• Lecture 5: TeX source, Postscript file, compressed Postscript file, PDF file.
  Digital signatures.
• Lecture 6: Source: TeX file and pictures: lecture6-01.ps and lecture6-02.ps; Postscript file, compressed Postscript file, PDF file.
  Quantum computation. Grover's algorithm.
• Lecture 7: notes will not appear. Please use Shor's paper instead:
  Peter Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal of Computing 26, pp. 1484-1509 (1997).

Some literature:

1. A very good (and very large) survey on cryptography (caution: it contains a lot of typos):
   Shafi Goldwasser and Mihir Bellare, Lecture Notes on Cryptography (MIT, 1996-2001).
2. Oded Goldreich, Foundations of Cryptography, Fragments of Volume I and Volume II.