5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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$
    – Martin Berger
    Commented 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
    Commented Nov 5, 2015 at 7:36

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

(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
else:
    output 100010

.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That is not correct. A will not output random numbers . A resembles in some way the function $f^{-1}$. $\endgroup$
    – user27950
    Commented 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.