125
$\begingroup$

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.

Improve this question
$\endgroup$
2

6 Answers 6

Reset to default
85
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Don't we need hardness in the best case, too? After all, all of our keys should be secure. Or can we effectively (and efficiently) prevent the best case from happening? $\endgroup$
    – Raphael ♦
    Mar 14, 2012 at 10:37
  • 9
    $\begingroup$ moreover, we should be able to generate hard instances in reasonable time. In short, we need much more than just $\sf{NP\text{-}hard}$ness. $\endgroup$
    – Kaveh
    Mar 14, 2012 at 13:49
  • 1
    $\begingroup$ @Raphael, it should be enough if the probability to get an undesirable "good" case is small enough. If it's say smaller than the probability to guess the correct key of a desirable "bad" case, this risk should be considered acceptable IMHO. $\endgroup$
    – quazgar
    Feb 10, 2014 at 13:37
  • $\begingroup$ @Raphael The best case scenario (at least from the point of view of the person trying to break the encryption) is that they randomly guess a key that happens to be correct. There's no way for an encryption system to have the best-case hardness be more difficult than the knows-the-key hardness. $\endgroup$
    – Acccumulation
    Aug 11, 2021 at 23:08
  • $\begingroup$ @Acccumulation That's switching the computation model (including randomization), IMHO in a not helpful way. Yes, brute force always works but is prohibitive. The problem with easy instances is that given the public information, deterministic solvers can find the key quickly. That would make the best case easier than guessing, which we should try to avoid. $\endgroup$
    – Raphael ♦
    Aug 12, 2021 at 13:35
52
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 8
    $\begingroup$ For the purposes of cryptanalysis, McEliece probably shouldn't be considered just one crytosystem; for each class of efficiently decodeable linear codes you plug in, you necessarily have to come up with a different strategy to break it. It's been broken for some classes of codes, but (as the Wikipedia article says) not for Goppa codes, which were McEliece's original suggestion. $\endgroup$
    – Peter Shor
    Mar 19, 2012 at 12:26
  • $\begingroup$ From that list I'd say NTRU looks the most promising, it has yet to be extensively tested the way RSA was tested based on what I have read about so far. $\endgroup$
    – Ken Li
    Mar 20, 2012 at 4:21
  • $\begingroup$ Merkle-Hellman cryptosystem is not an appropriate example. The Merkle-Hellman knapsack verctors are only a subset of all knapsack vectors so the Merkle-Hellman knapsack problem may not be NP hard. I don't think that it is NP-hard, at least I am not aware of any paper that shows this. $\endgroup$
    – miracle173
    Feb 10, 2014 at 21:16
29
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Excellent summary. But note that BQP-hardness has the same caveats as your first two points. $\endgroup$
    – Mitch
    Jul 14, 2017 at 17:02
14
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ RSA, yes it's a trapdoor function. I am not sure that dlog is TDF (is one way) $\endgroup$
    – 111
    Apr 1, 2017 at 2:12
  • $\begingroup$ If an NP-intermediate problem were NP-hard, they'd be NP-complete, a contradiction. $\endgroup$
    – Myria
    Jan 25, 2019 at 23:48
1
$\begingroup$

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 found 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!

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you give a reference? $\endgroup$
    – Raphael ♦
    May 12, 2014 at 8:29
  • 1
    $\begingroup$ "en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem" and also the monography: Postquantum Cryptography (Springer). $\endgroup$
    – user13675
    Jun 8, 2014 at 22:36
  • 1
    $\begingroup$ Shamir, Adi (1984). "A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem". IEEE Transactions on Information Theory. 30 (5): 699–704. doi:10.1109/SFCS.1982. $\endgroup$
    – Mohammad Al-Turkistany
    May 26, 2020 at 11:29

Your Answer

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

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