2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ One-way functions are not generally defined like that, since that definition is provably impossible to achieve. $\:$ $M$ could try guessing $k$ based on the length of its input and then search for a preimage by brute force. $\;\;\;\;$ $\endgroup$ – user991 Apr 21 '14 at 20:03
  • $\begingroup$ (Furthermore, that's not the wiki definition either.) $\;$ $\endgroup$ – user991 Apr 21 '14 at 20:04
3
$\begingroup$

The reason you are looking at a random choice of $x$ is that, otherwise, there is no probability space any longer. Put differently, if we require that for every x there should not be an algorithm that given an image $f(x)$ can output a preimage, we have a problem, because there is such an algorithm. For every $x$ consider the algorithm $M_x$ that on any input simply outputs $x$. Thus, we have just defined for every $x$ an algorithm that (on input $f(x)$) inverts the function.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't ask "for every $x$ there is an algorithm $M$ such that..." I mean simply "$M$ is algorithm such that for every $x$..." To be more precise, FIX the algorithm $M$; now saying that the property $2)$ is true for every $x\in\Sigma^k$ is the same as saying that it is true for $x$ randomly chosen in $\Sigma^k$? Math books generally don't use the phrase "for $x$ randomly chosen...", they simply use the statement "for any $x$ in...". On the other hands computer-science book underline the word "random". $\endgroup$ – Dubious Apr 21 '14 at 21:12
  • $\begingroup$ No, since 2) uses a probability over the choice of $x$. $\:$ "Math books generally don't use the phrase $\hspace{.4 in}$ 'for x randomly chosen...'" because they generally don't mean "for $x$ randomly chosen". $\hspace{1.02 in}$ $\endgroup$ – user991 Apr 21 '14 at 21:37
  • $\begingroup$ @Galoisfan: try to write a definition without using a random choice of $x$. Currently, you say that you want "the property to be true" for every $x$. But what exactly is the property, if you do not have a probability space any longer? $\endgroup$ – Arno Mittelbach Apr 22 '14 at 6:23

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.