Security preserving amplification of hardness
Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman · 2002
The task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted only on a negligible function of the range) is considered. The previously known transformation does not preserve the security (i.e. the running time of the inverting algorithm) within any polynomial. Its resulting function, F(x), applies the weak one-way function to many small (of length mod x mod /sup theta /, theta>