4.5.4 Low density knapsacks

One of the more efficient algorithms for solving the general subset sum problem is the meet-in-the-middle algorithm.
For knapsacks having low density there is still another method namely to reduce the subset sum problem to the problem of finding a vector with small length.

Definition
Given a knapsack vector A = (a₁, ..., a_n). Let a_max be the largest element in A: a_max = max_i a_i, i = 1 ... n. Then the density d_A of A is defined by

In Cryptosystems, based on the subset sum problem, the density of a knapsack is almost always less than one. If not so, several subsets may exist summing up to the same s and hence no clear decryption may be performed.

Definition
A vector v in Rⁿ is an orderd tuple with elements v_i in R:

Definition
Let v = (v₁, v₂, ..., v_n) be a vector in Rⁿ. The euclidian length of v is

Definition
Suppose {v_i}_i=1...m is a set of m vectors in Rⁿ with m <= n. Then {v_i} is linearly dependant if and only if there are k_i in R with

Definition
Let {b_i}_i=1...n be a set of n linearly independant vectors in Rⁿ. Then {b_i}_i=1...n forms a base for Rⁿ. All vectors v in Rⁿ may be written as linear combinations of {b_i}_i=1...n:

Definition
Given m linear independant vectors {b_i}_i=1...m, m <= n. Then the lattice L, spanned by {b_i}_i=1...m, is the set of all integral linear combinations of {b_i}, that is

Closely related to a lattice is the problem of finding the shortest nonzero vector of this lattice (SVP: shortest vector problem).
It is an open question whether or not this problem is NP-hard using the euclidean norm. Using the supremum norm, it is shown, that the problem is NP-hard. The supremum norm || ||₈ of a vector v is defined by

As stated above a lattice may have several bases. A "good" base consists of vectors with relatively small length. Such a base is called a reduced base. The theory of lattice-base-reduction deals with the problem of finding reduced bases, given a lattice.

Algorithms transforming a given base B into a reduced base B', are called lattice reduction algorithms. A popular one is the algorithm invented by Lenstra, Lenstra and Lovász, L³ for short. A L³-reduced base has ,besides others, the property that its first vector, b'₁ has a length of at most an exponential factor greater than the smallest nonzero vector of the lattice, spanned by the vectors of B:

This paragraph shows as to solve a subset sum problem with a knapsack having low density. Because cryptographic knapsacks almost always have a low density, this method applies to them as well.

Given

• a public key B = (b₁,b₂, ..., b_n)
• a cipher c = pB = b₁p₁ + ... + b_np_n

Wanted

• the plaintext p

To get the original message back, successively perform the following steps

1. Construct the (n+1)×(n+1) matrix M
   

   M =
   	1	0	0	...	0	tb1
   	0	1	0	...	0	tb2
   	0	0	1	...	0	tb3
   	...	...	...	...	...	...
   	0	0	0	...	1	tbn
   	0.5	0.5	0.5	...	0.5	tc

   with t an integer > (n/4)^1/2

   Now define the vector m_i to be the i-th row of M, i = 1...(n+1). Let L be the lattice spanned by {m_i}_i=1...(n+1).

   Now suppose p = (p₁, p₂, ..., p_n) is the plaintext corresponding to c.
   Regard the vector y = p₁m₁ + p₂m₂+ ... + p_nm_n - m_n+1. Either p_i = 0 or p_i = 1, hence y is an integral linear combination of {m_i}_i=1...(n+1) and the lattice L contains this vector y.
   Vector addition is perfomed by adding the elements componentwise. Therefore the components of y are
    

   y1 =	p1 + 0 + ... + 0 - 0.5 =  p1 - 0.5
   y2 =	0 + p2 + 0 + ... + 0 - 0.5 = p2 - 0.5
   ...
   yi =	0 + ... + 0 + pi + 0 + ... +0 - 0.5 = pi - 0.5
   ...
   yn =	0 + ... + 0 + pn - 0.5 = pn - 0.5
   yn+1 =	t(b1p1 + b2p2+ ... + bnpn) - tc = 0

   With p_i in {0, 1}, y is a vector having all its components in {±0.5} except the last one which is zero. Therefore the euclidian length of y is ||y|| = (n/4)^1/2 and hence y is a small vector.
   Now, if the knapsack B is of low density, most of the vectors arising from linear combinations of {m_i}_i=1...(n+1) are expected to have a large length.

2. The next step is to reduce the base {m_i}_i=1...(n+1) by applying a reduction algorithm, e.g. the L³ algorithm.
3. Let {m'_i}_i=1...(n+1) be the new reduced base.
   Now scan the reduced base for a vector with the properties that
   • m_{i, n+1} = 0 and
   • m_{i, j} = ±0.5, j = 1 ... n
   If no such vector exists, either there is no solution to (B, c) or the L³ algorithm has failed to find a proper reduced base.

   Now assume that there exists a m'_k with m'_k = (±0.5, ±0.5, ..., ±0.5, 0). Perform the following steps

   • define the vector X = (x₁, x₂, ..., x_n) by x_i = 0.5 + m'_{k, i} , i = 1 ... n
   • compute s = XB = x₁b₁ + ... + x_nb_n
   • If s equals c, a solution to (B, c) is found and the plaintext is the vector X.
   
   Otherwise, if s != c then
   • define X = (x₁, x₂, ..., x_n) by x_i = 0.5 - m'_{k, i} , i = 1 ... n
   • again compute s = XB = x₁b₁ + ... + x_nb_n.
   • if s = c, then X is the plaintext

In [CO91] it was proven, that for knapsacks having a density d of less than 0.9408, the subset sum problem can almost always be solved.
Assuming that there exists an oracle constructing ALWAYS a reduced base with the shortest nonzero vector, the probability that the shortest nonzero vector of the lattice is not of the form {±0.5, ±0.5, ..., ±0.5, 0} goes to zero as the dimension of the knapsack goes to infinity as well as the density of the knapsack is less than 0.9408.

The assumption of finding ALWAYS the shortest nonzero vector of a lattice is not given when using the L³ algorithm. The algorithm is only guaranteed to find a vector b with length of at most ||b|| <= 2^(n-1)/2||v|| with v the shortest nonzero vector of the lattice. Despite this, the algorithm performs much better than is expected to be.

---

Start applet

 

Shamirs algorithm