It is well-known that the Merkle–Hellman knapsack cryptosystem can be solved using the LLL algorithm. In the Merkle-Hellman knapsack cryptosystem, we're trying to find a solution $x_i \in \{0,1\}$ such that

\begin{align} \sum w_i x_i &= K, \end{align}

where the $w_i$ are integer weights. Is it possible to find an approximate solution to the standard 0-1 knapsack problem

\begin{gather} \text{maximize } \sum v_i x_i \\ \text{subject to} \sum w_i x_i \le K,\quad x_i \in \{0,1\} \end{gather}

Using LLL?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.