Instructor: Moni Naor

Grader: Hila Dahari

When: Monday 16:15--19:00

Where: 155 Ziskind. First Class Oct 25th 2021

**DESCRIPTION: ** Cryptography deals with methods for protecting the privacy, integrity and functionality of computer and communication systems. The goal of the course is to provide a firm foundation to the construction of such methods. In particular we will cover topics such as notions of security of a cryptosystem, proof techniques for demonstrating security and cryptographic primitives such as one-way functions and trapdoor permutations.

**PREREQUISITES:** Students are expected to be familiar with algorithms, data structures, probability theory, and linear algebra, at an *undergraduate* level. No prior cryptography course will be assumed.

**METHOD OF EVALUATION:** There will be around six to eight homework assignments and a final test. Homework assignments should be turned in on time (usually* two weeks* after they are given)! Try and do as many problems from each set. You may discuss the problems with other students, but the write-up should be individual. There will also be reading assignments. Each student should take notes of (at least) one lecture.

**Exam :** The exam will be a final assignment.

**Class Notes:** Summary of some of the classes

- Lecture 1 (Oct 25th ): History, Entropy, CSAM History, CSAM, Identification
- CSAM
- Benny Pinkas, The Private Set Intersection (PSI) Protocol of the Apple CSAM Detection System
- The Apple PSI System.
- A critique of the idea: Hal Abelson, Ross Anderson, Steven M. Bellovin, Josh Benaloh, Matt Blaze, Jon Callas, Whitfield Diffie, Susan Landau, Peter G. Neumann, Ronald L. Rivest, Jeffrey I. Schiller, Bruce Schneier, Vanessa Teague and Carmela Troncoso, Bugs in our Pockets: The Risks of Client-Side Scanning.

- Lecture 2 (Nov 1st ): Identification and One-way Functions
- Lecture 3 (Nov 8th ): More One-Way Functions and Authentication
- Universal Hashing: Larry Carter and Mark Wegman, Universal Classes of Has Functions 1979 and New hash functions and their use in authentication and set equality
- Gilbert, Macwilliams and Sloane Codes that Detect Deception Bell system Technical journal, 1974.
- A Local One-Way Hash Function (Goldreich):
- Oded Goldreich, Candidate One-Way Functions Based on Expander Graphs 2000.
- Benny Applebaum, A Dichotomy for Local Small-Bias Generators TCC 2012

- Lecture 5 (Nov 15th):
- Lecture 5 (Nov 22nd ):
- Lecture 6 (Nov 29th ):
- Lecture 7 (Dec 6th ): PRFs: Authentication, Encryption and Domain Extension
- Lecture 9 (Dec 20th)
- Leonid Levin and Oded Goldreich, A hard core predicate for anyone way function, Proceedings of the 21st ACM STOC, 1989, pp. 25--32.
- Goldreich Levin from the point of view of list decoding of the Hadamard Code: Lecture my Mary Wooters from Stanford.
- Maria Isabel González Vasco and Mats Näslund, A Survey of Hard Core Functions
- Lenore Blum, Manuel Blum and Michael Shub A Simple Unpredictable Pseudo-Random Number Generator

- Lecture 10 (Dec 27th)
- Mike Luby and Charlie Rackoff, How to Construct Pseudorandom Permutations from Pseudorandom Functions SIAM J. Comput., 17(2), 373–386, 1988
- Moni Naor and Omer Reingold, On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited, ournal of Cryptology volume 12, pages 29–66 (1999).

**HOMEWORK:**

- First Set Due Nov 22nd.
- Second Set Due Dec 20th.

**BIBLIOGRAPHY:** There is no textbook for the course. A lot of relevant material is available in

- Oded Goldreich,
*Foundations of Cryptography*Vol. 1 and 2, Cambridge, 2001 and 2004. - Katz and Lindell,
*Introduction to Modern Cryptography, 2nd Edition* - Lindell, Tutorials on the Foundations of Cryptography

**Online Courses and Material:**

- Boaz Barak, An Intensive Introduction to Cryptography, Harvard University
- Gil Segev, Cryptography Fall 2016/17, Hebrew University
- Mihir Bellare and Phillip Rogaway Introduction to Modern Cryptography
**Lecturer**: Jonathan Katz,**University**: Maryland link- Yehuda Lindell, Foundations of Cryptography (Bar-ilan)
- Manoj Prabhakaran, Theoretical Foundations of Cryptography UIUC
- Ran Canetti, Foundations of Cryptography – Tel Aviv
- Nir Bitansky Foundations of Cryptography – Tel Aviv
- Victor Shoup, A Computational Introduction to Number Theory and Algebra Cambridge University Press
- Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography
- Restricted to Weizmann users: Katz-Lindell writeup
- Old Foundation of Cryptography Course (Moni Naor) webpage and another one and another one Theoretical Cryptography - 2011/12 .

**SLIDES:**

- Moni Naor and Omer Reingold,
Crypto'98*From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs,**.**Abstract , Postscript , gzipped Postscript .* - Ronen Gradwohl, Moni Naor, Benny Pinkas and Guy Rohblum,
Abstract , Postscript , gzipped Postscript , PDF*Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles,*

- M. Blum. Coin flipping by telephone. In Proceedings of IEEE Spring Computer Conference, pages 133--137. IEEE, 1982.
- M. Blum and S. Micali, How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits, SIAM J. Comput. 13(4), 1984, pages 850-864.
- W. Diffie and M. Hellman, New Directions in Cryptography , IEEE Trans. on Information Theory, 1976.
- O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions , Journal of the ACM (JACM), Volume 33 , Issue 4 (October 1986), Pages: 792 - 807.
- S. Goldwasser and S. Micali, Probabilistic Encryption, Journal of Computer and System Sciences, 28:270-299, 1984. link
- S. Goldwasser, S. Micali, and C. Rackoff, The Knowledge Complexity of Interactive Proof Systems . SIAM J. of Computing, vol. 18, no. 1, 1989, Pages 186-208.
- S. Goldwasser, S. Micali, and R. L. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM J. on Computing, vol 17(2) 1988, pages 281-308.
- M. Luby and C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM J. on Computing, vol 17(2) 1988, pages 373 - 386.
- R.L. Rivest, A. Shamir, and L.M. Adleman, A Method for Obtaining Digital-Signatures and Public-Key Cryptosystems, Comm. ACM 21(2): 120-126 (1978).
- Michael O. Rabin, How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.
- C. Shannon, Communication Theory of Secrecy Systems, link
- C. Shannon,
*A mathematical Theory of Communication,**Bell System Technical Journal,*vol. 27, pp. 379-423 and 623-656, July and October, 1948. link