### 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:
http://cs.ioc.ee/ewscs/2009/