Is there a cryptography algorithm that will remain safe if P = NP?

Question

From what I heard, many encryption algorithms are based on the assumption that some problems are computationally hard, i.e., $\mathsf{NP}$-complete. In the unlikely event that someone proves that $\mathsf{P} = \mathsf{NP}$, these codes will break.

Is there a practical encryption algorithm that will remain safe even if $\mathsf{P} = \mathsf{NP}$? I.e., an algorithm that depends on problems that are more difficult than just $\mathsf{NP}$-complete?

My guess is that the answer is no: to be practical, a code must be verified in polynomial time, i.e., the problem must be in $\mathsf{NP}$. Is this correct?

Answer 1

Whether P = NP is a question about the asymptotic growth of computational costs of algorithms as functions of input sizes. It may provide hints about concrete computational cost estimates of algorithms for specific input sizes, but doesn't provide answers.

In the eyes of the asymptotic setting, an $O(n^{10000})$ cost is ‘smaller’ than an $O(1.0001^n)$ cost because for sufficiently large values of $n$, past some boundary $n_0$, all values of $1.0001^n$ exceed the corresponding values of $n^{10000}$.

Does that mean an instance of a cryptosystem that costs $128\;\text J$ energy to compute and costs $128^{10000}\;\text J \approx 10^{20000}\;\text J$ to break is less secure than a cryptosystem that costs $128\;\text J$ to compute and costs $1.0001^{128}\;\text J \approx 1.01\;\text J$ to break? Certainly not!

For example, finding $k \in \{0,1\}^{128}$ given $\operatorname{AES}_k(0)$ takes $O(1)$ time because the input size $n$ is a constant, but that fact implies nothing about its feasibility in practice. The asymptotic growth of the NFS and ECM costs guide us toward parameter growth curves for, e.g., RSA, but they require concrete analysis to attain confidence in concrete choice of parameters.

For a particularly goofy example of this, see

Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta, ‘Post-quantum RSA’, PQCrypto 2017, Springer LNCS 10346, 2017, pp. 311–329,

which shows how to take advantage of a merely quadratic difference between a user's asymptotic costs and an attacker's asymptotic costs to make a cryptosystem, with a recommendation for specific input sizes guided by concrete use and attack cost estimates, that is just barely usable by rich users but likely out of reach of attackers even if they had access to a large quantum computer.

So would it matter if there turned out to be an asymptotically polynomial-time algorithm to solve every NP-complete problem in $O(f(n)^{10000})$ time when testing a solution takes $O(f(n))$ time for polynomial $f$? No, not really.

Could it matter, if there were a really amazing trick to use a low-degree polynomial that is, in concrete terms, cheap to compute? Maybe, but at this point that seems implausible—and cryptography might survive nevertheless by high-degree polynomial asymptotic gaps and exorbitant concrete gaps between user and attacker costs even if they're not exponential.

Answer 2

It's not an encryption algorithm, but indistinguishability obfuscation exists if P=NP. In general, modern cryptography does not exist if P=NP.

Russell Impagliazzo wrote a paper which meditated on the implications of P=NP and other fundamental questions in complexity by positing some possible "worlds" we might live in. It's a nice read if you're curious about these questions.

Answer 3

One-time pad, with true random key of the same length of the plaintext, makes virtually impossible to recover the original message: for any possible plaintext there would be a key that generates the ciphered text, so any key becomes valid. Even if you know in advance some properties of the plaintext (language, partial content...), the attack will still generate valid messages, so, how do you know which one is the correct?

Of course, if the message carries validation information (like a checksum), then maybe the search space is small enough as to retrieve a valid message.

Answer 4

I guess Squeamish Ossifrage's answer on polynomial degrees are not practical, since the attackers might store your encrypted messages, and wait just a few years our hardware would easily break the previous encrypted messages. To resist the store and decrypt strategy, decrypting without key must at least NP (or BNP?)...

About the BNP in the previous paragraph, maybe there are some smart way to build a cryptography algorithm with the verifier in BPP and the attacker needs BNP to attack? In this case, while P = NP, we might still have BPP < BNP? Although it is not like the current fashion: generating random keys and use deterministic algorithms to encrypt... I believe it might hard to design...

For one who wants to keep your secret when P = NP, I recommend to buy a quantum key distribution device when it's affordable. Since it's security relies on quantum mechanics not decrypting complexity, your communication may still be secret on P = NP day, and keep being safe until someone break quantum mechanics...