arXiv CSopen access

Structured lattices and their applications to security

STRUCTURED LATTICES AND THEIR APPLICATIONS TO SECURITY

arXiv:2606.18920v1 [math.NT] 17 Jun 2026

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

Abstract. Euclidean lattices are an interesting object of study in many regards and can have a rich structure arising from various constructions, e.g., from number field extensions. A particularly interesting class is the one of well-rounded lattices, as they relate to the well-known densest sphere packing problem in geometry, theta function minimization, and the famous Minkowski and Woods conjectures. In addition to being an important mathematical object in their own right, lattices also play a central role in many applications. This paper offers a survey of structured lattices and discusses their recent applications in lattice-based cryptography and secure wireless communications. Our goal is to spark the interest of mathematicians and adjacent communities in these fascinating topics in the intersection of lattices, number theory, cryptography, and wireless communications.

Contents 1. Lattices 1.1. Introduction to lattice theory 1.2. Well-rounded and related classes 1.3. Algebraic constructions 1.4. Spherical designs and Epstein zeta-function 2. Lattice-based cryptography 2.1. Hard lattice problems 2.2. Gaussians, variational distance, and the smoothing parameter 2.3. Learning with errors (LWE) and its variants 2.4. Equivalence between RLWE and PLWE 2.5. Cryptanalysis of RLWE/PLWE 2.6. Further applications of lattice-based cryptography 3. Lattice codes for wireless security 3.1. Basic notions in information theory and related security paradigms 3.2. Wiretap channels and lattice coset codes 3.3. The flatness factor and connections to theta functions 3.4. Well-rounded lattices as theta minimizers

3 3 7 10 13 16 16 18 18 21 22 23 26 26 27 28 29

