Modifying Algorithm SL

The combination of the Seysen and LLL reduction algorithms used in Chapter 3 to solve subset sum problems is a significant improvement over previously tried techniques. There is still plenty of room for improvement. The performance of Algorithm SL declines steadily over the range $50 \leq n \leq 100$. For subset sum problems with $n \approx 100$, Algorithm SL had difficulty solving instances with density $d \approx 0.4$, well below the $0.9408\ldots{}$ theoretical density bound. There are a number of ways in which Algorithm SL could be extended in order to attack subset sum problems with larger n,d values. For example, any of the techniques mentioned in Section 2.3 above could be applied to the Seysen phases of the algorithm. We can clearly imagine that another measure function S'(A) might perform better for sparse, subset-sum generated lattices when compared to the performance of $S(A) = \sum_{i=1}^n \Vert\bold{b_i}\Vert^2 \Vert\bold{b_i^*}\Vert^2$. Another method of extending Algorithm SL would be to increase the values of the $\pi_1$ and $\pi_2$ parameters. We have seen that increasing $\pi_1$ (the number of different orderings of the initial LLL lattice basis vectors) from one to five yields markedly better performance. Along similar lines, one could also allow more LLL- Weight-Reduction-Sort loops to occur for each randomization. Recall that for Algorithm SL, $\pi_2$, the maximum number of loops, was set to eight. After eight iterations without finding the desired solution vector in the lattice basis, Algorithm SL would ``give up'' and select a new randomization of the LLL-Phase input lattice basis. The choice to set $\pi_2 = 8$ was made arbitrarily; Radziszowski and Kreher used $\pi_2 = 15$ in their experiments. The majority of the work performed during the LLL-Phase of Algorithm SL occurs during the first LLL-Loop on each of the $\pi_1$ iterations; the second through $\pi_2^{\text{th}}$ LLL-Loops perform only a fraction of the number of row moves performed by the first loop. In our experiments, subsequent LLL-Loops tended to perform only $\tfrac{1}{10}$ the row operations performed in the initial LLL- Weight-Reduction-Sort iteration. This means that $\pi_2$ could probably be increased to around 20 and the overall running time of the LLL-Phase would probably double. Increasing the number of LLL-Loops appears to be an inexpensive way to allow Algorithm SL to perform more reduction operations on a lattice basis. One must consider, however, how much an increase in $\pi_2$ will improve the rate at which Algorithm SL solves subset sum problems. We know from [33] that Radziszowski and Kreher were able to improve upon the Lagarias-Odlyzko algorithm by significantly increasing $\pi_2$. Furthermore, in some very recent experiments Euchner and Schnorr (personal communication) were able to obtain performance close to that of Algorithm SL with $\pi_1 = 1$ and $\pi_2 = 16$. The Euchner-Schnorr reduction algorithm utilizes some other heuristics not included in Algorithm SL but uses only the LLL algorithm as the main reduction technique. To date, Euchner and Schnorr have only reported on experiments involving subset sum problems of size $n \leq 66$; the performance of their technique on lattice bases in higher dimensions is unknown. Even their preliminary results, though, suggest that it might be worthwhile to increase the number of reduction stages in Algorithm SL, even if it is necessary to reduce $\pi_1$ in order to maintain comparable running times. Also, as their methods uses only the LLL algorithm, a combination of their techniques and Algorithm SL is certainly possible. Another factor to consider in Algorithm SL is the structure of our version of LLL. Recall that instead of running LLL with $y \lesssim 1.0$ we used a fixed number of LLL stages with varying y values. The first stage used a value of y slightly greater than $\tfrac{1}{4}$, and subsequent stages used larger and larger values of y. For the first stage of the $\pi_2$ reduction stages, the multiple-value version of LLL significantly reduced the overall running time of the algorithm. However, later reduction stages were generally unable to benefit from this structure; in fact, in many cases the lattice was reduced further only by the stages with $y \geq 0.875$. Future implementations might consider removing the LLL stages with small y values for the second through $(\pi_2)^{\text{th}}$ reduction loops. In Section 2.3.3 we discussed how Hadamard matrices could be used to randomly permute a lattice basis which was locally Seysen-reduced in the hope that reapplying Seysen's algorithm would yield a better reduced lattice basis. This same technique could be applied to both the Seysen and LLL phases of Algorithm SL and might yield significant improvements. Hadamard matrices could be used to permute a Seysen-reduced lattice basis whose Seysen measure is a local minimum of the S(A) function. Such a permutation might then permit Seysen's algorithm to reach another lattice basis with smaller S(A) value, which in turn could increase the ratio of work performed by the Seysen phase to that performed by the LLL phase. Similarly, recall that under the current scheme once a lattice basis has been LLL-reduced $\pi_2$ times without yielding a solution vector, that basis is forgotten and a new iteration is started using a random permutation of the output of the Seysen phase. Instead of ``throwing away'' the LLL-reduced basis, which has shorter basis vectors than the Seysen-reduced basis, a Hadamard permutation could be applied to the output of the $\pi_2$ stages. This permuted basis would then be used as the input basis to the next big iteration. Assuming that the Hadamard permutation method sufficiently ``scrambles'' the lattice basis, we could thus avoid the overhead of having to reduce the output of the Seysen phase more than once. Finally, it is possible to modify Algorithm SL to take into account additional information related to the creation of the specific subset sum problem. In [12] it is shown how to tailor the input lattice basis for a subset sum problem if it is known that the number of elements in the desired subset of weights is bounded by a fraction of n. That is, if it is known that

$$\sum_{i=1}^n e_i = \beta n,$$

then the lattice basis can be modified so that a solution vector exists of length $\sqrt{n \beta(1-\beta)}$. (In the worst case, $\beta = \tfrac{1}{2}$ and the solution vector is the familiar $\bold{\hat{e}'}$ vector with $\Vert\bold{\hat{e}'}\Vert = \tfrac{1}{2}\sqrt{n}$.) For instances of the general subset sum problem no information is known concerning $\sum e_i$. Some knapsack cryptosystem, such as the Chor-Rivest system [11], do use subsets with relatively few weights. When attacking such systems, Algorithm SL should be modified to use the tailored lattice basis described in [12].