Suppose a researcher discovers that $P=NP$, and has an efficient algorithm for some common NP-Complete problem. Given the implications for cryptography, what would be the most ethical way for them to reveal this knowledge to the world, without causing the downfall and destruction of technological civilization?

  • $\begingroup$ I don't know what other problems there are with this question, but [post-quantum-cryptography] is obviously not the right tag to use here. $\endgroup$
    – DannyNiu
    Dec 17 '20 at 5:39
  • $\begingroup$ @DannyNiu I agree, but I browsed through the other common tags, and they all seemed less relevant. I would have posted without any tags, but that is not allowed. $\endgroup$
    – CS.N00b
    Dec 17 '20 at 5:41
  • 1
    $\begingroup$ We do have complexity-related tags (sort of). $\endgroup$
    – DannyNiu
    Dec 17 '20 at 5:47
  • $\begingroup$ @DannyNiu: The complexity tag is very relevant, but I'm kind of disappointed that there's no obvious tag about responsible disclosure or, in general, appropriate ethical actions. integrity ; standards ; history are the closest I see, and I agree with CS.N00b that they seem less relevant. $\endgroup$
    – David Cary
    Dec 18 '20 at 5:53
  • $\begingroup$ @DavidCary I added (created) a "practice" tag, but I can't think of a good summary for it. $\endgroup$
    – DannyNiu
    Dec 18 '20 at 6:05

I'll try to answer what I view to be a much easier question to answer, while still (in my view) capturing the "essence" of the problem.

How can one "prove" that they have an efficient algorithm for an NP-complete problem without publishing the algorithm?

There are many things one can do, but the simplest is to solve challenges. There are a large number of computational challenges which have been posted over the years, for example:

  1. RSA factoring challenges

  2. Lattice Crypto challenges

If one solved a variety of these challenges in extremely high dimension and posted the solutions publicly, it would very quickly erode confidence in the hardness of the underlying problems. After waiting a suitable amount of time, you could then publicly post your algorithm. Of course, it is difficult to talk about what a "suitable amount of time" is for public disclosure that would break all of cryptography, which is why I avoided your initial question.

  • 4
    $\begingroup$ Importantly you should not allow people to submit arbitrary challenges for you to solve.If you did they could now use you as an oracle to attack things. $\endgroup$
    – Maeher
    Dec 17 '20 at 12:46
  • 3
    $\begingroup$ Other things you could publish to let people know you have something: a) an AES key that encrypts the all-0 block to the all-0 block, b) two strings that SHA-3 hash to the same value. $\endgroup$
    – poncho
    Dec 17 '20 at 14:16
  • $\begingroup$ @Maeher Maybe you could get around that by doing a zero-knowledge proof? Or does P = NP imply the non-existence of zero-knowledge proofs? $\endgroup$ Dec 18 '20 at 7:44
  • $\begingroup$ Technically, P = NP implies, on the contrary, that there are statistical zero-knowledge proofs for all of PSPACE. But the proofs are rather... trivial: simply send nothing and let the verifier check the truth of the statement without your help. Since P = NP implies P = PSPACE, this verification is efficient. So, what happens when P = NP, but the verifier does not know that? Well, it becomes much less clear. $\endgroup$ Dec 18 '20 at 8:45
  • $\begingroup$ What about safety? Many "bad" guys would want to get such algorithm at all costs. Also imagine bitcoin maniacs unhappy that their fortune is destroyed. $\endgroup$
    – Fractalice
    Dec 18 '20 at 8:54

There are algorithms to crack encryption, there are just no known algorithms to crack any half decent crypto in a reasonable amount of time.

A proof that P = NP doesn’t make such algorithms magically appear over night. And just because we now know there is a polynomial time algorithm, that doesn’t mean we are going to find one, and it most definitely doesn’t mean we can find an algorithm to break crypto in a reasonable amount of time. Breaking some crypto with an n-bit key in $n^{100}$ nanoseconds is polynomial time, but useless in practice.

PS. An efficient algorithm for SOME common NP-Complete problem X does not show that another problem Y which can be reduced in polynomial time and space to X can also be solved efficiently. For example, that reduction could take $n^{100}$ nanoseconds, and how long solving X takes is not of much interest anymore.

  • 2
    $\begingroup$ The question specifically posits "and has an efficient algorithm for some common NP-Complete problem"; an $O(n^{100})$ algorithm would not be considered efficient... $\endgroup$
    – poncho
    Dec 20 '20 at 17:54
  • $\begingroup$ Poncho, what you say is irrelevant. A polynomial time solution of one NP-complete problem guarantees polynomial-time solutions for all NP-complete problem, but a fast solution for one NP-complete problem doesn’t guarantee a fast solution for any other NP-complete problem. $\endgroup$
    – gnasher729
    Dec 23 '20 at 9:40
  • $\begingroup$ The various reduction methods I've seen between various NP complete problems are fairly efficient (that is, polynomial with moderately low exponents). Yes, it's possible that someone would find an NP complete problem with only inefficient reductions to other problems, and that they also find a P-time algorithm to solve that - that's certainly possible, but would also appear to be unlikely given the current experience... $\endgroup$
    – poncho
    Dec 23 '20 at 22:05

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.