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$ Commented Apr 21, 2014 at 20:03
  • $\begingroup$ (Furthermore, that's not the wiki definition either.) $\;$ $\endgroup$ Commented Apr 21, 2014 at 20:04

1 Answer 1

Reset to default
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$ Commented Apr 21, 2014 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$ Commented Apr 21, 2014 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$ Commented Apr 22, 2014 at 6:23

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.