2020 Mathematics Subject Classification. Primary: 11Hxx, 11E12, 11T71; Secondary: 94A60, 94Bxx. Key words and phrases. algebraic number fields, flatness factor, function fields, informationtheoretic security, lattices, lattice-based cryptography, learning with errors, physical layer security, secrecy gain, smoothing parameter, theta functions, well-rounded lattices. This work was supported in part by the Finnish Research Council (Grant #351271) and in part by the Business Finland Co-Innovation Consortium (Grant #5845483). R. Y. Njah Nchiwo was supported by the Magnus Ehrnrooth Foundation and the Finnish Academy of Science and Letters, Finland. 1

2

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

3.5. Related topics and generalizations 4. Conclusion and open problems Acknowledgments References

29 30 31 32

STRUCTURED LATTICES

3

1. Lattices 1.1. Introduction to lattice theory. The theory of Euclidean lattices has its origins in the work of Lagrange and Gauss, who studied lattices in the context of Kepler’s sphere packing conjecture and the arithmetic of quadratic forms. Major advances in the theory came with Minkowski’s development of geometry of numbers and further connections to number theory, convex and discrete geometry, algebraic geometry, optimization, geometric combinatorics and many other fields of mathematics. Today, lattice theory enjoys a central place within mathematics and its applications. Some of the major breakthroughs of the recent decades included T. Hales’s & S. Ferguson’s proof of Kepler’s conjecture [107], O. Musin’s proof of the kissing number conjecture in dimension 4 [138], and M. Viazovska et al. proof of the optimal sphere packing conjecture in dimensions 8 and 24, [184] and [54]. The goal of this survey paper is to give an overview of theory of Euclidean lattices and some of its recent developments with a view towards applications in coding theory and cryptography. We will especially focus on properties and constructions of important classes of lattices with additional structure (e.g., well-rounded, eutactic, perfect), which play a central role in optimization problems and applications. For comprehensive sources on the theory of Euclidean lattices, we refer the reader to the classical books by Conway & Sloane [57], Gruber & Lekkerkerker [106], and Martinet [127]. The first two authors of this paper have recently edited a special collection of research articles on “Euclidean lattices: theory and applications” (Communications in Mathematics, vol 31, no 2, 2023) which is surveyed in [90]. Throughout this paper we view Rn as a Euclidean space with respect to the usual Euclidean inner-product ⟨ , ⟩ and the corresponding Euclidean norm ∥x∥ := p ⟨x, x⟩ for every x ∈ Rn . A lattice L ⊂ Rn of rank r ≤ n (denoted rk(L) = r) is a discrete subgroup of Rn which is co-compact in the r-dimensional subspace V (L) := spanR L. This is equivalent to saying that there exists a collection of R-linearly independent vectors a1 , . . . , ar ∈ L such that ( r ) X L = spanZ {a1 , . . . , ar } = ci ai : c1 , . . . , cr ∈ Z . i=1

The collection a1 , . . . , ar is a basis for L and we refer to the n × r matrix A = (a1 . . . ar ) as a basis matrix for L, i.e., L = AZr . For any U ∈ GLr (Z), AU is another basis matrix for L. The subspace V (L) ⊆ Rn can be identified with Rr , so from here on we will talk about lattices of full rank in Rn , meaning that r = n. The space Ln of full-rank lattices in Rn can be identified with GLn (R)\ GLn (Z), the set of orbits of GLn (R) under the action of GLn (Z) by right multiplication. Two lattices L1 , L2 ⊂ Rn are said to be similar, denoted L1 ∼ L2 , if there exists α ∈ R+ , the group of positive real numbers, and U ∈ On (R), the n × n real orthogonal group, such that L2 = αU L1 . This is an equivalence relation, and the space Sn of similarity classes is (R+ × On (R))/Ln , the set of orbits of the space of full-rank lattices under the action of the group R+ × On (R) by left multiplication. A lattice L is called integral if for every x, y ∈ L, ⟨x, y⟩ ∈ Z and a lattice is called arithmetic if it is similar to an integral lattice. The group of isometries of a full-rank lattice L ⊂ Rn is O(L) := {U ∈ On (R) : U L = L}, which is compact as a subset of GLn (R) with respect to the Euclidean metric topology. The automorphisms of L are isometries given by integer linear transformations, so the automorphism group of L is Aut(L) := GLn (R) ∩ O(L).

4

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

Since Aut(L) is the intersection of a discrete subgroup with a compact set, it is finite. In fact, in all but seven exceptional dimensions the lattice with the largest (with respect to size) automorphism group is Zn , which is the signed permutation group consisting of 2n n! elements: it is generated by independent coordinate sign changes and permutations. When n = 2, 4, 6, 7, 8, 9, 10 more symmetric lattices with even larger automorphism groups exist. For example, | Aut(Z2 )| = 8 whereas the hexagonal lattice   1 √1/2 Z2 Λh = 3/2 0 has 12 automorphisms. This being said, most lattices have just two automorphisms: multiplication by ±1. The automorphism group is an invariant of the similarity class of a lattice. The determinant (also called co-volume) of a lattice L = AZn is defined as p det(L) := det(A⊤ A) and is equal to the volume the quotient group Rn /L. This is an invariant of L which does not depend on the choice of a basis matrix A. In other words, det(L) is the volume of any fundamental domain, i.e. a measurable full set of coset representatives of L in Rn . One example of a fundamental domain is a fundamental parallelotope {c1 a1 + · · · + cn an : 0 ≤ ci < 1 ∀ 1 ≤ i ≤ n}, corresponding to the basis matrix A = (a1 . . . an ). Another object more intrinsically dependent on L is its Voronoi cell V(L) := {x ∈ Rn : ∥x∥ ≤ ∥x − y∥ ∀ y ∈ L}. While V(L) is not a fundamental domain of L, it is the closure of S a fundamental domain, and hence its volume is still equal to det(L). Now, Rn = x∈L (x + V(L)), where two distinct translates x1 + V(L) and x2 + V(L) can intersect only at the boundary. A lattice L is called unimodular if det(L) = 1. For a given full-rank lattice L = AZn ⊂ Rn , its dual lattice is defined to be L∗ := {x ∈ Rn : ⟨x, y⟩ ∈ Z ∀ y ∈ L} = (A−1 )⊤ Zn , then det(L∗ ) = 1/ det(L). If L is integral then L ⊆ L∗ , hence unimodular integral lattices are self-dual, i.e., L = L∗ . We also define the successive minima 0 < λ1 (L) ≤ · · · ≤ λn (L) of a full-rank lattice L in Rn to be  λi (L) := min t ∈ R+ : dimR (spanR (L ∩ Bn (t)) ≥ i , where Bn (t) is a ball of radius t centered at the origin in Rn . In particular, the first successive minimum is the norm of a shortest nonzero vector in L. Additionally, the covering radius (also called the inhomogeneous minimum) of L is defined as  µ(L) := min t ∈ R+ : L + Bn (t) = Rn . The celebrated Minkowski’s Successive Minima Theorem (see, e.g., Chapter 2, § 9 of [106]) gives bounds on the product of successive minima of L: n 2n det(L) Y 2n det(L) (1) ≤ λi (L) ≤ , n!ωn ωn i=1 where ωn is the volume of a unit ball in Rn . An immediate implication of (1) is Minkowski Convex Body Theorem (see, e.g., Chapter 2, § 5 of [106]):  1/n det(L) (2) λ1 (L) ≤ 2 . ωn

STRUCTURED LATTICES

5

We define the set of minimal vectors of L to be S(L) := {x ∈ L : ∥x∥ = λ1 (L)}. The sphere packing associated to L is constructed by inscribing a ball of radius λ1 (L)/2 into each translate of the Voronoi cell V(L). The density of this packing is the proportion of the space occupied by the spheres, which is the same as ratio of the volume of the ball and volume of the Voronoi cell into which it is inscribed; it can be computed as ωn λ1 (L)n δ(L) := n ≤ 1. 2 det(L) This is a continuous function on the space of lattices Ln which is constant on any given similarity class, hence we can think of it as a continuous function of the space Sn of similarity classes. The objective of the lattice packing problem in a given dimension is to find a lattice that maximizes δ(L). Solutions to the lattice packing problem are only known in dimensions 1 ≤ n ≤ 9 (with n = 9 case being very recent still unpublished work by Dutour Sikirić and van Woerden) and n = 24 (see Chapter 1 of [57]). The celebrated Minkowski-Hlawka theorem (see, e.g., Chapter 1 of [57]) asserts that in every dimension n ≥ 2 there exists a full-rank lattice L ⊂ Rn such that ζ(n) δ(L) ≥ n−1 , 2 where ζ(n) the value of the Riemann zeta-function at n. The proof of this theorem, however, is not constructive, and in all but finitely many dimensions (up to 1000 or so) no constructions of lattices satisfying the Minkowski-Hlawka bound are known. This being said, the lower bound ζ(n)/2n−1 in the Minkowski-Hlawka theorem can be improved. The most significant improvement is due to B. Klartag [113], who established (also non-constructively) the lower bound cn2 /2n for some universal constant c > 0 in 2025. Notice that maximizing lattice packing density in dimension n ≥ 2 is equivalent to determining the value of the Hermite’s constant γn := maxn L⊂R

λ1 (L) . det(L)1/n

While the value of γn is only known in the few dimensions mentioned above, an upper bound on it follows, for instance, from Minkowski’s theorem (2). A linearly independent collection of vectors a1 , . . . , an ∈ L is said to correspond to successive minima if ∥ai ∥ = λi for each 1 ≤ i ≤ n. Finding the successive minima is equivalent to the shortest independent vector problem mentioned in Section 2, which is known to be NP-hard. Such a collection is not unique, but there are only finitely many of them in a given lattice. These vectors are known to form a basis for L in dimensions n ≤ 3, however in dimensions n ≥ 4 they do not necessarily form a basis. Consider, for example the lattice ( ) 4 1X L1 = spanZ e1 , e2 , e3 , ei ⊂ R4 , 2 i=1 where ei are the standard basis vectors. Then ( ) 4 1X e1 , e2 , e3 , ei and {e1 , e2 , e3 , e4 } 2 i=1

6

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

are both collections of vectors in L1 corresponding to successive minima, however the first one forms a basis whereas the second does not. Similarly, the lattice ( ) 5 1X (3) L2 = spanZ e1 , e2 , e3 , e4 , ei ⊂ R5 2 i=1 does not have a collection of vectors corresponding to successive minima that would form a basis. These observations raise a natural question: what is the shortest basis in L? Hermite inequality (see, e.g. Theorem 2.2.1 of [127]) guarantees that a lattice L of rank n has a basis a1 , . . . , an such that λ1 (L) = ∥a1 ∥ ≤ |a2 ∥ ≤ · · · ≤ ∥an ∥ and (4)

  n(n−1) 2 4 det(L). ∥ai ∥ ≤ 3 i=1 n Y

On the other hand, Hadamard inequality (see, e.g. Theorem 2.1.1 of [127]) states that the orthogonality defect of this basis is Qn ∥ai ∥ (5) ν(a1 , . . . , an ) := i=1 ≥ 1. det(L) Indeed, this basis is orthogonal if and only if ν(a1 , . . . , an ) = 1 and λ1 (L)n ≤ ν(a1 , . . . , an ) ≤ det(L)

  n(n−1) 2 4 , 3

n

1 (L) to achieve γnn entails maximizing the orthogonality implying that maximizing λdet(L) defect. We also want to mention two related optimization problems on lattices: the lattice covering problem and the kissing number problem. The covering configuration associated to the lattice L is constructed by circumscribing a sphere of radius µ(L) around each translate of the Voronoi cell, and the thickness of this covering is the ratio of the volume of the ball and volume of the Voronoi cell around which it is circumscribed; it can be computed as

(L) :=

ωn µ(L)n ≥ 1. det(L)

Again, this is a continuous function of the space Sn of similarity classes of lattices. The objective of the lattice covering problem in a given dimension is to find a lattice that minimizes (L). Solutions to the lattice covering problem are only known in dimensions 1 ≤ n ≤ 5 (see Chapter 1 of [57]). Finally, the kissing number problem on lattices asks for the maximal number of spheres centered at points of a lattice L in Rn that can touch the sphere centered at 0. This is equivalent to asking for a lattice with maximal number of minimal vectors in a given dimension, i.e., the kissing number of L is |S(L)|. The answer is known in dimensions 1 ≤ n ≤ 9 and n = 24 (see Chapter 1 of [57]).

STRUCTURED LATTICES

7

1.2. Well-rounded and related classes. A lattice L ⊂ Rn is called well-rounded (abbreviated WR) if λ1 (L) = · · · = λn (L), which is equivalent to saying that (6)

Rn = spanR S(L).

It is important to remark that WR condition (6) is not equivalent to the condition L = spanZ S(L), as demonstrated by the example L2 in (3) above: this second condition is strictly stronger than (6) for n ≥ 5; if it holds, we say that L is generated by minimal vectors (for n ≤ 4, all WR lattices are generated by their minimal vectors). Further, for all n ≥ 10 it is possible for a lattice L to be generated by minimal vectors while not containing a basis of minimal vectors: this was first demonstrated for n ≥ 11 by Conway and Sloane [56] and then extended to n ≥ 10 by Martinet and Schürmann [130]. On the other hand, for all n ≤ 9 lattices generated by minimal vectors contain a basis of minimal vectors (see [128], [129], [130]). WR property is preserved under similarity, hence we can speak of WR similarity classes, of which there are infinitely many in each dimension n ≥ 2. WR lattices appear in many different contexts in number theory, geometry, combinatorics and optimization. In particular, the space of WR lattices forms a “spine” (SLn (Z)equivariant deformation retract) for the space of all lattices in Rn , which is useful for cohomology computations [9], [155], [110]. Further, WR lattices appear prominently in regard to Minkowski conjecture [131]. Let L be a unimodular lattice. For each x ∈ L, define the multiplicative norm N (x) = |x1 · · · xn |. Notice that N is preserved under the left-multiplication action by the diagonal group      n  a1 . . . 0  Y  .. . .  . . An :=  . ai = 1 ,  : ai > 0, . .     i=1 0 . . . an in other words, N (x) = N (Ax) for any A ∈ An . Minkowski conjectured that for any unimodular lattice L ⊂ Rn , sup inf N (x − y) ≤

x∈Rn y∈L

1 . 2n

This conjecture was originally motivated by the study of certain “approximation properties” of algebraic integers in number fields (see [23])). Minkowski proved his conjecture for n = 2; up until 2005, the conjecture was proved in dimensions n ≤ 5. In his seminal paper [131], C. McMullen proved this conjecture for n = 6 (see [131] for references to the earlier work). He follows the Remak-Davenport approach (see Section 27.1 of [105] for details and history), splitting the Minkowski’s conjecture into two statements from which it follows: (Wn ) For any lattice L ⊂ Rn , there exists A ∈ An such that AL√is WR. (Cn ) For any unimodular WR lattice L ⊂ Rn , µ(L) ≤ µ(Zn ) = n/2. In the direction of (Wn ), McMullen established that if the closure of the orbit of L under the action of An is bounded, then it contains a WR lattice. This, along with (Cn ), turns out to be enough to establish Minkowski’s conjecture. The second part (Cn ) is known as A. C. Woods’ covering conjecture [185]; prior to McMullen’s work, it has been proved in dimensions n ≤ 6 and has since been proved in all dimensions n ≤ 10 (see [111] and references within). On the other hand, Woods’ conjecture has been disproved in dimensions n ≥ 30 by Regev, Shapira and Weiss [160], whose work has been extended by Chen and Xu to show that the conjecture fails for

8

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

n ≥ 24 [48]. This, however, does not necessarily mean that Minkowski conjecture in those dimensions is not true. Another important class of lattices (related to WR lattices at least in spirit) is semi-stable lattices: L ⊂ Rn is called semi-stable if for every sublattice M ⊆ L, det(M )1/ rk(M ) ≤ det(L)1/ rk(L) . Semi-stable lattices were first introduced in the context of reduction theory, where this condition was taken to heuristically suggest that the successive minima of L are not too far apart (see [7] and the excellent survey paper of Casselman [45] on semi-stable lattices, which in particular provides many references and the history of development of this subject). This, however, does not mean that WR lattices are necessarily semi-stable: this statement is only true for n = 2, whereas for n ≥ 3 the sets of semi-stable and WR lattices are independent (see, e.g., [85] for explicit examples of non-stable WR lattices in R3 ), although they do have an intersection. Similarly to the WR lattices, semi-stable lattices are also well-distributed among the orbits of the diagonal group action on the space of lattices. Specifically, in [172] the authors showed that, analogously to McMullen’s observation about WR lattices, if the closure of the orbit of L under the action of An is bounded, then it contains a semi-stable lattice. Remarkably, in [176] Solan strengthened this observations for both, WR and semi-stable lattices, proving that for any lattice L ⊂ Rn , there exist A, B ∈ An such that AL is WR and BL is semi-stable. In particular, this establishes the conjecture (Wn ) from above. The two-dimensional distribution of WR and semi-stable lattices can be described very explicitly and deserves some attention due to its connection to the parameterization of elliptic curves; our brief exposition follows [87], [86], [88]. Let H = {τ = a + bi : b ≥ 0} ⊂ C be the upper half-plane, and let D := {τ = a + bi ∈ H : −1/2 < a ≤ 1/2, |τ | ≥ 1}. Let F := {τ = a + bi ∈ H : 0 ≤ a ≤ 1/2, |τ | ≥ 1}, so, loosely speaking, F is “half” of D. Every point τ = a + bi ∈ F can be identified with a lattice   1 a Γτ := Z2 0 b in R2 . Every planar lattice L is similar to a unique lattice of the form Γτ for some τ ∈ F, hence we can say that the similarity class of L is represented by τ . Thus, F can be thought of as the space of similarity classes of lattices in R2 (see Figure 1). WR similarity classes correspond to the circular arc {τ ∈ F : |τ | = 1} and semistable similarity classes correspond to the set {τ = a + bi ∈ F : b ≤ 1}. On the other hand, the full domain D can be viewed as the space of isomorphism classes of elliptic curves: a point τ corresponds to the isomorphism class of the elliptic curve given by the complex torus C/Γτ , where we are identifying C with R2 and thinking of Γτ as spanZ {1, τ } ⊂ C. This being said, while the lattices Γτ and Γτ̄ are similar, the corresponding elliptic curves are not isomorphic: instead, the two elliptic curves have conjugate j-invariants, since j(−τ̄ ) = j(τ ) (here j is Klein’s modular j-function).

STRUCTURED LATTICES

9

Figure 1. Similarity classes of lattices in R2 with WR and semistable subregions marked by colors. Further, the question of distribution of WR sublattices of a given lattice L ⊂ R2 has been investigated by several authors via analysis of the properties of the socalled WR zeta-function ∞ X ζWR (s) = ak k −s , k=1

where ak is the number of WR sublattices of L of index k and s is a complex variable. Information about the position and order of the pole, as well as the residue at the pole of this function can be used along with Wiener-Ikehara Tauberian theorem and P its later variations to establish the order of growth of the counting function k≤n ak , the number of WR sublattices of L of index at most n as n → ∞. The result depends on whether the lattice L is arithmetic or not. Specifically, combining the results of [84] and [114], we obtain:  X O(n log n) if L is arithmetic, ak = O(n) if L is not arithmetic, k≤n

P as n → ∞. More detailed asymptotic results on the summatory function k≤n ak have later been obtained in [12]. There are several other contexts in which WR lattices have been investigated, e.g. in connection with the Frobenius problem [97]. Most importantly, WR lattices are key in discrete optimization and applications. In particular, the lattice packing problem can be restricted to WR lattices without loss of generality, i.e., any solution to the lattice packing problem in every dimension n ≥ 2 has to be a WR lattice. In fact, more is true. A lattice L ⊂ Rn with m = |S(L)| is called eutactic if there exist positive real numbers c1 , . . . , cm such that (7)

∥x∥2 =

m X

2

ci ⟨x, y i ⟩ ,

i=1

where S(L) = {y 1 , . . . , y m }. The lattice L is strongly eutactic if c1 = · · · = cm . On the other hand, if the space of n × n real symmetric matrices Symn (R) can be

10

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

represented as  Symn (R) = spanR y i y ⊤ i : y i ∈ S(L) , then the lattice L is called perfect. Both, perfect and eutactic properties are preserved under similarity. While the sets of eutactic and perfect lattices are independent (there are perfect non-eutactic and eutactc non-perfect lattices), both of them are WR, but not necessarily semi-stable: an example of a perfect non-stable lattice in dimension 8 has been obtained by Y. Kim [112], where he also proved that all other perfect lattices in dimension ≤ 8 are semi-stable. A lattice is called extreme if it is a local maximum of the packing density function in its dimensions, and a classical theorem of Voronoi (see, e.g., Theorem 3.4.6 of [127]) states that a lattice is extreme if and only if it is perfect and eutactic. It is well known that perfect lattices are necessarily arithmetic, hence so are extreme lattices. In every dimension n ≥ 2 there are only finitely many eutactic and finitely many perfect similarity classes. For instance, up to similarity in R2 , there are only two eutactic lattices (Z2 and Λh ) and only one perfect (Λh ). Further, Bacher proved [15] that the number pn of perfect similarity classes of lattices in Rn satisfies the following inequalities for any ε > 0: 1−ε 3+ε en < pn < en . 2

The upper bound has recently been improved by van Woerden [180] to eO(n log n) . The exact value of pn has so far been published in all dimensions n ≤ 8 with the 8-dimensional case being an extensive computational project by Dutour Sikirić, Schürmann and Vallentin [174] building on the previous results (see Section 6.6 of [127]): they showed that there are 10916 perfect lattices in R8 , but only 2408 of them are eutactic (hence, extreme) by the work of Riener [161]. The computational project by Dutour Sikirić and van Woerden to count and classify perfect lattices in R9 has been ongoing for some years and has recently completed: their work is currently being prepared for publication. We close this section with the notion of generic well-rounded (GWR) lattices, which has been considered in [119, 109]: a full-rank WR lattice L ⊂ Rn is called GWR if |S(L)| = 2n. One immediate example of a GWR lattice is Zn . GWR lattices can have a relatively high packing density while maintaining a relatively small kissing number, which is a useful property for some coding theory applications we detail below. One steady source of GWR lattices are the nearly orthogonal lattices. Given an ordered basis B = {b1 , . . . , bn } for a lattice L, define a sequence of angles θ1 , . . . , θn−1 so that each θi is the angle between bi+1 and the subspace spanR {b1 , . . . , bi }. Then each θi ∈ [0, π/2] and B is called a weakly nearly orthogonal basis if θi ≥ π/3 for each 1 ≤ i ≤ n − 1. A basis B is called nearly orthogonal if every ordering of it is weakly nearly orthogonal. If L has such a basis, we say that L is a nearly orthogonal lattice. Nearly orthogonal lattices were introduced in [16], where they were applied to the problem of image compression. Nearly orthogonal lattices that are also WR (and often GWR) have been studied in [92]. 1.3. Algebraic constructions. Due to their importance in a variety of theoretical contexts and applications, explicit constructions of WR families of lattices (often with additional properties) are of great interest. In particular, a great deal of attention was devoted to the study of constructions coming from different algebraic

STRUCTURED LATTICES

11

settings. To this end, let us start with a number field K of degree n ≥ 2 over Q and let us write ∆K for its discriminant and OK for its ring of integers. Assume that K has r1 real embeddings σ1 , . . . , σr1 : K → R and r2 pairs of complex conjugate embeddings τ1 , τ̄1 , . . . , τr2 , τ̄r2 : K → C. Then n = r1 + 2r2 and we can define the Minkowski embedding of K into Rn by ΣK := (σ1 , . . . , σr1 , ℜ(τ1 ), ℑ(τ1 ), . . . , ℜ(τr2 ), ℑ(τr2 )) : K → Rn . Let J ⊂ K be a fractional ideal, then ΣK (J) ⊂ Rn is a lattice of full rank. Lattices like this are called ideal lattices via Minkowski embedding. Notice that for any α, β ∈ K, ⟨ΣK (α), ΣK (β)⟩ = TrK (αβ̄), where TrK stands for the number field trace on K. Hence, the Euclidean lattice structure on ΣK (J) is induced by the trace of K. The theory of ideal lattices in a more general form has been developed by Bayer-Fluckiger, among other authors; see [22], [23] for a detailed survey of this area. WR ideal lattices have first been studied in [96], where it was in particular proved that for totally real and totally imaginary number fields, ΣK (OK ) is WR if and only if K is cyclotomic (see also [6]). More generally, let us say that an ideal J ⊆ OK is WR if the corresponding ideal lattice ΣK (J) is WR. Infinite families of real and imaginary quadratic number fields containing WR ideals have been constructed in [96]. Further, in√[89] it has been proved that for squarefree positive integer D, quadratic fields K( ±D) contain WR ideals when D has a divisor d satisfying r √ D ≤ d < D. 3 √ This condition is if √ and only if in the case K = Q( −D). On the other hand, [177] establishes that Q( D) contains WR ideals if and only D has a divisor d satisfying r √ D ≤ d < 3D. 3 Thus, relatively few of ideal lattices from quadratic number fields are WR. On the other hand, as follows from the results of McMullen [131] and Solan [176], any ideal lattice can be “twisted” into a WR one by the action of the diagonal group A2 . Damir and Karpuk in [65] investigated properties of the specific bases of ideals that result in the minimal basis of such corresponding WR twist. Further, situations when the canonical basis of an ideal in a quadratic number field can be so twisted have been studied in [63]. For higher degree number fields, WR ideals have been proved to exist in cyclic cubic and (some) cyclic quartic number fields [118]. Semistable ideal lattices have also been investigated; in particular, infinite families of semi-stable ideal lattices from any real quadratic number field were constructed in [85] (where it was also proved that a positive proportion of ideal lattices from real quadratic fields are semi-stable) and semi-stable twists of canonical bases of ideals in all quadratic number fields were studied in [63]. Well-rounded ideal lattices from totally definite quaternion algebras were recently studied in [49]. There is a different algebraic construction of lattices actively used in cryptography, which has also received the name of ideal lattices. Let f (x) ∈ Z[x] be a monic polynomial of degree n and consider the quotient ring R(f ) := Z[x]/ ⟨f (x)⟩. Define the coefficient embedding ρf : R(f ) → Zn ,

12

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

given by ρf (a0 + a1 x + · · · + an−1 xn−1 ) = (a0 , a1 , . . . , an−1 )⊤ . This is a linear map between two free Z-modules and an ideal J ⊆ R(f ) is mapped onto a sublattice ρf (J) ⊆ Zn . We will call such lattices the coefficient ideal lattices; they generalize the original construction of cyclic lattices (introduced by Micciancio in [133]), which are the special case ρf (J) for f (x) = xn − 1. These lattices were introduced and studied in the cryptographic context by Lyubashevsky and Micciancio [123]. WR cyclic lattices have been investigated in [98], [99], [93]. If f (x) is an irreducible polynomial, then the corresponding map ρf is a linear isomorphism of Z-modules R(f ) and Zn and the coefficient ideal lattices ρf (J) have full rank (Lemma 3.2 of [123]). In the special case when f (x) is n-th cyclotomic polynomial of degree φ(n), the ring R(f ) can be identified with the ring of integers Z[θn ] of the cyclotomic field Q(θn ) via the canonical isomorphism x 7→ θn , where θn = e2πi/n is n-th primitive root of unity. One can then ask about the relation between the two embeddings, i.e., between the ideal lattice ΣQ(θn ) (J) and the coefficient ideal lattice ρf (J) for a given ideal J in this ring. The linear transformation between the two has been worked out by Batson in [21] as we describe in Eq. (11) . The construction of lattices via Minkowski embedding can start from any free Z-module contained in the number field K, not only from an ideal in OK . Let, for instance, M(α) = spanZ {α1 , . . . , αn }, where α = α1 , α2 , . . . , αn are algebraic conjugates contained in K. A special case of this construction when K is a cyclic number field of odd prime degree has been considered in [68], [69], where families of WR such lattices (in fact, even having bases of minimal vectors) have been obtained. More general such constructions of GWR nearly orthogonal lattices with bases of minimal vectors and large automorphism groups – in particular, coming from Pisot numbers – are currently being explored in [91]. More generally, the so-called module lattices in Rnd , n = [K : Q], d ≥ 1, coming from modules M ⊂ K d via Minkowski embedding ΣK : K d → Rnd were used in [117] in the construction of lattice-based crypto-schemes; see Section 2 for more details. Another explicit algebraic construction of WR lattices comes from curves over finite fields. Let F be an algebraic function field of a single variable with the finite field Fq as its field of constants. Let P = {P0 , P1 , . . . , Pn−1 } be the set of rational places of F and for each Pi , let vi denote the corresponding normalized discrete ∗ valuation. Let OP be the abelian group of all nonzero functions f ∈ F whose Pn−1 ∗ divisor has support contained in the set P. Then i=0 vi (f ) = 0 for each f ∈ OP . Let n = |P|, the number of rational places of F , and define the homomorphism ∗ ϕP : OP → Zn by ϕP (f ) = (v0 (f ), v1 (f ), . . . , vn−1 (f )). ∗ Then LP := ϕP (OP ) is a finite-index sublattice of the root lattice ( ) n−1 X An−1 = x ∈ Zn : xi = 0 . i=0

These lattices, called function field lattices, are described in detail in the well known book [178] by Tsfasman and Vladut (Chapter 5.4); they were originally introduced in [165] by Rosenbloom and Tsfasman, who used this construction to produce asymptotically good families of lattices from the standpoint of packing density. A more systematic investigation of the geometric properties of these lattices was carried out more recently by several authors. In particular, the case of elliptic

STRUCTURED LATTICES

13

curves (algebraic function fields of genus 1) has been considered in [94] and [171], where it has been proved that for n ≥ 5 the lattice LP is WR and has a basis of minimal vectors. This, however, is a special case of the more general result of [39] on lattices from finite abelian groups discussed below. For fields of higher genus, the case of Hermitian function fields Fq (x, y) with y q + y = xq+1 for a prime power q is considered in [40], where it is proved that the corresponding lattice LP is WR and generated by minimal vectors. On the other hand, examples of hyperelliptic function fields giving rise to non-WR lattice LP are presented in [10]. We now turn to explicit algebraic constructions of families of extreme lattices. The most standard of these are the irreducible root lattices An , Dn , E6 , E7 , E8 and on some occasions their duals (a lattice is called irreducible if it is not an orthogonal sum of proper sublattices). We refer the reader to the excellent detailed exposition of the theory of root lattices (as well as related to them Coxeter lattices) in Martinet’s book [127] and focus instead on a more recent lesser-known construction. Let G = {0G , z1 , . . . , zn } be an additive abelian group and define ) ( n n X X n ai zi = 0G , ai = 0, LG := a ∈ Z : i=1

i=1

which is a lattice of rank n − 1. Böttcher et al. [39] proved that the lattice LG is WR and, in fact, has a basis of minimal vectors for G ̸= Z/4Z. Further, Böttcher et al. [38] established that LG is strongly eutactic for all G of odd order or elementary abelian 2-groups. Additionally, Ladisch [116] proved that LG is eutactic for all G ̸= Z/4Z. On the other hand, Bacher [14] proved that for all G of order at least 9, the lattice LG is perfect. Putting these results together, we see that LG is extreme for all finite abelian groups G of order at least 9. Additional constructions of strongly eutactic lattices from tight (equiangular) frames and distance transitive graphs have been given in [41] and [95], respectively. We choose, however, not to detail them here since they are somewhat more analytic in nature. Finally, we mention the notion of tame lattices that were introduced in [67] and motivated by the behavior of the trace pairing over tame cyclic number fields as well as by their ability to serve a method to explicitly construct WR lattices. Tame lattices have a Lagrangian basis [55] and they have Gram matrices of a nice specific form. Tame lattices are known to exist for any tame number field with a prime conductor [33]. GWR lattices arising from tame ones were constructed and studied in [109], including a discussion on their applicability to wireless security, which we discuss in Section 3. 1.4. Spherical designs and Epstein zeta-function. We also briefly discuss spherical designs and their connection to (highly structured) Euclidean lattices. Let Sn−1 (r) ⊂ Rn be the sphere of radius r centered at the origin in Rn . A finite collection of points {x1 , . . . , xm } ⊂ Sn−1 (r) is called a spherical t-design for an integer t ≥ 1 if for any polynomial p(y1 , . . . , yn ) ∈ R[y1 , . . . , yn ] of degree ≤ t, Z m 1 X p(xi ) = p(y)dy, m i=1 Sn−1 (r) R where the measure is normalized so that Sn−1 (r) dy = 1. Spherical t-designs have been originally introduced by Delsarte, Goethals and Seidel [71]. The existence of spherical t-designs in Rn for any t, n ≥ 1 was established by Seymour and T.

14

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

Zaslavsky [170]) with effective bounds on the size of such designs produced by Bondarenko, Radchenko and Viazovska [37]. We state here a convenient criterion for a 0-symmetric set X ⊂ Sn−1 (r) to be a spherical t-design for t = 2p and t = 2p + 1, p ≥ 1: such X is a spherical t-design if and only if there exists a constant cp such that cp X 2p ⟨y, x⟩ , (8) ∥y∥2p = 2p r |X| x∈X

