Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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. $\;\;\;\;$ – Ricky Demer Apr 21 '14 at 20:03
(Furthermore, that's not the wiki definition either.) $\;$ – Ricky Demer Apr 21 '14 at 20:04
up vote 3 down vote accepted

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.

share|improve this answer
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". – Dubious Apr 21 '14 at 21:12
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}$ – Ricky Demer Apr 21 '14 at 21:37
@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? – Arno Mittelbach Apr 22 '14 at 6:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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