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
9
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
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 $...
3
votes
1answer
50 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
188 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=...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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.
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
13 views

How to build knapsack cryptosystem using 5 secrets for encryption purpose? [closed]

Build knapsack cryptosystem using 5 secrets (m1, m2, m3, m4, m5) for encryption the message of five numbers with the base of 7* (c1, c2, c3, c4, c5). At the same time, all these numbers must be ...
0
votes
1answer
173 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, \...