n

for all y ∈ R . An important class of such symmetric spherical designs comes from sets of minimal vectors in lattices. Indeed, comparing (7) with (8), we see that a lattice L ⊂ Rn is strongly eutactic if and only its set of minimal vectors S(L) is a spherical 2-design. The connection between spherical designs and lattices has been studied by several authors, starting with the fundamental paper of B. Venkov [183] (see also Chapter 16 of [127] for a nice exposition of the results of [183]). A lattice whose set of minimal vectors is a spherical 4-design is called strongly perfect, and Venkov proves that strongly perfect lattices are extreme (hence, perfect, by Voronoi’s theorem, making the notation justified). In the same paper, Venkov also produced a list (albeit not a full classification) of strongly perfect lattices in dimensions n ≤ 24. Various classification results for strongly perfect lattices and lattices carrying even higher-degree spherical designs have appeared since (see, e.g., [148] and references within). We refer the reader to the paper [145] by Nebe for a detailed survey of Venkov’s theory of lattices and spherical designs and related contributions by other authors. Spherical designs play a role in another important optimization problem on lattices. The Epstein zeta-function of a lattice L ⊂ Rn is defined as X ZL (s) = ∥x∥−2s , x∈L\{0}

for a variable s ∈ C. For each lattice L in each dimension n ≥ 2, this Dirichlet series converges in the half-plane ℜ(s) > n/2, has a simple pole at s = n/2 and admits a meromorphic continuation to the whole complex plane. The classical minimization problem for the Epstein zeta-function considers a fixed real value s0 > 0, s0 ̸= n/2, and asks for a lattice L0 ⊂ Rn such that ZL0 (s0 ) = min {ZL (s0 ) : L ⊂ Rn } . Besides the intrinsic lattice theory interest, this problem also come up in the work of S. Sobolev [175] in regards to numerical integration. In dimension n = 2, this problem dates back at least to the work of Rankin [157], Cassels [46], Diananda [73] and Ennola [81], who established that for any such s0 the minimum occurs only at the hexagonal lattice. In dimension n = 3, the minimization problem was solved by Ennola [82] and in dimensions n = 4, 8, 24 by Sarnak and Strömbergsson [167]. It was separately proved by Ryškov [166] that the minimizer of ZL (s) as s → ∞ corresponds to the densest lattice packing in Rn . This last observation makes it especially interesting to look for such minimizers, and that is where spherical designs again make an appearance. Given a lattice L ⊂ Rn , let us define the spectrum of L to be the set {∥x∥ : x ∈ L \ {0}}. We can write the spectrum as an ordered set of real numbers {0 < a1 < a2 < . . . } and

STRUCTURED LATTICES

15

define the k-th layer of L to be {x ∈ L : ∥x∥ = ak }. With this notation, we can state a remarkable theorem of Coulangeon [59]: if every layer of L contains a spherical 4-design, then L is a minimizer of ZL (s) for every real value of s > n/2. The minimization problem for Epstein zeta-function also has an interesting apP∞ plied connection. APDirichlet series F (s) = n=1 an n−s and the corresponding ∞ power series f (z) = n=1 an z n are connected via the Mellin transform: Z ∞ Γ(s)F (s) = xs−1 f (e−x )dx, 0

where Γ(s) is the value of the Γ-function at s. Thus, ZL (s) for an integral lattice L corresponds to the power series ΘL (z), called the theta-function of L. The corresponding minimization problem for ΘL (z) has important implications for maximizing the reliability and security of communications when using lattices to construct coding schemes for wireless communications. We discuss this connection in more detail in Section 3.

16

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

2. Lattice-based cryptography Over the last few decades, interest in lattices has grown due to their applications in cryptography. In this chapter, we discuss lattice-based cryptography (LBC), focusing on paradigms whose security depends on hard mathematical problems involving lattices. We describe several complex problems in LBC and examine their worst-case and average-case hardness. In particular, our main focus will be on the Learning with Errors (LWE) problem and its variants, and analyze the relationships among them. For further background, see [50], [125], [159]. We begin with a general introduction to post-quantum cryptography (PQC). Post-quantum cryptography. Cryptography relies on complex mathematical problems, such as the discrete logarithm and integer factorization problems. The RSA [163] and Diffie-Hellman protocols [74], which protect our communication networks, are based on these two problems. However, rapid progress in quantum computing poses a serious threat to these foundations. The Shor algorithm [173], introduced by Peter Shor in 1994, solves both problems in polynomial time on a large enough quantum computer, rendering the protocols insecure. This leads us to the field of post-quantum cryptography [61], which focuses on cryptographic protocols that are resistant to quantum attacks. This provides an alternative for the soon-to-be-broken schemes. The main post-quantum approaches are code-based, isogeny-based, multivariate, hash-based, and lattice-based cryptography. Among these, lattice-based schemes are central for their simplicity, flexibility, and strong security guarantees. A problem is considered hard in the worst case if it is hard for at least one instance, and average-case hard if it is hard for most instances from a given distribution. Worst-case hardness provides theoretical assurance but may not guarantee security, as random instances might too often correspond to weak instances. To guarantee strong security, we require random (average) instances that are likely to be as hard as the worst case instances. Proving such a property is done by a process called worst-case-to-average-case reduction. We define several widely studied worst-case hard lattice problems in the following section.

2.1. Hard lattice problems. We define some of the fundamental lattice problems believed to be hard in the worst case. Shortest vector problem (SVP): Given a basis B of a lattice L, find a shortest non-zero vector of the lattice. Explicitly, find a nonzero vector x ∈ L such that ∥x∥ = λ1 (L). The approximate version, approximate SVP problem (SVPγ ), asks for a nonzero x ∈ L such that λ1 (L) ≤ γ(n)∥x∥ where γ(n) ≥ 1. The GapSVPγ problem (decision SVPγ ) asks to decide if λ1 (L) ≤ r or λ1 (L) ≥ γr where r ∈ Q. Closest vector problem (CVP): Given a basis B, of a lattice L, and a target vector t∈ / L, find a vector in L that is closest to t. When dist(t, L) ≤ d where d ∈ Z+ we refer to this as a bounded distance decoding problem (BDD). The approximate version, CVPγ , asks to find a lattice vector at distance at most γ. And the decision version, GapCVPγ asks to decide whether dist(t, L) < 1 or dist(t, L) < γ. Shortest independent vector problem (SIVP): Given a lattice L, find n linearly independent vectors v 1 , . . . , v n in L such that max ∥v i ∥ ≤ λn (L). The approximate i

