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

15 questions
Filter by
Sorted by
Tagged with
655 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 ...
193 views

### Is there any knapsack-based cryptosystem that has not yet been broken?

I co-authored and implemented SRVB, an asymmetric cryptosystem, only to eventually realize that it is strongly related to Merkel-Hellman cryptosystem, which has been broken. In order to help me ...
407 views

### How to compare the efficiency of public key cryptosystems, i.e., RSA vs El Gamal?

As part of my Mathematics degree I'm taking a Discrete Mathematics module which partially covers Public Key Cryptography but does not at all enter it in depth. I'm currently working on a project that ...
2k views

603 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 ...
91 views

### Knapsack and block size clarification

I am a bit confused about the knapsack implementation regarding the bits and block size for encryption. In the example from this link (https://nrich.maths.org/2199), the knapsack size is 6 and the ...
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 ...
348 views

### Would $\mathrm{LLL}$ give us a hint to solve $\mathrm{SIS}$ problem?

(I am sure this question might have been asked before). I know that $\mathrm{LLL}$ algorithm can find a short, not necessarily the shortest, basis in polynomial time. My question is: if we construct a ...
151 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.
756 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 ...
73 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 ...
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, \...