Rosario Gennaro
IBM T.J. Watson Research Centre
New York, USA
Provable Security and Efficiency in Cryptographic Constructions
Abstract
Some of the classical results in Modern Cryptography are elegant and beautiful constructions of cryptographic tools from basic complexity-theoretic primitives e.g. based on the Goldreich-Levin proof that every one-way function has a hard-core predicate:
- the Blum-Micali-Yao construction of pseudo-random number generators based on one-way permutations;
- the Naor-Yung construction of universal one-way hashing also from one-way permutations;
- the Goldwasser-Micali construction of probabilistic encryption based on trapdoor permutations.
The above schemes are examples of black-box constructions a general methodology to build cryptographic primitives. In this class we will review the above classical results, the black-box construction methodology and then show that for such type of constructions the above schemes are optimal in terms of their efficiency.
Course materials
- R. Gennaro. Provable security and efficiency in cryptographic constructions. Lecture slides for EWSCS 2009. 2009. [ppt]
- O. Goldreich. Foundations of Cryptography, Vol. 1: Basic Techniques. Cambridge Univ. Press, 2001. Secs. 2.1-2.5 and 3.1-3.4.
- R. Gennaro, L. Trevisan. Lower bounds on the efficiency of generic cryptographic constructions. In Proc. of 41st Ann. Symp. on Foundations of Computer Science, FOCS 2000 (Redondo Beach, CA, Nov. 2000), pp. 305-313, IEEE CS Press, 2000 (preprint version).
- R. Gennaro. An improved pseudo-random number generator based on the discrete logarithm problem. J. of Cryptology, v. 18, n. 2, pp. 91-110, 2005 (preprint version).
Last changed
March 9, 2009 0:24 EET
by
local organizers, ewscs09(at)cs.ioc.ee
EWSCS'09 page:
//cs.ioc.ee/ewscs/2009/