STRUCTURED LATTICES

17

version, SIVPγ finds these vectors with length at most γλn (L). On the other hand, the decision version, GapSIVPγ asks to determine if λn (L(B)) ≤ d or λn (L(B)) > γd. Generalized shortest independent vector problem (GIVPϕγ ): Given a lattice L(B) of dimension n, find n linearly independent vectors v 1 , . . . , v n in L such that max ∥v i ∥ ≤ γϕ(L(B)) where ϕ is an arbitrary real valued function of a lattice i

and γ(n) ≥ 1. When ϕ = λn , we get the SIVPγ . The hardness of these lattice problems has been widely studied due to their importance in applications. In particular, the SVP and the CVP, along with their approximate versions, form the basis for many secure post-quantum cryptographic schemes. The first results showing that CVP is computationally hard date back to Van Emde Boas [179], who showed that CVP is NP-hard via a deterministic reduction. That is, with high probability, any problem in NP can be reduced in polynomial time to an instance of CVP. Based on the similarities between SVP and CVP, he further conjectured SVP was also NP-hard. After almost two decades, Ajtai in [5] showed that SVP with the l2 -norm is NP-hard for randomized reduction, thus proving the van Emde Boas conjecture. In practice, one typically works with the approximate variants of SVP and CVP, which are also NP-hard for a small enough approximation factor γ. Arora et al. [8] showed that the approximate CVP is NP-hard within any constant. Micciancio [132] later √ showed that for any lp -norm, approximate SVP within any constant in the Euclidean factor γ < p 2 is hard under some random reductions. Specifically, √ norm, the approximate SVP is NP-hard with any factor γ < 2. Extending on [8], Dinur et al. in [75] later showed that the approximate CVP problem in an nc dimensional lattice is NP-hard for a factor γ = n log log n for some constant c > 0. Further studies on the hardness of these problems have been conducted within an exponential factor. However, the results show that these problems are unlikely to be NP-hard. In particular, √ the approximate CVP and SVP are highly likely not NP-hard within a factor n [104, 2]. Despite these limitations, these problems are computationally hard in the worst case and form the basis of modern cryptography. The connection between these worst-case hard lattice problems and security brings us to the field of lattice-based cryptography. The study of lattice-based cryptography began with Ajtai’s ground breaking work in [4], which introduced the first average-case hard problem, the short integer solution (SIS). On a high level, the SIS problem asks one to recover a short nonzero vector z ∈ Zm given a random matrix A ∈ Zn×m satisfying Az = 0 mod q. The requirement for z ̸= 0 and short is what makes this problem difficult. This hardness was shown by a worst-case-to-average-case reduction from a well known worst-case hard problem. Building on this, in 2005 Regev introduced the learning with errors (LWE) problem [158], which is a noisy analog of SIS. This problem plays a central role in LBC. On a high level, the LWE problem is the following: given arbitrary independent samples of noisy linear equations (a, b = a · s + e) ∈ Znq × Zq , recover the secret s ∈ Znq . The error e, is sampled from a Gaussian distribution. The choice of the error distribution plays a critical role in the hardness of the problem as well as in the correctness of the public key encryption scheme based on the LWE problem. We describe this below.

18

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

2.2. Gaussians, variational distance, and the smoothing parameter. A continuous Gaussian function centered at c ∈ Rn defined over Rn is given by −π∥x − c∥2 , s2 √ where s = 2πσ with σ being the standard deviation. Normalizing this function by 1/sn defines the corresponding probability density function ρs,c (x) = exp

1 −π∥x − c∥2 exp . sn s2 If c = 0, we denote ρs,0 = ρs , gs,0 = gs . P Let us consider the L-periodic function gs,L (x) = λ∈L gs,λ (x), which is a probability density function when restricted to Rn /L. We can now define the discrete Gaussian distribution DL,s,c as gs,c (x) =

DL,s,c (x) =

gs,c (x) gs,L (c)

for x ∈ L and zero otherwise. Again, we denote DL,s,0 = DL,s . An important tool used in lattice-based schemes is the smoothing parameter, which ensures that the noise parameter s is large enough to hide the underlying secret structure. More rigorously, it determines the minimal noise level that guarantees indistinguishability from a uniform distribution by a maximum gap δ. By “gap”, we mean the variational distance (equivalently, statistical distance) between two distributions pX and pY ; Z (9) V (pX , pY ) = |pX (x) − pY (x)|dx. Rn

Smoothing parameter [134]: Let L ⊂ Rn be a full-rank lattice and δ > 0. The smoothing parameter ηδ (L) is defined as  (10) ηδ (L) = inf s > 0 ρ1/s (L∗ \ {0}) ≤ δ . In other words, fixing s to be the infinimum ensures that the variational distance between the lattice Gaussian and the uniform distribution on the Voronoi cell is at most δ. The smoothing parameter is closely related to the flatness factor, which we will define in Section 3, Eq. (12). Remark 2.1. The continuous Gaussian is used for analysis such as defining the smoothing parameter and for reduction proofs. In contrast, the discrete Gaussian is used for the actual cryptographic constructions, such as sampling the errors. We will use both in this work as needed depending on the context. 2.3. Learning with errors (LWE) and its variants. We define the LWE problem and some of its variants like the ring learning with errors (RLWE), the polynomial learning with errors (PLWE) problems and the module learning with errors problem (MLWE). We closely follow the definitions in [158], [124], [44]. Learning with errors (LWE) problem. Let n ≥ 1 and q = q(n) ≥ 2 be integers. Let s ∈ Znq be a secret vector sampled uniformly where n is the security parameter. Additionally, let χ be the error distribution that follows a discrete Gaussian sampled over Z and reduced modulo q.

STRUCTURED LATTICES

19

LWE distribution: The LWE distribution As,χ over Znq × Zq is defined as follows: sample a ← Znq uniformly, e ← χ, and output (a, b) ∈ Znq × Zq where b = ⟨s, a⟩ + e (mod q). The addition is performed modulo q. Search LWE (LWEq,χ ): Given an arbitrary number of independent samples (ai , bi ), drawn from the LWE distribution As,χ , the search LWE problem asks to find the secret vector s. Decision LWE: Given arbitrary many independent samples the decision problem asks to determine with non-negligible advantage whether the sample (ai , bi ), is from the LWE distribution As,χ or from a uniform distribution. In matrix form: (A, b) ∈ Zn×m × Zm q q where A is a matrix whose columns are the t n t t vectors ai ∈ Zq and b = s A + e (mod q) with m the number of samples. Let L = {y ∈ Zm : AT z = y

(mod q) for some z ∈ Zn }.

Observe that L is a full rank integer lattice in Rn , when we choose m = n linearly independent ai ’s. The LWE problem can be viewed as a bounded distance decoding problem on L where b is a closest vector to a lattice point. The relevance of LWE lies in its reduction from a worst-case hard problem. We state the hardness result below. Theorem √ 2.1. ([158], Theorem 1.1) Let n, q be integers, α ∈ [0, 1) be such that αq > 2 n and χ a Gaussian distribution. If there exists an efficient algorithm that solves LWEq,χ , then there exists an efficient quantum algorithm that approximates the decision version of SVP (GapSVP) and SIVP to within Õ(n/α)1 in the worst case. The LWE decision and search versions are equivalent when the integer modulus q is prime [158]. Although LWE offers strong security guarantees, LWE-based schemes have a quadratic overhead in the key size in terms of the security parameter n, rendering them inefficient for practical purposes. To address this concern, Lyubashevsky, Peikert, and Regev [124], [125] introduced the ring variant of LWE, known as the ring learning with errors (RLWE) problem, which only induces a linear overhead. This variant was originally formulated in the so-called dual form. However, the primal version is preferable in practice. Since the dual and primal formulations are known to be equivalent [164], we restrict ourselves to the primal version, which we refer to as RLWE. We closely follow the definition in [78]. Ring learning with errors (RLWE) problem. Let n ≥ 1 and q = q(n) ≥ 2 be an integer modulus. Let K be a number field of degree n and R = OK its ring of integers. Set Rq = OK /qOK and let χ be the discrete Gaussian distribution obtained by sampling over the ideal lattice L = Σ(R) (see Section 1.3). Let s ∈ Rq be sampled uniformly at random. RLWE distribution (As,χ ): The RLWE distribution As,χ in Rq × Rq is defined by uniformly sampling a ← Rq , e ← χ, and returning (a, b) ∈ Rq × Rq where b = as + e mod q. Search RLWE (RLWEq,χ ): For an arbitrary number of independent samples (ai , bi ), drawn from the RLWE distribution As,χ , the RLWEq,χ problem asks to recover the 1The function f (n) = O(g(n)) if there exist constants c > 0 and n such that f (n) ≤ c g(n) 0 for all n ≥ n0 . We denote Õ(f (n)) = O(f (n)poly log(n)).

20

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

secret s. Decision RLWE (D-RLWEq,χ ): Given an arbitrary number of independent samples (ai , bi ), the D-RLWEq,χ asks to determine with non-negligible advantage whether it came from the RLWE distribution As,χ or a uniform distribution. The following result guarantees the hardness of this problem. Theorem 2.2 ([124]). Let K = Q(ζm ) be the mth cyclotomic number field with degree n = φ(m) and R = OK be its ring of integers. Let α = α(n) and√ let q = q(n) ≥ 2, q ≡ 1 (mod m) be a poly(n)-bounded prime such that αq > ω( log n)2. √ Then there is a polynomial time reduction from Õ( n/α)-approximate SIVP (or SVP) on ideal lattices in K to the problem of solving D-RLWEq,χ The assumption that K is a cyclotomic field is only needed in the reduction from RLWEq,χ to D-RLWEq,χ . This reduction has been extended to any Galois extension [78]. Unlike LWEbased schemes, cryptographic protocols based on RLWE have linear overhead in the degree of the number field due to the added structure [125]. However, this added structure may introduce weaknesses that are not present in plain LWE [80]. One way to improve the security is by increasing the field extension degree, thereby also increasing the degree of the involved polynomials. This has an obvious adverse effect on the computational complexity. A better alternative is by another structured LWE variant, the general or module LWE framework of [43], later formalized as MLWE with a worst-case hardness reduction by Langlois and Stehlé [117]. We will closely follow [42, 117]. Essentially, in a sample (a, b) we now consider a to be a vector of length d instead of a single ring element or polynomial (d = 1), resulting in a module structure over a ring. This enables increasing the security level by increasing the module rank d, while keeping the underlying field extension degree and ring intact. Moreover, instead of a single distribution, we will now need a family of distributions to match the varying d. Module learning with errors (MLWE) problem. Let K be a number field of degree n, R = OK , Ψ a family of distributions on KR and the torus T = KR /R. For q, d positive integers with q ≥ 2 and d ≥ 1, let s ∈ Rqd be the secret and ψ ∈ Ψ. Let N = nd denote the dimension of the corresponding module lattice. We define the primal version of the problem as presented in [42]. Module learning with errors distribution. The MLWE distribution AM s,ψ is obtained d d by sampling a ← U (Rq ), e ← ψ and returning (a, b) ∈ Rq ×T where b = q −1 ⟨a, s⟩+ e (mod R). Search MLWE: Given arbitrary many samples from AM s,ψ , the search MLWE problem, MLWEq,Ψ , asks to recover s. Decision MLWE: Let Υ be a distribution on a family of distributions on KR . The decision MLWE, D-MLWEn,d,q,Υ , is to distinguish with non-negligible advantage between arbitrary many independent samples from AM s,ψ and the same number of independent samples from U(Rqd × T). The MLWE problem was originally motivated by the goal of building a fully homomorphic scheme without bootstrapping. Langlois et al. in [117] later proved that MLWE is as hard as solving approximate SIVP over module lattices in the 2The function ω(f (n)) grows asymptotically faster than f (n).

STRUCTURED LATTICES

21

worst case. We refer to their paper for a thorough discussion on the security of MLWE. Theorem 2.3. Let ε(N ) = N −ω(1) , α ∈ (0, 1), and q ≥ 2 of known factorization such that p √ αq > 2 d · ω( log n). There is a quantum reduction from solving GIVPηγ,ε over module lattice in polynomial time (in the worst case, with high probability) to solving MLWEq,Ψ≤α in polynomial time with non-negligible advantage, where √ 8N d · ω( log n) γ= . α Assume that q is prime, q ≤ poly(N ), and that q ≡ 1 (mod m) where m is the conductor of a cyclotomic field. Then there exists a polynomial-time reduction from MLWEq,Ψ≤α to D-MLWEq,Υα . As mentioned earlier, the module learning with errors is a generalization of the previous variants of LWE. More precisely, setting n = d = 1 corresponds to the basic LWE, while d = 1, n > 1 yields RLWE. Although this is more efficient than standard LWE, in practice, concrete polynomial rings are often preferred for their practical advantages and simplicity. This leads us to the polynomial learning with errors (PLWE) problem, described in the following section. Polynomial learning with errors (PLWE) problem. Let n ≥ 1 and q = q(n) ≥ 2. Set R(f ) = Z[x]/(f (x)) to be the polynomial ring and Rq (f ) = R(f )/qR(f ) and χ be a discrete Gaussian over ρf (R(f )) (see Section 1.3). Let s ∈ Rq be sampled uniformly at random. PLWE distribution (Bf,s,χ ): The PLWE distribution Bf,s,χ in Rq (f ) × Rq (f ) is obtained by uniformly sampling a ← Rq (f ), e ← χ, and returning (a, b) ∈ Rq (f ) × Rq (f ) where b = as + e (mod q). PLWE (Search PLWEf,q,χ ): For an arbitrary number of independent samples (ai , bi ), drawn from the PLWE distribution Bf,s,χ , the PLWEf,q,χ search problem asks to find the secret s. Decision PLWE (D-PLWEf,q,χ ): Given an arbitrary number of independent samples (ai , bi ), the D-PLWEf,q,χ asks to determine whether it was drawn from the PLWE distribution Bf,s,χ or a uniform distribution. Unlike the RLWE problem, which admits an worst-case-to-average-case reduction, the PLWE problem has such reductions only for powers of two cyclotomic fields. A natural step to extend this reduction to a broader class of fields will be to study the equivalence between RLWE and PLWE. This allows us to enjoy both efficiency and security advantages. In the following section, we define the equivalence between RLWE and PLWE and survey known results on this topic. 2.4. Equivalence between RLWE and PLWE. The RLWE and PLWE problems are said to be equivalent if there exists an algorithm that transforms a RLWE sample into a PLWE sample and vice versa in polynomial time, incurring a noise increase that is polynomial in the degree of the number field. This sample transformation is performed using the following map. Vf : Z[x]/(f (x)) → σ1 (OK ) × · · · × σn (OK )

