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$– DannyNiuDec 17, 2020 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.N00bDec 17, 2020 at 5:41
-
1$\begingroup$ We do have complexity-related tags (sort of). $\endgroup$– DannyNiuDec 17, 2020 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 CaryDec 18, 2020 at 5:53
-
$\begingroup$ @DavidCary I added (created) a "practice" tag, but I can't think of a good summary for it. $\endgroup$– DannyNiuDec 18, 2020 at 6:05
3 Answers
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:
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$– MaeherDec 17, 2020 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$– ponchoDec 17, 2020 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, 2020 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, 2020 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$ Dec 18, 2020 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$– ponchoDec 20, 2020 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$ Dec 23, 2020 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$– ponchoDec 23, 2020 at 22:05
If the ethics equal common principles of faith and civilization it may go like this: In light of the global conflicts our species fights with Mutually Assured Destruction (MAD) and with respect to its complexity-based cryptographic infrastructure referred to in the question, only four out of five possibilities would be subject to immediate public debate:
- P!=NP
- undecidability
- P=NP (reductio ad absurdum)
- P=NP (constructive with important constant and/or polynomial)
The fifth possibility of P=NP with a constructive proof (hence, an algorithmic procedure i.e., computer program) and a sufficiently small constant/polynomial would represent the Black Swan Event not only to the current cryptographic infrastructure but also to all other possible areas of application.
Provided the whole species is enabled to leverage the fifth possibility (total symmetry), these areas totally balance the impact on the cryptographic infrastructure, i.e., the more impact on cryptographic infrastructure, the more impact on those areas which may generate an evolutionary quantum-leap of a species. And vice-versa.
Accordingly, whoever is knowledgable about the fifth possibility meeting common principles of faith and civilization would certainly try to assess if there is a tradeoff for the human species to make the knowledge unrestricted public domain. One thing “whoever” would know by simple logic reasoning is that if “whoever” knows anybody else could also know. Knowing that anybody else could know implies that it could already be known by anybody else. With this knowledge it could be assumed, that in contrast to “whoever”, this anybody may not share the same wisdom (e.g., because “anybody” has been socialized in egocentric settings being rather greedy than humble). In that case, although not publicly known, the fifth possibility may be already in action. If it is already in action but not publicly known, it can be assumed that the fifth possibility is not subject of any tradeoff for the human species but only for a few at the most. Historically, knowledge has often been subject of elites, high priests and organizations thereof with hermitic languages being the preferred choice of record.
This is why “whoever” must continue to consider to make the knowledge unrestricted public domain shall it serve the progress of civilization.
How could “whoever” possibly proceed with respective SWOT analysis?
Although esoteric at the first glance, “whoever” could search for heuristic metaphors such a represented by the Fermi Paradox and its dissolution. https://youtu.be/sNhhvQGsMEc
The Fermi Paradox argues, among others, that any intelligent species may extinct itself when it reaches a certain technological level (great filter), e.g., nuclear technology or with reference to this debate: the fifth possibility. This valid argument of great filters would then explain, why humanity is not knowledgeable about intelligent alien civilizations.
Evidently, any knowledge about technologically advanced, intelligent alien civilizations would represent a definitive dissolution of the Fermi Paradox, hence of no apodictic existence of great filters, irrespective whether publicly know or just by “whoever”. https://youtu.be/ZBtMbBPzqHY https://youtu.be/5v0y99VM9eA
With this heuristic metaphor at hand, “whoever” would know that the non-existence of a great filter in conjunction with the fifth possibility would not be a sufficient condition to bless humanity, yet, a necessary one.
Now with “whoever” continuing to strive for blessing humanity, any consideration to integrate the fifth possibility vertically with licensing and/or a dedicated enterprise business may safely be ruled out.
This is because “whoever” would know, that although the public enterprise space is honorable to a large extent, only one bad player would suffice to enslave the species even more (for a while), while going enterprise is not defendable by any means, not even with all the even and odd US Navy fleets at disposal.
It should be apparent by now, that “whoever” would not even consider to let the the fifth possibility be an asset of a nation state or any treaty thereof.
What is left for “whoever” to make the fifth possibility publicly known in an ethical, unrestricted way?
A horizontally integrated, collaborative cryptocurrency leveraging the fifth possibility for value creation and safe against its own method with a million or more bit public key and being an irreversible part of the global communication infrastructure such as Bitcoin? Or a Quantum Cryptocurrency with bullet proof public key distribution run by monopolies such as multi-billionaires, the defence sector or nation states?
“Whoever” knows that just a rumor about the fifth possibility may disrupt the current cryptographic infrastructure, which is not only the backbone of todays digital privacy&security, but of property, trade, and currency.
But “whoever” also knows, that the same rumor triggers new perspectives all the nodes.
Is there an ethical tradeoff?
The answer may be found in astro-politcal discussions in conjunction with non-tangible trade. Without currency. https://www.tandfonline.com/doi/abs/10.1080/14777620801910818
In short: shall the fifth possibility ever become public domain, it will be most ethically available under WTFPL. http://www.wtfpl.net/about/
-
$\begingroup$ There is of course possibility 6. In accordance with US NOBUS doctrine, you keep it secret and leverage that knowledge for your own advantage. World powers do not become so by sharing. $\endgroup$ Apr 3, 2022 at 22:16
-
1$\begingroup$ @paul-uszak crypto.stackexchange.com/a/99461/100967 $\endgroup$– alephcApr 3, 2022 at 23:59