ABSTRACT
In this chapter we present our first application of lattice basis reduction to cryptography: we use the LLL algorithm to break a knapsack cryptosystem.
Definition 7.1. Suppose that we are given a set of n distinct positive integers
A = { a1, a2, . . . , an },
together with another positive integer s. The subset-sum problem (also called the knapsack problem) asks whether there exists a subset
I ⊆ { 1, 2, . . . , n },
for which the sum of the corresponding elements of A is exactly s:∑ i∈I
ai = s. (7.1)
We think of s as the size of a knapsack, and the numbers ai as the sizes of items to be placed in the knapsack; the question is then whether the knapsack can be filled exactly by some subset of the items.