22

(11)

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

 1 n−1 1 X  ai xi 7→  .  ..

θ1 θ2 .. .

... ... .. .

  a0 θ1n−1   θ2n−1    a1  ..   ..  .  . 

1

θn

... {z

θnn−1

i=0

|

Vf

an−1 }

This transformation incurs some noise distortion, which is quantified by the condition number of Vf [164], defined by Cond(Vf ) = ∥Vf ∥∥Vf−1 ∥, where q ∥Vf ∥ = Tr(Vf Vf∗ ). This reduces the question of equivalence to analyzing the condition number of the transformation matrix Vf . This topic has been widely studied and we highlight some known results. Ducas and Durmus in [76] showed that equivalence holds for power-of-two cyclotomic fields where the change-of-basis matrix is a scaled isometry. In [164], equivalence was established for a certain ad hoc class of fields. Further results were obtained for cyclotomic fields whose conductors are divisible by two distinct prime factors [27], [168]. This result was later extended in [30] to cyclotomic fields whose conductors are divisible by six distinct prime factors. Later in [72] it was shown that equivalence fails for general cyclotomic fields. Other classes of fields have also been studied, such as the maximal real subfields of cyclotomic fields [3, 32] and the cyclo-multiquadratic fields (the composition of cyclotomic and multiquadratic fields) [30]. The security of the above structured lattice problems is based on our choice of f , the modulus polynomial, and the defining polynomial of the number field. A wrong choice of f could make the scheme vulnerable to attacks. We review some of the attacks that exploit these additional structures. For a more thorough survey we refer to [147]. 2.5. Cryptanalysis of RLWE/PLWE. In this section, Rq = Fq [x]/(f (x)) where f (x) is a monic irreducible polynomial in Z[x] and q prime. An attack on PLWE that exploits the algebraic structure of Rq , was first introduced by Eisenträger, Hallgren, and Lauter in [78]. Let α be a root of f (x) i.e f (α) = 0 mod q. They showed that when α = 1, an attacker, given arbitrary PLWE samples (ai , bi ) ∈ Rq2 , can efficiently distinguish them from uniform samples. In the same work, they extended this idea to the case where α has a small multiplicative order r mod q. Later, Elias, Lauter, Özman, and Stange [80], further constructed a distinguishing attack on PLWE when α has a small residue. Building on these root-based attacks, the authors of [28] constructed a similar attack that makes use of the number-theoretic properties of the trace function without requiring the order of the root to be small. Specifically, they show that if f (x) has a quadratic factor whose root has trace zero, then the adversary can identify whether the given samples are uniform or PLWE. This idea was subsequently generalized in [29], which extended the result from quadratic factors to factors of higher degree: it showed that if f (x) contains a factor of the form xn + ρ, where ρ is an element such that the root has trace zero, then a similar distinguishing attack applies. Furthermore, using a similar strategy of exploiting roots with trace

STRUCTURED LATTICES

23

zero, another attack was designed in [17] on PLWE over a subring Rq,0 × Rq of a cyclotomic field, where the integer modulus q does not split completely. Another attack proposed in [78] and addressed in [13] is the smearing attack. This distinguishing attack is performed by analyzing the behavior of the error to distinguish them from uniform samples. The natural question that arises is: can some of these attacks on PLWE be extended to RLWE? This question has been answered in the affirmative for some. A natural step in this direction will be to transform RLWE samples into PLWE (see Equation (11) ) and then apply one of the listed attacks to the PLWE samples. In [80], the authors demonstrate how the attack described in [78] can be applied to the RLWE decision problem, given that some conditions are satisfied. This result was later extended in [47] to the RLWE search problem, achieving 100% success probability with fewer samples. It is worth mentioning that these known attacks do not threaten the NISTstandardized schemes. However, these attacks confirm why we should stick to the parameters of the standardized schemes. They also provide a list of parameters to watch for when constructing new schemes or improving standardized ones. 2.6. Further applications of lattice-based cryptography. One interesting property of lattice-based cryptographic (LBC) schemes is their flexibility, which enables them to be applied across a wide range of applications. We briefly describe two notable examples below: homomorphic encryption and private information retrieval (PIR). We conclude this section by highlighting the new standardized schemes based on lattices. Homomorphic encryption. This is a form of encryption that allows computations to be done on encrypted data without decrypting it. The decrypted result matches the result of the same operation performed on the original plain data. There are three main types: partially homomorphic encryption (PHE), which allows for a single type of operation (either addition or multiplication) on encrypted data; somewhat homomorphic encryption (SHE), which allows for a limited, but greater than one, number of operations on encrypted data; and fully homomorphic encryption (FHE), which allows for an unlimited number of either of the two operations. Homomorphic encryption plays an important role in, e.g., cloud computing, secure voting, and medical data analysis. The problem of constructing a fully homomorphic encryption scheme was first introduced by Rivest, Adleman, and Dertouzos in 1978 [162]. For more than three decades, the existence of a solution remained an open problem. During this period, partial homomorphic schemes like RSA [163] and ElGamal [79] enabled unlimited modular multiplications, while others allowed for unlimited modular arithmetic [154], [26]. Gentry, in [100], [101] gave the first construction of an FHE scheme based on lattice-based cryptography. This FHE scheme supports both addition and multiplication operations on ciphertext, for an arbitrary number of computations. To achieve this, he starts from a somewhat homomorphic encryption scheme, which has limitations due to the noise growth when we add or multiply encrypted data. This noise growth may lead to decryption errors if the noise becomes too high. Addressing this, he shows that in any bootstrapped scheme, this SHE scheme can be converted into an FHE scheme. The security of this scheme is partly based on

24

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

worst-case problems over ideal lattices. Furthermore, in [43], this result is extended by removing the ideal lattice condition. Over the years, other schemes based on lattice-based problems have been proposed that offer improved efficiency. One of the well known applications of homomorphic encryption is the singledatabase computationally-Private Information Retrieval (cPIR), which we introduce below. Private information retrieval (PIR) Introduced by Chor et al. in [51], PIR allows a user to retrieve an item from a storage system or cloud in possession of a database without revealing which item is retrieved. The main idea is as follows: given a system holding a database consisting of a set of elements D1 , . . . , Dm , retrieve the ith element Di without revealing i to the system owner. A naive solution will be to retrieve the entire database and discard all entries but the one of interest. However, this will be at a cost proportional to the number of data items O(m), and therefore not practical when the database is large. It has been shown that this is the only way to guarantee information-theoretic privacy if we store the database on one server. However, using multi-server schemes we can do much better. Here, the user sends masked queries to different non-colluding servers, ensuring that no subset of servers of size below a design threshold learns the original query. The methods utilized in this approach typically draw from coding theory, and various extensions to the problem have been made. The literature is vast and as our core topic is lattices, we refrain from expanding our reference list by these coding-theoretic works and simply refer to the brief tutorial [77] and the references therein. Another way is to only use a single server but instead rely on computational security and hence cryptographic techniques to hide the query from the server, originally introduced in [115] where a scheme based on quadratic residues was constructed. This method is generally known as single-server computationally private information retrieval (cPIR). The drawback of the original cPIR scheme is that it is computationally more expensive than the naive method of downloading everything and therefore not practical [115]. This aspect has later been improved by several works, notably in [1] where, using LBC, much more efficient cPIR schemes based on LWE and RLWE were constructed. NIST standardized schemes. Due to the fast progress in the field of quantum computing, the National Institute of Standards and Technology (NIST) launched a PQC standardization process (competition) in 2016 aimed at identifying quantumsafe cryptographic protocols. A call for proposals [139] was made in which researchers were invited to submit candidates which were evaluated at several rounds based criteria that included security, efficiency, and practical implementation. A total of 82 algorithms were submitted, of which 69 were accepted into the first round[140], 26 advanced to the second round [141], and 15 selected as third round finalist [142]. Of these candidates, 4 was chosen for standardization [143] and the rest moved to the fourth round [144] and are currently undergoing further analysis. Among the four schemes chosen for standardization, CRYSTALS-Kyber (MLKEM), CRYSTALS-Dilithium (ML-DSA), and Falcon are based on hard latticeproblems. In particular, Kyber and Dilithium are based on hard problems over

STRUCTURED LATTICES

25

module lattices [11] such as MLWE. It is worth noting that the above listed attacks on RLWE/PLWE do not threaten any of these standardized schemes.

26

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

3. Lattice codes for wireless security In the previous section, we have seen how lattices can be applied to provide computational security due to several hard lattice problems, such as the shortest vector problem. In addition to computational security where we assume that the adversary has bounded computational resources, lattices can also be used to provide physical layer security (PLS), which for its part relies on the concept of informationtheoretic security. Here, the adversary can have unlimited computational power, since the security is based on (full or partial) lack of relevant information. While traditional cryptographic methods like AES (the Advanced Encryption Standard) or RSA operate at higher protocol layers, PLS provides a complementary layer of defense. As the 6th generation (6G) communication networks move toward high-mobility, low-latency, and decentralized networks (e.g., Internet of Vehicles), traditional key exchange mechanisms can become bottlenecks. Lattice-based PLS offers a way to establish security guarantees by leveraging the intrinsic physical properties of the wireless medium, making it a vital research area for future secure communication systems against both classical and potential quantum threats. We refer to the recent white paper [53] for a general introduction to the utility of physical layer security. Let us start by defining relevant notions in information theory. 3.1. Basic notions in information theory and related security paradigms. For a general reference for information theory and information-theoretic security, we refer to [60, 31]. Let X and Y be two discrete random variables taking values from respective sets X and Y. The entropy of X is X H(X) = − p(x) log p(x), x∈X

where p(x) is the probability of x. The entropy of a continuous random variable is defined analogously. Let us denote the conditional entropy of X given Y by H(X|Y ). The mutual information can then be defined as I(X; Y ) = H(X) − H(X|Y ). Assume now that we are sending a message X and the adversary is gaining access to Y . The secrecy can be measured by how much information can be obtained based on Y , quantized by information leakage I(X; Y ). The mutual information is zero, yielding perfect secrecy, if and only if X and Y are independent. In cryptography, typically operating over positive characteristic and finite structures, this can be achieved by adding uniformly random noise to X, referred to as one-time pad. On a wireless (physical) channel, however, the noise is not selected by the user as in cryptography but is induced by the physical conditions of the channel and the equipment used and as such largely beyond our control. Such noise is typically real or complex Gaussian, and we cannot (non-asymptotically) obtain perfect secrecy anymore. Instead, the goal in physical layer security is to minimize information leakage while guaranteeing good decoding probability for the legitimate user. This will be our focus in the rest of this section. We refer the interested reader to [151, 24, 52, 58] and references therein for more details on lattice-based reliable and secure wireless communications.

STRUCTURED LATTICES

27

3.2. Wiretap channels and lattice coset codes. Lattice codes, defined as finite collections of lattice vectors within a bounding region, are effective tools for wireless communications. The channel model for single-input single-output (SISO) is described as y = Hx + n ∈ Rn , where x ∈ L is the message, n ∈ Rn is additive white Gaussian noise (AWGN), and H ∈ Rn×n represents random fading. For an AWGN channel, H = In , while for a Rayleigh fast fading channel, H is a diagonal matrix with independent Rayleigh distributed entries. Maximum-likelihood (ML) decoding here is equivalent to the closest vector problem in a (distorted) lattice. This may sound counter-intuitive after the previous section on lattice-based cryptography, where it was pointed out that many lattice problems, including the CVP, are computationally hard. Fortunately for us, now the security is based on information-theoretic notions, not on computational hardness. This means that, in practice, we can resort to relatively low-dimensional lattices making the CVP feasible for the legitimate receiver. However, in order to approach the theoretical perfect secrecy capacity [149], highdimensional lattices are still needed. In a channel with not too much fading and noise with respect to the signal power, measured by signal-to-noise ratio (SNR), reliability is optimized by maximizing the modulation diversity ℓ := min0̸=x∈L | {i : xi ̸= 0} | and the minimum product distance n Y |xi | dp,min (L) := inf 0̸=x∈L

i=1

