Tensor-based Trapdoors for CVP and their Application to Public Key

Cryptography

(Extended Version)

Roger Fischlin and Jean-Pierre Seifert

Fachbereich Mathematik (AG 7.2) Johann Wolfgang Goethe-Universität Frankfurt am Main Postfach 111932 D-60054 Frankfurt/Main, Germany

       {fischlin,seifert} @ informatik.uni-frankfurt.de
          http://www.mi.informatik.uni-frankfurt.de/

January 3, 2000

Abstract. We propose two trapdoors for the Closest-Vector-Problem in lattices (CVP) related to the lattice tensor product. Using these trapdoors we set up a lattice-based cryptosystem which resembles to the McEliece scheme.^{1}

Keywords. Public Key Cryptosystem, Closest Vector Problem, Lattice Reduction, Trapdoor, McEliece

1 Introduction

Since the invention of public key cryptography in 1976 by Diffie and Hellman [DH76] security of most cryptosystems is based on the (assumed) hardness of factoring or computing discrete logarithms. Only a few schemes based on other problems remain unbroken. Among which there is the McEliece scheme [St95] based on the computational difficulty of decoding a random code. It is still a challenge to develop new public key cryptosystem originating from the hardness of non number-theoretic problems.

In a pioneer work Ajtai [A96] constructed an efficiently computable function which is hard to invert on the average if the underlying lattice problem is intractable in the worst-case. This result has inspired many researchers. Ajtai

1 \begin{matrix}c \\ ◯ \end{matrix}Springer-Verlag, Berlin/Heidelberg 1999. This paper was presented at the 7^{th} IMA conference Cryptography and Coding which took place 20–22 December 1999 at the Royal Agricultural College, Cirencester, UK. The proceedings have been published as Springer Lecture Notes in Computer Science, vol. 1746, editor Michael

Walker (pp. 244–257). See http://www.springer.de/comp/lncs/index.html.

himself and Dwork [AD97] designed a public key cryptosystem based on the worst-case hardness of a lattice problem. But Nguyen and Stern [NS98] show that breaking the Ajtai-Dwork cryptosystem is unlikely N P-hard and for realistic choices of the parameters one may recover the private key from the public key.

Using the idea from the McEliece cryptosystem it is straightforward to set up a cryptosystem based on the hardness of the Closest-Vector-Problem (CVP). A message is encoded as a lattice point plus a small error vector. To decipher the encrypted message look for the closest lattice point eliminating the small error. The open problem (which we address in this paper) is to find a suitable trapdoor. For the general case the only known trapdoor is an obvious one: a strongly reduced lattice base. But:

– If we apply lattice reduction algorithms to compute a reduced base for a given lattice, then an adversary can do it, too.

– In general it is not known how to create strongly reduced bases.

At Crypto ’97 Goldreich, Goldwasser and Halevi [GGH97] took a practical approach to design a CVP-based cryptosystem (GGH scheme). Based on experiments they restrict themselves to a class of lattices defined by rather simple reduced bases. But simple attacks on the secret key show some weakness in the security of the trapdoor [SF^{+}97]. A detailed cryptanalysis is given by Nguyen [N99].

In this paper we propose two trapdoors for the Closest-Vector-Problem based on the tensor product. We build a kind of strongly reduced lattice base using the tensor product of low dimensional lattices. The construction resembles to iterated codes where one efficiently decodes the tensor product given decoding algorithms for the individual codes. The second idea also applies the tensor product of lattices but in a different way. Finding the nearby vector in one component lattice enables to solve a restricted closest vector problem for the tensor product which is used to hide this secret structure.

2 Lattices, Reduction and Closest-Vector-Problem

In this section we recall facts about lattices and lattice reduction. To simplify, we usually restrict ourselves to full dimensional lattices.

Definition 1 (Lattice). Given an ordered set (matrix) B := [b_{1}, b_{2}, …, b_{n}] of n linear independent column vectors in IR^{m}, the set of all integral linear combinations of the vectors

L = L(B) := {∑_{i=1}^{n} t_{i}b_{i} | t_{i} ∈ ZZ } = ∑_{i=1}^{n} ZZb_{i}

is called a lattice generated by the base B. Its dimension is dim L := n and if n = m we call it a full dimensional lattice. The vectors L are called lattice points. A lattice L_{sub} ⊆ L with dim L_{sub} = dim L is a sublattice of L. Sublattices of ZZ^{m} are called integer lattices.

For example, ZZ^{n} is a lattice and

D_{n} := {v ∈ ZZ^{n} | ∑_{i=1}^{n} v_{i} ≡ 0 (mod 2)}

is a sublattice of ZZ^{n} with [ZZ^{n} : D_{n}] = 2 as there are exactly two cosets representing the vectors where the sum of entries is even/odd. Another integer lattice originating from coding theory is E_{n} which can be written for n ≡ 0 (mod 4) as

E_{n} = {v ∈ ZZ^{n} | ∑_{i=1}^{n} v_{i} ≡ 0 (mod 4), v_{i} ≡ v_{i+1} (mod 2)} .

We have [ZZ_{n} : E_{n}] = 2^{2}·2^{n−1} = 2^{n+1}. These lattices D_{n} and E_{n} are well-studied [CS88, Chapter 4].

There are several bases for a lattice. Multiplying a base vector with −1 or adding an integral multiple of another base vector does not change the generated lattice. Two bases B, B′ generate the same lattice iff there is an unimodular matrix

U ∈ GL_{n}(ZZ) := {U ∈ ZZ^{n×n} | det U = ±1}

with B′ = BU (note that GL_{n}(ZZ) is a group).

Definition 2 (Reciprocal Base and Lattice). If B is a base for the lattice L ⊆ IR^{m}, then the unique m × n matrix B^{∗} with B · (B^{∗})^{T} = Id_{n} is called the reciprocal (or dual) base to B. The lattice L^{∗} := L(B^{∗}) is called the reciprocal lattice to L.

The relation between primal/dual lattice and the lattice determinant are independent of the chosen lattice base for the lattice L:

Definition 3 (Determinant). The determinant det L of a lattice L = L(B) with base vectors b_{1}, b_{2}, …, b_{n} is the n-dimensional volume of the fundamental parallelepiped ∑_{i=1}^{n}[0, 1)b_{i} which equals \sqrt{det(BB^{T})} and in case of a full dimensional lattice |det B|.

