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.

learn more… | top users | synonyms

0
votes
1answer
139 views

Is this problem based on a known hard problem?

Suppose I generated an $n$-dimentional vector $a_{(1)} = [a_1, \dotsc, a_n]$ with integer component (actually I can generate as many $a_{(i)}$ as possible). Now I need to get an vector $b = [b_1, ...
1
vote
1answer
49 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 ...
0
votes
1answer
75 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.
6
votes
1answer
245 views

How secure is the knapsack?

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 ...
2
votes
0answers
173 views

An example of Knapsack Cryptosystem cracks/attacks?

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