for a full diversity lattice (ℓ = n) [151]. At low SNR, the minimum distance λ1 (L) dominates the decoding performance. Note that the minimum product distance coincides with the multiplicative norm defined in 1. Wyner’s coset coding, introduced by Aaron Wyner in 1975 [186, 153] for the wiretap channel 3, is a foundational technique in information-theoretic security that achieves secure communication without relying on unproven computational assumptions or shared cryptographic keys. The original core mechanism involves partitioning a standard error-correcting code into distinct, non-overlapping subsets, i.e., (cosets), where each coset corresponds to a specific secret message. To transmit a message, the sender selects the appropriate coset and deliberately introduces structured randomness by transmitting a randomly chosen codeword from the coset. This approach is useful in physical-layer security as it exploits the differences in the channel quality between the legitimate user and an eavesdropper. A legitimate receiver with a stronger channel (i.e., lower noise) can successfully decode to identify the correct coset and recover the message, while an eavesdropper on a noisier channel is overwhelmed by the errors. Due to the random codeword selection, the eavesdropper’s degraded signal lacks enough information to even determine which coset was used, mathematically ensuring that the intercepted data reveals (practically) zero information about the original message regardless of the attacker’s computing power. We refer to [126, Ch. 3] and the references therein for a nice exposition on coset codes and wiretap channels for error-correcting codes, as well as their intimate connection to (homomorphic) secret sharing. 3Here, in addition to the legitimate receiver, we have an eavesdropper who is “tapping the wire” in order to intercept secret messages. With slight abuse of language, we also call a wireless channel with an eavesdropper a wiretap channel, even though there is no wire.

28

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

In our lattice code context, instead of quotients of vector spaces we consider quotients of lattices, both of which have an analogous additive group structure. A message m is masked by a random sublattice vector r ∈ Ls ⊂ L, and x = m + r ∈ L/Ls is transmitted. Again, assuming the eavesdropper experiences relatively stronger noise, the legitimate receiver decodes reliably while the eavesdropper gains negligible information. For more details and examples, we refer to [150]. Next, let us make the “negligible information” more rigorous. 3.3. The flatness factor and connections to theta functions. The flatness factor EL (σ) bounds from above the deviation of the lattice Gaussian gσ from uniformity on the Voronoi cell V(L) (cf. variational distance, Eq. (9)): (12)

EL (σ) := max

x∈V(L)

gσ,L (x) −1 . 1/ Vol(L)

The flatness factor bounds from above both the eavesdropper’s correct decoding probability and information leakage [120, 121, 66], and minimizing it makes the channel appear “flatter” (more uniform) to the eavesdropper. The flatness factor can be related to the primal and dual theta series (via the Poisson summation formula) as follows: Vol(L)gσ,L (x) − 1 ≤ (13)

Vol(L)gσ,L (0) − 1 2 Vol(L) √ = ΘL (e−1/2σ ) − 1 ( 2πσ)n 2

=

ΘL∗ (e−2πσ ) − 1

=

EL (σ)

where σ 2 is the noise variance. A practical complication now arises. Namely, if we want to compare different lattices (of the same volume) and compare their flatness factors, how do we efficiently compute the theta function, known to be notoriously hard? In a relatively low dimension, one can use truncations and brute force point enumeration or, more efficiently, resort to the theta function approximation proposed in [19]. However, as mentioned by the authors, the approximation is not universally good and gets worse with growing dimension or if the lattice is very skewed. To make a connection to lattice-based cryptography, we point out that the flatness factor and the smoothing parameter (cf. Eq. (10)) are closely related [120]. To this end, let us slightly redefine √ the smoothing parameter up to constants by changing the variable s to σ = s/ 2π: X 2 2 2 ηδ (L) = inf{σ > 0 | e−2π σ ||λ|| ≤ δ}. 0̸=λ∈Λ∗

Then we have EL (ηδ (L)) = δ. Essentially, if we compare two lattices (of the same volume), the one with the smaller flatness factor allows for adding smaller noise while maintaining the same variational distance, helping the correct decoding/decryption of the legitimate receiver.

STRUCTURED LATTICES

29

3.4. Well-rounded lattices as theta minimizers. Well-rounded lattices were studied and constructed for the SISO wiretap channel in [103, 64]. Interestingly, it has been shown that the minimizer of the flatness factor (equivalently, the theta function) is well-rounded [66]. Furthermore, it is conjectured that the closer the lattice is to being stable, the smaller the flatness factor [156]. Since they also maximize the minimum product distance [63] and support dense packings [167, 59, 70], WR lattices are excellent candidates for secure, reliable communication. As minimizing the theta function globally is difficult, [109] focused on generic WR lattices — increasing the first minimum and decreasing the kissing number reduces the dominating term, motivating the study of dense GWR lattices for physical layer security. 3.5. Related topics and generalizations. Here, we have concentrated on the single-antenna channel model. For multi-antenna wireless communications, socalled space-time lattice codes based on cyclic division algebras and their maximal orders can be used [152, 169, 108, 182]. Lattice coset codes and related design criteria for such a multiple-input multiple-output (MIMO) wiretap channel have also been considered [137, 122]. The utility of well-rounded lattices for MIMO channels have been demonstrated in [102, 20]. Furthermore, an analogous design criterion to minimize the lattice theta series in the ℓ1 (taxicab) norm instead of the euclidean norm was proposed in [135], and related kissing number problems in [136]. The setting of point-to-point communications can be extended to relay channels, where the message is relayed by an intermediate node. Lattice coset codes also come into play here via physical layer network coding, the security of which has been considered in [181] for the so-called compute-and-forward channels. Generalized theta series was considered in [36], motivated by connections to the identification of stable lattices, the lattice isomorphism problem, and the so-called isodual secrecy gain conjecture. The secrecy gain is closely related to the flatness factor, and measures how much better the coding lattice used is with respect to “no coding”, i.e., the Zn lattice, by looking at the ratio of the respective theta functions called the secrecy function [25, 150]. Its ultimate goal is the same as that of the flatness factor minimization: to minimize the the theta function of the eavesdropper’s lattice (the reader can think of this as the “noise” lattice, which is used to confuse Eve). While the flatness factor directly bounds the eavesdroppers correct decoding probability and information leakage, hence making comparison to the integer lattice obsolete, the secrecy gain does allow the use of somewhat different type of analytical tools by looking at the maximum of the secrecy function. For more details on the secrecy gain and various conjectures related to it, we refer to [25, 150, 83, 34]. Finally, we mention that the maximization of the flatness factor has been studied in [35]. For a more general and broader introduction to many of the topics discussed in Sections 2 and 3, we refer the reader to the following PhD theses: [62, 146, 18, 126].

30

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

4. Conclusion and open problems In this survey, we have discussed the theory of structured Euclidean lattices and its applications — a very active area of current research. A great deal of research here is motivated by the original discrete optimization problems on lattices, such as packing, covering, and kissing number problems. This being said, the field of potential work here is much wider than suggested by these classical problems, both in terms of theory and applications. We mention here some additional directions for future work. Minkowski conjecture has been proved in dimensions n ≤ 10, and the related Woods’ covering conjecture has been disproved in dimensions n ≥ 24. However, it is not clear that the failure of Woods’ conjecture in higher dimensions implies the failure of Minkwoski’s conjecture. It would be interesting to understand whether Minkowski conjecture holds in some dimensions where Woods’ conjecture fails. In addition, the question of which subclasses of lattices satisfy the Woods’ conjecture either in dimensions where the question is open or for those where the general conjecture fails is intresting. Classification of perfect and eutactic lattices is known only in low dimensions. In fact, there are not even known asymptotic formulas for the number of perfect or eutactic similarity classes of lattices in growing dimensions: the upper and lower bounds known for perfect similarity classes are of different orders of magnitude as functions of the dimension. An important avenue for future research would be to obtain stronger general bounds with a view toward asymptotic formulas. Zeta-function of well-rounded sublattices in a fixed planar lattice was studied by several authors and its behavior is generally understood. However, there seem to be no analogous results in higher dimensions. Studying the analytic property of this function in higher dimensions would provide insight into the quantitative distribution properties of well-rounded sublattices and their dependence on the arithmetic structure of the ambient lattice. Algebraic constructions of well-rounded lattices have received some attention in the recent years. In particular, ideal well-rounded lattices from quadratic number fields are fairly well understood. On the other hand, there are few results for number fields of higher degree. Also, constructions of well-rounded lattices from more general free Z-modules in number fields deserve more attention as they can often display interesting properties, such as large automorphism groups. Further investigation of tame lattices is also an interesting related project. Further constructions of lattices with special geometric properties, such as well-roundedness, stability, eutaxy, and perfection coming from function fields, graph theory, theory of tight frames and other areas of mathematics are of great interest. Connections between lattices and spherical designs is a topic of research that also naturally falls here. Continuing investigations in these directions is certainly worthwhile. Studying the local and global extrema of theta functions and finding close-to-optimal constructions is a very natural question in mathematics and, as discussed in this survey, also motivated by applications both in lattice-based cryptography and physical layer security via the variational distance. The question of finding the precise minimum and the lattice(s) achieving it is generally very hard,

STRUCTURED LATTICES

31

and the answer is known only in a few small dimensions. Hence, any new insight toward this goal will be valuable. The equivalence of variants of the LWE problem such as RLWE and PLWE has been studied in the literature for some classes of number fields. These equivalence results enable the construction of cryptographic schemes with improved efficiency while maintaining strong security guarantees. Extending these results to broader classes of number fields would provide more options for designing secure and efficient protocols. This will be particularly important if the currently standardized lattice-based schemes (e.g. Kyber) would render themselves vulnerable to fatal attacks. Analyzing the hardness of approximate versions of worst-case hard problems such as SVP and SIVP for varying approximation factors remains an important research direction. In particular, understanding the hardness of approximate SVP or SIVP over structured lattices may either strengthen the security guarantees of the newly standardized schemes or reveal potential weaknesses in their underlying hardness assumptions. Cryptanalysis of variants of LWE has also been extensively studied in the literature. This line of research helps maintain robust security by identifying vulnerable instances before they are exploited by adversaries. Exploring the algebraic structures of the underlying schemes may reveal additional weak instances of these problems. Constructions of explicit lattice coset codes for wireless communications under varying channel conditions and dimensions. In particular, it would be interesting to see which further lattice properties (in addition to the density, flatness factor, and product distance) may contribute toward high performance. Moreover, constructing WR lattices from cyclic division algebras and studying their properties in terms of multi-antenna communications would be useful as existing constructions thus far are scarce, especially beyond quaternion algebras. Acknowledgments We would like to thank Dr. Ragnar Freij-Hollanti and Prof. Russell Lai for useful discussions and helpful comments on the original manuscript.

32

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

References [1] C. Aguilar Melchor, J. Barrier, L. Fousse, and M.-O. Killijian. XPIR : Private information retrieval for everyone. Proceedings on Privacy Enhancing Technologies, pages 155–174, Apr 2016. [2] D. Aharonov and O. Regev. Lattice problems in NP ∩ coNP. J. ACM, 52(5):749–765, Sept. 2005. [3] J. Ahola, I. Blanco-Chacón, W. Bolaños, A. Haavikko, C. Hollanti, and R. M. SánchezLedesma. Fast multiplication and the PLWE–RLWE equivalence for an infinite family of maximal real subfields of cyclotomic fields. Designs, Codes and Cryptography, 93:2947–2969, 2025. [4] M. Ajtai. Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 99–108, 1996. [5] M. Ajtai. The shortest vector problem in l2 is np-hard for randomized reductions. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 10–19, 1998. [6] C. Alves, J. E. Strapasson, and R. R. de Araujo. On well-rounded lattices and lower bounds for the minimum norm of ideal lattices. Arch. Math. (Basel), 124(2):121–130, 2025. [7] Y. André. On nef and semistable hermitian lattices, and their behaviour under tensor product. Tohoku Math. J. (2), 63(4):629–649, 2011. [8] S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317–331, 1997. [9] A. Ash and M. McConnell. Cohomology at infinity and the well-rounded retract for general linear groups. Duke Math. J., 90(3):549–576, 1997. [10] L. Ateş and H. Stichtenoth. A note on short vectors in lattices from function fields. Finite Fields Appl., 39:264–271, 2016. [11] R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, D. Stehlé, et al. Crystals-kyber algorithm specifications and supporting documentation. NIST PQC Round, 2(4):1–43, 2019. [12] M. Baake, R. Scharlau, and P. Zeiner. Well-rounded sublattices of planar lattices. Acta Arith, 166(4):301–334, 2014. [13] L. Babinkostova, A. Chin, A. Kirtland, V. Nazarchuk, and E. Plotnick. The polynomial learning with errors problem and the smearing condition. Journal of Mathematical Cryptology, 16(1):215–232, 2022. [14] R. Bacher. Constructions of some perfect integral lattices with minimum 4. J. Théor. Nombres Bordeaux, 27(3):655–687, 2015. [15] R. Bacher. On the number of perfect lattices. J. Théor. Nombres Bordeaux, 30(3):917–945, 2018. [16] R. Baraniuk, S. Dash, and R. Neelamani. On nearly orthogonal lattice bases. SIAM J. Discrete Math., 21(1):199–219, 2007. [17] B. Barbero-Lucas, I. Blanco-Chacón, R. Durán-Dı́az, R. Y. N. Nchiwo, and R. M. SánchezLedesma. Cryptanalysis of PLWE based on zero-trace quadratic roots. Accepted for publication in Journal of Mathematical Cryptology, 2026. [18] A. Barreal. Lattice Codes for Physical Layer Communications. PhD thesis, Aalto University publication series Doctoral Theses, 71/2017, 2017. [19] A. Barreal, M. T. Damir, R. Freij-Hollanti, and C. Hollanti. An approximation of theta functions with applications to communications. SIAM Journal on Applied Algebra and Geometry, 4(4):471–501, 2020. [20] A. Barreal, A. Karrila, D. A. Karpuk, and C. Hollanti. Information bounds and flatness factor approximation for fading wiretap MIMO channels. In IEEE International Telecommunications Networks and Applications Conference, pages 277–282, 2016. [21] S. C. Batson. The linear transformation that relates the canonical and coefficient embeddings of ideals in cyclotomic integer rings. Int. J. Number Theory, 13(9):2277–2297, 2017. [22] E. Bayer-Fluckiger. Ideal lattices. In A panorama of number theory or the view from Baker’s garden (Zürich, 1999), pages 168–184. Cambridge Univ. Press, Cambridge, 2002. [23] E. Bayer-Fluckiger and G. Nebe. On the euclidean minimum of some real number fields. J. Théor. Nombres Bordeaux, 17(2):437–454, 2005.

