We prove complexity lower bounds for the tasks of hardness amplification of one-way functions and construction of pseudo-random generators from one-way functions, which are realized non-adaptively in black-box ways. First, we consider the task of converting a one-way function f : {0, 1}~n → {0, 1}~m into a harder one-way function f : {0,1}~n → {0,1}~m, with n, m ≤ poly(n), in a black-box way. The hardness is measured as the fraction of inputs any polynomial-size circuit must fail to invert. We show that to use a constant-depth circuit to amplify hardness beyond a polynomial factor, its size must exceed 2~(poly(n)), and to amplify hardness beyond a 2~(o(n)) factor, its size must exceed 2~(2~(o(n))). Moreover, for a constant-depth circuit to amplify hardness beyond an n~(1+o(1)) factor in a security preserving way (with n = O(n)), it size must exceed 2~(n~(o(1))). Next, we show that if a constant-depth polynomial-size circuit can amplify hardness beyond a polynomial factor in a weakly black-box way, then it must basically embed a hard function in itself. In fact, one can derive from such an amplification procedure a highly parallel oneway function, which is computable by an NC~0 circuit (constant-depth polynomial-size circuit with bounded fan-in gates). Finally, we consider the task of constructing a pseudo-random generator G : {0, 1}~n → {0, 1}~m from a strongly one-way function f : {0,1}~n → {0, 1}~m in a black-box way. We show that any such a construction realized by a constant-depth 2~(n~(o(1))) -size circuit can only have a sublinear stretch (with m — n = o(n)).
展开▼
