Nov 23

Séminaire du LIAFA mardi prochain à 11h

séminaire du LIAFA mardi prochain à 11h

Date: 2011-11-29/2011-11-29 [11:00]

Author: Thomas Holenstein (ETH Zurich)

Title: Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls

Summary:
We show that a black-box construction of a pseudorandom
generator from a one-way function needs to make Omega(n/log(n))
calls to the underlying one-way function. The bound even holds if the
one-way function is guaranteed to be regular. In this case it matches
the best known construction due to Goldreich, Krawczyk, and Luby (SIAM
J. Comp. 22, 1993), which uses O(n/log(n)) calls.


Le séminaire se tient le mardi à 11h00, Salle 1D06.
175 rue du Chevaleret (angle rue Clisson), XIIIème arrt.
(Métro Chevaleret ou Bibliothèque F. Mitterrand)