STRUCTURED LATTICES

33

[24] J.-C. Belfiore and F. Oggier. Lattice code design for the Rayleigh fading wiretap channel. In 2011 IEEE International Conference on Communications Workshops (ICC), pages 1–5, 2011. [25] J.-C. Belfiore and F. E. Oggier. Secrecy gain: A wiretap lattice code design. 2010 International Symposium On Information Theory and Its Applications, pages 174–178, 2010. [26] J. Benaloh. Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas in Cryptography (SAC), 1994. [27] I. Blanco-Chacón. On the RLWE/PLWE equivalence for cyclotomic number fields. Applicable Algebra in Engineering, Communication and Computing, 33(1):53–71, 2022. [28] I. Blanco-Chacón, B. Barbero-Lucas, R. Durán-Dı́az, and R. Y. Njah Nchiwo. Trace-based cryptanalysis of cyclotomic Rq,0 × Rq -PLWE for the non-split case. Communications in Mathematics, 31, 2023. [29] I. Blanco Chacón, R. Durán Dı́az, and R. Martı́n Sánchez-Ledesma. A generalized approach to root-based attacks against PLWE. Cryptography and Communications, pages 1–45, 2025. [30] I. Blanco-Chacón, A. Pedrouzo-Ulloa, R. Y. Njah Nchiwo, and B. Barbero-Lucas. Fast polynomial arithmetic in homomorphic encryption with cyclo-multiquadratic fields. Cryptography and Communications, pages 1–35, 2025. [31] M. Bloch, O. Günlü, A. Yener, F. Oggier, H. V. Poor, L. Sankar, and R. F. Schaefer. An overview of information-theoretic security and privacy: Metrics, limits and applications. IEEE Journal on Selected Areas in Information Theory, 2(1):5–22, 2021. [32] W. Bolaños, A. Haavikko, and R. M. Sánchez-Ledesma. A fast multiplication algorithm and RLWE-PLWE equivalence for the maximal real subfield of the 2r ps -th cyclotomic field. Advances in Mathematics of Communications, 21:212–238, 2026. [33] W. Bolaños and G. Mantilla-Soler. The trace form over cyclic number fields. Canad. J. Math., pages 1–23, 2020. [34] M. Bollauf, H.-Y. Lin, and O. Ytrehus. Secrecy gain of formally unimodular lattices from codes over the integers modulo 4. IEEE Transactions on Information Theory, 2024. [35] M. F. Bollauf and H.-Y. Lin. On the maximum flatness factor over unimodular lattices. arXiv preprint arXiv:2403.16932, 2024. [36] M. F. Bollauf and H.-Y. Lin. Generalized theta series of a lattice. In 2025 IEEE Information Theory Workshop (ITW), pages 827–832, 2025. [37] A. Bondarenko, D. Radchenko, and M. Viazovska. Optimal asymptotic bounds for spherical designs. Ann. of Math. (2), 178(2):443–452, 2013. [38] A. Böttcher, S. Eisenbarth, L. Fukshansky, S. R. Garcia, and H. Maharaj. Spherical 2-designs and lattices from abelian groups. Discrete Comput. Geom., 61(1):123–135, 2019. [39] A. Böttcher, L. Fukshansky, S. R. Garcia, and H. Maharaj. On lattices generated by finite abelian groups. SIAM J. Discrete Math., 29(1):382–404, 2015. [40] A. Böttcher, L. Fukshansky, S. R. Garcia, and H. Maharaj. Lattices from hermitian function fields. J. Algebra, 447:560–579, 2016. [41] A. Böttcher, L. Fukshansky, S. R. Garcia, H. Maharaj, and D. Needell. Lattices from equiangular tight frames. Linear Algebra Appl., 510:395–420, 2016. [42] K. Boudgoust, C. Jeudy, A. Roux-Langlois, and W. Wen. On the hardness of module learning with errors with short distributions. Journal of Cryptology, 36(1), 2023. [43] Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014. [44] Z. Brakerski and V. Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Annual cryptology conference, pages 505–524. Springer, 2011. [45] B. Casselman. Stability of lattices and the partition of arithmetic quotients. Asian J. Math., 8:607–637, 2004. [46] J. W. S. Cassels. On a problem of Rankin about the Epstein zeta-function. Proc. Glasgow Math. Assoc., 4:73–80 (1959), 1959. [47] W. Castryck, I. Iliashenko, and F. Vercauteren. Provably weak instances of ring-LWE revisited. In Annual international conference on the theory and applications of cryptographic techniques, pages 147–167. Springer, 2016. [48] H. Chen and L. Xu. Counterexamples to the Woods conjecture in dimensions d ≥ 24. J. Théor. Nombres Bordeaux, 31(3):723–726, 2019.

34

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

[49] Y. X. Chew and F. Oggier. Well-rounded ideal lattices from totally definite quaternion algebras, 2025. [50] D. P. Chi, J. W. Choi, J. San Kim, and T. Kim. Lattice based cryptography for beginners. Cryptology ePrint Archive, 2015. [51] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. J. ACM, 45(6):965–981, nov 1998. [52] A. Chorti, C. Hollanti, J. Belfiore, and H. Poor. Physical layer security: A paradigm shift in data confidentiality, volume 358 of Springer Lecture Notes in Electrical Engineering, pages 1–15. Springer, 2016. [53] A. Chorti, S. Tomasin, M. Baldi, S. Delbruel, and G. Karabulut Kurt (editors). 2025 working group white paper, security and privacy. https://futurenetworks.ieee.org/roadmap/ physical-layer-security-focus-group, 2025. IEEE Focus Group on Physical Layer Security, International Networks Generations Roadmap (INGR). [54] H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, and M. S. Viazovska. The sphere packing problem in dimension 24. Ann. of Math. (2), 185(3):1017–1033, 2017. [55] P. E. Conner and R. Perlis. A Survey of Trace Forms of Algebraic Number Fields. World Scientific, 1984. [56] J. H. Conway and N. J. A. Sloane. A lattice without a basis of minimal vectors. Mathematika, 42(1):175–177, 1995. [57] J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices, and Groups. Springer-Verlag, Third edition, 1999. [58] S. I. Costa, F. Oggier, A. Campello, J.-C. Belfiore, and E. Viterbo. Lattices Applied to Coding for Reliable and Secure Communications. Springer, 2017. [59] R. Coulangeon. Spherical designs and zeta functions of lattices. Int. Math. Res. Not., pages Art. ID 49620, 16, 2006. [60] T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, Ltd, 2005. [61] D.-T. Dam, T.-H. Tran, V.-P. Hoang, C.-K. Pham, and T.-T. Hoang. A survey of postquantum cryptography: Start of a new race. Cryptography, 7(3):40, 2023. [62] M. T. Damir. Well-Rounded Lattices and Applications to Physical Layer Security. PhD thesis, Aalto University publication series Doctoral Theses, 160/2020, 2020. [63] M. T. Damir and L. Fukshansky. Canonical basis twists of ideal lattices from real quadratic number fields. Houston J. Math., 45(4):999–1019, 2019. [64] M. T. Damir, O. Gnilke, L. Amorós, and C. Hollanti. Analysis of some well-rounded lattices in wiretap channels. In IEEE Int. Workshop on Signal Process. Adv. in Wireless Commun., pages 1–5, 2018. [65] M. T. Damir and D. Karpuk. Well-rounded twists of ideal lattices from real quadratic fields. J. Number Theory, 196:168–196, 2019. [66] M. T. Damir, A. Karrila, L. Amoros, O. W. Gnilke, D. Karpuk, and C. Hollanti. Wellrounded lattices: towards optimal coset codes for Gaussian and fading wiretap channels. IEEE Trans. Inform. Theory, 67(6):3645–3663, 2021. part 2. [67] M. T. Damir and G. Mantilla-Soler. Bases of minimal vectors in tame lattices. Acta Arith, 205:265–285, 2022. [68] R. R. de Araujo and S. I. R. Costa. Well-rounded algebraic lattices in odd prime dimension. Arch. Math. (Basel), 112(2):139–148, 2019. [69] R. R. de Araujo, A. de Andrade, T. d. Nóbrega Neto, and J. Bastos. Constructions of wellrounded algebraic lattices over odd prime degree cyclic number fields. Commun. Math., 33(1), 2025. Paper No. 6. 18 pp. [70] B. N. Delone and S. S. Ryshkov. A contribution to the theory of the extrema of a multidimensional ζ-function. Doklady Akademii Nauk, 173(5):991–994, 1967. [71] P. Delsarte, J. M. Goethals, and J. J. Seidel. Spherical codes and designs. Geometriae Dedicata, 6(3):363–388, 1977. [72] A. J. Di Scala, C. Sanna, and E. Signorini. RLWE and PLWE over cyclotomic fields are not equivalent. Applicable Algebra in Engineering, Communication and Computing, 35(3):351– 358, 2024. [73] P. H. Diananda. Notes on two lemmas concerning the Epstein zeta-function. Proc. Glasgow Math. Assoc., 6:202–204 (1964), 1964.

STRUCTURED LATTICES

35

[74] W. Diffie and M. E. Hellman. New Directions in Cryptography, pages 365–390. Association for Computing Machinery, New York, NY, USA, 1 edition, 2022. [75] I. Dinur, G. Kindler, and S. Safra. Approximating CVP to within almost-polynomial factors is NP-hard. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 99–109. IEEE, 1998. [76] L. Ducas and A. Durmus. Ring-LWE in polynomial rings. In International Workshop on Public Key Cryptography, pages 34–51. Springer, 2012. [77] R. G. L. D’Oliveira and S. E. Rouayheb. A guided walk through coded private information retrieval. IEEE BITS the Information Theory Magazine, 3(4):51–66, 2023. [78] K. Eisenträger, S. Hallgren, and K. Lauter. Weak instances of PLWE. In International Conference on Selected Areas in Cryptography, pages 183–194. Springer, 2014. [79] T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Advances in Cryptology – CRYPTO 1984, pages 10–18, 1985. [80] Y. Elias, K. E. Lauter, E. Ozman, and K. E. Stange. Provably weak instances of Ring-LWE. In Annual Cryptology Conference, pages 63–92. Springer, 2015. [81] V. Ennola. A lemma about the Epstein zeta-function. Proc. Glasgow Math. Assoc., 6:198– 201 (1964), 1964. [82] V. Ennola. On a problem about the Epstein zeta-function. Proc. Cambridge Philos. Soc., 60:855–875, 1964. [83] A.-M. Ernvall-Hytönen and B. A. Sethuraman. Counterexample to the generalized BelfioreSolé secrecy function conjecture for l-modular lattices. IEEE Transactions on Information Theory, 62(8):4514–4522, 2016. [84] L. Fukshansky. Well-rounded zeta-function of planar arithmetic lattices. Proc. Amer. Math. Soc., 142(2):369–380, 2014. [85] L. Fukshansky. Stability of ideal lattices from quadratic number fields. Ramanujan J., 37(2):243–256, 2015. [86] L. Fukshansky, P. Guerzhoy, and S. Kühnlein. On sparse geometry of numbers. Res. Math. Sci., 8(1), 2021. Paper No. 2. 18 pp. [87] L. Fukshansky, P. Guerzhoy, and F. Luca. On arithmetic lattices in the plane. Proc. Amer. Math. Soc., 145(4):1453–1465, 2017. [88] L. Fukshansky, P. Guerzhoy, and T. Nielsen. Deep hole lattices and isogenies of elliptic curves. Res. Number Theory, 10(2), 2024. Paper No. 33. 12 pp. [89] L. Fukshansky, G. Henshaw, P. Liao, M. Prince, X. Sun, and S. Whitehead. On well-rounded ideal lattices ii. Int. J. Number Theory, 9(1):139–154, 2013. [90] L. Fukshansky and C. Hollanti. Euclidean lattices: theory and applications. Commun. Math., 31(2):251–263, 2023. [91] L. Fukshansky and E. Knight. On lattices generated by algebraic conjugates. in preparation. [92] L. Fukshansky and D. Kogan. On the geometry of nearly orthogonal lattices. Linear Algebra Appl., 629:112–137, 2021. [93] L. Fukshansky and D. Kogan. Cyclic and well-rounded lattices. Mosc. J. Comb. Number Theory, 11(1):79–96, 2022. [94] L. Fukshansky and H. Maharaj. Lattices from elliptic curves over finite fields. Finite Fields Appl., 28:67–78, 2014. [95] L. Fukshansky, D. Needell, J. Park, and Y. Xin. Lattices from tight frames and vertex transitive graphs. Electron. J. Combin., 26(3), 2019. Paper No. 3.49. 30pp. [96] L. Fukshansky and K. Petersen. On well-rounded ideal lattices. Int. J. Number Theory, 8(1):189–206, 2012. [97] L. Fukshansky and S. Robins. Frobenius problem and the covering radius of a lattice. Discrete Comput. Geom., 37(3):471–483, 2007. [98] L. Fukshansky and X. Sun. On the geometry of cyclic lattices. Discrete Comput. Geom., 52(2):240–259, 2014. [99] L. Fukshansky and X. Sun. Erratum to: On the geometry of cyclic lattices. Discrete Comput. Geom., 53(4):971–972, 2015. [100] C. Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University, 2009. [101] C. Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the fortyfirst annual ACM symposium on Theory of computing, pages 169–178, 2009.

