Structural Complexity and Cryptography
Semester II. Structural Cryptography.
The lecture notes are put on a "postmoderating" 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.
Worstcase, weak and strong oneway functions. Families of oneway functions.
 Lecture 2 (April 2):
TeX source,
Postscript file,
compressed Postscript file,
PDF file.
Candidate oneway functions.
Levin's universal oneway function.
Trapdoor permutations.
Hardcore predicate from any oneway 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.
Pseudorandom generators.
A more efficient secure (general) PKCS from any lengthpreserving trapdoor permutation.
 Lecture 5 (April 17):
TeX source,
Postscript file,
compressed Postscript file,
PDF file.
Oneway functions from pseudorandom generators.
Pseudorandom generators from lengthpreserving oneway 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, 199899.

Christos H. Papadimitriou, Computational Complexity, AddisonWesley, 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