In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to invert), what would be the situation?
-
$\begingroup$ Possible duplicate of What does it mean for an adversary to run in PPT? $\endgroup$– fkraiemSep 1, 2018 at 11:57
1 Answer
Suppose we live in a work where $\mathsf{P}\neq\mathsf{BPP}$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.
Note, however, that it is widely believed that $\mathsf{P} = \mathsf{BPP}$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $\mathsf{DTIME}(2^{O(n)})$ which have circuit complexity $2^{\Omega(n)}$, then $\mathsf{P} = \mathsf{BPP}$.
-
$\begingroup$ Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear. $\endgroup$ Sep 1, 2018 at 14:14