Ideal Lattices

Abstract

In Chapter 2, interesting lattices together with their parameters and applications were presented. In Chapter 3, one method to build such lattices was discussed, which consists of obtaining lattices from linear codes. This chapter presents two other methods to construct lattices, both called ideal lattices, because they both rely on the structure of ideals in rings. We recall that given a commutative ring R, an ideal of R is an additive subgroup of R which is also closed under multiplication by elements of R. The same terminology is used for two different view points on lattices because of the communities that studied them. We will explain the former technique using quadratic fields, and refer to [79] for general number field constructions. We note that such a lattice construction from number fields can in turn be combined with Construction A to obtain further lattices, e.g., [59] and references therein. For the latter case, “ideal lattices” refer to a family of lattices recently used in cryptography.

In Chap. 2, interesting lattices together with their parameters and applications were presented. In Chap. 3, one method to build such lattices was discussed, which consists of obtaining lattices from linear codes. This chapter presents two other methods to construct lattices, both called ideal lattices, because they both rely on the structure of ideals in rings. We recall that given a commutative ring R, an ideal of R is an additive subgroup of R which is also closed under multiplication by elements of R. The same terminology is used for two different viewpoints on lattices because of the communities that studied them. We will explain the first method using quadratic fields and refer to [79] for general number field constructions. We note that such a lattice construction from number fields can in turn be combined with Construction A to obtain further lattices, e.g., [59] and references therein. In the second method, “ideal lattices” refer to a family of lattices recently used in cryptography.

4.1 Ideal Lattices from Quadratic Fields

For d > 1 a squarefree integer, consider the field

$$\displaystyle \begin{aligned} \mathbb{Q}(\sqrt{d})=\{a+b\sqrt{d},~a,b\in\mathbb{Q}\} \end{aligned}$$

which is called quadratic because it has dimension 2 as a vector space over $\mathbb {Q}$ (elements in $\mathbb {Q}(\sqrt {d})$ can be written as vectors (a, b), fixing, for example, $\{1,\sqrt {d}\}$ as a basis).

Since d > 1, $\mathbb {Q}(\sqrt {d})\subset \mathbb {R}$. It is clear that we have this field inclusion, but what is maybe less clear is that there are actually two meaningful ways of embedding $\mathbb {Q}(\sqrt {d})$ into $\mathbb {R}$:

$$\displaystyle \begin{aligned} \begin{array}{rcl} \sigma_{1}: & a+b\sqrt{d}\mapsto a+b\sqrt{d}\\ \sigma_{2}: & a+b\sqrt{d}\mapsto a-b\sqrt{d} \end{array} \end{aligned} $$

The first one, the identity map, is probably the one that everyone thinks of. However, the second one is just as “meaningful,” in the sense that σ ₂, just as σ ₁, includes $\mathbb {Q}(\sqrt {d})$ into $\mathbb {R}$ while preserving (1) its ring structure (σ ₂(x + y) = σ ₂(x) + σ ₂(y) and σ ₂(xy) = σ ₂(x)σ ₂(y) for all $x,y\in \mathbb {Q}(\sqrt {d})$) (2) its vector space structure (σ ₂(a) = a for any $a\in \mathbb {Q}$). In fact, σ ₁, σ ₂ are the only two maps that satisfy the above (2) conditions. Suppose τ satisfies both of them, then:

