Can the input to a one way function be pseudorandom?

Question

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.

Answer 1

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)]<n^{-c},}$$

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.