3
$\begingroup$

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.

| improve this question | | | | |
$\endgroup$
4
$\begingroup$

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.

| improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.