Obviously det ZZ^{n} = 1 and using [L : L_{sub}] = det L_{sub}/ det L one derives det D_{n} = 2 and det E_{n} = 2^{n+1}. For a full dimensional lattice L ⊆ ZZ^{n} we have (det L) · e_{i} ∈ L for i = 1, 2, …, n [DKT87]. Thus, given a lattice base b_{1}, b_{2}, …, b_{n} one derives a base “reduced modulo the lattice determinant” for the same lattice by iteratively adding integral multiples of (det L) · e_{i} ∈ L such that the n vectors are linear independent and their entries are in [0, det L].^{2}

With a base b_{1}, b_{2}, …, b_{n} of a lattice L we associate the Gram-Schmidt orthogonalization b̂_{1}, b̂_{2}, …, b̂_{n} which is computed together with the Gram-Schmidt coefficients μ_{i,j} := ⟨b_{i}, b̂_{j}⟩ / ∥b̂_{j}∥ for i > j by the recursion b̂_{1} := b_{1}

2 We cannot simply reduce the base vectors entries modulo det L because then the resulting vectors may be linear dependent and do not generate the lattice (for example, take L = 2ZZ, b_{1} = 2 and det L = 2).

and

b̂_{i} := b_{i} − ∑_{j=1}^{i−1} μ_{i,j}b̂_{j} for i = 2, 3, …, n.

∥b̂_{i}∥ is the height of the i^{th} base vector. Unless stated otherwise, we use the standard scalar product ⟨·, ·⟩ and the corresponding Euclidean norm ∥·∥. Letting μ_{i,i} := 1 and μ_{i,j} := 0 for i < j one gets the Gram-Schmidt decomposition

[b_{1}, b_{2}, …, b_{n}] = [ b̂_{1}, b̂_{2}, …, b̂_{n}] · [μ_{i,j}]^{T} .

Observe that det L = ∏_{i=1}^{n} ∥b̂_{i}∥ and that in general the vectors b̂_{1}, b̂_{2}, …, b̂_{n} do not generate the lattice L. Call π_{i} the orthogonal projection

π_{i} : span{b_{1}, b_{2}, …, b_{n}} → span{b_{1}, b_{2}, …, b_{i}}^{⊥}.

We have π_{i}(b_{i}) = b̂_{i}.

Definition 4 (Successive Minima). The i^{th} successive minimum λ_{i}(L) of a lattice L ⊆ IR^{m} is the smallest ρ > 0 such that there are i linear independent lattice points v_{1}, v_{2}, …, v_{i} ∈ L \ {0} with ∥v_{i}∥ ≤ ρ.

For example, λ_{1}(ZZ^{n}) = 1, λ(D_{n}) = \sqrt{2} and λ_{1}(E_{n}) = \sqrt{8} for n ≥ 8 [CS88]. Minkowski derived a general upper bound for the first successive minimum in terms of the lattice determinant [Ca97]:

Proposition 1 (Minkowski 1896). If L ⊆ IR^{m} is a lattice, then

λ_{1}(L) ≤ \sqrt{m} · (det L)^{\frac{1}{dim L}} .

If we scale the lattice by a factor σ > 0, i.e. multiply each lattice point by σ, the successive minimum are scaled, too. To normalize the quantity λ_{1}(L) one takes the ratio λ_{1}(L)/ det L^{\frac{1}{dim L}}. The squared maximum of this ratio for full dimensional lattices is called the Hermite constant γ_{n}. According to the previous proposition we have γ_{n} ≤ n.

The closest lattice point is uniquely determined if the minimal distance is less than \frac{1}{2}λ_{1}(L) because otherwise the difference of two distinct nearby vectors would be a non-zero lattice point with length less than λ_{1}(L). Given the value for the lattice determinant we look for lattices with large first successive minimum (so called dense lattices).

Definition 5 (Closest-Vector-Problem CVP). Given a full dimensional lattice L ⊆ IR^{n} and a point x ∈ IR^{n} the Closest-Vector-Problem is to find a lattice point b ∈ L with minimal distance μ(L, x) := min_{b∈L} ∥x − b∥.

CVP is N P-hard [Boas81,K87] and for large dimension it is conjectured to be “average-case” intractable. On the other hand, Babai [B86] proposed a procedure which efficiently approximates the nearby vector within a factor of 2^{n/2}. Using a (fairly theoretical) algorithm of Schnorr [S87] one approximates in polynomial time the closest vector up to a factor (1+ϵ)^{n} for any fixed ϵ > 0, but the running time badly depends on ϵ. If the distance μ(L, x) is below a threshold and we know a suitable (reduced) base B for the lattice L, then CVP can be easily solved [B86,FK89]:

Lemma 1 (Nearest Plane). Suppose L is a full dimensional lattice given by a base b_{1}, b_{2}, …, b_{n} with ∥b̂_{i}∥ > 2d. For x ∈ IR^{n} with μ(L, x) ≤ d one can efficiently compute the uniquely determined closest lattice vector.

The aim of lattice reduction is to find a base such that the vectors are rather orthogonal and the heights are large. We define lattice reduction in terms of the generalized β-reduction introduced by Schnorr [S87,S94]:

Definition 6 (Lattice Reduction). Given a base B = [b_{1}, b_{2}, …, b_{n}] and β ∈ [2, n] denote L_{i,β} := L(b_{i}, b_{i+1}, …, b_{min(i+β−1,n)}). We call the base B βreduced if

a) |μ_{i,j}| ≤ \frac{1}{2} for 1 ≤ j < i ≤ n.

b) ∥b̂_{i}∥ = λ_{1} (π_{i}(L_{i,β})) for i = 1, 2, …, n.

There are two special cases: For β = 2 it is called LLL base and for β = n one calls it HKZ base. B is a reciprocal β-reduced base, if the reduction holds for the reverse ordered reciprocal base B^{∗} [LLS90].

For reduced bases in the sense of Hermite, Korkine and Zolotarev (HKZ) the first base vector is a shortest non-zero vector of the lattice. Like finding a shortest non-zero vector (Shortest Vector Problem, SVP) computing a HKZ base is intractable. To the best of our knowledge it is an open problem if a β-reduced base can be efficiently computed for a given lattice (even if β is fixed). For practical purposes an implementation of Schnorr and Hörner [SH95] quickly computes a β-reduced base for β ≤ 50 and n ≤ 200. On the other hand a reduced base in the sense of Lenstra, Lenstra and Lovász (LLL) can be computed in polynomial time [LLL82]. We have the following bounds for the heights of reduced bases:

