Course Schedule

Weekday Regular Schedule

Group Type Hours Location
01 Lecture Tue 15-18 Dan David 201
02 Recitation Thu 10-11 Software Engineering 104
03 Recitation Thu 11-12 Software Engineering 104

Lectures and Recitations

Week Dates Crypto Subject Mathematics Background Recitation
1 Oct 15,17 Popular introduction to Modern Crypto;
Administrativia, course topics, etc. Lecture1
Group Theory and Lagrange Theorem. Computational Assumptions, One-Way Functions, Discrete Logarithms in $\mathbb{Z}_p^*$ Recitation1. A (non-mandatory) exercise on groups Groups
2 Oct 22,24 Perfect and computational indistinguishably. Pseudo random generators and one way functions. Stream Ciphers. Lecture2 (updated Oct. 25) More group theory. The ring $(\mathbb{Z}_m,+_{\pmod m},\cdot_{\pmod m})$. Indistinguishability and Pseudo-Randomness, Computational and Decisional Diffie-Hellman. Recitation2.
3 Oct 29,31 Stream Ciphers. Pseudo random generators and bit commitment. Pseudo random functions and permutations. Block Ciphers. Lecture3 (updated Nov. 2) Euler totient function $\phi(n)$. The multiplicative group $\mathbb{Z}^*_m$. Euclid's gcd: Time analysis. Decisional Diffie-Hellman isn't hard in $\mathbb{Z}_p^*$ , and Quadratic Residues. Recitation3.
4 Nov 5,7 Finite fields. Block Ciphers. Feistal networks. DES and AES. Iterated ciphers. Lecture4 (updated Nov. 12) Extended gcd Python code. Hardcore bits. Blum-Micali HCB for DL Recitation4.
5 Nov 12,14 Message authentication codes. Discrete logarithm and Diffie Hellman key exchange over a public network Lecture5 (updated Nov. 13) Finite fields arithmetic. Collision-resistant hashing Recitation5.
6 Nov 19,21 Primality testing. The RSA public key cryptosystem. Lecture6 The prime numbers theorem. Public-key encryption, El-Gamal, CPA-security Recitation6.
7 Nov 26,28 The RSA public key cryptosystem. Quadratic residues and non residues in $\mathbb{Z}^*_{pq}$. The quadratic residuosity assumption, and a public key probabilistic encryption scheme based on it. Lecture7 (updated Nov. 27) CRT (Cathode Ray Tube, aka Chinese Remainder Theorem). Partially Homomorphic Encryption, Private Information Retrieval Recitation7.
8 Dec 3,5 Self reducibility of RSA, revisited. Digital signature schemes. Pollard's $\rho$ algorithm for integer factoring Lecture8 (updated Dec. 14) Digital signatures from OWFs (and CRHs) Recitation8.
9 Dec 12 Secret sharing Lecture9 Lagrange polynomial interpolation
10 Dec 17, 19 Secret sharing. Interactive proof systems. Zero knowledge proofs Lecture10. Power point presentation by Prof. Safra [http://www.cs.tau.ac.il/~safra/Complexity/ZKP.ppt] Distribution of $t-1$ shares ZK Proofs. The GMW 3COL protocol (the malicious verifier case) Recitation10.
11 Dec 24, 26 Guest lecture: Zvika Brakerski on fully-homomorphic encryption Lecture11. ZK from FHE Recitation11.
12 Dec 31, Jan 2 Secret sharing and error correction codes. Multi party computation: Models, security requirements. Yao's millionaires problem. Oblivious transfer and Yao's garbled circuit evaluation Lecture12. Oblivious Transfer. The EGL protocol. Recitation12.
13 Jan 7,9 Fast verification of long computations and delegation Lecture13. The story of PCPs by Ryan O'donnel
14 Jan 14,16 For your ears only: RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis Guest Lecture by Daniel Genkin (10MB file). Concluding remarks. Example questions towards the exam.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License