Cyclic Lattices, Ideal Lattices and Bounds for the Smoothing Parameter ()
1. Introduction
Cyclic lattices and ideal lattices were introduced by Micciancio in [1], Lyubashevsky and Micciancio in [2] respectively, which play an efficient role in Ajtai’s construction of a collision-resistant Hash function (see [3] and [4]) and in Gentry’s construction of fully homomorphic encryption (see [5]). Let
be a quotient ring of the integer coefficients polynomials ring, Lyubashevsky and Micciancio regarded an ideal lattice as the correspondence of an ideal of R, but they don’t explain how to extend this definition to whole Euclidean space
. Many researchers have presented some results in their works about cyclic lattices and ideal lattices, however, none of them exhibit the relationship between cyclic lattices and ideal lattices.
In this paper, we regard the cyclic lattices and ideal lattices as the correspondences of finitely generated R-modules, so that we may show that ideal lattices are actually a special subclass of cyclic lattices, namely, cyclic integer lattices. In fact, there is a one-to-one correspondence between cyclic lattices in
and finitely generated R-modules (see Theorem 4.9 below). On the other hand, since R is a Noether ring, each ideal of R is a finitely generated R-module, so it is natural and reasonable to regard ideal lattices as a special subclass of cyclic lattices (see Corollary 4.11 below). It is worth noting that we use a more general rotation matrix here, so our definition and results on cyclic lattices and ideal lattices are more general forms. In application, we provide a cyclic lattice with an explicit and countable upper bound for the smoothing parameter (see Theorem 5.5 below). It is an open problem that is the shortest vector problem on cyclic lattice NP-hard (see [1]). Our results may be viewed as substantial progress in this direction.
2. Discrete Subgroup in
Let
be the real numbers field,
be the integers ring and
be Euclidean space of which is an n-dimensional linear space over
with the Euclidean norm
given by
We use column vector notation for
throughout this paper, and
is transpose of x, which is called row vector of
.
Definition 2.1 Let
be a non-trivial additive subgroup, it is called a discrete subgroup if there is a positive real number
such that
(2.1)
As usual, a ball of center
with radius
is defined by
If L is a discrete subgroup of
, then there are only finitely many vectors of L lie in every ball
, thus we always find a vector
such that
(2.2)
is called one of shortest vector of L and
is called the minimum distance of L.
Let
be a
dimensional matrix with
, it means that
are m linearly independent vectors in
. The lattice
generated by B is defined by
(2.3)
which is all linear combinations of
over
. If
,
is called a full-rank lattice.
It is a well-known conclusion that a discrete subgroup L in
is just a lattice
. Firstly, we give a detail proof here by making use of the simultaneous Diophantine approximation theory in real number field
(see [6] and [7]).
Lemma 2.1 Let
be a discrete subgroup,
be m vectors of L. Then
are linearly independent over
, if and only if which are linearly independent over
.
Proof: If
are linearly independent over
, trivially which are linearly independent over
. Suppose that
are linearly independent over
, we consider arbitrary linear combination over
. Let
(2.4)
We should prove (2.4) is equivalent to
, which implies that
are linearly independent over
.
By Minkowski’s Third Theorem (see Theorem VII of [7]), for any sufficiently large
, there are a positive integer
and integers
such that
(2.5)
By (2.4), we have
(2.6)
Let
be the minimum distance of L,
be any positive real number. We select N such that
It follows that
and
By (2.6) we have
Since
, thus we have
,
and
. By (2.5) we have
for all i,
.
Since
is sufficiently small positive number, we must have
. We complete the proof of lemma.
口
Suppose that
is an
-dimensional matrix and
,
is the transpose of B. It is easy to verify
which implies that
is an invertible square matrix of
dimension, here
is the determinant of the matrix
. Since
is a positive defined symmetric matrix, then there is an orthogonal matrix
such that
(2.7)
where
are the characteristic value of
, and
is the diagonal matrix of
dimension.
Lemma 2.2 Suppose that
with
,
are m characteristic values of
, and
is the minimum distance of lattice
, then we have
(2.8)
where
.
Proof: Let
, by (2.7), there exists an orthogonal matrix
such that
If
,
, we have
Since
and
, we have
, it follows that
We have Lemma 2.2 immediately.
口
Another application of Lemma 2.2 is to give a countable upper bound for smoothing parameter (see Theorem 5.5 below). Combining Lemma 2.1 and Lemma 2.2, we show that the following assertion.
Theorem 2.3 Let
be a subset, then L is a discrete subgroup if and only if there is an
dimensional matrix
with
such that
(2.9)
Proof: If
is a discrete subgroup, then L is a free
-module. By Lemma 2.1, we have
. Let
be a
-basis of L, then
Writing
, then the rank of matrix B is m, and
Conversely, let
be arbitrary lattice generated by B, obviously,
is an additive subgroup of
, by Lemma 2.2,
is also a discrete subgroup, we have Theorem 2.3 at once.
口
Corollary 2.4 Let
be a lattice and
be an additive subgroup of L, then G is a lattice of
.
Corollary 2.5 Let
be an additive subgroup, then L is a lattice of
. These lattices are called integer lattices.
According to above Theorem 2.3, a lattice
is equivalent to a discrete subgroup of
. Suppose
is a lattice with generated matrix
, and
, we write
, and
(2.10)
In particular, if
is a full-rank lattice, then
as usual. A sublattice N of L means a discrete additive subgroup of L, the quotient group is written by L/N and the cardinality of L/N is denoted by |L/N|.
Lemma 2.6 Let
be a lattice and
be a sublattice. If
, then the quotient group L/N is a finite group.
Proof: Let
, and
, where
with
. We define a mapping
from L to
by
. Clearly,
is an additive group isomorphism,
is a full-rank lattice of
, and
. It is a well-known result that
It follows that
Lemma 2.6 follows.
口
Suppose that
,
are two lattices of
, we define
. Obviously,
is an additive subgroup of
, but generally speaking,
is not a lattice of
again.
Lemma 2.7 Let
,
be two lattices of
. If
or
, then
is again a lattice of
.
Proof: To prove
is a lattice of
, by Theorem 2.3, it is sufficient to prove
is a discrete subgroup of
. Suppose that
, for any
, we define a distance function
by
Here the function inf(A) is the infimum of a set A. Since there are only finitely many vectors in
, where
is any a ball of center x with radius
. Therefore, we have
(2.11)
On the other hand, if
,
and
, then there is
such that
, and we have
. It means that
is defined over the quotient group
. Because we have the following group isomorphic theorem
By Lemma 2.6, it follows that
In other words,
is also a finite group. Let
be the representative elements of
, we have
Therefore,
is a discrete subgroup of
, thus it is a lattice of
by Theorem 2.3.
口
Remark 2.8 The condition
or
in Lemma 2.7 seems to be necessary. As a counterexample, we see the real line
, let
and
, then
is not a discrete subgroup of
, thus
is not a lattice in
. Because
is dense in
by Dirichlet’s Theorem (see Theorem I of [7]).
As a direct consequence, we have the following generalized form of Lemma 2.7.
Corollary 2.9 Let
be m lattices of
and
Then
is a lattice of
.
Proof: Without loss of generality, we assume that
Let
, then
Since
, by Lemma 2.7, we have
is a lattice of
and the corollary follows.
口
3. Ideal Matrices
Let
and
be the polynomials rings over
and
with variable x respectively. Suppose that
(3.1)
is a polynomial with integer coefficients of which has no multiple roots in complex numbers field
. Let
be the n different roots of
in
, the Vandermonde matrix
is defined by
(3.2)
According to the given polynomial
, we define a rotation matrix
by
(3.3)
where
is the
unit matrix. Obviously, the characteristic polynomial of H is just
.
We use column notation for vectors in
, for any
, the ideal matrix generated by vector f is defined by
(3.4)
which is a block matrix in terms of each column
. Sometimes, f is called an input vector. It is easily seen that
is a more general form of the classical circulant matrix (see [8]) and r-circulant matrix (see [9] and [10]). In fact, if
, then
is the ordinary circulant matrix generated by f. If
, then
is the r-circulant matrix.
By (3.4), it follows immediately that
(3.5)
Moreover,
is a zero matrix if and only if
is a zero vector, thus one has
if and only if
. Let
be the set of all ideal matrices, namely
(3.6)
We may regard
as a mapping from
to
of which is a one to one correspondence.
In [11], we have shown that some basic properties for ideal matrix, most of them may be summarized as the following theorem.
Theorem 3.1 Suppose that
is a fixed polynomial with no multiple roots in
, then for any two column vectors f and g in
, we have
1)
;
2)
and
;
3)
;
4)
;
5)
is an invertible matrix if and only if
in
.
where
is the Vandermonde matrix given by (2.2),
are all roots of
in
, and
is the diagonal matrix.
Proof: See Theorem 2 of [11].
口
Let
be unit vectors of
, that is
It is easy to verify that
(3.7)
This means that the unit matrix
and rotation matrices
are all the ideal matrices.
Let
and
be the principal ideals generated by
in
and
respectively, we denote the quotient rings R and
by
(3.8)
There is a one to one correspondence between
and
given by
We denote this correspondence by t, that is
(3.9)
If we restrict t in the quotient ring R, then which gives a one to one correspondence between R and
. First, we show that t is also a ring isomorphism.
Definition 3.2 For any two column vectors f and g in
, we define the
-convolutional product
by
.
By Theorem 3.1, it is easy to see that
(3.10)
Lemma 3.3 For any two polynomials
and
in
, we have
Proof: Let
, then
It follows that
(3.11)
Hence, for any
, we have
(3.12)
Let
, by (i) of Theorem 3.1, we have
The lemma follows.
口
Theorem 3.4 Under
-convolutional product,
is a commutative ring with identity element
and
is its subring. Moreover, we have the following ring isomorphisms
where
is the set of all ideal matrices given by (3.6), and
is the set of all integer ideal matrices.
Proof: Let
and
, then
and
This means that t is a ring isomorphism. Since
and
, then
is a commutative ring with
as the identity elements. Noting
is an integer matrix if and only if
is an integer vector, the isomorphism of subrings follows immediately.
口
According to property (v) of Theorem 3.1,
is an invertible matrix whenever
in
, we show that the inverse of an ideal matrix is again an ideal matrix.
Lemma 3.5 Let
and
in
, then
where
is the unique polynomial such that
(mod (
)).
Proof: By Lemma 3.3, we have
, it follows that
Thus we have
. It is worth to note that if
is an invertible integer matrix, then
is not an integer matrix in general.
口
Sometimes, the following lemma may be useful, especially, when we consider an integer matrix.
Lemma 3.6 Let
and
in
, then we have
in
.
Proof: Let
be the rational number field. Since
in
, then
in
. We know that
is a principal ideal domain, thus there are two polynomials
and
in
such that
This means that
in
.
口
4. Cyclic Lattices and Ideal Lattices
As we know that cyclic code play a central role in algebraic coding theorem (see Chapter 6 of [12]). In [11], we extended ordinary cyclic code to more general forms, namely
-cyclic codes. To obtain an analogous concept of
-cyclic code in
, we note that every rotation matrix H defines a linear transformation of
by
.
Definition 4.1 A linear subspace
is called a
-cyclic subspace if
. A lattice
is called a
-cyclic lattice if
.
In other words, a
-cyclic subspace C is a linear subspace of
, of which is closed under linear transformation H. A
-cyclic lattice L is a lattice of
of which is closed under H. If
, then H is the classical circulant matrix and the corresponding cyclic lattice was first appeared in Micciancio [1], but he do not discuss the further property for these lattices. To obtain the explicit algebraic construction of
-cyclic lattice, we first show that there is a one to one correspondence between
-cyclic subspaces of
and the ideals of
.
Lemma 4.2 Let t be the correspondence between
and
given by (3.9), then a subset
is a
-cyclic subspace of
, if and only if
is an ideal.
Proof: We extend the correspondence t to subsets of
and
by
(4.1)
Let
be an ideal, it is clear that
is a linear subspace of
. To prove C is a
-cyclic subspace, we note that if
, then by (3.11)
Therefore, if
is an ideal of
, then
is a
-cyclic subspace of
. Conversely, if
is a
-cyclic subspace, then for any
, we have
whenever
, it implies
which means that
is an ideal of
. We complete the proof.
口
By above lemma, to find a
-cyclic subspace in
, it is enough to find an ideal of
. There are two trivial ideals
and
, the corresponding
-cyclic subspace are
and
. To find non-trivial
-cyclic subspaces, we make use of the homomorphism theorems, which is a standard technique in algebra. Let
be the natural homomorphism from
to
,
. We write
by
. Let N be an ideal of
satisfying
(4.2)
Since
is a principal ideal domain, then
is a principal ideal generated by a monic polynomial
. It is easy to see that
It follows that all ideals N satisfying (4.2) are given by
We write by
mod
, the image of
under
, i.e.
It is easy to check
(4.3)
more precisely, which is a representative elements set of
mod
. By homomorphism theorem in ring theory, all ideals of
given by
(4.4)
Let d be the number of monic divisors of
in
, we have the following corollary.
Corollary 4.3 The number of
-cyclic subspace of
is d.
Next, we discuss
-cyclic lattice, which is the geometric analogy of cyclic code. The
-cyclic subspace of
maybe regarded as the algebraic analogy of cyclic code. Let the quotient rings R and
given by (3.8). A R-module is an Abel group
such that there is an operator
for all
and
, satisfying
and
. It is easy to see that
is a R-module, if
and
is a R-module, then
is called a R-submodule of
. All R-modules we discuss here are R-submodule of
. On the other hand, if
, then I is an ideal of R, if and only if I is a R-module. Let
, the cyclic R-module generated by
be defined by
(4.5)
If there are finitely many polynomials
in
such that
, then
is called a finitely generated R-module, which is a R-submodule of
.
Now, if
is a
-cyclic lattice,
,
is the ideal matrix generated by vector g, and
is the lattice generated by
. It is easy to show that any
is a
-cyclic lattice and
(4.6)
which implies that
is the smallest
-cyclic lattice of which contains vector g. Therefore, we call
is a minimal
-cyclic lattice in
.
Lemma 4.4 There is a one to one correspondence between the minimal
-cyclic lattice in
and the cyclic R-submodule in
, namely,
and
Proof: Let
, by Lemma 3.3, we have
and
. Conversely, if
, and
for some integer vector b, by Lemma 3.3 again, we have
, and
. This implies that
, and
The lemma follows immediately.
口
Suppose
is arbitrary
-cyclic lattice, where
is the generated matrix of L. L may be expressed as the sum of finitely many minimal
-cyclic lattices, in fact, we have
(4.7)
To state and prove our main results, first, we give a definition of prime spot in
.
Definition 4.5 Let
, and
. If
in
, we call g is a prime spot of
.
By (v) of Theorem 3.1,
is a prime spot if and only if
is an invertible matrix, thus the minimal
-cyclic lattice
generated by a prime spot is a full-rank lattice.
Lemma 4.6 Let g and f be two prime spots of
, then
is a full-rank
-cyclic lattice.
Proof: According to Lemma 2.7, it is sufficient to show that
(4.8)
In fact, we should prove in general
(4.9)
Since
is an invertible matrix, then
, and (4.8) follows immediately.
To prove (4.9), we note that
It follows that
It is easy to see that
Therefore, we have
This is the proof of Lemma 4.6.
口
It is worth to note that (4.9) is true for more general case, do not need the condition of prime spot.
Corollary 4.7 Let
be arbitrary m vectors in
, then we have
(4.10)
Proof: If
are integer vectors, then (4.10) is trivial. For the general case, we write
where
is the
-convolutional product, then
Since
It follows that
We have this corollary.
口
By Lemma 4.6, we also have the following assertion.
Corollary 4.8 Let
be m prime spots of
, then
is a full-rank
-cyclic lattice.
Proof: It follows immediately from Corollary 2.9.
口
Our main result in this paper is to establish the following one to one correspondence between
-cyclic lattices in
and finitely generated R-modules in
.
Theorem 4.9 Let
be a finitely generated R-module in
, then
is a
-cyclic lattice in
. Conversely, if
is a
-cyclic lattice in
, then
is a finitely generated R-module in
, that is a one to one correspondence.
Proof: If
is a finitely generated R-module, by Lemma 4.4, we have
The main difficult is to show that
is a lattice of
, we require a surgery to embed
into a full-rank lattice. To do this, let
,
, and
,
. Since
has no multiple roots by assumption, then
in
. In other words, each
is a prime spot. It is easy to verify
, thus we have
By Corollary 4.8 and Corollary 2.4, we have
is
-cyclic lattice. Conversely, if
is a
-cyclic lattice of
, and
, by (4.7), we have
which is a finitely generated R-module in
. We complete the proof of Theorem 4.9.
口
As we introduced in abstract, since R is a Noether ring, then
is an ideal if and only if I is a finitely generated R-module. On the other hand, if
is an ideal, then
is a discrete subgroup of
, thus
is a lattice.
Definition 4.10 Let
be an ideal,
is called the
-ideal lattice.
Ideal lattice was first appeared in [2] (see Definition 3.1 of [2]). As a direct consequences of Theorem 4.9, we have the following corollary.
Corollary 4.11 Let
be a subset, then L is a
-cyclic lattice if and only if
where
and
. Furthermore, L is a
-ideal lattice if and only if every
,
.
Corollary 4.12 Suppose that
is an irreducible polynomial in
, then any non-zero ideal I of R defines a full-rank
-ideal lattice
.
Proof: Let
be a non-zero ideal, then we have
, where
and
. It follows that
Since each
is a prime spot, we have
by Corollary 4.8, and the corollary follows at once.
口
According to Definition 3.1 of [2], we have proved that any an ideal of R corresponding to a
-ideal lattice, which just is a
-cyclic integer lattice under the more general rotation matrix
. Cyclic lattice and ideal lattice were introduced in [1] and [2] respectively to improve the space complexity of lattice based cryptosystems. Ideal lattices allow to represent a lattice using only two polynomials. Using such lattices, class lattice based cryptosystems can diminish their space complexity from
to
. Ideal lattices also allow to accelerate computations using the polynomial structure. The original structure of Micciancio’s matrices uses the ordinary circulant matrices and allows for an interpretation in terms of arithmetic in polynomial ring
. Lyubashevsky and Micciancio [2] latter suggested to change the ring to
with an irreducible
over
. Our results here suggest to change the ring to
with any a polynomial
. There are many works are subsequent to Micciancio [1] and Lyubashevsky and Micciancio [2], such as [13] - [19].
Example 4.13 It is interesting to find some examples of
-cyclic lattices in an algebraic number field K. Let
be rational number field, without loss of generality, an algebraic number field K of degree n is just
, where
is a root of
. If all
(
), then K is called a totally real algebraic number field. Let
be the ring of algebraic integers of K, and
be an ideal,
. Since there is an integral basis
such that
We may regard every ideal of
as a lattice in
, our assertion is that every nonzero ideal of
is corresponding to a full-rank
-cyclic lattice of
. To see this example, let
It is known that
, thus every
corresponds to a vector
by
If
is an ideal of
and
, let
, which is full-rank matrix. We have
is a full-rank lattice. It remains to show that
is a
-cyclic lattice, we only prove that if
. Suppose that
, then
. It is easy to verify that
(see (3.7)) and
This means that
is a
-cyclic lattice of
, which is a full-rank lattice.
5. Smoothing Parameter
As application of the algebraic structure of
-cyclic lattice, we show that an explicit upper bound of the smoothing parameter for the
-cyclic lattices. Firstly, we introduce some basic notations.
A Gauss function
in
is given by
(5.1)
where
,
and
is a positive real number.
is called the Gauss function around original point c with parameter s. It is easy to see that
Thus we may define a probability density function
by
(5.2)
Suppose
is a lattice, let
(5.3)
The discrete Gauss distribution over L is a probability distribution
over L given by
(5.4)
If
is the zero vector of
, we write
,
,
and
. Suppose that L is a full-rank lattice and
is its dual lattice, we define the smoothing parameter
of L to be the smallest s such that
, more precisely,
(5.5)
where
is a positive number. Notice that
is a continuous and strictly decreasing function of s, thus the smoothing parameter
is a continuous and strictly decreasing function of
.
Let
be a full-rank lattice with a basis
, the fundamental region
is given by
(5.6)
Suppose that X and Y are two discrete random variables on
, the statistical distance between X and Y over L is defined by
(5.7)
If X and Y are continuous random variables with probability density function
and
respectively, then
is defined by
(5.8)
The smoothing parameter was introduced by Micciancio and Regev in [20], which plays an important role in the statistical information of lattices. An important property of smoothing parameter is for any lattice
and any
, the statistical distance between
mod L and the uniform distribution over the fundamental region
is at most
. More precisely, for any
and any
, the statistical distance is at most
, namely
(5.9)
Lemma 5.1 Let
be a full-rank lattice, we have
(5.10)
where
is the dual lattice of L, and
is the minimum distance of
.
Proof: See Lemma 3.2 of [20] [21].
Lemma 5.2 Suppose that
and
are two full-rank lattices in
, and
, then for any
, we have
(5.11)
Proof: Let
, we are to show that
. Since
It is easy to check that
, it follows that
which implies
and
, thus we have Lemma 5.2.
According to (3.4), the ideal matrix
with input vector
is just the ordinary circulant matrix when
. Next lemma shows that the transpose of a circulant matrix is still a circulant matrix. For any
, we denote
, which is called the conjugation of g.
Lemma 5.3 Let
, then for any
, we have
(5.12)
Proof: Since
, then
(see(3.3)) is an orthogonal matrix, and we have
. We write
. The following identity is easy to verify
It follows that
and we have the lemma.
Lemma 5.4 Suppose that
and the circulant matrix
is invertible. Let
, then all characteristic values of A are given by
where
are the n-th roots of unity.
Proof: By Lemma 5.3 and (ii) of Theorem 3.1, we have
where
. Let
is the corresponding polynomial of
. By (iii) of Theorem 3.1 all characteristic values of A are given by
(5.13)
Let
. It is easy to see that
where
for all
, then the lemma follows at once.
By definition 4.5, if
is a prime spot, then there is a unique polynomial
such that
(mod
). We define a new vector
and its corresponding polynomial
by
(5.14)
If
is an integer vector, then
is also an integer vector, and
is a polynomial with integer coefficients. Our main result on smoothing parameter is the following theorem.
Theorem 5.5 Let
,
be a full-rank
-cyclic lattice, then for any prime spots
, we have
(5.15)
where
, and
is given by (5.14).
Proof: Let
be a prime spot, by Lemma 5.2, we have
(5.16)
To estimate the smoothing parameter of
, the dual lattice of
is given by
where
and
(mod
), and
is given by (5.14). Let
, by Lemma 5.4, all characteristic values of A are
By Lemma 2.2, the minimum distance
is bounded by
(5.17)
Now, Theorem 5.5 follows from Lemma 5.1 immediately.
Let
be a full-rank lattice and
. We denote by
the Gram-Schmidt orthogonal vectors
of the ordered basis
. It is a well-known conclusion that
which yields by Lemma 5.1 the following upper bound
(5.18)
where
is the orthogonal basis of dual lattice
of L.
For a
-cyclic lattice L, we observe that the upper bound (5.17) is always better than (5.18) by numerical testing, we give two examples here.
Example 5.6 Let
and
, the rotation matrix H is
We select a
-cyclic lattice
, where
Since
, thus L is a
-cyclic lattice. It is easy to check
On the other hand, we randomly find a prime spot
and
. Since
(mod
), we have
, it follows that
, and
Example 5.7 Let
and
, the rotation matrix H is
We select a
-cyclic lattice
, where
Since
, thus L is a
-cyclic lattice. It is easy to check
On the other hand, we randomly find a prime spot
and
. Since
we have
It follows that
,
, and
6. Conclusion
In this study, we show that ideal lattices are actually a special subclass of cyclic lattices, and prove that there is a one-to-one correspondence between cyclic lattices in
and finitely generated R-modules. Here, we use a more general rotation matrix so that our definition and results on cyclic lattices and ideal lattices are more general forms. Finally, we give a more explicit and countable upper bound for the smoothing parameter of cyclic lattices.