Structural Complexity and Cryptography

Semester II. Structural Cryptography.

The lecture notes are put on a "post-moderating" basis, that is, they are posted mostly unedited right when received. The dates point to the last substantial changes.

defs.tex (you need this file to compile .tex sources).

Lecture 1 (March 13; exercises as of April 23; updated on March 11, 2008):
TeX source, Postscript file, compressed Postscript file, PDF file.
Worst-case, weak and strong one-way functions. Families of one-way functions.
Lecture 2 (April 2):
TeX source, Postscript file, compressed Postscript file, PDF file.
Candidate one-way functions. Levin's universal one-way function. Trapdoor permutations. Hardcore predicate from any one-way function.
Lecture 3 (April 2):
TeX source, Postscript file, compressed Postscript file, PDF file.
Bitwise encryption: PKCS, secure PKCS, complete PKCS with error, secure PKCS from any trapdoor permutation.
Lecture 4 (April 18):
TeX source, Postscript file, compressed Postscript file, PDF file.
General encryption: Indistinguishability versus semantic security. Pseudo-random generators. A more efficient secure (general) PKCS from any length-preserving trapdoor permutation.
Lecture 5 (April 17):
TeX source, Postscript file, compressed Postscript file, PDF file.
One-way functions from pseudo-random generators. Pseudo-random generators from length-preserving one-way permutations.
Lecture 6 (last (unchecked) addition: April 25):
TeX source, Postscript file, compressed Postscript file, PDF file.
Digital signature schemes.
Lecture 7 (unchecked):
TeX source, Postscript file, compressed Postscript file, PDF file.
Secure function evaluation.

Semester I. Structural Complexity Basics.

This year lazy participants prepared lecture notes of only a few lectures. You may want to check the web pages of my previous course to get older lecture notes and this year additions (other lectures remain in the previous course version, and some of them were different this year).

Questions:

[ .tex ] [ .ps ] [ .ps.gz ] [ .pdf ]

Literature:

Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach.
Madhu Sudan, Course: Advanced Complexity Theory, 2005.
JASS'2006 Course: Proofs and Computers.
Oded Goldreich, Introduction to Complexity Theory. Lecture Notes, Weizmann Institute of Science, 1998-99.
Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
Lane A. Hemaspaandra, Mitsunori Ogihara, The Complexity Theory Companion, Springer, 2002.
Kitaev, Shen, Vyalyi (in Russian), Klassicheskie i kvantovye vychislenija, MTsNMO, 1999.

Back to Home Page