0
$\begingroup$

I am attempting to try some sample knapsack encryption problems and the attack on them using the LLL algorithm. I am using here and here as the guides.

They both provide examples to walk through, giving the $M$ matrix which is to be put into the LLL algorithm, and the output of the reduction. I have been attempting to walk through, however I always get the incorrect output of the LLL reduction.

It seems that the algorithm just eliminates all of the public key entries in the bottom row of the matrix, instead of finding the solution given in the papers. Using both python and sage I get the same results.

The example from the first link:

from olll import * reduced = reduction([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [575, 436, 1586, 1030, 1921, 569, 721, 1183, 1570, -6665]], .75) print(reduced) [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, -6665]]

Is there something wrong with the implementations of LLL that I'm using, or is there another issue at play? The output of the algorithm given by the papers is much different from what I am getting. The one for the above is given as:

[[-2, 0, 1, 0, 1, 0, 1, -1, -2, 1], [-1, 0, -1, 1, -1, 0, 0, -1, 0, 1], [1, 0, 0, -1, -1, -1, 1, 0, -1, 0], [0, -1, -2, -1, 1, 0, 1, 1, 0, -1], [0, 0, , 1, 0, 1, 0, -1, -1, -2], [0, 1, 0, 0, 2, 0, 0, 0, 0, 0], [0, -1, 0, 2, -1, -1, 1, 1, 1, 1], [0, 1, 0, -1, 0, -1, 1, 1, 2, 0], [0, 0,, 0, 0, 0, 1, 1, 0, 1, 2], [0, 1, 0, 0, 0, 1, 0, 2, 0, 0]]

but I am unsure how to get this.

$\endgroup$
  • 1
    $\begingroup$ Have you tried transposing the matrix first? I know that some implementation of LLL I found for python did not match up with fplll until I transposed the matrix I was feeding it. $\endgroup$ – Ella Rose Feb 27 '19 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.