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

18 questions
Filter by
Sorted by
Tagged with
34 views

### Convert an arbitrary array of integers to super increasing sequence

I have an arbitrary array $X = (x_1, x_2, \dots, x_n)$ of disjoint integers. I want to determine whether there exists a prime number, $p$, and a value $y < p$ such that the sequence Y = \left(y_1,...
• 497
29 views

### Density in terms of knapsack public-key cryptosystems

I am quite new to knapsack cryptosystems (specifically the merkle-hellman cryptosystem) and don't quite understand what exactly is the density $d(a) = \frac{n}{\log_2max_i a_i}$ defined here among ...
182 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 ...
602 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 ...
61 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 ...
• 3,932
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 ...
• 19.6k
3k views

• 312
239 views

• 23
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 ...
522 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.
• 131
1k views

### An example of Knapsack Cryptosystem cracks/attacks? [closed]

I have been studying papers on various ways to crack the knapsack cryptosystem, unfortunately the mathematics in these papers involves lattices and LLL which is over my head. The paper "New Attacks ...
• 127
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 ...