Instructor: Moni Naor

Grader:

When: Tuesday 14:00--16:00

Where:
FGS B (Midrasha Building)

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

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

**Online Courses and Material:**

- 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
- Restricted to Weizmann users: Katz-Lindell writeup
- Old Foundation of Cryptography Course (Moni Naor) webpage and another one

**HOMEWORK:**

**SLIDES:**

- Lecture 1: Identification, Entropy and One-way functions. (ppt)
- Lecture 2: One-way functions are
**essential**for identification.**Amplification**: from weak to strong one-way functions (ppt) - Lecture 3:
**Amplification**: from weak to strong one-way, One-way on it iterates, Authentication

- 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 and Benny Pinkas,
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