36

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

[102] O. W. Gnilke, A. Barreal, A. Karrila, H. T. N. Tran, D. A. Karpuk, and C. Hollanti. Wellrounded lattices for coset coding in MIMO wiretap channels. In Proc. IEEE International Telecommunication Networks and Applications Conference (ITNAC), pages 289–294, 2016. [103] O. W. Gnilke, H. T. N. Tran, A. Karrila, and C. Hollanti. Well-rounded lattices for reliability and security in Rayleigh fading SISO channels. In Proc. IEEE Information Theory Workshop, pages 359–363, 2016. [104] O. Goldreich and S. Goldwasser. On the limits of non-approximability of lattice problems. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, page 1–9, New York, NY, USA, 1998. Association for Computing Machinery. [105] P. M. Gruber. Convex and Discrete Geometry. North-Holland, Publishing Co, 1987. [106] P. M. Gruber and C. G. Lekkerkerker. Geometry of Numbers. Grundlehren der mathematischen Wissenschaften. 336. Springer, Berlin, 2007. [107] T. Hales and S. Ferguson. The Kepler conjecture. The Hales-Ferguson proof. Including papers reprinted from Discrete Comput. Geom. 36 (2006), no. 1. Edited by Jeffrey C. Lagarias. Springer, New York, 2011. [108] C. Hollanti, J. Lahtonen, and H.-f. Lu. Maximal orders in the design of dense space-time lattice codes. IEEE Transactions on Information Theory, 54(10):4493–4510, 2008. [109] C. Hollanti, G. Mantilla-Soler, and N. Miller. Dense generic well-rounded lattices. SIAM J. Appl. Algebra Geom., 9(1):154–185, 2025. [110] L. Ji. Well-rounded equivariant deformation retracts of teichmüller spaces. Enseign. Math., 60(1-2):109–129, 2014. [111] L. Kathuria and M. Raka. On conjectures of Minkowski and Woods for n=10. In Proc. Indian Acad. Sci. Math. Sci., Paper No. 45 , 2022, 2022. 132(2). 27 pp. [112] Y. Kim. On semistability of perfect lattices. Alabama Journal of Mathematics, 39, 2015. [113] B. Klartag. Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid. arXiv:2504.05042, 2025. [114] S. Kühnlein. Well-rounded sublattices. Int. J. Number Theory, 8(5):1133–1144, 2012. [115] E. Kushilevitz and R. Ostrovsky. Replication is not needed: single database, computationally-private information retrieval. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 364–373, 1997. [116] F. Ladisch. Lattices of finite abelian groups. Discrete Comput. Geom., 65(3):938–951, 2021. [117] A. Langlois and D. Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3):565–599, 2015. [118] N. H. Le, D. T. Tran, and H. T. N. Tran. Well-rounded ideal lattices of cyclic cubic and quartic fields. Commun. Math., 31(2):209–250, 2023. [119] M. Levin, U. Shapira, and B. Weiss. Closed orbits for the diagonal group and well-rounded lattices. Groups Geom. Dyn., 10(4):1211–1255, 2016. [120] C. Ling, L. Luzzi, J.-C. Belfiore, and D. Stehlé. Semantically secure lattice codes for the Gaussian wiretap channel. IEEE Transactions on Information Theory, 60(10):6399–6416, 2014. [121] L. Luzzi, R. Vehkalahti, and C. Ling. Almost universal codes for fading wiretap channels. In IEEE Int. Symp. Inf. Theory, 2016. [122] L. Luzzi, R. Vehkalahti, and C. Ling. Almost universal codes for MIMO wiretap channels. IEEE Transactions on Information Theory, 64(11):7218–7241, 2018. [123] V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. automata, languages and programming. In I. I. Part, editor, Lecture Notes in Comput. Sci., 4052, pages 144–155. Springer, Berlin, 2006. [124] V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In Annual international conference on the theory and applications of cryptographic techniques, pages 1–23. Springer, 2010. [125] V. Lyubashevsky, C. Peikert, and O. Regev. A toolkit for ring-LWE cryptography. In Annual international conference on the theory and applications of cryptographic techniques, pages 35–54. Springer, 2013. [126] O. Makkonen. Algebraic methods for secure coded computing. PhD thesis, Aalto University publication series Doctoral Theses, 195/2025, 2025. [127] J. Martinet. Perfect Lattices in Euclidean Spaces. Springer-Verlag, 2003. [128] J. Martinet. Bases of minimal vectors in lattices. i. Arch. Math. (Basel), 89(5):404–410, 2007.

STRUCTURED LATTICES

37

[129] J. Martinet. Bases of minimal vectors in lattices. ii. Arch. Math. (Basel), 89(6):541–551, 2007. [130] J. Martinet and A. Schürmann. Bases of minimal vectors in lattices. iii. Int. J. Number Theory, 8(2):551–567, 2012. [131] C. T. McMullen. Minkowski’s conjecture, well-rounded lattices and topological dimension. J. Amer. Math. Soc., 18(3):711–734, 2005. [132] D. Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM journal on Computing, 30(6):2008–2035, 2001. [133] D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complexity, 16(4):365–411, 2007. [134] D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, 37(1):267–302, 2007. [135] N. Miller. A design criterion for the rayleigh fading wiretap channel based on ℓ1 -norm theta functions. SIAM Journal on Applied Algebra and Geometry, 9(3):682–706, 2025. [136] N. Miller. On the kissing number of the cross-polytope. https://arxiv.org/abs/2501. 09245, 2025. [137] H. Mirghasemi and J.-C. Belfiore. Lattice code design criterion for MIMO wiretap channels. In 2015 IEEE Information Theory Workshop (ITW), pages 277–281, 2015. [138] O. Musin. The kissing number in four dimensions. Ann. of Math. (2), 168(1):1–32, 2008. [139] National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/ documents/call-for-proposals-final-dec-2016.pdf, 2016. Accessed: 2026-03-26. [140] National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization round 1 submission. https://csrc.nist.gov/projects/ post-quantum-cryptography/post-quantum-cryptography-standardization/ round-1-submissions, 2017. Accessed: 2026-03-26. [141] National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization round 2 submission. https://csrc.nist.gov/projects/ post-quantum-cryptography/post-quantum-cryptography-standardization/ round-2-submissions, 2017. Accessed: 2026-03-26. [142] National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization round 3 submission. https://csrc.nist.gov/projects/ post-quantum-cryptography/post-quantum-cryptography-standardization/ round-3-submissions, 2021. Accessed: 2026-03-26. [143] National Institute of Standards and Technology (NIST). NIST announces first group of cryptographic algorithms for post-quantum cryptography standardization. https://www.nist.gov/news-events/news/2022/07/ nist-announces-first-four-quantum-resistant-cryptographic-algorithms, 2022. Accessed: 2025-01-17. [144] National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization round 4 submission. https://csrc.nist.gov/projects/ post-quantum-cryptography/post-quantum-cryptography-standardization/ round-4-submissions, 2022. Accessed: 2026-03-26. [145] G. Nebe. Boris Venkov’s theory of lattices and spherical designs. In Diophantine methods, lattices, and arithmetic theory of quadratic forms, volume 587 of Contemp. Math., pages 1–19. Amer. Math. Soc., Providence, RI, 2013. [146] R. Y. Njah Nchiwo. Algebraic number theory and lattice based cryptography: equivalence and cryptanalysis of RLWE and PLWE. PhD thesis, Aalto University publication series Doctoral Theses, 147/2026, 2026. [147] R. Y. Njah Nchiwo. Cryptanalysis of polynomial learning with errors (PLWE): A survey. Accepted for publication in Springer “Association for Women in Mathematics Series”, 2026. [148] E. Nossek. Spherical designs and lattices. Beitr. Algebra Geom., 55(1):25–31, 2014. [149] F. Oggier and B. Hassibi. The secrecy capacity of the MIMO wiretap channel. IEEE Transactions on Information Theory, 57(8):4961–4972, 2011. [150] F. Oggier, P. Solé, and J. Belfiore. Lattice codes for the wiretap Gaussian channel: Construction and analysis. IEEE Transactions on Information Theory, 62(10):5690–5708, 2016.

38

LENNY FUKSHANSKY, CAMILLA HOLLANTI, AND RAHINATOU Y. NJAH NCHIWO

[151] F. Oggier and E. Viterbo. Algebraic Number Theory and Code Design for Rayleigh Fading Channels, volume 1(3) of Foundations and Trends in Communications and Information Theory. Now Publisher Inc., 2004. [152] F. E. Oggier, J.-C. Belfiore, and E. Viterbo. Cyclic division algebras: A tool for space-time coding. Found. Trends Commun. Inf. Theory, 4:1–95, 2007. [153] L. H. Ozarow and A. D. Wyner. Wire-tap channel II. AT&T Bell Laboratories technical journal, 63(10):2135–2157, 1984. [154] P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, pages 223–238, 1999. [155] A. Pettet and J. Souto. Minimality of the well-rounded retract. Geom. Topol., 12(3):1543– 1556, 2008. [156] J. Piispanen. On well-rounded lattices and theta function minimization, 2026. M.Sc. Thesis, Aalto University. [157] R. A. Rankin. A minimum problem for the Epstein zeta-function. Proc. Glasgow Math. Assoc., 1:149–158, 1953. [158] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009. [159] O. Regev. The learning with errors problem (invited survey). In Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity, pages 191–204, 2010. [160] O. Regev, U. Shapira, and B. Weiss. Counterexamples to a conjecture of woods. Duke Math. J., 166(13):2443–2446, 2017. [161] C. Riener. On extreme forms in dimension 8. J. Théor. Nombres Bordeaux, 18(3):677–682, 2006. [162] R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169–180, 1978. [163] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, 21(2):120–126, 1978. [164] M. Rosca, D. Stehlé, and A. Wallet. On the ring-LWE and polynomial-LWE problems. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 146–173. Springer, 2018. [165] M. Y. Rosenbloom and M. A. Tsfasman. Multiplicative lattices in global fields. Invent. Math., 101:687–696, 1990. [166] S. S. Ryškov. On the question of the final ζ-optimality of lattices that yield the densest packing of n-dimensional balls. Sibirsk. Mat. Ž., 14:1065–1075, 1158, 1973. [167] P. Sarnak and A. Strömbergsson. Minima of Epstein’s zeta function and heights of flat tori. Invent. Math., 165(1):115–151, 2006. [168] A. J. D. Scala, C. Sanna, and E. Signorini. On the condition number of the vandermonde matrix of the n th cyclotomic polynomial. Journal of Mathematical Cryptology, 15(1):174– 178, 2020. [169] B. Sethuraman, B. Rajan, and V. Shashidhar. Full-diversity, high-rate space-time block codes from division algebras. IEEE Transactions on Information Theory, 49(10):2596–2616, 2003. [170] P. D. Seymour and T. Zaslavsky. Averaging sets: a generalization of mean values and spherical designs. Adv. in Math., 52(3):213–240, 1984. [171] M. Sha. On the lattices from elliptic curves over finite fields. Finite Fields Appl., 31(2):84– 107, 2015. [172] U. Shapira and B. Weiss. Stable lattices and the diagonal group. J. Eur. Math. Soc. (JEMS), 18(8):1753–1767, 2016. [173] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994. [174] M. D. Sikirić, A. Schürmann, and F. Vallentin. Classification of eight-dimensional perfect forms. Electron. Res. Announc. Amer. Math. Soc., 13:21–32, 2007. [175] S. L. Sobolev. Formulas for mechanical cubatures in n-dimensional space. Dokl. Akad. Nauk SSSR, 137:527–530, 1961. [176] O. Solan. Stable and well-rounded lattices in diagonal orbits. Israel J. Math., 234(2):501– 519, 2019.

STRUCTURED LATTICES

39

[177] A. Srinivasan. A complete classification of well-rounded real quadratic ideal lattices. J. Number Theory, 207:349–355, 2020. [178] M. A. Tsfasman and S. G. Vladut. Algebraic-Geometric Codes. Kluwer Academic Publishers, 1991. [179] P. van Emde Boas. Another np-complete problem and the complexity of computing short vectors in a lattice. Tecnical Report, Department of Mathmatics, University of Amsterdam, 1981. [180] W. P. J. van Woerden. An upper bound on the number of perfect quadratic forms. Adv. Math., 365, 2020. 107031, 12 pp. [181] S. Vatedka, N. Kashyap, and A. Thangaraj. Secure compute-and-forward in a bidirectional relay. IEEE Transactions on Information Theory, 61(5):2531–2556, 2015. [182] R. Vehkalahti, C. Hollanti, J. Lahtonen, and K. Ranto. On the densest mimo lattices from cyclic division algebras. IEEE Transactions on Information Theory, 55(8):3751–3780, 2009. [183] B. Venkov. Réseaux et designs sphériques. In Réseaux euclidiens, designs sphériques et formes modulaires, volume 37 of Monogr. Enseign. Math., pages 10–86. Enseignement Math., Geneva, 2001. [184] M. S. Viazovska. The sphere packing problem in dimension 8. Ann. of Math. (2), 185(3):991– 1015, 2017. [185] A. C. Woods. Covering six space with spheres. J. Number Theory, 4(2):157–180, 1972. [186] A. D. Wyner. The wiretap channel. Bell system technical journal, 54(8):1355–1387, 1975.

Department of Mathematics, 850 Columbia Avenue, Claremont McKenna College, Claremont, CA 91711, USA Email address: [email protected] Department of Mathematics and Systems Analysis, Aalto University, P.O. Box 11100, FI-00076 Aalto, Finland Email address: [email protected], [email protected]