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.
16
questions
2
votes
1
answer
65
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 ...
3
votes
1
answer
426
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 ...
- 195
0
votes
0
answers
48
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 ...
- 1
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 ...
- 3,892
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 ...
- 19.4k
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 $...
5
votes
1
answer
266
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 ...
- 59
2
votes
1
answer
108
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 ...
- 21
1
vote
1
answer
536
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}...
- 302
2
votes
1
answer
221
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=...
- 23
5
votes
1
answer
485
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 ...
- 113
0
votes
1
answer
208
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, \...
- 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 ...
1
vote
1
answer
284
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.
- 111
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 ...
- 127
9
votes
1
answer
776
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 ...
- 1,659