Foundations of Cryptography  Winter 2006/7
Instructor: Moni Naor
Grader: Gil Segev
When:
Wednesday 16:0018:00
Where: Ziskind 261
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 oneway 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 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 writeup 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:
HOMEWORK:

Homework 1. ps. Solution to Question 1 pdf

Homework 2. ps

Homework 3. ps Due Dec 20th

Homework 4. ps Due Jan 7th 2007

Homework 5. ps Due Jan 28th 2007

Homework 6. ps Due Feb 11th 2007

Take home exam . ps Due March 11th 2007
HANDOUTS:

Lecture 1: Identification, Entropy and Oneway functions. (ppt)

Lecture 2: Oneway functions are essential for identification. Amplification: from weak to strong oneway function. (ppt)

Lecture 3: Oneway on their iterates. Authentication and Universal Hash Functions.
(ppt)

Lecture 4: Universal Oneway Hash Functions (UOWHFs) .
(ppt)

Lecture 5: Signatures Scheme Definition and Construction from UOWHFs. Computational Indistinguishability and Pseudorandom Generators.
(ppt)

Lecture 6: Pseudorandom generators, Hardcore predicates, GoldreichLevin Theorem.
(ppt)

Lecture 7: Gil Segev, Message Authentication in the Manual Channel Model.
(ppt)
 Lecture 8: Applications of hardcore predicates, Composition, Pseudorandom Functions.
(ppt)
 Lecture 9: Pseudorandom functions existence and applications, Pseudorandom permutations.
(ppt)
 Lecture 10: Construction of
Pseudorandom permutations, notions of security for encryption schemes.
(ppt)
 Lecture 11:
Notions of security for encryption schemes. Examples of encryption schemes.
(ppt)
 Lecture 12:
Commitments Schemes and ZeroKnowledge.
(ppt)
 Lecture 13:
ZeroKnowledge Variants.
(ppt)
 Lecture 14:
Nonmalleability, Chosen Ciphertext Attacks, The CramerShoup Cryptosystem.
(ppt)
 Lecture 15:
Oblivious Transfer and Secure Function Evaluation.
(ppt)
Reading assignment:

Moni Naor and Omer Reingold, From
Unpredictability to Indistinguishability: A Simple Construction of
PseudoRandom Functions from MACs, Crypto'98.
Abstract ,
Postscript ,
gzipped Postscript .
 Ronen Gradwohl, Moni Naor and Benny Pinkas,
Cryptographic and Physical ZeroKnowledge 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 133137. IEEE, 1982.
 M. Blum and S. Micali,
How to Generate Cryptographically Strong Sequences of PseudoRandom Bits, SIAM J. Comput. 13(4), 1984, pages
850864.
 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:270299, 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 186208.

S. Goldwasser, S. Micali, and R. L. Rivest,
A Digital Signature Scheme Secure Against Adaptive ChosenMessage Attacks,
SIAM J. on Computing, vol 17(2) 1988, pages 281308.

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
DigitalSignatures and PublicKey Cryptosystems, Comm. ACM 21(2): 120126 (1978).

Michael O. Rabin, How to exchange secrets by oblivious transfer. Technical Report TR81, 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. 379423 and 623656, July and
October, 1948. link