Theoretical Cryptography - Winter 2011/12
Instructor: Moni Naor
When: Tuesday 14:00--16:00
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
Goldreich, Foundations of Cryptography
Vol. 1 and 2, Cambridge, 2001 and 2004.
Online Courses and Material:
Naor and Omer Reingold,
From Unpredictability to Indistinguishability:
A Simple Construction of Pseudo-Random Functions from MACs, Crypto'98.
, gzipped Postscript .
- Ronen Gradwohl,
Moni Naor and Benny Pinkas, Cryptographic and Physical
Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles, Abstract
, gzipped Postscript , PDF
History: Key Papers
- 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,
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,
Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks,
SIAM J. on Computing, vol 17(2) 1988, pages
- 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):
- 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