Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

Question

Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. I wonder, why has there not been an encryption algorithm which is based on an known NP-hard problem. It sounds (at least in theory) like it would make a better encryption algorithm than a one which is not proven to be NP-hard.

Answer 1

Worst-case Hardness of NP-complete problems is not sufficient for cryptography. Even if NP-complete problems are hard in the worst-case ($P \ne NP$), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106

Answer 2

There have been.

One such example is McEliece cryptosystem which is based on hardness of decoding a linear code.

A second example is NTRUEncrypt which is based on the shortest vector problem which I believe is known to be NP-Hard.

Another is Merkle-Hellman knapsack cryptosystem which has been broken.

Note: I have no clue if the first two are broken/how good they are. All I know is that they exist, and I got those from doing a web search.

Answer 3

I can think of four major hurdles which are not entirely independent:

• NP-hardness only gives you information about complexity in the limit. For many NP-complete problems, algorithms exist that solve all instances of interest (in a certain scenario) reasonably fast. In other words, for any fixed problem size (e.g. a given "key"), the problem is not necessarily hard just because it is NP-hard.
• NP-hardness only considers worst-case time. Many, even most of all instances may be easy to solve with existing algorithms. Even if we knew how to characterise the hard instances (afaik, we don't), we'd still have to find them.
• You need to have huge instances that are hard to solve. Searching for (products of) large prime numbers is easy in the sense that the search space is flat: one number is either suited or not. Imagine using graphs: out of all $2^{n(n-1)}$ graphs of size $n$ for large $n$, you have to find those that have nice properties.
• You need some kind of reversability. For example, any integer is uniquely described by its prime factorisation. Image we would want to use TSP as encryption method; given all shortest tours, can you (re)construct the graph they came from uniquely?

Note that I have no expertise in cryptography; these are merely algorithmic resp. complexity-theoretic objections.

Answer 4

Public-key cryptography as we know it today is built on one-way trapdoor permutations, and the trapdoor is essential.

For a protocol to be publicly secure, you need a key available to anyone, and a way to encrypt a message using this key. Obviously, once encrypted, it should be hard to recover the original message knowing only its cipher and the public key : the cipher must only be decipherable with some extra information, namely your private key.

With that in mind, it's easy to build a primitive crypto system based on any one-way trapdoor permutation.

1. Alice gives the one-way permutation to the public, and keep the trapdoor to herself.
2. Bob put its input in the permutation, and transmit the output to Alice.
3. Alice uses the trapdoor to invert the permutation with Bob's output.

The difficulty now is to find actual one-way trapdoor permutations, and there's a bunch of function we think are good candidates (RSA, Discrete logarithm, some variations on the lattice problem). However, if we can find with certainty a one-way function, then we also prove that $\mathsf{P} \ne \mathsf{NP}$, so actually proving that a function is one-way is intractable.

The other way around, if we prove that $\mathsf{P} \ne \mathsf{NP}$, we also prove that there is a class in between called $\mathsf{NPI}$ (intermediate), of the problems in $\mathsf{NP}$ but not $\mathsf{NP}$-hard. Some good candidates for problems in $\mathsf{NPI}$ are also the candidates for one-way permutations, as we've not yet been able to prove that they are $\mathsf{NP}$-hard.

So to answer your question, we don't use $\mathsf{NP}$-hard problems because we need one-way permutation with trapdoors, and these special functions probably live in a class between $\mathsf{NP}$ and $\mathsf{NP}$-hard.

Answer 5

Just to give a heuristic argument, based on practical experience.

Almost all instances, of almost all NP-complete problems, are easy to solve. There are problems where this isn't true, but they are hard to find, and it's hard to be positive you have sound such a class.

This has come up in practice several times when people try to write random problem generators for some famous NP-complete class, such as Constraint Programming, SAT or Travelling Salesman. At some later date someone finds a method of solving almost all the instances that random generator produces trivially. Of course, if that was the case for an encryption system we would be in serious trouble!

Answer 6

Merkle-Hellman cryptosystems are based on binary knapsack problems (subset sum).