1
$\begingroup$

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

Is there a practical encryption algorithm that will remain safe even if P=NP? I.e, an algorithm that depends on problems that are more difficult than just 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 NP. Is this correct?

$\endgroup$
  • 1
    $\begingroup$ Have a look at the search results for P=NP (may also be useful for answerers). $\endgroup$ – SEJPM Sep 14 '17 at 10:16
  • $\begingroup$ Note that "computationally hard" is not the same as "NP-complete". NP-completeness refers to a very specific level of difficulty, and most of the problems used in encryption are not (quite) that difficult. At least, they're not thought to be; if it turns out the P=NP, then they are. $\endgroup$ – Gordon Davisson Sep 15 '17 at 5:37
8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I think your answer could potentially be very good if you had the time to elaborate on some of the content of the links that you shared $\endgroup$ – Ella Rose Sep 14 '17 at 18:37
  • 1
    $\begingroup$ But iO is not useful on its own --- all the applications of iO assume one-way functions (which don't exist if $\mathsf{P}=\mathsf{NP}$). $\endgroup$ – Occams_Trimmer Sep 14 '17 at 20:07
  • $\begingroup$ @EllaRose I don't have that time, unfortunately. Feel free to edit! $\endgroup$ – pg1989 Sep 15 '17 at 19:06

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.