Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 37 down vote favorite
7

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.

share|improve this question
4  
Nice one! congrats for the 100th question! – Ran G. Mar 14 '12 at 8:11

4 Answers

up vote 33 down vote accepted

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

share|improve this answer
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? – Raphael♦ Mar 14 '12 at 10:37
6  
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. – Kaveh Mar 14 '12 at 13:49
1  
All the more interesting that a problem we don't even know to NP-hard is best practice in cryptography. – Raphael♦ Mar 19 '12 at 14:48
@Raphael, this may suggest that we need to revise the notion of computational hardness. – Mohammad Al-Turkistany Mar 19 '12 at 16:09
@MohammadAl-Turkistany: I disagree. Or rather, the concept of "the notion" is ill-formed. Sometimes what we want to know is whether some (significant number of) instances are hard, other times whether (almost) all instances are hard. Call the two notions hard-A and hard-B. Let's say we use "hard" to mean hard-A. That doesn't make the need to ask "is it hard-B" go away (or vice versa). – Jonas Kölker Feb 2 at 14:56
show 1 more comment
up vote 28 down vote

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.

share|improve this answer
2  
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. – Peter Shor Mar 19 '12 at 12:26
@PeterS: Thanks! – Aryabhata Mar 19 '12 at 15:44
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. – Ken Li Mar 20 '12 at 4:21
up vote 12 down vote

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.

share|improve this answer
up vote 5 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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