Consequences of P=NP for Authentication

Question

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.

Answer 1

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.