I've been reading up on probabilistic polynomial-time algorithms and one-way functions, and I was hoping to get some guidance on the topic.

A textbook I'm reading states the following for one of the conditions for one-way functions:

Hard to invert: For every probabilistic polynomial-time inverting algorithm A, there exists a negligible function negl such that $$Pr[A(f(x))\in f^{-1}(f(x))] \leq negl(n)$$ where the probability is taken over the uniform choice of x in $\{0,1\}^n$ and random coin tosses of A.

What exactly does it mean by "random coin tosses of A"? Is it stating that the "inversion function" is randomly generated by such a process?

  • 1
    $\begingroup$ By definition $A$ is computed by a probabilistic poly-time Turing machine, and such a machine can make coin-tosses to compute its result(s). So $A$ is not randomly generated, but instead a mechanism that make random choices. And the proportion of random choices $A$ makes that lead to inverting $f$ must be small (negligible). $\endgroup$ Oct 6, 2015 at 7:31
  • $\begingroup$ A suggestion: if your (crypto) textbook does not describe Turing machines (including probabilistic ones) in sufficient detail, do consult a complexity theory textbook (such as Arora-Barak) to get familiar with them. In general, it is assumed in crypto that "algorithm" means "Turing machine", and some notions related to such machines are freely used but not always explained. $\endgroup$
    – fkraiem
    Nov 5, 2015 at 7:36

2 Answers 2


A probabilistic algorithm uses random numbers to define the next step it should do (google for instance "Monte Carlo Algorithm").
"Random coin tosses" merely says that the random numbers are equally distributed.
The algorithm A will use the random numbers only internally, it will not output any random number. But A's output will depend on those random numbers.
Therefore, it will output a correct pre-image only with a certain probability.


(For that definition, one will also need that $\hspace{.04 in}f\hspace{.02 in}$'s outputs are not too much shorter than $\hspace{.04 in}f\hspace{.02 in}$'s inputs.)

It means "random bits generated by A". $\:$ For example, A might be

flip 7 coins
if exactly 5 of those come up heads:
    output 011101
    output 100010


  • $\begingroup$ That is not correct. A will not output random numbers . A resembles in some way the function $f^{-1}$. $\endgroup$
    – user27950
    Oct 6, 2015 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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