# Questions tagged [knapsack]

Knapsack is the problem of determining which numbers from a given collection of numbers have been added together to yield a specific sum: used in cryptography to encipher (and sometimes decipher) messages.

14 questions
Filter by
Sorted by
Tagged with
74 views

### Unicity Distance of the Merkle-Hellman Knapsack Cryptosystem with Hidden Public Key

The original Merkle-Hellman scheme has undergone many successful attacks, the most famous being Shamir's from 1982. As Shamir noted about his method, "An important property of the proposed attack is ...
50 views

### Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$

Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$ with high probability over ...
618 views

### How to generate hard subset sum instances

A subset sum problem can be defined as: Given a set of integers $S$ A target integer $x$ Find some subset of elements $s \in S$ such that $\sum_0^{n}s_i = x$ The "density" of a subset sum problem ...
2k views