Foundations and Advances in Cryptography

Spring 2013

ITCS @ IIIS, Tsinghua University
Instructor: Periklis A. Papakonstantinou []
Teaching assistants: Hongyu Liang
Lectures: Monday 9.50am-12.10pm (2.5x45min) @ FIT 1-222
Office hours: Monday 12.20-1.20pm (or by appointment), FIT 4-608-7


[May 26] The 3rd problem-set is out!

Discussion forum

Handouts, problem-sets, and links



Date Topic
May 27 Efficient cryptographic construction using weak pseudorandom objects: An introduction to theory and applications of expander graphs.
May 20 The Hastad-Impagliazzo-Levin-Luby (HILL): pseudorandom generators from any one-way function (this is the last part of the Fundamental Theorem of Private-Key Cryptography)
May 13 The details of the Impagliazzo-Rudich impossibility result
Back to private-key primitives: the left-over hash lemma.
May 6 Finish-up the hardness amplification proof
Black-box and non-black-box constructions: the Impagliazzo and Rudich impossibility result of basing public-key cryptography on public-key cryptography
Apr 29 Luby-Rackoff: constructing pseudorandom permutation generator.
Yao's XOR lemma. Weak vs strong one-way functions
Apr 22 The Mansour-Kushilevitz (Fourier analysis based) proof for GL
Apr 15 More on Fourier analysis on the boolean cube
Apr 12 Introduction to Fourier Analysis on the boolean cube: towards a 2nd proof for GL
Apr 8 The "pairwise-independence"-based proof of the Goldreich-Levin (GL) Theorem
Apr 1 Hybrid arguments (add-on to the 2nd lecture). Yao's unpredictability implies pseudorandomness. An overview of the Goldreich-Levin hardcore bit theorem.
Mar 25 Types of adversaries. A diversion to Computational Complexity. Circuits vs Turing Machines: Cook's theorem. Non-uniformity and derandomization.
Mar 15 P vs NP and Cryptography, average-case forms of NP. How to structure a typical argument in Cryptography? From pseudorandom generators to one-way functions. From one-time pad to private-key encryption. Arbitrary polynomial stretch pseudorandom generators.
Mar 11 Course Overview
Introduction to theoretical cryptography. Private-key Encryption, Pseudorandom generators, one-way functions