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? enter image description here


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}$.

| improve this answer | |
  • $\begingroup$ Thanks a lot, Geoffroy. You helped me out. Your explanation was so clear. $\endgroup$ – Amirhossein Adavoudi Sep 1 '18 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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