讨论组:学生讲座
标题:A remark on one-wayness versus pseudorandomness
演讲人: 杨光 University
时间: 2011-10-18 16:00-2011-10-18 17:00
地点: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