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.

Filter by
Sorted by
Tagged with
1
vote
0answers
53 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 ...
0
votes
0answers
49 views

Errors in LLL cracking knapsack crypto

I am attempting to try some sample knapsack encryption problems and the attack on them using the LLL algorithm. I am using here and here as the guides. They both provide examples to walk through, ...
3
votes
1answer
49 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 ...
2
votes
1answer
419 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 ...
4
votes
1answer
2k views

How to attack Merkle-Hellman cryptosystem if the first element in the superincreasing series is too small?

In An Introduction to Mathematical Cryptography Jeffrey Hoffstein et al. claim that "It turns out that if $r_1$ is too small, then there are easy attacks, so we must insist that $r_1>2^n$." Here $...
5
votes
1answer
186 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 ...
2
votes
1answer
84 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 ...
1
vote
1answer
294 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 ...
2
votes
1answer
183 views

Naccache–Stern knapsack cryptosystem: How to calculate $p_i ^{s^{-1}} \mod p$?

In the algorithm(link), for calculated n and chosen secret key s, we need to calculate $\sqrt[s]{p_{i}} \bmod p $. As an example in original research paper (link) , For a given $p=9700247$ and $s=...
5
votes
1answer
341 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 ...
0
votes
1answer
171 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
548 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
135 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.
2
votes
0answers
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 ...
8
votes
1answer
607 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 ...