In terms of complexity classes, we assume that NP = RP. In other words, we assume that there is a randomized algorithm that solves a NP complete problem (and through polynomial time reductions, all of them in the class ) in polynomial time (assume quadratic ) with high probability. Also assume that the algorithm can be efficiently coded and implemented. How would this impact cryptography, in particular RSA?

  • $\begingroup$ This question is not related to my older question "Is it possible to attack RSA with a WalkSat derivative? ". Behind the algorithm described there, a long time ago I found a flaw in the mathematics. $\endgroup$ – Cristian Dumitrescu Sep 4 '17 at 1:17
  • 3
    $\begingroup$ For the purposes of cryptography, there is likely (I would like to say almost certainly) no distinction between P=NP and RP=NP in terms of practical implications. So, these answers should apply. $\endgroup$ – otus Sep 4 '17 at 4:59

The implications for solving a problem quickly with high probability of success (especially if this probability is arbitrarily high and the cost grows reasonably with the increased likelihood) are nearly the same as should the solution be deterministic. In cryptography we routinely use probabilistic methods. Nearly everyone uses probabilistic primality testing because it is far more efficient than the deterministic version (where we have outstanding exponential drop in error probability and only one type of error). Also cryptography deals with uniformly hard problems, we usually need a random instance of a problem to be hard to build secure cryptosystem around it. If what you are doing is solving many instances of an NP-hard problem this does not imply NP=RP and has no impact. If we actually could do what you propose we could with high probability break all cryptography. This would essentially mean there are no one-way functions and obviously no trapdoor one-way functions which are essential for cryptography.


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.