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
0 votes
0 answers
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,...
Lisbeth's user avatar
  • 497
0 votes
1 answer
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 ...
sp8cky's user avatar
  • 1
2 votes
1 answer
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 ...
Anh Nguyễn Tuấn's user avatar
3 votes
1 answer
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 ...
Craig Feinstein's user avatar
0 votes
0 answers
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 ...
jillatik's user avatar
3 votes
1 answer
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 ...
Daniel's user avatar
  • 3,932
2 votes
1 answer
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 ...
Ella Rose's user avatar
  • 19.6k
4 votes
1 answer
3k 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 $...
OskarOlaussen's user avatar
5 votes
1 answer
298 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 ...
Yuri S VB's user avatar
2 votes
1 answer
112 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 ...
bobH's user avatar
  • 21
1 vote
1 answer
569 views

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

I know that the $\mathrm{LLL}$ algorithm can find a short, not necessarily the shortest, basis in polynomial time. My question is: if we construct a lattice from $\textbf{A}$ and then run $\mathrm{LLL}...
Node.JS's user avatar
  • 312
2 votes
1 answer
239 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=...
Kishan Desai's user avatar
5 votes
1 answer
503 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 ...
Jonathan's user avatar
  • 113
0 votes
1 answer
211 views

Is this problem based on a known hard problem?

Suppose I generated an $n$-dimensional 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, \...
JeffLee's user avatar
  • 23
1 vote
1 answer
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 ...
Ind F. Ashiku's user avatar
3 votes
1 answer
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.
Marco's user avatar
  • 131
2 votes
0 answers
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 ...
Seth's user avatar
  • 127
9 votes
1 answer
805 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 ...
Jus12's user avatar
  • 1,659