Score:0

Consequences of P=NP for Authentication

ca flag

Let's suppose that P=NP. That is, every problem whose solution can be quickly verified can also be solved quickly, regardless of what that means at a formal level. So, not only does P=NP, but there are practical polynomial-time algorithms for NP-complete problems. Also, the proof is either constructive or non-constructive. That is, an algorithm can be found that we would eventually find fast enough to start using, even if we couldn't prove it. Then it becomes much harder to keep a secret--a massive problem. What scares me would not be our inability to hide information, but our inability to reveal it.

In a complex society, we need to trust others, and what we can independently verify is not enough. In practice, we establish trust with institutions when they repeatedly supply us with accurate information. I don't see an alternative method, so if we lose the ability to verify that we are receiving information from a specific institution, then an impostor could exploit our trust, which must not be allowed. Therefore, we cannot be sufficiently well-informed to have a complex society. P=NP would destroy current authentication and therefore pose a fundamental risk if other solutions are not found.

Could other solutions be found? If P=NP, we have a world without privacy, but, cutting our losses in that regard, we could try to build authentication around that fact. Instead of entities giving us the information we need to identify them, we could just squeeze it out of them. One idea is that upon receiving a message, we would send out our message containing some information to be sent back to us with the original message, so we would know that our message had been received and that the recipient at least wanted to send the original message. Our message is spyware, enhanced by our efficient algorithm for NP-complete problems, which we use to verify the original message's source.

Score:4
ng flag

I'll try to answer what I believe to be what you are asking, namely:

If $P = NP$, can one "fix" cryptography by replacing constructions with interactive protocols?

This is a natural enough question, but has a well-known (negative) answer. Specifically, any interactive protocol that requires a fixed (finite) number of rounds of interaction is said to live in a complexity class called the polynomial hierarchy $PH$. It is a priori possible that $P = NP$, but $P \subsetneq PH$. In this setting the answer to the above question is "yes, in principle" (although I know of no constructions).

Unfortunately, one of the basic results about $PH$ is that this is false, meaning $P = NP\implies P= PH$, so basing cryptography (in a world where $P = NP$) on solely a finite number of rounds of interactivity is not possible. There are some caveats here with protocols that have $\omega(1)$ rounds (these are in a complexity class called IP), but those would be so unbelievably slow (due to each round incurring an unavoidable latency from the speed of light) that they are not particularly interesting.

There are a few other potential ways to get (something like) cryptography in a world where $P = NP$ though, namely:

  1. Using "noisy channel" assumptions, for example the wiretap channel, and
  2. Using quantum channels

Both have significant downsides compared to complexity-theoretic cryptography (which I will not attempt to summarize here), but their validity is not threatened by $P = NP$, and are probably good things to look up if you are interested in the possibility of secure communication in a world where $P = NP$.

That all being said, authenticating yourself to computers would be much more difficult overall. Another "solution" would be to rely on in-person authentication. Of course, one can behave fraudulently here, but it is somewhat more difficult to do at scale.

Thomas Anton avatar
ca flag
Would in-person authentication really last long-term? We can already clone.
cn flag
There are also approaches such as Fine-grained Cryptography that are not necessarily affected by $\mathsf{NP}\subseteq \mathsf{BPP}$.
Mark avatar
ng flag
@ThomasAnton it is difficult to predict, but non-digital forms of authentication are harder to impersonate millions of people at once, even given the ability to clone people or whatever.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.