# How secure is the knapsack?

Can the knapsack be used in cryptography in a secure sense (described below)?

Knapsack problem: Given some number $X$ and a set $W$ of weights $w_1, w_2, ... w_n$, find a subset $S$ of $W$ (if it exists) whose weights sum to $X$.

Even though this problem is NP hard, there exist "pseudo-polynomial-time" algorithms for it and the average case hardness is questionable. So I am not sure how secure the knapsack is in reality.

I want to use the knapsack in a symmetric key sense (like a hash function), and NOT in a public key scheme, so there are no restrictions on $X$ and $W$. Uniqueness of solution is also not required. The only requirement is that finding any such $S$ should be hard. So my qustions are:

• Is there a strategy for choosing $W$ and $X$ that makes the problem hard?
• What are the practical values of $W$ and $X$ that make the problem hard?

EDIT: I don't need the strategy to also give me a solution $S$. The solution is never needed. The use-case requires finding any solution to be hard. The person generating the problem need not know the solution. Additionally, given the problem, it should not be easy for anyone to decide if a solution exists or not.

• I assume you'd also want the process for generating $W$ and $X$ to give you $S$ as well (since knowing a hard problem that even you can't solve, and which may or may not have a solution, isn't generally very useful), right? What were you actually planning to do with it if you had one, anyway? – Ilmari Karonen Jan 10 '13 at 1:18
• @Ilmari Karonen: Not really, but good point. In my use-case, we don't need the solution, just the problem to be hard. I have updated the question with this information. – Jus12 Jan 10 '13 at 5:46

If you choose the weights $w_1,\dots,w_n$ independently and uniformly at random from a large enough space, and if $n$ is large enough, and if $S$ is chosen at random, then I suspect this should be secure (it'll probably be computationally infeasible to find $S$). But I couldn't tell you exactly what parameter choices you'd need to make. You'd need to read up on all known attacks on knapsack problems, including LLL-based algorithms and generalized birthday-based methods. At minimum, I expect you need the weights to be (say) at least 256 bits long and $n \ge 160$, but I don't know if that is sufficient for security.
• I am using the special properties of the knapsack (the sum). It is actually meant to be used in another protocol. In my case $X$ (the target sum) is defined by the user. We are free to choose $W$. However, as a first solution, I will be happy even if both $(W, X)$ are freely chosen, as this might be extended even when $X$ is fixed. – Jus12 Jan 10 '13 at 7:51
• @Jus12, ok, sounds good! My suggestion is to read the literature on known attacks on knapsack systems, and that should let you pick parameters that defeat all known attacks. (An extra caveat: I expect that, for natural parameter settings, if you pick a uniformly random $X$, then with high probability there will be no solution, i.e., no subset $S$ of weights will sum to $X$. Make sure that's OK in your application.) – D.W. Jan 10 '13 at 19:34