Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-005 | 13th January 2012 09:49

A remark on one-wayness versus pseudorandomness


Authors: Periklis Papakonstantinou, Guang Yang
Publication: 20th January 2012 08:51
Downloads: 3446


Every 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.

ISSN 1433-8092 | Imprint