Proposition 2 ([LLL82,LLS90]). Let B = [b_{1}, b_{2}, …, b_{n}] be a base of the lattice L ⊆ IR^{m}. For i = 1, 2, …, n

a) If B is LLL reduced, then ∥b̂_{i}∥ ≥ \frac{λ_{i}(L)}{2^{(i−1)/2}} ≥ \frac{λ_{1}(L)}{2^{(n−1)/2}} .

b) If B is reciprocal HKZ reduced, then ∥b̂_{i}∥ ≥ \frac{λ_{1}(L)}{γ_{i}} ≥ \frac{λ_{1}(L)}{n}.

For reciprocal β-reduced bases the lower bound is about λ_{1}(L)/γ_{i}·γ_{β}^{n/β} (combine the proof of [LLS90, Prop. 4.1] and [S94, Theorem 4]).

3 Tensor Product of Lattices

Starting in 1954 when P. Elias introduced so called iterated or product code the tensor product has become a major way to combine two codes [MS77]. Given two error correcting codes C_{1}, C_{2} with generator matrices G_{1}, G_{2} the iterated code C is the tensor product C_{1}⊗C_{2} which is generated by the so called Kronecker product (direct product) G_{1} ⊗ G_{2} of both generator matrices. The minimal distance d(C) equals to d(C_{1}) · d(C_{2}), i.e. the product of the minimal distances of the component codes.

The tensor product applies to lattices, too [M96]. Given two full dimensional lattice bases A, B the Kronecker product A ⊗ B of the two matrices is a base for the tensor product L(A)⊗L(B) which is a lattice, too. The Kronecker product of a k × ℓ matrix A = [a_{ij}] and an m × n matrix B = [b_{ij}] is the km × ℓn matrix obtained from A by replacing each entry a_{ij} by a_{ij}B.

A = [\begin{matrix}a_{11} & … & a_{1ℓ} \\ ⋮ & ... & ⋮ \\ a_{k1} & … & a_{kℓ} \end{matrix}] A ⊗ B = [\begin{matrix}a_{11}B & … & a_{1ℓ}B \\ ⋮ & ... & ⋮ \\ a_{k1}B & … & a_{kℓ}B \end{matrix}]

For example, scaling a lattice L by a factor σ > 0 can be written as tensor product σL = L⊗σZZ as [σ] is a base of σZZ. Despite the fact that in general A ⊗ B ≠ B ⊗ A the associative and distributive law still hold [L96]:

A ⊗ (B ⊗ C) = (A ⊗ B) ⊗ C
(A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD).

Let L := L_{1}⊗L_{2} denote the tensor product of two full-dimensional lattices L_{1} ⊆ IR^{n_{1}} and L_{2} ⊆ IR^{n_{2}}. The lattice point b := (b_{1}, b_{2}, …, b_{n_{1}n_{2}}) ∈ L can be written as a two dimensional array

b_{1}  b_{2}  … b_{n_{2}} ∈ L_{2}
b_{n_{2}+1}  b_{n_{2}+2}  … b_{2n_{2}} ∈ L_{2}
⋮  ⋮  ⋮  ⋮
b_{(n_{1}−1)n_{2}+1} b_{(n_{1}−1)n_{2}+2} … b_{n_{1}n_{2}} ∈ L_{2}
∈  ∈  ∈
L_{1}  L_{1}  L_{1}

such that the column vectors belong to the lattice L_{1} and the row vectors to L_{2}. The converse is true for product codes but not for lattices: for example, 2 ∈ 2ZZ but 2 ∉ 2ZZ⊗2ZZ = 4ZZ.

Finally, let us recall some facts about the tensor product of lattices, for details see [K93, Chapter 7] or [M96, §1.10]. It is easy to verify [M96, Prop. 10.1]:

Proposition 3. Suppose L_{1}, L_{2} are two full dimensional lattices. Then

dim(L_{1}⊗L_{2}) = dim L_{1} · dim L_{2}
det(L_{1}⊗L_{2}) = (det L_{1})^{dim L_{2}} · (det L_{2})^{dim L_{1}}.

Using induction we derive for the tensor product of t lattices L_{1}, …, L_{t}:

det(L_{1}⊗ ⋯ ⊗L_{t}) = ∏_{i=1}^{t} det L_{i}^{∏_{j≠i} dim L_{j}}.  (1)

For the first successive minimum we have the following result given in Lemma 7.1.1 and Theorem 7.1.1 of [K93]. The bound 43 is related to the Hermite constant γ_{n} for which only lower and upper bounds are known (except for n ≤ 8).

Proposition 4. Suppose L_{1}, L_{2} are two full dimensional lattices. Then

λ_{1}(L_{1}⊗L_{2}) ≤ λ_{1}(L_{1}) · λ_{1}(L_{2})

with equality if dim L_{1} ≤ 43 or dim L_{2} ≤ 43.

For any dimension n ≥ 292 examples with non-equality are known. Compared to the tensor product of two codes this differs as the minimal distance of iterated codes always equals to the product of the minimal distances.

4 CVP-based Public Key Cryptosystems

We describe the general frame work for public key cryptosystems based on the computational hardness of CVP and present a general attack on these schemes. We compare these systems with the well-known analogous McEliece scheme based on error correcting codes.

Frame Work. We call lattices L ⊆ IR^{n} d(n)-decodable if using a trapdoor one can easily determine the nearby vector for x ∈ IR^{n} with μ(L, x) ≤ d(n) (bounded distance decoding). Let B be a base of the d(n)-decodable lattice L. The trapdoor (for example B) is the secret key. The public key consists of a base B_{pub} for the public lattice L_{pub} := L(B_{pub}) which is related to L (or even equals L). By choosing a public base B_{pub} one must regard two aspects:

1. Given the base B_{pub} an adversary may not get “useful information” about the secret trapdoor enabling him to break the system.

2. It should be intractable to solve the closest vector problem by simply applying lattice reduction to B_{pub}.

To avoid native attacks select a random unimodular matrix U transforming the base B. Analogous to the McEliece scheme we use a random orthogonal mapping R (rotation, i.e. R^{−1} = R^{T}) to hide the trapdoor (tensor lattice structure). Set

B_{pub} := R · (BU).