$$\displaystyle \begin{aligned} \tau\left((\sqrt{d})^{2}\right)=\left\{ \begin{array}{l} \tau(d)=d\\ \tau(\sqrt{d})^{2} \end{array}\right. \end{aligned}$$

and thus $\tau (\sqrt {d})$ must satisfy

$$\displaystyle \begin{aligned} \tau(\sqrt{d})^{2}-d=0 \end{aligned}$$

showing that $\tau (\sqrt {d})=\pm \sqrt {d}$. As a consequence σ = (σ ₁, σ ₂) gives an embedding of $\mathbb {Q}(\sqrt {d})$ into $\mathbb {R}^{2}$.

4.1.1 Lattice Constructions

Now our purpose is to obtain lattices, which are discrete structures. The above embedding suggests it may be possible to obtain 2-dimensional lattices, if we start from a discrete structure within $\mathbb {Q}(\sqrt {d})$. A natural candidate for this is

$$\displaystyle \begin{aligned}\mathbb{Z}[\sqrt{d}] = \left\{a+b\sqrt{d}, a,b, \in \mathbb{Z} \right\}.\end{aligned}$$

Now $\mathbb {Z}[\sqrt {d}]$ is not a vector space, but it has a basis, given, for example, by $\{1,\sqrt {d}\}$. Embedding this basis using σ gives,

$$\displaystyle \begin{aligned} B=\begin{bmatrix}1 & \sigma_{1}(\sqrt{d})\\ 1 & \sigma_{2}(\sqrt{d}) \end{bmatrix}=\begin{bmatrix}1 & \sqrt{d}\\ 1 & -\sqrt{d} \end{bmatrix} \end{aligned}$$

and integer linear combinations of rows of B do define a lattice (since the two rows are linearly independent). Note that

$$\displaystyle \begin{aligned} Bu=\begin{bmatrix}1 & \sqrt{d}\\ 1 & -\sqrt{d} \end{bmatrix}\begin{bmatrix}u_{1}\\ u_{2} \end{bmatrix}=\begin{bmatrix}u_{1}+u_{2}\sqrt{d}\\ u_{1}-u_{2}\sqrt{d} \end{bmatrix}=\begin{bmatrix}\sigma_{1}(x)\\ \sigma_{2}(x) \end{bmatrix},~x=u_{1}+u_{2}\sqrt{d} \end{aligned} $$

(4.1)

which gives a nice geometric interpretation of how an element $x\in \mathbb {Z}[\sqrt {d}]$ is embedded in the lattice $\sigma (\mathbb {Z}[\sqrt {d}])$.

The lattice construction proposed above only relies on having a “discrete structure”¹ in $\mathbb {Q}(\sqrt {d})$ with a $\mathbb {Z}$-basis. If d ≡ 1( mod 4), it is possible for example to take $\mathbb {Z}[\tfrac {1+\sqrt {d}}{2}]$. Let us give some examples, before discussing the meaning of the condition d ≡ 1( mod 4).

Example 4.1

The ring $\mathbb {Z}[\tfrac {1+\sqrt {5}}{2}]=\{a+b\tfrac {1+\sqrt {5}}{2},~a,b\in \mathbb {Z}\}$ is a subset of the field $\mathbb {Q}(\sqrt {5})=\{a+b\sqrt {5},~a,b\in \mathbb {Q}\}$. The two ways of embedding $\mathbb {Q}(\sqrt {5})$ into $\mathbb {R}$ are:

$$\displaystyle \begin{aligned} \sigma_{1}:\sqrt{5}\mapsto\sqrt{5},~\sigma_{2}:\sqrt{5}\mapsto-\sqrt{5}. \end{aligned}$$

We then embed $\mathbb {Z}[\tfrac {1+\sqrt {5}}{2}]$ into $\mathbb {R}^{2}$ using σ = (σ ₁, σ ₂), to get a generator matrix

$$\displaystyle \begin{aligned} B=\begin{bmatrix}1 & \sigma_{1}(\tfrac{1+\sqrt{5}}{2})\\ 1 & \sigma_{2}(\tfrac{1+\sqrt{5}}{2}) \end{bmatrix}. \end{aligned}$$

This lattice is shown in Fig. 4.2. Its corresponding Gram matrix is

$$\displaystyle \begin{aligned} G=B^{T}B=\begin{bmatrix}1 & 1\\ \sigma_{1}(\tfrac{1+\sqrt{5}}{2}) & \sigma_{2}(\tfrac{1+\sqrt{5}}{2}) \end{bmatrix}\begin{bmatrix}1 & \sigma_{1}(\tfrac{1+\sqrt{5}}{2})\\ 1 & \sigma_{2}(\tfrac{1+\sqrt{5}}{2}) \end{bmatrix}=\begin{bmatrix}2 & 1\\ 1 & 3 \end{bmatrix}. \end{aligned}$$

To compare, a Gram matrix for the lattice $\sigma (\mathbb {Z}[\sqrt {5}])$, shown in Fig. 4.1, is

$$\displaystyle \begin{aligned} \begin{bmatrix}1 & 1\\ \sigma_{1}(\sqrt{5}) & \sigma_{2}(\sqrt{5}) \end{bmatrix}\begin{bmatrix}1 & \sigma_{1}(\sqrt{5})\\ 1 & \sigma_{2}(\sqrt{5}) \end{bmatrix}=\begin{bmatrix}2 & 0\\ 0 & 10 \end{bmatrix}. \end{aligned}$$

Fig. 4.1

Lattices from the quadratic fields $\mathbb {Z}[ \sqrt {5}]$ and $\mathbb {Z}[ \sqrt {2}]$, respectively. (a) The lattice obtained from $\{1, \sqrt {5}\}$. (b) The lattice obtained from $\{1, \sqrt {2}\}$

Fig. 4.2

Lattices from the quadratic field $\mathbb {Z}[\tfrac {1+ \sqrt {5}}{2}]$ with and without twisting. (a) The lattice obtained from $\{1,\tfrac {1+ \sqrt {5}}{2}\}$. (b) The lattice obtained from $\{1,\tfrac {1+ \sqrt {5}}{2}\}$ using a twisting element $\alpha =3-\tfrac {1+ \sqrt {5}}{2}$

Let us now consider d≢1( mod 4).

Example 4.2

The two ways of embedding $\mathbb {Q}(\sqrt {2})$ into $\mathbb {R}$ are:

$$\displaystyle \begin{aligned} \sigma_{1}:\sqrt{2}\mapsto\sqrt{2},~\sigma_{2}:\sqrt{2}\mapsto-\sqrt{2}. \end{aligned}$$

We then embed $\mathbb {Z}[\tfrac {1+\sqrt {2}}{2}]$ into $\mathbb {R}^{2}$ using σ = (σ ₁, σ ₂), to get as Gram matrix

$$\displaystyle \begin{aligned} \begin{bmatrix}1 & 1\\ \sigma_{1}(\tfrac{1+\sqrt{2}}{2}) & \sigma_{2}(\tfrac{1+\sqrt{2}}{2}) \end{bmatrix}\begin{bmatrix}1 & \sigma_{1}(\tfrac{1+\sqrt{2}}{2})\\ 1 & \sigma_{2}(\tfrac{1+\sqrt{2}}{2}) \end{bmatrix}=\begin{bmatrix}2 & 1\\ 1 & 3/2 \end{bmatrix}, \end{aligned}$$

while a Gram matrix for the lattice $\sigma (\mathbb {Z}[\sqrt {2}])$ is

$$\displaystyle \begin{aligned} \begin{bmatrix}1 & 1\\ \sigma_{1}(\sqrt{2}) & \sigma_{2}(\sqrt{2}) \end{bmatrix}\begin{bmatrix}1 & \sigma_{1}(\sqrt{2})\\ 1 & \sigma_{2}(\sqrt{2}) \end{bmatrix}=\begin{bmatrix}2 & 0\\ 0 & 4 \end{bmatrix}.\end{aligned} $$

This lattice is shown in Fig. 4.1.

The difference between the first example and the second is that in the first example, both Gram matrices have integer coefficients (the lattice is integral; see Definition 2.13), while in the second example, this is not the case.

The reason behind this is that the ring $\mathbb {Z}[\sqrt {d}]$ turns out to contain elements from $\mathbb {Q}(\sqrt {d})$ which all have the property of being the root of some monic polynomial whose coefficients live in $\mathbb {Z}$ (we recall that a polynomial p(X) is monic if the coefficient of its leading term is equal to one). Now when d≢1( mod 4), it turns out (see Exercise 4.1) that $\mathbb {Z}[\sqrt {d}]$ is exactly the set of elements from $\mathbb {Q}(\sqrt {d})$ which are roots of monic polynomials with coefficients in $\mathbb {Z}$, while when d ≡ 1( mod 4), this set is $\mathbb {Z}[\tfrac {1+\sqrt {d}}{2}]$ and $\mathbb {Z}[\sqrt {d}]\subset \mathbb {Z}[\tfrac {1+\sqrt {d}}{2}]$.

Now for a $\mathbb {Z}$-basis {θ ₁, θ ₂} (of, respectively, $\mathbb {Z}[\sqrt {d}]$ or $\mathbb {Z}[\tfrac {1+\sqrt {d}}{2}]$ depending on the congruence of d( mod 4) or of (an ideal of) an order of these two rings), a Gram matrix is of the form

$$\displaystyle \begin{aligned} \begin{array}{rcl} & & \begin{bmatrix}\sigma_{1}(\theta_{1}) & \sigma_{2}(\theta_{1})\\ \sigma_{1}(\theta_{2}) & \sigma_{2}(\theta_{2}) \end{bmatrix}\begin{bmatrix}\sigma_{1}(\theta_{1}) & \sigma_{1}(\theta_{2})\\ \sigma_{2}(\theta_{1}) & \sigma_{2}(\theta_{2}) \end{bmatrix}\\ & = & \begin{bmatrix}\sigma_{1}(\theta_{1})^{2}+\sigma_{2}(\theta_{1})^{2} & \sigma_{1}(\theta_{1})\sigma_{1}(\theta_{2})+\sigma_{2}(\theta_{1})\sigma_{2}(\theta_{2})\\ \sigma_{1}(\theta_{1})\sigma_{1}(\theta_{2})+\sigma_{2}(\theta_{1})\sigma_{2}(\theta_{2}) & \sigma_{1}(\theta_{2})^{2}+\sigma_{2}(\theta_{2})^{2} \end{bmatrix}\\ & = & \begin{bmatrix}\sigma_{1}(\theta_{1}^{2})+\sigma_{2}(\theta_{1}^{2}) & \sigma_{1}(\theta_{1}\theta_{2})+\sigma_{2}(\theta_{1}\theta_{2})\\ \sigma_{1}(\theta_{1}\theta_{2})+\sigma_{2}(\theta_{1}\theta_{2}) & \sigma_{1}(\theta_{2}^{2})+\sigma_{2}(\theta_{2}^{2}) \end{bmatrix}. \end{array} \end{aligned} $$

If we observe the coefficients of this matrix, they all are of the form

$$\displaystyle \begin{aligned} \sigma_{1}(a+b\sqrt{d})+\sigma_{2}(a+b\sqrt{d})=2a \end{aligned}$$

for some $a,b\in \mathbb {Q}$, which explains why the Gram matrix coefficients are in $\mathbb {Q}$.

Now $\sigma _{1}(a+b\sqrt {d}),\sigma _{2}(a+b\sqrt {d})$ and thus $\sigma _{1}(a+b\sqrt {d})+\sigma _{2}(a+b\sqrt {d})$ belong to the intersection of $\mathbb {Z}[\sqrt {d}]$ (or $\mathbb {Z}[\tfrac {1+\sqrt {d}}{2}]$ depending on d( mod 4)) and $\mathbb {Q}$. We claim that this intersection is $\mathbb {Z}$, and therefore the Gram matrix has integer coefficients.

To prove that the intersection is $\mathbb {Z}$, recall that we are looking at elements in $\mathbb {Q}$, thus of the form u/v, v ≠ 0, $u,v\in \mathbb {Z}$, and we can assume $\gcd (u,v)=1$, which are roots of some monic polynomial p(X) with coefficients in $\mathbb {Z}$. This means

$$\displaystyle \begin{aligned} p(u/v)=p_{0}+p_{1}(u/v)+p_{2}(u/v)^{2}+\cdots+p_{n-1}(u/v)^{n-1}+(u/v)^{n}=0 \end{aligned}$$

which implies

$$\displaystyle \begin{aligned} v^{n}p_{0}+p_{1}uv^{n-1}+p_{2}u^{2}v^{n-2}+\cdots+p_{n-1}u^{n-1}v+u^{n}=0. \end{aligned}$$

Now it must be that

$$\displaystyle \begin{aligned} v^{n}p_{0}+p_{1}uv^{n-1}+p_{2}u^{2}v^{n-2}+\cdots+p_{n-1}u^{n-1}v=-u^{n} \end{aligned}$$

but the left-hand side is divisible by v, while the right-hand side is not, a contradiction, apart for v = 1.

Canonical $\mathbb {Z}$-bases are $\{1,\sqrt {d}\}$ and $\{1,\tfrac {1+\sqrt {d}}{2}\}$ depending on d. A variety of interesting lattices can be obtained by introducing a “twisting” element α such that σ ₁(α) > 0 and σ ₂(α) > 0 as follows. Let θ denote $\sqrt {d}$ or $\tfrac {1+\sqrt {d}}{2}$ depending on d( mod 4). A generator matrix of a lattice using a twisting element α is given by

$$\displaystyle \begin{aligned} B=\begin{bmatrix}\sqrt{\sigma_{1}(\alpha)} & \sqrt{\sigma_{1}(\alpha)}\sigma_{1}(\theta)\\ \sqrt{\sigma_{2}(\alpha)} & \sqrt{\sigma_{2}(\alpha)}\sigma_{2}(\theta) \end{bmatrix}=\begin{bmatrix}\sqrt{\sigma_{1}(\alpha)} & 0\\ 0 & \sqrt{\sigma_{2}(\alpha)} \end{bmatrix}\begin{bmatrix}\sigma_{1}(1) & \sigma_{1}(\theta)\\ \sigma_{2}(1) & \sigma_{2}(\theta) \end{bmatrix} \end{aligned}$$

and a Gram matrix by

$$\displaystyle \begin{aligned} B^{T}B=\begin{bmatrix}\sigma_{1}(\alpha)+\sigma_{2}(\alpha) & \sigma_{1}(\alpha\theta)+\sigma_{2}(\alpha\theta)\\ \sigma_{1}(\alpha\theta)+\sigma_{2}(\alpha\theta) & \sigma_{1}(\alpha\theta^{2})+\sigma_{2}(\alpha\theta^{2}) \end{bmatrix}. \end{aligned}$$

Note that the conditions σ ₁(α) > 0 and σ ₂(α) > 0 ensure that the lattice remains real (and no complex value is introduced when taking the square root). Furthermore, by taking α in $\mathbb {Z}[\theta ]$, the lattice will remain an integral lattice, even though $\sqrt {\alpha }$ typically has no reason to be in $\mathbb {Z}[\theta ]$. By Definition 2.4, the volume of the lattice² $\sigma (\sqrt {\alpha }\mathbb {Z}[\theta ])$ is given by the square root of

$$\displaystyle \begin{aligned} \left(\det\begin{bmatrix}\sigma_{1}(1) & \sigma_{2}(1)\\ \sigma_{1}(\theta) & \sigma_{2}(\theta) \end{bmatrix}\right)^{2}\left(\det\begin{bmatrix}\sqrt{\sigma_{1}(\alpha)} & 0\\ 0 & \sqrt{\sigma_{2}(\alpha)} \end{bmatrix}\right)^{2}=\sigma_{1}(\alpha)\sigma_{2}(\alpha)(\sigma_{2}(\theta)-\sigma_{1}(\theta))^{2}, \end{aligned}$$

thus

$$\displaystyle \begin{aligned} V(\sigma(\sqrt{\alpha}\mathbb{Z}[\theta]))=\sqrt{|\sigma_{1}(\alpha)\sigma_{2}(\alpha)|}|\sigma_{2}(\theta)-\sigma_{1}(\theta)|. \end{aligned}$$

We continue Example 4.1.

Example 4.3

Take

$$\displaystyle \begin{aligned} \alpha = 3-\tfrac{1+\sqrt{5}}{2},~\alpha\theta = -1+2\tfrac{1+\sqrt{5}}{2},~ \alpha\theta^{2} = 2+\tfrac{1+\sqrt{5}}{2}. \end{aligned}$$

Then a generator matrix of $\sigma (\sqrt {\alpha }\mathbb {Z}[\tfrac {1+\sqrt {5}}{2}])$, illustrated in Fig. 4.2 is

$$\displaystyle \begin{aligned} B=\begin{bmatrix}\sqrt{\alpha} & \sqrt{\alpha}\tfrac{1+\sqrt{5}}{2}\\ \sqrt{\sigma_{2}(\alpha)} & \sqrt{\sigma_{2}(\alpha)}\tfrac{1-\sqrt{5}}{2} \end{bmatrix} \end{aligned}$$

with corresponding Gram matrix

$$\displaystyle \begin{aligned} \begin{array}{rcl} G & {=} & \begin{bmatrix}\sigma_{1}(3{-}\tfrac{1{+}\sqrt{5}}{2}){+}\sigma_{2}(3{-}\tfrac{1{+}\sqrt{5}}{2}) & \sigma_{1}({-}1{+}2\tfrac{1{+}\sqrt{5}}{2}){+}\sigma_{2}({-}1+2\tfrac{1+\sqrt{5}}{2})\\ \sigma_{1}(-1+2\tfrac{1+\sqrt{5}}{2})+\sigma_{2}(-1+2\tfrac{1+\sqrt{5}}{2}) & \sigma_{1}(2+\tfrac{1+\sqrt{5}}{2})+\sigma_{2}(2+\tfrac{1+\sqrt{5}}{2}) \end{bmatrix}\\ & = & \begin{bmatrix}5 & 0\\ 0 & 5 \end{bmatrix} \end{array} \end{aligned} $$

and volume

$$\displaystyle \begin{aligned} \begin{array}{rcl} V(\sigma(\sqrt{\alpha}\mathbb{Z}[\tfrac{1+\sqrt{5}}{2}])) & = & \sqrt{|\sigma_{1}(\alpha)\sigma_{2}(\alpha)|}|\sigma_{2}(\theta)-\sigma_{1}(\theta)|\\ & = & \sqrt{5}|\sqrt{5}|=5. \end{array} \end{aligned} $$

This lattice is equivalent to (a scaled version of) $\mathbb {Z}^2$ (see Exercise 4.3).

4.1.2 Some Sublattices

Consider two lattices $\sigma (\beta \mathbb {Z}[\sqrt {d}])$ and $\sigma (\alpha \mathbb {Z}[\sqrt {d}])$, or $\sigma (\beta \mathbb {Z}[\tfrac {1+\sqrt {d}}{2}])$ and $\sigma (\alpha \mathbb {Z}[\tfrac {1+\sqrt {d}}{2}])$, with β = ασ(α), α ≠ σ(α). Then $\sigma (\beta \mathbb {Z}[\sqrt {d}])$ is a sublattice of $\sigma (\alpha \mathbb {Z}[\sqrt {d}])$, or in the other case, $\sigma (\beta \mathbb {Z}[\tfrac {1+\sqrt {d}}{2}])$ is a sublattice $\sigma (\alpha \mathbb {Z}[\tfrac {1+\sqrt {d}}{2}])$. Indeed, consider, for the former case, the sets $I_1=\{\alpha a+ \alpha b \sqrt {d},~a,b\in \mathbb {Z}\}$, $I_2=\{\sigma (\alpha ) a+ \sigma (\alpha ) b \sqrt {d},~a,b\in \mathbb {Z}\}$, and $I=\{\beta a+ \beta b \sqrt {d},~a,b\in \mathbb {Z}\}$. Define the sets I, I ₁, I ₂ accordingly for the latter case, and the following argument also hold by replacing $\sqrt {d}$ by $\tfrac {1+\sqrt {d}}{2}$. Then I ₁ + I ₂ = 1, from which it follows that I ₁ I ₂ = I ₁ ∩ I ₂ (see Exercise 4.4), and I ₁ I ₂ = I, where I ₁ I ₂ is the set formed by finite sums of terms of the form i ₁ i ₂, i ₁ ∈ I ₁, i ₂ ∈ I ₂. Take the lattice point

$$\displaystyle \begin{aligned} \begin{bmatrix} \sigma_{1}(\beta x)\\ \sigma_{2}(\beta x) \end{bmatrix} \end{aligned}$$

in $\sigma (\beta \mathbb {Z}[\sqrt {d}])$. It is obtained by embedding βx ∈ I, with I = I ₁ I ₂ = I ₁ ∩ I ₂. Thus βx also belongs to I ₁, so its embedding will appear in the embedding of I ₁, which yields $\sigma (\alpha \mathbb {Z}[\sqrt {d}])$. This is illustrated in Fig. 4.3.

Fig. 4.3

The lattice $\sigma (5\mathbb {Z}[\tfrac {1+ \sqrt {5}}{2}])$ and a sublattice. (a) The lattice obtained from $\{5,5\tfrac {1+ \sqrt {5}}{2}\}$. (b) The sublattice obtained from $\{\alpha ,\alpha \tfrac {1+ \sqrt {5}}{2}\}$, $\alpha =3-\tfrac {1+ \sqrt {5}}{2}$

4.1.3 Coding Applications

Recall from (4.1) that points in lattices obtained from quadratic fields are of the form

$$\displaystyle \begin{aligned} \begin{bmatrix}\sigma_{1}(x)\\ \sigma_{2}(x) \end{bmatrix},\mbox{ or }\begin{bmatrix}\sqrt{\sigma_{1}(\alpha)}\sigma_{1}(x)\\ \sqrt{\sigma_{2}(\alpha)}\sigma_{2}(x) \end{bmatrix} \end{aligned}$$

for $x=u_{1}+u_{2}\sqrt {d}\in \mathbb {Q}(\sqrt {d})$, depending on the presence or not of a twisting element α. Such pairs of points satisfy the property that

$$\displaystyle \begin{aligned} \sigma_{1}(x)\neq0,~\sigma_{2}(x)\neq0 \end{aligned}$$

for all x ≠ 0, since $\sigma _{1}(x)=u_{1}+u_{2}\sqrt {d}=0$ if and only if x = 0, and similarly $\sigma _{2}(x)=u_{1}-u_{2}\sqrt {d}=0$ if and only if x = 0. Now take any two arbitrary distinct lattice points

$$\displaystyle \begin{aligned} \begin{bmatrix}\sigma_{1}(x)\\ \sigma_{2}(x) \end{bmatrix},~\begin{bmatrix}\sigma_{1}(y)\\ \sigma_{2}(y) \end{bmatrix},\mbox{ or }\begin{bmatrix}\sqrt{\sigma_{1}(\alpha)}\sigma_{1}(x)\\ \sqrt{\sigma_{2}(\alpha)}\sigma_{2}(x) \end{bmatrix},~\begin{bmatrix}\sqrt{\sigma_{1}(\alpha)}\sigma_{1}(y)\\ \sqrt{\sigma_{2}(\alpha)}\sigma_{2}(y) \end{bmatrix}, \end{aligned}$$

then their difference belongs to the lattice and

$$\displaystyle \begin{aligned} \begin{array}{rcl} \sqrt{\sigma_{1}(\alpha)}\sigma_{1}(x)-\sqrt{\sigma_{1}(\alpha)}\sigma_{1}(y) & = & \sqrt{\sigma_{1}(\alpha)}\sigma_{1}(x-y)\neq0,\\ ~\sqrt{\sigma_{2}(\alpha)}\sigma_{2}(x)-\sqrt{\sigma_{2}(\alpha)}\sigma_{2}(y) & = & \sqrt{\sigma_{2}(\alpha)}\sigma_{2}(x-y)\neq0. \end{array} \end{aligned} $$

Geometrically, this means that given any two distinct lattice points, they will always differ on both their components, as can be observed on the different earlier figures of this chapter.

This is meaningful when lattice points are used for transmission over fast-fading channels. We have already seen in Chap. 2 how lattice points are used for transmission over Gaussian channels. Over a fast-fading channel, communication is modeled by

$$\displaystyle \begin{aligned} \mathbf{y}=H\mathbf{x}+\mathbf{n},~H=\begin{bmatrix}h_{1} & 0\\ 0 & h_{2} \end{bmatrix} \end{aligned}$$

where n is a random vector whose components are independent Gaussian random variables with mean 0 and variance σ ², and h ₁, h ₂ are independently Rayleigh distributed. We notice that the model is very similar to (2.20), except for the matrix H which takes into account fading in a wireless environment. Assuming the receiver knows H (this is called a coherent channel), he is facing a channel similar to a Gaussian channel, only the lattice constellation transmitted is now twisted by the fading H. If x is a lattice point of the form B u, then it is as if the lattice used for transmission had in fact generator matrix HB, and

$$\displaystyle \begin{aligned} H\mathbf{x}=\begin{bmatrix}h_{1} & 0\\ 0 & h_{2} \end{bmatrix}\begin{bmatrix}\sigma_{1}(x)\\ \sigma_{2}(x) \end{bmatrix}=\begin{bmatrix}h_{1}\sigma_{1}(x)\\ h_{2}\sigma_{2}(x) \end{bmatrix}. \end{aligned}$$

A lattice constellation for a Gaussian channel will make sure that lattice points are separated enough to resist the channel noise. However, even if σ _j (x) and σ _j (y) are designed to be apart, h _j σ _j (x) and h _j σ _j (y) could be arbitrarily close, depending on h _j , j = 1, 2.

The relevant distance in this case is the so-called product distance , which is the minimum of the absolute value of the product of the coordinates of non-zero vectors in the lattice. We may check (see Exercise 4.5) that the product distance, despite its name, is actually not a distance, as per Definition 3.2. It was shown that constellations in lattices with greater minimum product distance are associated to smaller error probability when used in signal transmission over Rayleigh fading channels [15]. The intuition is that the product distance captures the number of components in which lattice points (and therefore differences of lattice points) differ, guaranteeing that if the fading affects some components, the lattice points will still be distinguishable on their other non-zero components. Therefore lattices Λ in $\mathbb {R}^{n}$ with full diversity n are preferred, that is, lattices such that any of their vectors x = (x ₁, x ₂, …, x _n ), have x _i  ≠ 0, for any i. For a general lattice, it is computationally hard to determine its minimum product distance, which makes the interest of algebraic constructions of the type presented above; see, e.g., [9, 58]. Furthermore, since for a lattice in dimension n, its diversity is at most n, it can be increased by augmenting n, the dimension in which the lattice lives. One technique to do so is by considering tensor products, as explained next.

4.1.4 High-Dimensional Lattices

Consider two generator matrices

$$\displaystyle \begin{aligned} B_{1}=\begin{bmatrix}\sigma_{1}(\theta_{1}) & \sigma_{1}(\theta_{2})\\ \sigma_{2}(\theta_{1}) & \sigma_{2}(\theta_{2}) \end{bmatrix},~B_{2}=\begin{bmatrix}\tau_{1}(\nu_{1}) & \tau_{1}(\nu_{2})\\ \tau_{2}(\nu_{1}) & \tau_{2}(\nu_{2}) \end{bmatrix} \end{aligned}$$

and their Kronecker (tensor) product

$$\displaystyle \begin{aligned} B_{1}\otimes B_{2}=\begin{bmatrix}\sigma_{1}(\theta_{1})B_{2} & \sigma_{1}(\theta_{2})B_{2}\\ \sigma_{2}(\theta_{1})B_{2} & \sigma_{2}(\theta_{2})B_{2}. \end{bmatrix} \end{aligned}$$

Surely this defines the generator matrix of a 4-dimensional lattice, since the columns of this matrix are linearly independent: the determinant of the generator matrix is the product of the determinants of B ₁ and B ₂. Now in terms of diversity, it is harder to say something in general, though there is one case where we can easily show that the property of diversity is inherited from B ₁ and B ₂. Suppose that τ _i (θ _j ) = θ _j and σ _i (ν _j ) = ν _j , and we place ourselves in a large enough field³ which contains θ _j , ν _j , and for which τ _i , σ _i are embeddings. Then

$$\displaystyle \begin{aligned} B_{1}\otimes B_{2}= \begin{bmatrix} \sigma_1\tau_1(\theta_1\nu_1) & \sigma_1\tau_1(\theta_1\nu_2) &\sigma_1\tau_1(\theta_2\nu_1)&\sigma_1\tau_1(\theta_2\nu_2) \\ \sigma_1\tau_2(\theta_1\nu_1) & \sigma_1\tau_2(\theta_1\nu_2) &\sigma_1\tau_2(\theta_2\nu_1)&\sigma_1\tau_2(\theta_2\nu_2) \\ \sigma_2\tau_1(\theta_1\nu_1) & \sigma_2\tau_1(\theta_1\nu_2) &\sigma_2\tau_1(\theta_2\nu_1)&\sigma_2\tau_1(\theta_2\nu_2) \\ \sigma_2\tau_2(\theta_1\nu_1) & \sigma_2\tau_2(\theta_1\nu_2) &\sigma_2\tau_2(\theta_2\nu_1)&\sigma_2\tau_2(\theta_2\nu_2) \end{bmatrix} \end{aligned}$$

which is now the generator matrix of a lattice of dimension 4 and diversity 4. This process can be iterated to obtain lattices in dimensions which are powers of 2 (see Exercise 4.6).

Example 4.4

Take

$$\displaystyle \begin{aligned} B_1 = \begin{bmatrix} 1 & \sigma_1(\tfrac{1+\sqrt{5}}{2}) \\ 1 & \sigma_2(\tfrac{1+\sqrt{5}}{2}) \end{bmatrix},~ B_2 = \begin{bmatrix} 1 & \tau_1(\sqrt{2}) \\ 1 & \tau_2(\sqrt{2}) \end{bmatrix}. \end{aligned}$$

We place ourselves in $\mathbb {Q}(\sqrt {2},\sqrt {5})=\{a_0+a_1\sqrt {5}+a_2\sqrt {2}+a_3\sqrt {5}\sqrt {2},~a_0,a_1,a_2,a_3\in \mathbb {Q}\}$, so that $\sigma (\sqrt {2})=\sqrt {2}$ and $\tau (\sqrt {5})=\sqrt {5}$. Then B ₁ ⊗ B ₂ is a 4-dimensional lattice with diversity 4.

4.2 Ideal Lattices for Cryptography

Consider a lattice Λ of dimension n living in $\mathbb {Z}^n$ instead of $\mathbb {R}^n$, meaning that all lattice points have integer coordinates. Now we ask for the following further cyclic property that for every x = (x ₁, …, x _n ) ∈ Λ, it must be that (x _n , x ₁, …, x _n−1) also belongs to Λ. Note that since the cyclic property is asked for every lattice point, it means that (x _n−1, x _n , x ₁, …, x _n−2) ∈ Λ and, iteratively, all shifts of x = (x ₁, …, x _n ) must be in Λ.

Example 4.5

The lattice $\mathbb {Z}^2$ is cyclic. Indeed, if $(x_1,x_2)\in \mathbb {Z}^2$, this means that x ₁, x ₂ are integers, and (x ₂, x ₁) also belongs to $\mathbb {Z}^2$.

One way to obtain cyclic lattices is to use the following lemma.⁴

Lemma 4.1

A lattice Λ in $\mathbb {Z}^n$ is a cyclic lattice if Λ is an ideal of $\mathbb {Z}[X]/(X^n-1)$.

Proof

Given a lattice point a = (a ₁, ⋯ , a _n ) ∈ Λ, associate the polynomial in $\mathbb {Z}[X]$ given by a ₁ + a ₂ X + a ₃ X ² + …a _n X ⁿ⁻¹. We notice that this polynomial belongs to $\mathbb {Z}[X]/(X^n-1)$ since its degree is less than n. By definition of ideal, Λ is an ideal of $\mathbb {Z}[X]/(X^n-1)$ means that it is closed under multiplication, that is, if we multiply a ₁ + a ₂ X + a ₃ X ² + …a _n X ⁿ⁻¹ by X (and iteratively by powers of X), the result remains in Λ. But if we compute

$$\displaystyle \begin{aligned} (a_1+a_2X+a_3X^2+\ldots a_nX^{n-1})X = a_1X+a_2X^2+a_3X^3+\cdots a_nX^{n}, \end{aligned}$$

we obtain a ₁ X + a ₂ X ² + a ₃ X ³ + …a _n since X ⁿ ≡ 1 in $\mathbb {Z}[X]/(X^n-1)$. This shows that $(a_n,a_1,\ldots ,a_{n_1})\in \varLambda$ as desired.

Example 4.6

Consider $\mathbb {Z}[X]/(X^2-1)$, which is the set of polynomials a ₁ + a ₂ X, $a_1,a_2\in \mathbb {Z}$. Take the polynomial $g(X)=2+X \in \mathbb {Z}[X]/(X^2-1)$ and the ideal (g(X)) which is the set of all polynomials in $\mathbb {Z}[X]/(X^2-1)$ which are multiples of g(X). It is indeed an ideal since it is closed under addition:

$$\displaystyle \begin{aligned} g(X)(a_1+a_2X)+g(X)(a^{\prime}_1+a_2^{\prime}X) \end{aligned}$$

is a multiple of g(X). It is also clearly closed under multiplication: a multiple of g(X) multiplied by any polynomial will remain a multiple of g(X). Furthermore:

$$\displaystyle \begin{aligned} (2+X)(a_1+a_2X) =2a_1+2a_2X+a_1X+a_2=(a_2+2a_1)+(2a_2+a_1)X. \end{aligned}$$

This gives a set of vectors of the form (a ₂ + 2a ₁, 2a ₂ + a ₁) corresponding to a generator matrix:

$$\displaystyle \begin{aligned} \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. \end{aligned}$$

One may check explicitly (see Exercise 4.7) that this lattice is indeed cyclic.

Remark 4.1

The quotient $\mathbb {Z}[X]/(X^n-1)$ does not have a field structure, therefore the underlying multiplicative structure of this construction is different from that of the previous “ideal lattices.”

One interest in this construction of lattices is its succinct representation, since an n-dimensional lattice can be encoded with one vector. Furthermore, fast arithmetic is enabled using the fast Fourier transform (FFT). Yet unlike the q-ary lattices of Sect. 3.2.1, ideal lattices come with some guarantee in terms of complexity, e.g., the worst-case hardness of the SVP (see Problem 2.1) in cyclic lattices was analyzed in [71], to build one-way functions. Thus cyclic ideal lattices have been considered to build efficient cryptographic primitives and homomorphic encryption schemes. However, such lattice exhibit some weaknesses; see, e.g., [73, p.11], due to the fact that X ⁿ − 1 is reducible over the rationals.

A natural generalization is to consider a polynomial⁵ $p(X)\in \mathbb {Z}[X]$ other than X ⁿ − 1, such as X ⁿ + 1, for example, (in particular, the factor X − 1 of X ⁿ − 1 is not present, and thus X ⁿ + 1 tends to be preferred to X ⁿ − 1). If p(X) is instead a monic irreducible polynomial (X ⁿ − 1 is not), then the quotient $\mathbb {Z}[X]/(p(X))$ becomes a field. A family of polynomials that has been considered in the literature is that of cyclotomic polynomials. The m-th cyclotomic polynomial ϕ _m (X) is by definition

$$\displaystyle \begin{aligned} \phi_m(X) = \prod_{k,\gcd(k,m)=1}(X-e^{\frac{2ik\pi}{m}}). \end{aligned}$$

If m is prime, then $\phi _m(X)=\frac {X^m-1}{X-1}$. If m is a power of 2, then ϕ _m (X) = X ^m/2 + 1 (see Exercise 4.8). We use the notation $\zeta _m=e^{\frac {2ik\pi }{m}}$. In that case, we have

$$\displaystyle \begin{aligned} \mathbb{Z}[X]/(\phi_m(X)) \simeq \mathbb{Z}[\zeta_m] \subset \mathbb{Q}(\zeta_m)\simeq \mathbb{Q}(X)/(\phi_m(X)) \end{aligned}$$

and $\mathbb {Q}(\zeta _m)=\{a_1+a_2\zeta _m+\cdots +a_{d-1}\zeta _m^{d-1},~a_1,\ldots ,a_{d-1}\in \mathbb {Q}\}$ and d = φ(n) is the Euler totient of n. The reason for considering cyclotomic polynomials is that they have been well studied.

Remark 4.2

Unlike for the quotient $\mathbb {Z}[X]/(X^n-1)$, in this case of cyclotomic polynomials, both notions of “ideal lattices” coincide.

Thus to a vector, (a ₁, …, a _d−1) corresponds a polynomial a ₁ + a ₂ X + ⋯ + a _d−1 X ^d−1 in $\mathbb {Z}[X]/\phi _m(X)$, which in turn corresponds to an element $a_1+a_2\zeta _m+\cdots +a_{d-1}X^{d-1}\in \mathbb {Q}(\zeta _m)$. The corresponding lattice is now obtained by embedding $\mathbb {Q}(\zeta _m)$ into $\mathbb {C}^n$. We illustrate this for the case m = 4, corresponding to the cyclotomic polynomial ϕ ₄(X) = X ² + 1. Then $\mathbb {Q}(X)/(X^2+1)\simeq \mathbb {Q}(i)$.There are two embeddings (see the previous ideal construction):

$$\displaystyle \begin{aligned} \sigma_1: i \mapsto i,~\sigma_2: i \mapsto -i. \end{aligned}$$

A generator matrix is given by

$$\displaystyle \begin{aligned} \begin{bmatrix} 1 & i \\ 1 & -i \end{bmatrix}. \end{aligned}$$

There is a similar problem to that of the shortest vector problem (see Problem 2.1) for ideal (see [102], [84], Sec. 4.3.4. and the references therein). Consider σ = (σ ₁, …, σ _d ) the vector of embeddings of a degree-d number field K.

Problem 4.1

Given an ideal I of $\mathcal {O}_K$, where K is a number field, find a non-zero element b ∈ I which minimizes $\left \|\sigma (b)\right \|$.

The complexity of ideal lattice problems are summarized in [102], together with applications.

4. Exercises

Exercise 4.1

Show that the set of elements from $\mathbb {Q}(\sqrt {d})$ which are roots of monic polynomials with coefficients in $\mathbb {Z}$ is $\mathbb {Z}[\tfrac {1+\sqrt {d}}{2}]$ when d ≡ 1( mod 4) and $\mathbb {Z}[\sqrt {d}]$ when d≢1( mod 4).

Exercise 4.2

Construct a 2-dimensional lattice from $\mathbb {Z}[\sqrt {3}]$.

Exercise 4.3

Show that the lattice $\sigma (\sqrt {\alpha } \mathbb {Z}[(1+\sqrt {5})/2])$ in Example 4.3 is equivalent to $\mathbb {Z}^2$. Exhibit the explicit orthogonal transformation matrix and scaling factor.

Exercise 4.4

Show that the sets $I_1=\{\alpha a+ \alpha b \sqrt {d},~a,b\in \mathbb {Z}\}$, $I_2=\{\sigma (\alpha ) a+ \sigma (\alpha ) b \sqrt {d},~a,b\in \mathbb {Z}\}$ and $I=\{\beta a+ \beta b \sqrt {d},~a,b\in \mathbb {Z}\}$ with β = ασ(α), α ≠ σ(α) satisfy I ₁ I ₂ = I ₁ ∩ I ₂. Discuss what happens if α = σ(α).

Exercise 4.5

Show that the product distance is not a mathematical distance.

Exercise 4.6

Construct an 8-dimensional lattice by tensor product.

Exercise 4.7

Show that the lattice with generator matrix

$$\displaystyle \begin{aligned} \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} \end{aligned}$$

is cyclic.

Exercise 4.8

Prove that for m a power of 2, the cyclotomic polynomial is ϕ _m (X) = X ^m/2 + 1.