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. |