Presentations

Procedure: Everyone who attends will be required to give a 30-minute talk about a paper which implements some standard tool we have discussed based on a concrete complexity assumption. Below are some examples of this kind of paper. You may choose one from the list or propose another paper. When you have done so, email your proposed paper and talk date to the instructor, and if there are no conflicts, you will be added to the class schedule.

Moni Naor and Omer Reingold, Number-Theoretic constructions of efficient pseudo-random functions , Extended abstract in: Proc. 38th IEEE Symp. on Foundations of Computer Science, 1997, pp. 458-467
Russell Impagliazzo and Moni Naor, Efficient Cryptographic Schemes Provably as Secure as Subset Sum , J. of Cryptology 9(4):, 1996, pp. 199--216 .
Oded Regev. New Lattice Based Cryptographic Constructions , to appear in STOC 2003.
Shafi Goldwasser and Silvio Micali, Probabilistic Encryption & How to Play Mental Poker Keeping Secret All Partial Information, in Proc. 14th STOC, 1982, pp. 365-377.
Lenore Blum, Manuel Blum, and Michael Shub, A Simple Unpredictable Pseudo-Random Number Generator , SIAM J. Comput. 15(2): 364-383 (1986).
Ron Cramer and Victor Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, in Proc. Crypto '98.
Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes , In: Eurocrypt 99.
Manuel Blum and Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits . SIAM J. Comput. 13(4): 850-864 (1984).
Daniele Micciancio, Improved cryptographic hash functions with worst-case/average-case connection ,
Proceedings of the 34th STOC, 2002. pp. 609-618.
Danielie Micciancio, Generalized compact knapsaks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions, 43rd FOCS, 2002. pp. 356-365