As of May 31, 2023, we have updated our Code of Conduct.

# 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.

16 questions
Filter by
Sorted by
Tagged with
65 views

### Decrypt Merkle-Hellman Knapsack Cryptosystem without public key

I am reading the Lightweight Introduction to Lattices and it is a problem Challenge 8 that makes me quite struggle. Basically, the problem give us an encrypted ...
426 views

### Solving subset sum via the LLL algorithm

I wrote code that solves the subset sum problem via the LLL algorithm, as given in chapter three of the Handbook of Applied Cryptography https://cacr.uwaterloo.ca/hac/ I ran the code on ten random ...
48 views

### Super increasing knapsack encryption programme

Im creating a super increasing knapsack encryption scheme. Im supposed to ask the user to key in the size of the super-increasing knapsack. My question is - is there a minimum number of elements that ...
55 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 ...
1k 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 ...
3k views

221 views

1 vote
1k views

### Knapsack Public to Private (Superincreasing knapsack)

I need to convert a hard knapsack to a superincreasing knapsack. I have these superincreasing values (3,6,11,22,43,87). I also have w = 7 and n = 173. I converted the superincreasing values to hard ...
1 vote
284 views

### Cryptography systems based on NP complete problems

There is any cryptography system that have a good reputation based on NP complete problem? I read about the knapsack, but it was cracked.
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 ...