Fundamentals of Cryptography (Spring 2015)

 
Instructor: Periklis A. Papakonstantinou [ppapakons.tsinghua.old@gmail.com]
Teaching assistant: Fu Li
Lectures: Friday 1.30-4.05pm (3x45min) at TX117
Office hours: Friday 11am-12pm (or by appointment), FIT 4-608-7










Jun 21
   
The sixth problem-set 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


Date Topic
Introduction to the art of practical cryptanalysis
Public-Key Systems. Diffie-Hellman key-exchange. Security definitions for key-exchange and Public-Key Encryption systems. El-Gamal encryption
Why we cannot rely in constructing PKE on Private Key Primitives?
More on collision resistant hash functions
Block-ciphers and PRPs in the real-world
Message Authentication Schemes: how to implement them, efficient implementations, modes and MACs
Hash functions and their significance in cryptography
Modes of private-key encryption: their security, significance, practical implications
Practical uses of PRFs and PRPs
Back to pseudorandomness: practical constructions. Efficiency issues in the real world
Finish-up the full proof of Goldreich-Levin
Generic constructions of PRGs, PRFs, PRPs, Private-Key Encryption
Discussion about the relation of OWFs and OWP
The fundamental theorem of private-key cryptography: discussion and importance
Goldreich-Levin and its full proof (part 1)
P vs NP and the existence of Private-Key Cryptography
The hybrid argument: discussion, examples, Blum-Micali
More on uniformity vs non-uniformity
An example of using measure concentration in computational arguments: derandomizing non-uniform families of circuits
Generic vs Concrete cryptographic assumptions. The main objects of private-key encryption
Digression: a crash course in computational complexity. Turing Machines, families of circuits, notions of efficiency, and their relations. Uniform vs non-uniform adversaries.
More on perfectly secure private-key encryption -- permutations and Shannon's original work
Introduction to private-key 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 Katz-Lindel
Readings for the 12th lecture:
  • Chapter 5 from Katz-Lindel
  • Revise everything we saw so far: Chapters 1-6
Readings for the 11th lecture:
  • Chapter 4 from Katz-Lindel
Readings for the 10th lecture:
  • Chapter 3 from Katz-Lindel
Readings for the 9th lecture:
  • Chapter 3 from Katz-Lindel
Readings for the 8th lecture:
  • Chapter 3 from Katz-Lindel
Readings for the 7th lecture:
  • Chapter 6 from Katz-Lindel
  • 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 Katz-Lindel
  • 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 Katz-Lindel
Readings for the 4th lecture:
  • Chernoff-Hoeffding 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 Katz-Lindel
  • 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 Katz-Lindel
  • 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 high-level article on readings for cryptanalysis