# Can the input to a one way function be pseudorandom?

I know that normally a one-way function takes in a completely random input, but can a one-way function take in something pseudorandom instead of completely random? Will it still be a one-way function? Intuitively it seems like it would be, but I don't actually know why.

The definition of a one=way function, according to Wikipedia, is:

A function $$f : \{0,1\}^* \to \{0,1\}^*$$ is one-way if $$f$$ can be computed by a polynomial time algorithm, but any polynomial time randomized algorithm $$F$$ that attempts to compute a pseudo-inverse for $$f$$ succeeds with negligible probability. That is, for all randomized algorithms $$F$$ , all positive integers $$c$$ and all sufficiently large $$n = \mathrm{length}(x)$$ ,

$${\displaystyle \Pr[f(F(f(x)))=f(x)]

where the probability is over the choice of $$x$$ from the discrete uniform distribution on $$\{0,1\}^n$$, and the randomness of $$F$$.

The definition doesn't say anything about pseudorandom choices of $$x$$, and this means that we do not have to contemplate such choices when assessing whether $$f$$ is one-way. So your question if $$f$$ would "still be a one-way function" if $$x$$ is drawn pseudorandomly has a trivial "yes" answer.

The question I think you're actually interested in is this: if $$f$$ is a one-way function but $$x$$ in the definition above is drawn from some pseudorandom distribution $$D$$ over $$\{0,1\}^n$$, could there exist a polynomial time randomized algorithm $$F$$ that finds a pseudo-inverse of $$f(x)$$ with non-negligible probability? Well, if there is such an $$F$$, then we could use it to construct a distinguisher for $$D$$:

1. Accept an input $$x$$;
2. Output $$1$$ if $$f(F(f(x))) = f(x)$$, $$0$$ otherwise.

Now:

• Since we assumed that $$F$$ succeeds with non-negligible probability for $$x$$ drawn from $$D$$, in that case the distinguisher will output $$1$$ with non-negligible probability;
• Since we assumed that $$f$$ is one way, this means when $$x$$ is random $$F$$ outputs $$1$$ with negligible probability;
• The difference between a negligible probability and a non-negligible one is non-negligible.

But that contradicts our assumption that $$D$$ is pseudorandom, so there cannot be such an $$F$$. In plainer English: feeding pseudorandom inputs to a one-way function is not significantly likelier in practice to pick "bad" (easy to invert) inputs than choosing inputs at random.