ECCC-Report TR12-005https://eccc.weizmann.ac.il/report/2012/005Comments and Revisions published for TR12-005en-usFri, 20 Jan 2012 08:51:00 +0200
Paper TR12-005
| A remark on one-wayness versus pseudorandomness |
Periklis Papakonstantinou,
Guang Yang
https://eccc.weizmann.ac.il/report/2012/005Every pseudorandom generator is in particular a one-way function. If we only consider part of the output of the
pseudorandom generator is this still one-way? Here is a general setting formalizing this question. Suppose
$G:\{0,1\}^n\rightarrow \{0,1\}^{\ell(n)}$ is a pseudorandom generator with stretch $\ell(n)> n$. Let $M_R\in\{0,1\}^{m(n)\times \ell(n)}$ be a linear operator computable in polynomial time given randomness $R$. Consider the function
$$F(x,R)=\big(M_R G(x), R \big)$$
We obtain the following results.
- There exists a pseudorandom generator such that for every constant $\mu<1$ and for an arbitrary polynomial time computable $M_R\in\{0,1\}^{(1-\mu)n\times \ell(n)}$, $F$ is not one-way. Furthermore, our construction yields a tradeoff between the hardness of the pseudorandom generator and the output length $m(n)$. For example, given $\alpha=\alpha(n)$ and a $2^{cn}$-hard pseudorandom generator we construct a $2^{\alpha\; cn}$-hard pseudorandom generator such that $F$ is not one-way, where $m(n)\leq \beta n$ and $\alpha+\beta = 1 - o(1)$.
- We show this tradeoff to be tight for 1-1 pseudorandom generators. That is, for any $G$ which is a $2^{\alpha n}$-hard 1-1 pseudorandom generator, if $\alpha+\beta=1+\epsilon$ then there is $M_R\in\{0,1\}^{ \beta n\times \ell(n)}$ such that $F$ is a $\Omega(2^{\epsilon n})$-hard one-way function.Fri, 20 Jan 2012 08:51:00 +0200https://eccc.weizmann.ac.il/report/2012/005