7 votes

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

It seems that the Okamoto-Tanaka-Uchiyama and the Murakami-Nasako knapsack cryptosystem have not been broken, but I'm not an expert in this field and cannot tell whether it received enough attention ...
Geoffroy Couteau's user avatar
5 votes
Accepted

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

Let's begin with a short description of the Merkle-Hellman knapsack scheme. The private key is a superincreasing sequence of $n$ elements $b_1, b_2, \dots, b_n$, along with a secret element $W$ and $N$...
Samuel Neves's user avatar
  • 12.4k
4 votes

Solving subset sum via the LLL algorithm

Caveat: I'm not an expert on these types of attacks. If a subset-sum instance is of the form $\sum_{i=1}^n a_i x_i = t$, i.e. $n$ is the length of the sum, then density is defined to be $n / \max_i\...
Mark's user avatar
  • 12.5k
2 votes

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

As mentioned by 111 in the comments, solving SIS comes down to finding a short vector in the underlying lattice of some prescribed norm $\beta$ or less. Lattice basis reduction methods like LLL help ...
TMM's user avatar
  • 343
2 votes
Accepted

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

In the Naccache-Stern knapsack cryptosystem, it holds that $\gcd(s,p-1) = 1$. Hence, you can compute the inverse of $s$ modulo $p-1$ (the coprimality ensure the existence of such an inverse). ...
Geoffroy Couteau's user avatar
2 votes

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$, where $\gamma$ and the $\...
poncho's user avatar
  • 146k
2 votes
Accepted

How to generate hard subset sum instances

How can we generate hard instances of the subset sum problem that are not solvable in polynomial time, or more specifically, require exponential time to solve? Is it sufficient to use any size set and ...
Ella Rose's user avatar
  • 19.6k
1 vote

Density in terms of knapsack public-key cryptosystems

Your expression for the density should read $$d(a):=\frac n{\log_2\max_i\log a_i}.$$ In this case, $n$ is the number of weights. It's sort of a measure of how "spread out" different ...
Daniel S's user avatar
  • 23k
1 vote

Decrypt Merkle-Hellman Knapsack Cryptosystem without public key

There is much more structure to this problem than a generic substitution cipher, and consequently much more that can benefit an attacker. As this is for the purposes of an exercise, I shall only ...
Daniel S's user avatar
  • 23k
1 vote

Knapsack and block size clarification

The example there is instructional, not for implementation. Also, if you only want 26 characters plus a few punctuation marks, 5 or 6 bits would be enough.
kodlu's user avatar
  • 22.1k

Only top scored, non community-wiki answers of a minimum length are eligible