Note that rotating the base also changes the lattice, i.e. L_{pub} = R(L), meanwhile this does not change the vector lengths nor the lattice determinant. To encrypt a message m ∈ ZZ^{n} select an error vector e ∈ IR^{n} with ∥e∥ ≤ d(n) and send

y := B_{pub}m + e = RBUm + e.

Using the trapdoor one determines the closest vector to R^{−1}y = B(Um) + R^{−1}e which is b := Um because ∥R^{−1}e∥ = ∥e∥ ≤ d(n). Now U^{−1}b equals the plaintext m.

Choosing the unimodular matrix U is done by multiplying several elementary matrices (representing the elementary operations: exchanging two columns, adding a multiple of a column to another, flipping the sign of a column) [GGH97]. Choosing a random rotation R is more difficult. This problem has been addressed by Sloane [Sl82] suggesting orthogonal matrices based on Hadamard matrices. This solves a second problem as, in general, orthogonal matrices have real coefficients. But for the restricted class of orthogonal matrices the elements are rational numbers such that scaling the lattice by \sqrt{n} yields an integer one (details are given in Appendix A). Then we can reduce the public base “modulo det L_{pub}”.

But scaling has a disadvantage: The determinant increases by a factor (\sqrt{n})^{n} and the bit length of the public key grows by O(n^{3} log_{2} n) bits. So depending on the trapdoor and efficiency one may use only a permutation matrix P instead of a rotation R. Or simply apply a unimodular transformation without any rotation. The GGH scheme just applies a permutation as the structure of the secret base is publicly known. It uses as secret key a random lattice base

B ∈_{R} \sqrt{n} · Id_{n} +[−4, +4]^{n×n}

which (based on experiments) enables one to decrypt a message with probability of order 1 − \frac{1}{n} for a random error vector e ∈_{R} \{±σ\}^{n} where σ = 2.

Finding the Tensor Decomposition. To the best of our knowledge no efficient algorithm for finding a tensor lattice decomposition is known. For matrices over a finite field a tensor decomposition can be found in (small) dimensions [OL97]. But for the CVP trapdoor the matrices are over ZZ, the dimension is rather large and the coordinates are permutated (respectively we rotate the lattice).

One possible weakness is the special form of the lattice determinant (1). Factoring this number may yield the dimension of the component lattices. To counteract this possible weakness simply choose lattices with equal determinant whose dimensions have many prime factors (for example, powers of 2). For a small number of component lattices (say t = 2) one might alternatively select lattices with determinants having many prime factors in a way that factoring (1) permits many decompositions. Even if the adversary cannot deduce the dimensions from the determinant he knows that the dimensions of the component lattices are at most 43. In case of a small number of component lattices the adversary might try all possible decompositions of the dimension.

To undo the permutation P the adversary tries to identify coordinates belonging to the same copy of a component lattice. Let L_{1} = L(A) and L_{2} = L(B) denote the component lattices and L := P (L_{1}⊗L_{2}) the public key. From the proof given in Appendix B we derive

det L = ∏_{i=1}^{dim L_{1}} ∏_{j=1}^{dim L_{2}} ∥â_{i}∥ · ∥b̂_{j}∥ = ∏_{i=1}^{dim L_{1}} ∥â_{i}∥^{dim L_{2}} det L_{2}.

If one removes a coordinate then the heights change, the new lattice has no tensor structure and the determinant is no longer of the form (1). But if we delete dim L_{2} coordinates belonging to the same i^{th} copy of the component lattice L_{2}, then the lattice determinant is divided by ∥â_{i}∥^{dim L_{2}} det L_{2}. But in general this in no integer because the height is a real number (although its square is a rational number). So the adversary cannot verify the correctness of his choice by checking the divisibility. For higher dimension this “attack” is intractable as there are \binom{dim L_{1}·dim L_{2}}{dim L_{2}} possible choices.

Attacks by Lattice Reduction. There is a simple but very powerful heuristic attack on the GGH scheme and all other CVP-based cryptosystems [SF^{+}97]. Given an encrypted message x = B_{pub}m+e apply a lattice reduction algorithm to the lattice L_{ext} generated by the (n + 1) × (n + 1) matrix

B_{ext} := [\begin{matrix}x & B_{pub} \\ 1 & 0 \end{matrix}] = [\begin{matrix}e & B_{pub} \\ 1 & 0 \end{matrix}] · U, for some U ∈ GL_{n+1}(ZZ).

Experiments suggest that the shortest non-zero vector of L_{ext} is e_{ext} := ±(e, 1) (which yields the plaintext) and that λ_{2}(L_{ext}) = λ_{1}(L_{pub}). To retrieve e_{ext} the adversary approximates the shortest vector for L_{ext} within a factor less than λ_{1}(L_{pub})/ ∥e∥ (ignoring the additional ±1 entry).^{3} To minimize this ratio take ∥e∥ ≈ \frac{1}{2}λ_{1}(L) such that the adversary retrieves the message if he computes the shortest non-zero vector up to a factor of ≈ 2. The LLL algorithm [LLL82] approximates the shortest vector up to a factor of 2^{\frac{n−1}{2}} and for β-reduced bases the factor is about 2^{n/β} [S94, Theorem 4].

Although in case of the GGH scheme one must approximate the shortest vector within a factor 2, in dimension 150 it takes 15 minutes to retrieve the error vector [SF^{+}97]. As within 1\frac{1}{2} hours lattice reduction even yields the secret key for the lattice. Thus, it is questionable if the class of lattice is a good choice. The recent cryptanalysis of Nguyen [N99] strengthens these results and reveals a second weakness: as e ∈ {±σ}^{n} the adversary retrieves m mod 2σ by solving the modular system

y + [σ, …, σ]^{T} = B_{pub}m (mod 2σ)

which simplifies the closest vector problem where the error vector length is now \frac{1}{2} \sqrt{n} compared to σ\sqrt{n}. To counteract this attack the error vector should not have a pattern like e ∈ {±σ}^{n}. For example, take a random e ∈_{R} [−σ, +σ]^{n}.

Comparison with McEliece Scheme. Although being one of the first public key cryptosystems and still remaining unbroken the McEliece scheme has not become widely used because rather large key is required. It is commonly believed that CVP-based cryptosystems are weaker than the analogous McEliece schemes

3 We say an algorithm approximates the shortest vector for the lattice L within a factor τ ≥ 1 if it outputs b ∈ L \ {0} with ∥b∥ ≤ τ · λ_{1}(L).

