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.