Instructor: Moni Naor

Grader: Hila Dahari

When: Monday 13:00--16:00

Where: 155 Ziskind

**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 in class.

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

- Lecture 1 (Nov 5th): History, Entropy, PSR, History, Entropy, Identification, PSR

**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:**

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

**HOMEWORK:**

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