Group:Student Seminar
Title: A remark on one-wayness versus pseudorandomness
Speaker: Guang Yang University
Time: 2011-10-18 16:00-2011-10-18 17:00
Venue: FIT 1-222


Every pseudorandom generator is in particular a one-way function. If we consider only part of the output of a pseudorandom generator is it still one-way? Somewhat surprisingly the answer is no in a general setting formalizing the question. In particular, assuming the existence of a pseudorandom generator of any stretch and hardness, we construct a pseudorandom generator of the same stretch and hardness, where an O(n/logn)-large random projection of the output is not one-way. More generally, the same holds if we sample a linear operator and apply it on the output of such a pseudorandom generator G. Specifically, let n be the seed length, l(n)>n the output length of G and let M_R in {0,1}^{m(n) x l(n)}, m(n)=O(n/log n), be a linear operator sampled in polynomial time using randomness R. Then, f(x,R) = (M_R G(x), R) is not even weakly one-way. This formulation in particular rules out the application of universal families of hash functions and randomness extractors.


Joint work with Periklis Papakonstantinou