3
$\begingroup$

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 sets, each with positive integers from one to $2^n$, each with a random subset adding up to a target integer. The code found the solution ten out of ten times when $n=10$.

However when I ran the code on ten random sets, each with positive integers from one to $4^n$, each with a random subset adding up to a target integer, the code found the solution only one time out of ten times when $n=10$.

My question is shouldn’t it be the other way around, since the sets with positive integers from one to $4^n$ have a lower density than those with positive integers from one to $2^n$ and the algorithm is supposed to have a higher probability of finding a solution for lower density instances?

What might explain this output?

$\endgroup$

1 Answer 1

4
$\begingroup$

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\log a_i$. It follows that

  1. the density of your first subset-sum is $\approx 10/n$
  2. the density of your second subset-sum is $\approx 5/n$.

This is lower density (as you claim). That being said, both are actually higher density than is typically required for LLL to solve things. These notes of Peikert state that density $2/n$ is typically the threshold for things to start working.

So based on the theory I believe neither should (guaranteed to) work with high probability, and instead the threshold for things to work well should be somewhere around $2^{5n}\approx 32^n$ (for your parameterization of things).

$\endgroup$
7
  • $\begingroup$ Actually the results I got were only for $n=10$. When I went higher, the results got worse. $\endgroup$ Mar 29, 2023 at 3:49
  • $\begingroup$ @CraigFeinstein, I guess it might be an implementation problem possibly then? Just a blind guess. $\endgroup$
    – kodlu
    Mar 29, 2023 at 12:33
  • $\begingroup$ It could be. I am going to go over things again today. $\endgroup$ Mar 29, 2023 at 13:07
  • $\begingroup$ Note that there is no theory guaranteeing that the LLL must find solutions with high probability for low density instances. It is only claimed from experiments that it does happen to find solutions in the 1985 paper by Odlyzko and Lagarias. I still have not been able to replicate these but perhaps they were using a different implementation of the algorithm? I do not know. $\endgroup$ Mar 30, 2023 at 2:32
  • 1
    $\begingroup$ @mark You are correct. I should have qualified that I was only talking about the papers by Odlyzko and Lagarias in which the density does not depend on n. I am only interested in these types of problems. $\endgroup$ Mar 30, 2023 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.