Instructor: Periklis A. Papakonstantinou [ppapakons.tsinghua.old@gmail.com] 
Teaching assistant: Fu Li 
Lectures: Friday 1.304.05pm (3x45min) at TX117 
Office hours: Friday 11am12pm (or by appointment), FIT 46087 
Jun 21 
The sixth problemset is out (deadline: Saturday, July 4th) 
Remark: check out regularly the Handouts Page for readings and homeworks
* click on the lecture date for reading material
* click on the lecture date for reading material
Date  Topic 


Introduction to the art of practical cryptanalysis 

PublicKey Systems. DiffieHellman keyexchange. Security definitions for keyexchange and
PublicKey Encryption systems. ElGamal encryption Why we cannot rely in constructing PKE on Private Key Primitives? 

More on collision resistant hash functions Blockciphers and PRPs in the realworld 

Message Authentication Schemes: how to implement them, efficient implementations, modes and MACs Hash functions and their significance in cryptography 

Modes of privatekey encryption: their security, significance, practical implications 

Practical uses of PRFs and PRPs 

Back to pseudorandomness: practical constructions. Efficiency issues in the real world 

Finishup the full proof of GoldreichLevin Generic constructions of PRGs, PRFs, PRPs, PrivateKey Encryption Discussion about the relation of OWFs and OWP 

The fundamental theorem of privatekey cryptography: discussion and importance GoldreichLevin and its full proof (part 1) 

P vs NP and the existence of PrivateKey Cryptography The hybrid argument: discussion, examples, BlumMicali 

More on uniformity vs nonuniformity An example of using measure concentration in computational arguments: derandomizing nonuniform families of circuits Generic vs Concrete cryptographic assumptions. The main objects of privatekey encryption 

Digression: a crash course in computational complexity. Turing Machines, families of circuits, notions of efficiency, and their relations. Uniform vs nonuniform adversaries. 

More on perfectly secure privatekey encryption  permutations and Shannon's original work Introduction to privatekey cryptography based on computational assumptions 

What is Cryptography, what is Security, and what is this course about? Introduction to information theoretic cryptography 
Readings for the 14th lecture:
 TBA
Readings for the 13th lecture:
 Chapters 9 and 10 from KatzLindel
Readings for the 12th lecture:
 Chapter 5 from KatzLindel
 Revise everything we saw so far: Chapters 16
Readings for the 11th lecture:
 Chapter 4 from KatzLindel
Readings for the 10th lecture:
 Chapter 3 from KatzLindel
Readings for the 9th lecture:
 Chapter 3 from KatzLindel
Readings for the 8th lecture:
 Chapter 3 from KatzLindel
Readings for the 7th lecture:
 Chapter 6 from KatzLindel
 For students with more intense interest in cryptography: "Foundations of Cryptography, Volume I", by Oded Goldreich. Read chapters 2 and 3.
Readings for the 6th lecture:
 Chapter 6 from KatzLindel
 For students with more intense interest in cryptography: "Foundations of Cryptography, Volume I", by Oded Goldreich. Read chapters 2 and 3.
Readings for the 5th lecture:
 Chapter 6 from KatzLindel
Readings for the 4th lecture:
 ChernoffHoeffding inequalities. Pairwise independent random variables and weak concentration
Readings for the 3rd lecture:
 Use any source you wish to study: polynomial running time = polynomial (uniform) circuit size

First half of the 3rd Chapter of Katz Lindel.
Readings for the 2nd lecture:
 The 2nd chapter from KatzLindel

First half of the 3rd Chapter of Katz Lindel.
Remark: you must have prepared the prerequisites on theory of computing from last week
Readings for the 1st lecture:
 The 1st chapter from KatzLindel
 Prerequisite reading: basic models of computation: (i) Turing Machines & Circuits, from Sipser's textbook, (ii) elements of discrete probability & combinatorics, (iii) algebra & linear algebra
 Read Schneier's highlevel article on readings for cryptanalysis