due to the powerful lattice reduction algorithms. On the other hand, the strong attacks on the McEliece schemes [CSe98] seem not to be suitable for its lattice based variants. Let G be the generating n × k matrix of the secret [n, k, d] error correcting code C, i.e. C ⊆ {0, 1}^{n}, dim C = k and the minimal Hamming distance is d. The public matrix for the McEliece scheme is

G_{pub} := SGP

over the field ZZ/2ZZ where S ∈ GL_{k}(ZZ/2ZZ) and P is a permutation matrix. The matrix S ensures that the generating matrix G is not systematic, e.g. G ≠ [Id_{k} A], because otherwise an encrypted message y := mG_{pub} + r reveals some bits of the plain text. The trapdoor (the error correcting code) is only hidden by applying the permutation which restricts the class of suitable codes.

For codes and lattices multiplying the generating matrix respectively base matrix by an unimodular matrix does not change the code and lattice. Applying a permutation P changes the code into an equivalent code while the hamming weight of code words remains. Applying a rotation R changes the lattice into an isometric lattice while the Euclidean length of lattice vectors remains. In both cases knowing the transformation one reduces decoding respectively find the closest vector to the original code (lattice). But without this knowledge it is assumed that an adversary does not get any “useful information” about the underlying structure.

Although there are unique normal forms for lattice bases (like the Hermite normal form [DKT87,Co93]) they do not play the same role as systematic generator matrices for codes where most algorithms are based on this form. The well-known normal forms for lattice bases rely on the matrix structure rather on reduced lattice bases. Nevertheless the known SVP algorithms are far more powerful than algorithms for finding the smallest code word. Thus, it seems that the McEliece scheme is more liable to structural attacks trying to retrieve the secret key meanwhile for CVP systems it is easier to regain the error vector of a single message.

CVP-Trapdoor Based on Tower of Error Correcting Codes. Given a tower C_{t} ⊆ C_{t−1} ⊆ ⋯ ⊆ C_{1} ⊆ {0, 1}^{n} of (suitable)^{4} binary nested error correcting codes one uses “Construction D” of Barnes and Sloane [CS88, Chapter 8.1] to create a dense lattice L. The closest vector is found using a bounded-distance multi-stage decoding algorithm based on the error correcting codes [F89]. Although we can find the unique closest vector up to the limit \frac{1}{2}λ_{1}(L) it may be difficult to find a suitable tower. Lattices generated by the given examples [CS88] are well-known such that an adversary even might conclude the underlying choice from the public lattice base. As the choice for the tower is restricted in most cases we have t = 1. Then the lattice is L = C + 2ZZ^{n} for a binary code C (whose code words are written as elements of ZZ^{n}) and the trapdoor equals

4 The choice of the error correcting codes has to be restricted to ensure that L is actually a lattice.

the McEliece trapdoor. The construction can be relaxed [CP94,FV96] but these lattices have a higher dimension and are not as dense as for “Construction D”.

5 HKZ-Tensor-Trapdoor

We construct a kind of strongly reduced lattice bases for a large general class of lattices using the tensor product to iteratively combine low dimensional lattices. If A and B are reciprocal HKZ-reduced then the lower bound for the heights of A ⊗ B is the product of both lower bounds. This enables us to apply Nearest-Plane like given a reciprocal HKZ base. In Appendix B we show:

Proposition 5. Suppose A and B are bases of two lattices with ∥â_{i}∥ ≥ h_{A} and ∥b̂_{i}∥ ≥ h_{B}. For the base C := A ⊗ B of L(A)⊗L(B) we have ∥ĉ_{i}∥ ≥ h_{A}h_{B}.

Using this result, one sets up the candidate trapdoor by composing the lattice L with dimension n out of t lattices L_{1}, L_{2}, …, L_{t} with dim L_{i} ∈ [2, 43]. For simplicity we assume all lattices have the same dimension c, e.g. n = c^{t} and t = log_{c} n. As we do not require any secret structure for the underlying low dimensional lattices we take “random” lattices (see discussion in Appendix C). For these lattices of fixed and low dimension we can efficiently compute (reciprocal) HKZ bases both in a theoretical setting [K87] and in practice [SH95]. Let B_{1}, B_{2}, …, B_{t} denote the reciprocal HKZ bases,

B := B_{1} ⊗ B_{2} ⊗ … ⊗ B_{t}

their Kronecker product and L := L(B) the tensor product lattice. By induction based on Proposition 3 we derive

det L = ∏_{i=1}^{t}(det L_{i})^{c^{t}} = (∏_{i=1}^{t} det L_{i})^{n}

and according to Proposition 4 and Proposition 5:

λ(L) = ∏_{i=1}^{t} λ_{1}(L_{i})  ∥b̂_{i}∥ ≥ ∏_{i=1}^{t} \frac{λ_{1}(L_{1})}{γ_{c}} = \frac{λ_{1}(L)}{γ_{c}^{t}}

Now applying Nearest-Plane we are in the same situation as given a reciprocal HKZ base for the lattice L. Using the Kronecker product of the reciprocal HKZreduced bases we find the nearby vector if the distance is below \frac{1}{γ_{c}^{t}} λ_{1}(L). An adversary trying to find the error vector by embedding it into a SVP problem has to approximate the shortest lattice vector within a factor at least γ_{c}^{t}. Using stronger bounds [CS88, Chapter 1] we have γ_{c} < 1.75 + 0.12c for c ∈ [8, 50]. For n = 529 this means: taking two 23-dimensional lattices (i.e. c = 23, t = 2), the adversary has to approximate the shortest vector within a factor less than 21. Note, this is a worst case scenario and by building the lattice one may simply re-select a small lattice L_{i} if the heights of the HKZ base are too close to \frac{λ_{1}(L_{i})}{γ_{c}}.

6 Tensor-Hiding-Trapdoor

Again, we use the tensor product but unlike creating a reduced base for the product we try to hide the component lattices. We solve a restricted Closet-Vector-Problem for the tensor product using an algorithm which finds the nearby vector in a component lattice. To generate a candidate trapdoor for an n-dimensional lattice L select two full dimensional lattices L_{decode} and L_{hide} with the following properties:

– We have n_{decode} := dim L_{decode} ≤ 43, n_{hide} := dim L_{hide} = \frac{n}{n_{decode}} .

– L_{decode} is a dense lattice, i.e., for a given lattice determinant the first successive minimum λ_{1}(L_{decode}) is large.

