Strong one-way functions: a remark on the definition

61 Views Asked by At

Notation: $\Sigma^k$ is the set of $k$-strings on the alphabet $\Sigma$; $\Sigma^\ast$ is the set of all finite dimensional strings on the alphabet $\Sigma$.


In the context of computer-science a strong one-way function is generally defined as follows:

A function $f:\Sigma^{\ast}\longrightarrow\Sigma^\ast$ where $\Sigma=\{0,1\}$is a strong one-way function if the following conditions holds:

1) $f$ can be calculated in polynomial time.

2) If $M$ is a probabilistic Turing machine that inverts $f$, then for every polynomial $q:\mathbb N\longrightarrow\mathbb N$ there is a $k_q\in\mathbb N$ such that for every $k>k_q$ we have that $$\textrm{Pr}\bigg(M\left(f(x)1^k\right)\in f^{-1}(f(x))\bigg)\le \frac{1}{q(k)}$$ for $x$ randomly chosen in $\Sigma^k$.


Many book emphasize the fact that $x$ is randomly chosen amongst all strings of length $k$. But what is the difference between the condition 2) stated as above and a condition $2)'$ where the phrase "for $x$ randomly chosen in $\Sigma^k$" is replaced by "for every $x\in\Sigma^k$"? Generally if a property is true for a generic element of some set, then we conclude that the same property holds for all the elements of the set. Why this importante on the random choice of the string $x$? To be more precise, when I read "for $x$ randomly chosen in..." can I interpret this sentence as "for any $x$ in..."? It seems that the answer is NO, but I don't understand the reason.

(This is the Wiki definition ).

1

There are 1 best solutions below

2
On BEST ANSWER

The idea behind condition 2 is that, if $f$ is really a strong one-way function, then if we give any PPTM (probabilistic polynomial time Turing machine) a random output of $f$, the probability it should be able to successfully invert this random output should be very small.

With your change to condition 2, you're asking for a much stronger condition; namely, no matter what output of $f$ we give our PPTM, the probability it successfully inverts it is very small. Unfortunately, a bit of thought shows that this stronger condition is completely unreasonable (and in fact, impossible to satisfy). For example, consider the PPTM that always outputs the string $0^k$. On all of the inputs except for $f(0^k)$, it will always be wrong, but whenever we feed it $f(0^k)$, it will be right with probability $1$ (regardless of $f$).