9
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Ilmari Karonen
    Commented Jan 10, 2013 at 1:18
  • $\begingroup$ @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. $\endgroup$
    – Jus12
    Commented Jan 10, 2013 at 5:46

1 Answer 1

Reset to default
5
$\begingroup$

It may be possible to use the knapsack problem to build a secure cryptosystem, though experience suggests it is tricky and delicate. There are many known algorithms for attacking the knapsack problem, which may or may not work, depending upon the specific parameters you choose. Therefore, the security of the scheme will depend on the specific parameter values you use (e.g., the exact strategy you use for choosing all values, and the sizes of each value).

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.

Are you using this only for one-wayness? Can you use a standard one-way function (e.g., SHA256) instead, in lieu of the knapsack problem? Or are you taking advantage of the special structure of the knapsack problem?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jus12
    Commented Jan 10, 2013 at 7:51
  • 3
    $\begingroup$ @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.) $\endgroup$
    – D.W.
    Commented Jan 10, 2013 at 19:34

Your Answer

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

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