– For the lattice L_{decode} we efficiently find the nearby vector if the distance is at most a large threshold d_{decode}, for example d_{decode} ≈ \frac{1}{2}λ_{1}(L_{decode}). Let σ := d_{decode}/\sqrt{n_{decode}} denote the distances in terms of the maximum norm.

– We have for a small κ ≥ 1:

\frac{\sqrt{2n_{decode}} · d_{decode}}{λ_{1}(L_{decode})} ≤ λ_{1}(L_{hide}) ≤ κ · \frac{\sqrt{2n_{decode}} · d_{decode}}{λ_{1}(L_{decode})}

The lower bound ensures that the plaintext still corresponds to the closest vector and the upper bound makes it intractable finding the message by means of simple lattice reduction.

The lattice L_{decode} may be based on a tower of nested error correcting codes. For the lattice L_{hide} use the tensor product and (for example) the lattices D_{n}, E_{n} or the method given in Appendix C Let L := L_{decode}⊗L_{hide} (or visa versa) denote the public lattice. As in Section 4 we set up the cryptosystem but with two restrictions:

1. The error vector is e ∈ [−σ, +σ]^{n} (note ∥e∥ ≤ \frac{1}{2} \sqrt{2n} · d_{decode}) and

2. Instead of using an orthogonal matrix we just apply a permutation because rotations do not not keep the length in terms of the maximum norm fixed.

According to the choice of λ_{1}(L_{hide}) and n_{decode} ·n_{hide} = n Proposition 4 implies

\sqrt{2n} · d_{decode} ≤ λ_{1}(L) ≤ κ · \sqrt{2n} · d_{decode}.

Retrieving the paintext is done by computing the unique nearby point: given a point y := b + e with b ∈ L we write y as the two-dimensional array and apply the given algorithm to determine the nearby point in L_{decode} for the dim L_{hide} rows. The concatenation of the results is the closest vector in L because otherwise there are two nearby lattice points. On the other hand, an adversary trying to find the error vector by embedding it into a SVP problem has to approximate the shortest lattice vector within a factor of at least 2κ. To avoid lattice reduction attacks the lattice dimension should be at least 500.

7 Conclusions and Open Problems

We have suggested two trapdoors for the Closest-Vector-Problem based on the conjectured computational difficulty of finding tensor decomposition after applying a permutation (respectively a rotation). It is nearly as hard as possible to retrieve the cipher text by means of simply applying lattice reduction such that these “brute force” attacks should not succeed. But like the McEliece scheme the public key is very large in a way that CVP-based crypto systems have no practical impact as long as factoring or discrete logarithm remain intractable.

Given two lattices L_{1}, L_{2} and oracles solving the closest vector problem in L_{1}, L_{2}, can one efficiently compute the nearby vector for the tensor product L_{1}⊗L_{2}? To the best of our knowledge this is an open problem whereas iterated codes are majority decodable if one of the component codes is majority decodable [R70]. Can one take advantage from these decoding algorithm? One obstacle may be that for tensor lattices the lattice vectors cannot be characterized by a two dimensional array as opposite to product codes.

8 Acknowledgment

We thank Marc Fischlin for proof reading.

References

[A96] M. Ajtai: Generating Hard Instances of Lattice Problems, in Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, pp. 402–412, 1996.

[AD97] M. Ajtai and C. Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, in Proceedings of the 29^{th} Annual ACM Symposium on Theory of Computing (STOC), ACM Press, pp. 284–293, 1997.

[B86] L. Babai: On Lovász’ Lattice Reduction and the Nearest Lattice Point Problem, Combinatorica, vol. 6, pp. 1–13, 1986.

[CSe98] A. Canteaut and N. Sendrier: Cryptanalysis of the Original McEliece Cryptosystem, Advances in Cryptology — Proceedings Asiacrypt ’98, Lecture Notes in Computer Science, vol. 1541, Springer Verlag, Berlin/Heidelberg, pp. 187-199, 1998.

[Ca97] J.W.S. Cassels: An Introduction to the Geometry of Numbers, Springer Verlag, Berlin/Heidelberg, 1997.

[Co93] H. Cohen: A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer Verlag, Berlin/Heidelberg, 1993.

[CS88] J.H. Conway and N.J. Sloane: Sphere Packings, Lattices and Groups, Springer Verlag, New York, 1988.

[CP94] M.A.O. da Costa e Silva and R. Palazzo, Jr.: A Bounded-Distance Algorithm for Lattices Obtained from a Generalized Code Formula, IEEE Transaction on Information Theory, Vol. 40(6), pp. 2075–2082, 1994.

[DKT87] P.D. Domich, R. Kannan and L.E. Trotter: Hermite Normal Form Computation using modulo Determinant Arithmetic, Mathematics of Operation Research, vol. 12(1), pp. 50–59, 1987.

[DH76] W. Diffie and M. Hellman: New Directions in Cryptography, IEEE Transaction on Information Theory, Vol. 22(6), pp. 644–654, 1976.

[D97] C. Dwork: Positive Applications of Lattices to Cryptography, Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 1295, Springer Verlag, Berlin/Heidelberg, pp. 44–51, 1997.

[Boas81] P. van Emde Boas: Another N P-complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice, technical report 81-04, Department of Mathematics, University of Amsterdam, 1981.

[FK89] M.L. Furst and R. Kannan: Succinct Certificates for Almost all Subset Sum Problems, SIAM Journal on Computing, vol. 18(3), pp. 550–558, 1989.

[F89] G.D. Forney, Jr.: A Bounded-Distance Algorithm for the Leech Lattices with Generalization, IEEE Transaction on Information Theory, Vol. 35(4), pp. 960–909, 1989.

[FV96] G.D. Forney, Jr. and A. Vardy: Generalized Minimum Distance Decoding of Euclidean-space Codes and Lattices, IEEE Transaction on Information Theory, Vol. 42, pp. 1992–2026, 1996.

[GGH97] O. Goldreich, S. Goldwasser and S. Halevi: Public-Key Cryptosystems from Lattice Reduction Problems, Advances in Cryptology — Proceedings Crypto ’97, Lecture Notes in Computer Science, vol. 1294, Springer Verlag, Berlin/Heidelberg, pp. 112–131, 1997. Previous version as ECCC report TR96-056.

[K87] R. Kannan: Minkowski’s Convex Body Theorem and Integer Programming, Mathematics of Operation Research, vol. 12(3), pp. 415–440, 1987.

