Testing Random Integer Lattices

The reductions of $B_{\theta }$ lattices tested application of Seysen's algorithm to a very narrow class of lattices. From a cryptographic point of view (see Chapter 3 below), and in many other cases, our goal is to reduce random lattices with integer basis vectors. In general, we do not know that our lattice conforms to some specific structure; we are give only the basis vectors themselves. Thus, it is appropriate to investigate the performance of Seysen's algorithm on randomly generated integer lattices. When we considered in Section 2.2.1 the choice of a lazy or greedy selection method for Seysen's algorithm, we ran tests on random integral lattices L with $\det(L) = 1$ of small dimension ( $n \leq 35)$. We utilize the same technique for generating random lattices as used before, except now we consider lattices up to dimension 50. In addition to running Seysen's algorithm over these test cases, each lattice was also reduced using the LLL algorithm with $y \lesssim 1.0$. Table 2.4 summarizes the results of these experiments. For each value of $n \equiv 0 \bmod 5$, $20 \leq n \leq 50$, twenty different test lattices were generated. The columns n, L₁₀, S(A), L₁₀^*, L₁₀', S(A'), and L₁₀^*' identify the same quantities as in Table 2.2 above. The column labeled ``# Steps (Seysen)'' reports the average number of reduction steps (row moves) performed by Seysen's algorithm for each test lattice. The average number of row operations performed by the LLL algorithm is listed in the ``# Steps (Lovasz)'' column. (LLL reduction was not performed on lattices with $n \geq 45$ because of the excessive amount of computer time required to obtain results).

 

Table 2.4: Performance of Seysen's Algorithm on Random Integer Lattices

n	L10	S(A)	L10*	L10'	S(A')	L10*'	# Steps (Seysen)	# Steps (Lovasz)
20	82.37	$4.71 \cdot 10^{11}$	118.22	0. (20)	20.	0.	757.37	4424.0
25	131.95	$5.67 \cdot 10^{14}$	192.93	0. (20)	25.	0.	1622.11	12977.4
30	195.81	$9.28 \cdot 10^{17}$	287.24	0. (20)	30.	0.	3275.30	32718.5
31	205.86	$3.05 \cdot 10^{18}$	308.06	0. (20)	31.	0.	3690.51	38085.2
32	222.41	$1.04 \cdot 10^{19}$	323.66	0. (11)	1695.8	0.	3626.00	44770.0
33	237.86	$5.07 \cdot 10^{19}$	348.19	0. (5)	86999.0	0.	3408.27	53407.4
34	243.86	$4.48 \cdot 10^{19}$	358.86	0. (1)	$4.26 \cdot 10^6$	0.	3075.63	60299.7
35	269.25	$6.24 \cdot 10^{20}$	390.02	110.39	$1.00 \cdot 10^8$	112.57	3036.95	70047.2
36	287.16	$5.26 \cdot 10^{21}$	423.62	138.11	$2.48 \cdot 10^9$	141.13	2738.39	80836.3
37	291.86	$5.23 \cdot 10^{21}$	438.94	162.17	$3.20 \cdot 10^{10}$	167.33	2400.10	91491.5
38	310.35	$3.17 \cdot 10^{22}$	469.18	175.52	$1.07 \cdot 10^{11}$	182.50	2520.02	103624.0
39	329.32	$1.78 \cdot 10^{23}$	500.89	196.26	$7.45 \cdot 10^{11}$	203.87	2555.72	118338.0
40	343.84	$1.82 \cdot 10^{23}$	507.02	216.88	$5.21 \cdot 10^{12}$	227.10	2240.23	132901.0
45	434.01	$2.02 \cdot 10^{26}$	656.67	304.56	$4.20 \cdot 10^{15}$	323.53	2369.90	-
50	541.20	$4.53 \cdot 10^{29}$	833.54	402.80	$2.33 \cdot 10^{18}$	429.15	2698.11	-

The LLL basis reduction algorithm was able to reduce all tested lattice bases to the n-dimensional cubic lattice basis (i.e. B' = I_n), which has Seysen measure zero. Seysen's algorithm performed similarly on all lattice bases with $n \leq 31$. (Values in parentheses in the L₁₀' column indicate the number of lattice bases which were Seysen-reduced to the n-dimensional cubic lattice.) For $32 \leq n \leq 34$ the Seysen algorithm was able to completely reduce only some of the attempted lattice bases; no lattice basis with $n \leq 35$ was ever reduced by the Seysen algorithm to I_n. The degradation in the performance of Seysen's algorithm as n increases from 30 to 35 is quite surprising. Apparently, for these types of lattices, the probability of reaching a lattice basis which is a local minimum of the Seysen measure function increases substantially over that range. The LLL reduction algorithm does not exhibit any decrease in performance, except for an overall increase in the number of reduction steps required to convert the given lattice basis into the n-dimensional cubic lattice basis. Of course, the LLL algorithm does take significantly longer to run than the Seysen algorithm, but these tests suggest that Seysen's algorithm alone will not be sufficient to reduce lattice bases in higher dimensions. We may need to combine Seysen's algorithm with other lattice basis reduction techniques to efficiently reduce large lattice bases. Alternately, it may be possible to use some heuristic technique to reduce the probability of reaching a lattice basis which is a local minimum of S(A), or to ``kick'' a Seysen-reduced basis out of a local minimum. The following section suggests a few possible methods which may be employed when Seysen's algorithm fails to S-reduce a lattice basis and stops at a local minimum of S(A).