First of all, I only understand the P versus NP debate on a rather shallow level as I am not a computer scientist. So perhaps the answer to the question is straightforward but if not, I would be interested to know more.

I believe the consensus amongst computer scientists, complexity theorists, and programmers today is inclined more towards P $\neq$ NP than the equality. Nonetheless, I also find that the Internet is rife with doomsday pictures if

  1. the P = NP conjecture were indeed proven true, or/and
  2. large scale quantum computers (running Shor's algorithm) do become a reality.

To tackle the 2nd problem, the field of post-quantum cryptography has been developing ciphers that are resistant to cryptanalysis by Shor's algorithm and variants. However, I have not been able to find any convincing answer to the question: Do the post-quantum ciphers also address the 1st problem?

As such, I checked the elementary description of a few ciphers, e.g., the McEliece cryptosystem, which is explored under the banner of post-quantum cryptography. Some of them are apparently based on NP-hard problems (such as the shortest vector problem) which mean that these ciphers won't become vulnerable (even in theory) even if the P =NP conjecture holds true. But is that the also case with all current as well as future post-quantum cryptographic mechanisms?


1 Answer 1


Do the post-quantum ciphers also automag/tically address the 1st problem?

Not really, however to explore that in any detail, we need to explore what the 1st problem is.

If $P=NP$ is proven true, what does that practically mean? Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems can be trivially broken.

Why is this? Well, for two reasons: one, if we know $P=NP$ is true, we know that any problem within NP can be solved in polynomial time; it doesn't say we know how it can do it. If the proof of $P=NP$ doesn't give an algorithm (e.g. the proof shows that $P \ne NP$ leads to a contradiction), the knowledge that there is a polytime algorithm doesn't help us to solve any particular problem.

Secondly, even if we knew a polytime algorithm to solving an arbitrary problem within $NP$, it doesn't say that it runs in any sort of practical time. If the algorithm runs in $O(N^{1000})$ time, it is infeasible to run against any realistic problem, and hence does not practically impact the security of any cryptographical system at all.

On the other hand, what $P=NP$ might mean is that there is a practical algorithm for solving any reasonably sized problem; by practical, I mean that it is feasible to run the algorithm against a reasonable sized problem. If this were the case, all but a handful of cryptographical algorithms would be broken.

Here's why: known cryptographical systems are based on one of three security assumptions:

  • Informational security; the attacker literally does not have enough information to recover the plaintext; an example of this is One Time Pad (OTP)

  • Quantum security; the laws of physics prohibit the attacker from listening into the message without detectably disturbing in; Quantum Cryptography (QC) is in this category

  • Computational security; the attacker has all the information he needs; however recovering the plaintext would require more computation than he has; virtually all cryptographical systems are in this category

A practical way to solve an arbitrary $NP$ problem would invalidate everything in the computational security category, as everything in that category can be reduced to a series of $NP$ problems. Hence, in the absolute worse case scenario, we'd be left with OTP, QC and not much else.

So, in summary, just saying $P=NP$ doesn't give us enough information about what the practical aspects would be. However, 'post-quantum' algorithms, that is, algorithms that cannot be practically broken, even given access to the algorithms that can be run on a quantum computer, don't bring anything special to the table.

Now, you state that:

Some of them are apparently based on $NP$-hard problems (such as the shortest vector problem) which means that these ciphers won't become vulnerable (even in theory) even if the $P=NP$ conjecture holds true.

Actually, you misunderstand what $NP$-hard means; it doesn't mean that the problem is harder than an $NP$ problem; what it means is that if you can solve that problem, you can solve any problem in $NP$ (and so it is at least as hard as any $NP$ problem). However, it doesn't state whether it goes the other way; if you can solve an $NP$-complete problem, you may or may not be able to solve your $NP$-hard problem. In practice, we often dub a problem as $NP$-hard (and not $NP$-complete) if the problem is not a decision problem (that is, the answer to the problem isn't limited to "Yes" or "No"), and so pedantically not within $NP$ (and hence not within the set of $NP$-complete problems).

  • 5
    $\begingroup$ I just wanted to add that there is a common misconception that quantum computers can somehow solve all problems in NP in poly time. This is not (known to be) the case. They just happen to be able to efficiently solve some NP problems we usually base cryptography on (like factoring, which is not NP-complete). There are other NP problems that are not known to be in P or to be more efficiently solvable on a quantum computer. These are the type problems that post-quantum cryptography is based on. So this is why post-quantum crypto does not really address the P=NP case. They simply dont have to. $\endgroup$
    – Guut Boy
    Nov 12, 2014 at 20:29
  • $\begingroup$ "Doesn't not" under information-theoretical security should just be "doesn't" (or "does not"). $\endgroup$
    – cpast
    Dec 1, 2014 at 19:30
  • $\begingroup$ If P=NP is proven, then an algorithm is automatically known that solves an NP-complete problem in polynomial time, even though that algorithm need not be practical in any way, shape or form. One simply enumerates all programs and runs program 1 for one step, then program 1 and 2 for one step, then programs 1,2,3 for one step, and so on, checking after each step whether one of the programs has solved the NP problem; this blows up the runtime of the fastest solver only quadratically (and by horrible constants). Also, fine grained complexity based crypto may be possible even if P=NP. $\endgroup$
    – Polytropos
    Feb 9, 2021 at 21:09
  • $\begingroup$ To see why the blow up isn't exponential, the execution has a constant term of something like $2^C$ where $C$ is the length of the description of the TM. As the TM exists, $C$ is some finite number, so $2^C$ is some finite (horrendous) constant. $\endgroup$
    – Mark Schultz-Wu
    Feb 9, 2021 at 21:37
  • $\begingroup$ @GuutBoy This is somewhat complicated by one of the leading post-quantum schemes (lattice based crypto) having worst-case to average-case reductions (Although from a problem in $\mathsf{NP}\cap\mathsf{coNP}$, so that is unlikely to be $\mathsf{NP}$-hard). The existence of these reductions is a separate matter than the problem being thought to not be in $\mathsf{BQP}$ though (although this is even more complicated by some of the reductions requiring a polyt-time quantum computer to run). $\endgroup$
    – Mark Schultz-Wu
    Feb 9, 2021 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.