[K93] Y. Kitaoka: Arithmetic of Quadratic Forms, Cambridge Tracts in Mathematics, vol. 106, Cambridge University Press, Cambridge, 1993.

[LLL82] A.K. Lenstra, H.W. Lenstra and L. Lovász: Factoring Polynomials with Rational Coefficients, Springer Mathematische Annalen, vol. 261, pp. 515– 534, 1982.

[LLS90] J.C. Lagarias, H.W. Lenstra and C.P. Schnorr: Korkin-Zolotarev Bases and successive Minima of a Lattice and its Reciprocal Lattice, Combinatorica, vol. 10, pp. 333–348, 1990.

[L96] H. Lütkepohl: Handbook of Matrices, John Wiley & Son, Chichester, England, 1996.

[MS77] F.J. MacWilliams and N.J. Sloane: The Theory of Error Correcting Codes, North-Holland Mathematical Library Vol. 16, North-Holland, Amsterdam, 1977.

[M96] J. Martinet: Les Réseaux Parfaits des Espaces Euclidiens, Masson, Paris, 1996.

[MO90] J.E. Mazo and A.M. Odlyzko: Lattice Points in high-dimensional Spheres, Monatshefte Mathematik, vol. 110(1), pp. 47–61, 1990.

[NS98] P. Nguyen and J. Stern: Cryptanalysis of the Ajtai-Dwork Cryptosystem, Advances in Cryptology — Proceedings Crypto ’98, Lecture Notes in Computer Science, vol. 1294, Springer Verlag, Berlin/Heidelberg, pp. 223–242, 1998.

[N99] P. Nguyen: Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97, Advances in Cryptology — Proceedings Crypto ’99, Lecture Notes in Computer Science, vol. 1666, Springer Verlag, Berlin/Heidelberg, pp. 288–304, 1999.

[OL97] E. O’Brien and C.R. Leedham-Green: Recognising Tensor Products of Matrix Groups, International Journal Algebra Computing, vol. 7, pp. 541– 559, 1997.

[PS87] A. Paz and C.P. Schnorr: Approximating Integer Lattices by Lattices with cyclic Factor Group, in Proceedings of the 14.th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 267, Springer Verlag, Berlin/Heidelberg, pp. 386–393, 1987.

[R70] S.M. Reddy: On Decoding Iterated Codes, IEEE Transaction on Information Theory, Vol. 16(5), pp. 624–627, 1970.

[S87] C.P. Schnorr: A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms, Theoretical Computer Science, vol. 53, pp. 201–224, 1987.

[S94] C.P. Schnorr: Block Reduced Lattice Bases and Successive Minima, Combinatorics, Probability and Computing, vol. 3, pp. 507–522, 1994.

[SH95] C.P. Schnorr and H.H. Hörner: Attacking the Chor-Rivest Cryptosystem by improved Lattice Reduction, Advances in Cryptology — Proceedings Eurocrypt ’95, Lecture Notes in Computer Science, vol. 921, Springer Verlag, Berlin/Heidelberg, pp. 1–12, 1995.

[SF^{+}97] C.P. Schnorr, M. Fischlin, R. Fischlin, H. Koy and A. May: Lattice

Attacks on the GGH Cryptosystem, Crypto ’97 Rump Session, 1997.

[Sl82] N.J.A. Sloane: Encryption by Random Rotations, in Proceedings of the Workshop on Cryptography Burg Feuerstein, 1982, Lecture Notes in Computer Science, vol. 149, Springer Verlag, Berlin/Heidelberg, pp. 71–128, 1983.

[St95] D.R. Stinson: Cryptography: Theory and Practice, CRC Press, Boca Raton, 1995.

A Quasi-random Orthogonal Matrix

In Section 4 we faced the problem how to generate a random orthogonal matrix and how to transform the possible real lattice into an integer one. Sloane [Sl82] has suggested using orthogonal matrices based on Hadamard matrices. He calls the generated rotations quasi-random orthogonal matrices. Let H_{n} be a Hadamard matrix of order n, in other words H_{n} is an n × n matrix with coefficients ±1 and H_{n}H_{n}^{T} = nId_{n}. Note that \frac{1}{\sqrt{n}}H_{n} is an orthogonal matrix. Flipping the sign of any row or column changes a Hadamard matrix into another. There are several known constructions for Hadamard matrices if the order n is a multiple of 4 [MS77, Ch. 2, §3]. For example, if n is a power of 2 one gets a Hadamard matrices by the recursion H_{1} = [1] and

H_{2n} = [\begin{matrix}H_{n} & H_{n} \\ H_{n} & −H_{n} \end{matrix}] .

To create an orthogonal matrix choose arbitrary permutations matrices P, P′ and diagonal matrices D, D′ with coefficients ±1. Let

R := \frac{1}{\sqrt{n}} · DP H_{n}P′D′

i.e. we permute and flip the sign of the rows and columns of the Hadamard matrix. Restrict n to powers of 2 and scale the lattice to get integral coefficients:

B_{pub} := \sqrt{n} · RBU = (DP H_{n}P′D′)BU

As we scale the lattice in each direction we have L(B_{pub}) = \sqrt{n} · L(RB). Successive minima and the base heights are also stretched by \sqrt{n} and instead of e with ∥e∥ ≤ d we demand ∥e∥ ≤ \sqrt{n}d. Clearly, the complexity of the closest vector problems remains the same. But the determinant increases by \sqrt{n}^{n}. To reduce this disadvantage may combine independent rotations which apply only to a fixed number c of directions. Select c × c random orthogonal matrices R_{1}, R_{2}, …, R\frac{n}{c} and a n × n permutation matrix P′:

R := P′ · [\begin{matrix}R_{1} \\ & R_{2} & & 0 \\ 0 & & ... \\ & & & R\frac{n}{c} \end{matrix} ] · P′.

Using this class of orthogonal matrices it is sufficient to scale the lattice by a factor \sqrt{c} instead of \sqrt{n}.

B Proof of Proposition 5

Given two bases A, B of lattices with ∥â_{i}∥ ≥ h_{A} and ∥b̂_{i}∥ ≥ h_{B} we show ∥ĉ_{i}∥ ≥ h_{A}h_{B} for the base C := A ⊗ B of L(A)⊗L(B). Recall a well-known result [L96]:

Proposition 6. For two orthogonal matrices A, B the Kronecker product C := A ⊗ B is orthogonal, too.

