Private key encryption based on NP-complete problem

Question

Over a decade ago, a question was asked on Stack Overflow, which basically asked if there were any encryption schemes that are reducible to an NP-complete problem, in the sense that breaking the encryption implies breaking the underlying NP-complete problem, and hence proving $P\not=NP$.

As a concrete example, is there a symmetric key cryptosystem which can be proved to be CPA-secure under the assumption that some underlying NP-complete problem is hard to solve? That is, if the adversary is given the encryption of one of two messages, then an algorithm that can determine which message was encrypted can also be used to solve the underlying NP-complete problem (in polynomial time)?

In the original Stack Overflow question, the answer was an unequivacle "no". I ask this question today because 12+ years is a long time in the world of research, and I am curious if any progress has been made on this problem yet.

Answer 1

We do not have such an encryption. One of the challenges is the gap between worst case and average case. When we build an encryption based on a well known problem it is not sufficient to reduce the encryption problem to a problem which is known to be NP hard. Because the problem is only NP hard with respect to the hardest instances. The instances of we generate in our encryption may not be hard even if phrased as a hard problem.

e.g subgraph isomorphism is hard but it is trivial to find families of such problems with an efficient solutions.

We like building encryption on random self reducible problems like dlog where solving a random instance is hard as solving the hardest instances. We have good reason to believe there are no random self reducible NP complete problems, as this would collapse the polynomial hierarchy.

Your question was specifically about symmetric encryption which is even more problematic. Proving relationship between well known hard(not NP hard) problems and encryption is standard in asymmetric encryption but not in symmetric encryption. Our leading symmetric primitives like AES and SHA3 are not related to known hard problems.