-----------

Tel-Aviv University - Computer Science Colloquium

Sunday, May 23, 14:15-15:15

COFFEE at 14:00

Room 309
Schreiber Building
-----------

Pseudo-Random Functions, Permutations and Synthesizers

Omer Reingold

The Weizmann Institute of Science

Abstract:

Pseudo-random functions and permutations model the key components of private-key cryptography. They allow parties who share a common key to send secret messages to each other, identify themselves and authenticate their messages. In addition, these functions have many other applications, essentially in any setting that calls for a random function that is provided as a black-box.

In recent years we have presented several constructions of pseudo-random functions and permutations. The main objective of this research was to

obtain efficient constructions based on standard intractability assumptions (where efficiency refers both to the sequential and parallel time-complexity of the computation). Significant progress towards this goal was achieved by introducing a new cryptographic primitive called a pseudo-random synthesizer. Among the additional results of this research:

i) A simple Zero-Knowledge proof of the value of our functions.
ii) A very efficient pseudo-random mode of operation for block-ciphers.
Furthermore, our constructions have implications to computational learning theory and lower bounds for circuit complexity.

This talk will survey some of the applications of pseudo-random functions and permutations, and some of our results. In addition, we will discuss several open questions of the field.

Most of this talk is based on joint research with Moni Naor.

-----------

For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html