We use the so called Iwasawa decomposition [Co93, Corollary 2.5.6]. The base matrix C can be uniquely written as C = DOT with

– a diagonal matrix D,

– an orthogonal matrix O and

– an upper triangle matrix T with diagonal elements equal to 1.

Compare the Iwasawa decomposition to the Gram-Schmidt decomposition. As ĉ_{1}, ĉ_{2}, …, ĉ_{n} are orthogonal we have that T is the transposed Gram-Schmidt matrix and the i^{th} diagonal entry of D equals the height ∥ĉ_{i}∥. Let A = D_{A}O_{A}T_{A} and B = D_{B}O_{B}T_{B} denote the Iwasawa decomposition of A and B. Using the associative and distributive law [L96]

U ⊗ (X ⊗ Y) = (U ⊗ X) ⊗ Y
(U ⊗ V)(X ⊗ Y) = (UX) ⊗ (V Y)

we get for the Kronecker product C = A ⊗ B:

C = (D_{A}O_{A}T_{A}) ⊗ (D_{B}O_{B}T_{B})
= ([D_{A}O_{A}] · T_{A}) ⊗ ([D_{B}O_{B}] · T_{B})
= ([D_{A}O_{A}] ⊗ [D_{B}O_{B}]) · (T_{A} ⊗ T_{B})
= (D_{A} ⊗ D_{B}) · (O_{A} ⊗ O_{B}) · (T_{A} ⊗ T_{B}).

D_{A} ⊗ D_{B} is a diagonal matrix

D_{A} ⊗ D_{B} = [\begin{matrix}∥â_{1}∥ · D_{B} & & 0 \\ & ⋯ \\ 0 & & ∥â_{n_{A}}∥ · D_{B} \end{matrix}] D_{B} = [\begin{matrix}∥b̂_{1}∥ & & 0 \\ & ⋯ \\ 0 & & ∥b̂_{n_{B}}∥ \end{matrix}]

where n_{A} := dim L(A) and n_{B} := dim L(B). Applying Proposition 6 yields that O_{A}⊗O_{B} is an orthogonal matrix, too. Finally, it is straightforward to verify that T_{A} ⊗ T_{B} is an upper triangle matrix with diagonal elements equal to 1. Hence, the diagonal coefficients of D_{A} ⊗ D_{B} are the heights of the base C. Using the lower bound for the entries of D_{A}, D_{B} we get the desired lower bound for the heights of the base C. This also proves Proposition 3 as

det C = det(D_{A} ⊗ D_{B}) · \underbrace{det(O_{A} ⊗ O_{B})}_{=±1} · \underbrace{det(T_{A} ⊗ T_{B})}_{=1}

and det(L(A)⊗L(B)) = | det C|.

C Choosing a Random Lattice

We used the term “random lattice” in a sloppy way not precisely defining it. The main reason is that there is no canonical uniform distribution for lattices. One approach is to set up the distribution in terms of lattice bases in a given unique normal form like the Hermite normal form [Co93,DKT87]. A matrix B = [b_{ij}] with full row rank is in Hermite normal form, if

1. B is an lower triangular matrix^{5} and

2. 0 ≤ b_{ij} < b_{ii} for j < i.

Every lattice has a unique lattice base in Hermite normal form where the product of the diagonal elements equals the lattice determinant. To choose a random lattice base B, first select random diagonal coefficients from a given interval b_{ii} ∈_{R} [1, r] and afterwards select the other non-zero coefficients, i.e. b_{j,i} ∈_{R} [0, b_{ii}). This method can be used for generating the underlying lattices for the HKZ-Tensor-Trapdoor introduced in Section 5.

But for the Tensor-Hiding-Trapdoor we require some side information about the first successive minimum, e.g. λ_{1}(L) = Θ(\sqrt{n}) for some small constants. We

5 Some authors define it in terms of an upper triangular matrix.

relax our definition of “random lattices” because to the best of our knowledge given a base in normal form one cannot derive a bound for the first successive minimum beside Minkowski’s upper bound. A well understood class of integer lattices is given by modular homogeneous linear equations [FK89]:

L_{a,m} := {x ∈ ZZ^{n} | ∑_{i=1}^{n} x_{i}a_{i} ≡ 0 (mod m)} .

Paz and Schnorr [PS87] have shown that any integer lattice can be “approximated” by such a lattice. L_{a,m} is a n-dimensional lattice with determinant equal to m/ gcd(a_{1}, …, a_{n}, m). We restrict ourselves to prime moduli turning ZZ/mZZ into a finite field. Fix a prime module p. What is the probability for a ∈_{R} [1, p)^{n} that λ_{1}(L_{a,p}) ≤ k for a given threshold k? Given a non-zero x ∈ S_{n}(k) ∩ ZZ^{n} (where S_{n}(k) denotes the sphere around the origin with radius k), let i with x_{i} ≠ 0. Then x ∈ L_{a,p} iff

x_{i}a_{i} ≡ − ∑_{j≠i} a_{j}x_{j} (mod p).

As p is a prime, given x and a_{j} for j ≠ i, there exists exactly one solution a_{i} in [0, p). This yields:

Pr_{a∈_{R}[1,p)^{n}} [λ_{1}(L_{a,p}) ≤ k] < \frac{|S_{n}(k) ∩ ZZ^{n}|}{p}

It is by no means trivial to derive a (sharp) bound for the number of integer points in a sphere [MO90]. But for our purpose it is sufficient to approximate the number by the volume of the sphere:

vol_{n} (S_{n}(k)) = k^{n} · vol_{n} (S_{n}(1)) = \frac{k^{n} · π^{\frac{n}{2}}}{Γ (1 + \frac{n}{2})}

If k = c_{0}\sqrt{n} for a small constant c_{0}, then for sufficient large n

Pr_{a∈_{R}[1,p)^{n}} [λ_{1}(L_{a,p}) ≤ c_{0}\sqrt{n} ] ≤ \frac{2^{c_{1}n}}{p}

where c_{1} > 0 is a moderate constant, too. Now, choose a random (c_{1} + 1)n bit prime p and a ∈_{R} [1, p)^{n}, then with probability 1 − 2^{n}

c_{0}\sqrt{n} < λ_{1}(L_{a,p}) < \sqrt{n} · 2^{c_{1}+1+ \frac{1}{n}}

where the upper bound is derived using det L_{a,p} = p < 2^{(c_{1}+1)n+1} and Minkowski’s Proposition 1.