Structural Complexity II: Advanced Topics
Monday, 16:00, Fontanka 27, room 203
Prerequisites 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.
(Worstcase) oneway functions and permutations.
Trapdoor permutations.
Publickey 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 oneway 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: lecture601.ps
and lecture602.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,
Polynomialtime algorithms for prime factorization and
discrete logarithms on a quantum computer,
SIAM Journal of Computing 26, pp. 14841509 (1997).
Some literature:

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, 19962001).
 Oded Goldreich,
Foundations of Cryptography,
Fragments of
Volume I
and
Volume II.
Back to homepage