Foundations of Cryptography - Winter 2019/20

Instructor: Moni Naor

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

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

Online Courses and Material:

HOMEWORK:

SLIDES:

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

History: Key Papers in Cryptography:

• 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