APPLICATION TO LATTICE SIGNATURES THOMAS ESPITAU , ALEXANDRE WALLET , AND YANG YU †

A

. We present a general framework for polynomial-time la ice Gaussian sampling. It revolves around a systematic study of the discrete Gaussian measure and its samplers under extensions of la ices; we rst show that given la ices Λ ⊂ Λ we can sample e ciently in Λ if we know how to do so in Λ and the quotient Λ/Λ , regardless of the primitivity of Λ . As a direct application, we tackle the problem of domain extension and restriction for sampling and propose a sampler tailored for la ice ltrations, which can be seen as a broad generalization of the celebrated Klein's sampler. en, we demonstrate how to sample using a change of bases, or even switching the ambient space, even when the target la ice is not represented as full-rank in the ambient space. We show how to correct the induced distortion with the "convolution-like" technique of Peikert (Crypto 2010) (which we encompass as a byproduct). Since our framework aims at modularity and leverage the combinations of smaller samplers to build new ones, we also propose ad-hoc samplers for the so-called root la ices An, Dn, En as base cases, extending the state-of-the-art for root la ice sampling, which was limited to Z n . We also show how our framework blends with the so-called king construction and provides a sampler for the remarkable Leech and Barnes-Wall la ices.

As a by-product, we obtain novel, quasi-linear samplers for prime and smooth conductor (as 2 3 k ) cyclotomic rings, achieving essentially optimal Gaussian width. In a practice-oriented application, we showcase the impact of our work on hash-and-sign signatures over la ices.

In the best case, we can gain around 200 bytes (which corresponds to an improvement greater than 20%) on the signature size. We also improve the new gadget-based constructions (Yu, Jia, Wang, Crypto 2023) and gain up to 110 bytes for the resulting signatures.

Lastly, we sprinkle our exposition with several new estimates for the smoothing parameter of la ices, stemming from our algorithmic constructions and by novel methods based on series reversion. For the last few decades, la ices have proved themselves to be a cornerstone of modern cryptography, allowing the development of feature-rich schemes, including digital signatures [START_REF] Ducas | CRYSTALS-Dilithium: A la ice-based digital signature scheme[END_REF][START_REF] Omas Prest | Falcon: Submission to the NIST's post-quantum cryptography standardization process[END_REF][START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF], identity-based encryption [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF], functional encryption [START_REF] Agrawal | Stronger security for reusable garbled circuits, general de nitions and a acks[END_REF], (non-interactive) zeroknowledge proofs [START_REF] Peikert | Noninteractive zero knowledge for NP from (plain) learning with errors[END_REF] and last but not least fully homomorphic encryption [START_REF] Gentry | Fully homomorphic encryption using ideal la ices[END_REF][START_REF] Ilaria Chillo I | TFHE: Fast fully homomorphic encryption over the torus[END_REF]. A common denominator of many such schemes revolves around the ability of sampling from the so-called discrete Gaussian distribution over a given la ice Λ. Given a center c in the ambient space Λ R and a "width" s -which is essentially the standard deviation by analogy with the normal distribution -the distribution D Λ,c,s 2 assigns the vector v ∈ Λ the probability proportional to the Gaussian function exp(-π vc 2 /s 2 ). Remark that this distribution only depends on the la ice and not on the basis used to represent it. In this sense it does not leak any information about a possible secret basis: this "zero-knowledge" property accounts for its utility in cryptography.

For speci c la ices such as Z n or la ices stemming from some trapdoor sampling as in [START_REF] Micciancio | Trapdoors for la ices: Simpler, tighter, faster, smaller[END_REF], ad-hoc approaches are commonly used. In comparison, to sample in an a priori arbitrary la ice, two polynomial time samplers are well-known and widely used in constructions and beyond: the so-called Klein sampler (or sampler) [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF] and the Peikert sampler [START_REF] Peikert | An e cient and parallel Gaussian sampler for la ices[END_REF], both having di erent advantages and drawbacks. e former is a sequential sampler: the algorithm performs adaptive iterations of sampling in projected lines, where the choices made in each iteration a ect the values used in the next. It is rather costly and imposes to work with the Gram-Schmidt orthogonalization of the input basis. e la er is a naturally parallel sampler, reducing the problem of sampling in Λ to sample the coe cients of the desired sample on the input basis. is "change of basis" induces a distortion, blurred by convolving with a su ciently wide perturbation. It is faster than Klein's sampler at the price of slightly worse quality, in the sense that the minimal sampleable width is larger. Note that these two algorithms correspond to the randomization of two famous polynomial time oracles for the (approximate) Closest

Vector Problem from Babai [START_REF] Babai | On lovasz' la ice reduction and the nearest la ice point problem[END_REF]: the Klein sampler corresponds to the nearest plane algorithm and the Peikert sampler to the rounding algorithm. Fine-tuning such algorithms is one of the main tasks for designers of signatures in the hash-then-sign framework of [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF][START_REF] Ducas | E cient identity-based encryption over NTRU la ices[END_REF].

On hash-and-sign digital signatures. Designing, selecting, and analyzing quantum-resistant schemes is the main goal of the ongoing NIST standardization e ort for post-quantum cryptography. In July 2022, NIST eventually announced four post-quantum algorithms to be standardized. For signatures, two of the three selected algorithms are la ice-based, [START_REF] Omas Prest | Falcon: Submission to the NIST's post-quantum cryptography standardization process[END_REF] and [START_REF] Ducas | CRYSTALS-Dilithium: A la ice-based digital signature scheme[END_REF], epitomizing two known classes of la ice signatures: hash-and-sign and Fiat-Shamir with aborts. Recently, Espitau et al. designed an alternative approach to , called [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF]. As an a ractive advantage, can be instantiated over arbitrary cyclotomic elds, conveniently allowing it to reach all NIST security levels. relies on a so-called hybrid sampler [START_REF] Omas Prest | Gaussian Sampling in La ice-Based Cryptography[END_REF], which acts as Klein's sampler at the level of the module and calls the Peikert sampler to sample within this ring. For power-of-two cyclotomics, this approach is su cient, as the sampling of the ring of integers amounts to sampling in a square la ice Z n .

However, for the other cyclotomic rings considered in [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF], this induces a non-negligible quality loss, thus a slight degradation in security. Recently, the scheme Hawk [START_REF] Ducas | Hawk: Module LIP makes la ice signatures fast, compact and simple[END_REF] presented a new hash-and-sign signature tied to la ices, relying on a more recent-yet natural-cryptographic assumption, the so-called la ice isomorphism problem. is la er scheme raises the non-trivial question of the possibility of sampling e ciently in la ices with remarkable packing properties, such as the Leech or the Barnes-Walls la ices. Interestingly, the same question was also independently triggered in the new design of la ice gadgets of [START_REF] Yu | Compact la ice gadget and its applications to hash-and-sign signatures[END_REF] to improve the e ciency and compactness of trapdoors. All in all, the quest for new e cient samplers, especially for remarkable la ices, has interesting consequences in the realm of cryptographic design.

Contributions. In this work, we aim at going beyond this Klein/Peikert dichotomy for polynomial time sampling. We showcase a general framework based on a systematic study of the discrete Gaussian distribution under extensions: algebraic extensions through short exact sequences and metric extensions through linear transformations. is framework allows us to build new samplers over extensions or restrictions of domains in which we already know how to sample. Our abstract samplers correspond to e ective versions of general bounds on the smoothing parameter of la ices: this correspondence is a unifying thread in all our exposition. To complete our modular framework, we also provide ad-hoc samplers of essentially optimal widths for root la ices, to use them as fundamental blocks to instantiate more involved samplers. Optimality is deduced from a new theoretical bound on the smoothing parameter obtained from the relation between the Gaussian function over a la ice and its theta series. When the kissing number and minimum of the (dual) la ice are known, it gives a tighter bound on the smoothing, unconditionally on the value of ε -unfortunately, it is unlikely to get this information for an arbitrary la ice. As an application, we obtain novel, optimal, and e cient samplers over cyclotomic rings of prime and smooth conductors and optimized trapdoors in the spirit of [START_REF] Yu | Compact la ice gadget and its applications to hash-and-sign signatures[END_REF]. e technical details of our contributions are as follows.

Exploiting the decomposition over short exact sequences. Given a la ice Λ and one of its subla ices Λ , we can associate the short exact sequence of Z-modules:

0 -→ Λ -→ Λ -→ Λ Λ -→ 0.
Note that in this sequence, the quotient Λ/Λ is not necessarily a la ice 1 itself, and as such, Λ cannot be identi ed as a la ice to Λ ⊕ Λ/Λ . We show how to deal with this extension of groups to extend samplers for Λ and Λ/Λ into a sampler for Λ, for standard deviations above the smoothing parameters of the Λ component. In particular, we identify precisely the projection of the Gaussian measure onto the quotient, recovering the known situation where Λ is either full-rank or primitive. is construction translates into a simple bound on the smoothing parameter, namely

η 3ε (Λ) max η ε (Λ ), η ε Λ Λ ,
where the notion of smoothing is generalized to accommodate non-la ice quotients. Note that the choice of the subla ice is arbitrary here. is su ces, for instance, to deal with the problem of domain extension and restriction of samplers: given a sampler over Λ, how can one extend it to an overla ice or restrict it to a subla ice?

A ltered sampler. A ltration of a la ice is an increasing sequence of la ices

0 ⊂ Λ 1 ⊂ • • • ⊂ Λ k = Λ.
Iterating the previous construction gives us a generic sampler for Λ. Namely, we have a rst short exact sequence stemming from the ltration:

0 -→ Λ 1 -→ Λ -→ Λ Λ 1 -→ 0,
and by our sampler over sequences, we can e ciently sample in Λ if we know how to sample in both Λ 1 and Λ/Λ 1 . However, we can remark that quotienting by Λ 1 induces a ltration 1 Generally, the quotient is a product of the torsion part, which is a nite abelian group and its free part, which corresponds to a la ice too. Even when the quotient is torsion-free, Λ does not identify to Λ ⊕ Λ/Λ as la ices in general.

0 ⊂ Λ 2 /Λ 1 ⊂ • • • ⊂ Λ k = Λ/Λ 1 .
Hence, we can recursively apply this technique and devise a sampler for Λ from samplers over (Λ i+1 /Λ i ) i . is approach yields a natural generalization of Klein's sampler (as presented in [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF]), which corresponds to the particular case where rk(Λ i ) = i for all 1 i rk(Λ), and the successive quotients correspond to the Gram-Schmidt orthogonalization. Expectedly, we obtain a bound on the smoothing parameter of Λ in terms of the smoothing parameter of these quotients, generalizing that of [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF]:

η ε (Λ) max 1 i k η ε k+1 (Λ i /Λ i-1 ).
In a later section, we show how this abstract sampler and its designated bound can lead to signi cant improvements over the Klein-Peikert dichotomy on a concrete example.

A linear sampler. Change of basis is a natural technique in linear algebra allowing to reexpress sets of linear equations in more congenial forms, by looking at the coordinates of a linear space under a di erent basis. It is a deep principle undertaking numerous aspects of numerical algorithm, whether by making incremental changes (like in Gaussian elimination or la ice reduction), or in one take (e.g., computing the Discrete Fourier transform representation). Unsurprisingly, we can apply it to discrete Gaussian sampling as well 2 . Hence, from a high-level point of view, one can design a Gaussian sampler in a given la ice Λ as long as one can sample discrete Gaussians in the la ice spanned by a ( xed) congenial basis C, which can even live in a di erent space. is process amounts to controlling the distortion on the Gaussian distribution induced by the change-of-basis procedure, and to smooth it out with a carefully chosen normal 3 perturbation. is algorithm encompasses the sampler of Peikert [START_REF] Peikert | An e cient and parallel Gaussian sampler for la ices[END_REF], which reduces sampling in a la ice Λ to sampling spherically in Z rk Λ -this can be done coordinatewise. is construction yields a natural bound on the smoothing parameter, writing a basis B of Λ as the product TC:

η ε (Λ) s 1 (T) • η ε (L(C))
for s 1 (T) being the largest singular value of T. Again, note that the choice of the decomposition is arbitrary (as long as C is invertible). A generic sampler in tensor la ices Λ 1 ⊗Λ 2 follows almost immediately. 2 Of course, change of basis works very well for continuous Gaussians: it simply amounts to matrix-vector multiplication. 3 What ma ers for proofs is that the perturbation distribution has good convolution properties with Gaussian kernels.

Sampling in remarkable lattices. e previous contributions aim at building a framework for e cient Gaussian sampling, by joining existing samplers through extensions (namely module extension for the exact sequence sampler, linear extension for the linear sampler and tensor extension for the tensor sampler). It means that we need to be able to sample in some base cases to fully instantiate these higher-order constructions. We thus introduce a set of ad-hoc samplers for some of the so-called root la ices (A n la ices, the face-centered la ices D n , the Gosset la ice E 8 ) emerging in many contexts. ey are, for example, well-known for their outstanding geometric properties, e.g., enjoying quasi-linear decoding [START_REF] Conway | Fast quantizing and decoding and algorithms for la ice quantizers and codes[END_REF][START_REF] Conway | A fast encoding method for la ice codes and quantizers[END_REF], or their appearance in more mathematical topics such as the classi cation of Lie algebras. In particular, our samplers rely on their well-understood structures and exceptional isomorphisms between them, coming from the la er topic, and we reach standard deviations quite close to the smoothing of these la ices. Generally, we add another tribute to the deep connexions of these remarkable la ices with coding theory, as we combine our algebraic framework with the king construction [START_REF] Corlay | On the decoding of la ices constructed via a single parity check[END_REF] to devise samplers in the Leech and low-dimensional Barnes-Wall la ices. e technique allows as a byproduct to construct samplers in parity-check-like la ices.

Cryptographic impact. To showcase our framework in a cryptographic context, we demonstrate how to instantiate various samplers over some structured la ices. ere are well-known identi cations between certain ideals in prime cyclotomic rings and A p-1 la ices (or their duals), already subject to algorithmic works [START_REF] Lyubashevsky | A toolkit for ring-LWE cryptography[END_REF][START_REF] Ducas | e closest vector problem in tensored root la ices of type a and in their duals[END_REF]. Cyclotomic rings of smooth conductors can also identify as (direct sums of) prime cyclotomic rings. We exploit our ad-hoc samplers to devise novel samplers in cyclotomic rings: our result combines quasi-linear e ciency and optimal Gaussian width. To our knowledge, all previous approaches reached worse Gaussian widths, and at best equivalent e ciency.

We also detail the implication for the design of hash-and-sign signatures, where the ability to sample e ciently and precisely is crucial for the security and bandwidth of the scheme.

We compare our variations with the recently proposed and state-of-the-art Falcon [START_REF] Omas Prest | Falcon: Submission to the NIST's post-quantum cryptography standardization process[END_REF] and Mitaka [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF] signatures. In particular, we show how to design hash-and-sign signatures more tightly on smooth cyclotomic elds, giving more security (around 20 bits in both classical and quantum regimes) and slightly shorter signatures for free compared to [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF] (although bitsize is not the focus of this work). More interestingly, we show how to implement them on prime cyclotomics, allowing a very tight choice of parameter selections. At a high-level, our results are also satisfying in the sense that they not only increase the security level for prime cyclotomics compared to [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF], they also show a more regular growth and behavior of the ratio security level over cyclotomic-conductors compared to [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF]. en, we also give new instantiations of the recent framework of [START_REF] Yu | Compact la ice gadget and its applications to hash-and-sign signatures[END_REF] for compact gadget-based sampling with a target la ice constructed as a tensor of the root E 8 and Z n . We again get slightly shorter signatures for free (110 bytes shorter) for higher security, both in the classical and quantum se ings.

A

General notation. e bold capitals Z, Q, and R refer respectively to the ring of integers, the eld of rational and real numbers. Given a real number x, the integral roundings oor, ceil and round to the nearest integer are denoted respectively by x , x , x . Let ln denote the natural logarithm. For a real-valued function f and a countable set S, we write generically f (S) = x∈S f (x) assuming that this sum is absolutely convergent. Vectors and matrices are understood column-wise. For A, B two matrices, we write [A, B] for the concatenation of the columns from A and B. e transpose of a matrix T is T t and if T is non singular, its pseudo-inverse is T = (T t T) -1 T t . In this work, when dealing with la ices embedded in R n , we only consider the standard Euclidean norm, corresponding to the canonical inner product , , but we stress that most of our algorithms are agnostic to the choice of the norm. e dual of a la ice Λ is the la ice

Λ ∨ = {x ∈ Λ R | x, v ∈ Z, ∀ v ∈ Λ},
and we always endow it with the same norm as Λ. If Λ is a full-rank la ice of basis B, then

B -t is a basis of Λ ∨ ; if it is not full rank, B(B t B) -1 is a basis of Λ ∨ . 2.1.1. Orthogonality. For a subspace V ⊂ Λ R , let V ⊥ = {y ∈ Λ R | y, v = 0, ∀ v ∈ V } be the orthogonal. Let π V ⊥ denote the orthogonal projection onto V ⊥ equipped
* i = π (b 1 ,...,b i-1 ) ⊥ (b i ).
2.1.2. Subla ices, quotient la ices. Let (Λ, • ) be a la ice, and let Λ be a nitely generated submodule of Λ. e restriction of • to Λ endows it with a la ice structure : (Λ , • ) is called a subla ice of Λ. If any basis of Λ extends into a basis of Λ, then Λ is called primitive. In this case, the quotient Λ/Λ is endowed with a canonical la ice structure by de ning:

v + Λ Λ/Λ = inf v ∈Λ R v -v .
en, there is an isometry between (Λ/Λ , • Λ/Λ ) and

(π Λ ⊥ R (Λ), •
). E ectively, this means we represent quotient la ices by computing the projection of a given basis for Λ. We write Λ = Λ ⊥ Λ to highlight that Λ is the orthogonal direct sum of two la ices. In this case, π Λ ⊥ R (Λ) = Λ and we have an isometry Λ ∼ = Λ ⊕ Λ/Λ .

Whether Λ is primitive or not, the quotient Λ/Λ always decomposes as a product of its torsion part T ( nite subgroup of torsion elements) and its torsion-free part. Torsion elements in the quotient represent x ∈ Λ such that ax ∈ Λ for some a ∈ Z, that is, the set Λ ∩ Λ R . e torsion-free part is itself a la ice: if Λ is the (primitive) la ice generated by Λ and a system of representative for T, it identi es to Λ/Λ , with the quotient norm. It is thus equivalent for Λ to be primitive and for Λ/Λ to be torsion-free. When Λ has full-rank, Λ/Λ is just the torsion group T. Usual solutions to perform the li from a coset representative to a la ice point use Babai's rounding or Babai's nearest plane algorithm.

2.1.3. E ective li ing. Given a coset t+Λ of the quotient Λ/Λ , we might need to nd a representative of this class in Λ. While any element could be theoretically taken, from an algorithmic point of view, we shall take an element of norm somewhat small, so that its coe cients remain polynomial in the input representation of the la ice. Below is the pseudo-code for Nearest Plane based li ing.

Algorithm 1 Li (by Babai's nearest plane)

Input: A la ice basis B = (b 1 , . . . , b n ) of Λ in Λ, a vector t ∈ Λ.
Result: A vector s ∈ Λ in the coset t + Λ .

1 Compute the Gram-Schmidt orthogonalization (b * 1 , . . . , b * k ) of B 2 s ← t 3 for i = k downto 1 do s ← s - s,b * i b * i 2 b i 4 return s 2.1.4. Filtrations. A ltration of a la ice Λ is an increasing sequence of subla ices {0} = Λ 0 ⊂ Λ 1 ⊂ Λ 2 ⊂ • • • ⊂ Λ k = Λ where each Λ i is a primitive subla ice of Λ i+1 . Let rk(Λ i ) = d i , then 0 = d 0 < d 1 < d 2 < • • • < d k = rk(Λ). A ltration is called complete if d i = i
for all i: for example, any basis of Λ gives a complete ltration. Filtrations are compatible with quotienting: a ltration (Λ i ) i of Λ yields a ltration (Λ i+j /Λ j ) i of Λ/Λ j . 2.2. Discrete Gaussian distributions. Let Σ be a positive de nite matrix. We de ne ρ Σ (x) = exp(-πx t Σ -1 x) as the Gaussian kernel of covariance Σ. Equivalently, we could call it the standard Gaussian mass for the norm induced by Σ -1 . In that case, one sees that a Gaussian function is always isotropic, i.e., its value only depends on the designated norm of its input. When Σ = s 2 I n , the subscript Σ is shortened4 in s 2 and s is called the width.

Let now Λ ⊂ R m of rank n m.
e discrete Gaussian distribution over Λ with center c ∈ Λ R and covariance Σ ∈ R m×m is de ned by the density

D Λ,c,Σ (x) = ρ Σ (x -c) ρ Σ (Λ -c) , ∀x ∈ Λ.
When c = 0, we omit the script c.

2.2.1. Smoothing parameter. For a la ice Λ and real parameter ε > 0, the smoothing parameter

η ε (Λ) is the smallest s > 0 such that ρ 1 s 2 (Λ ∨ ) 1 + ε.
When the Gaussian width s exceeds the smoothing parameter, all the la ice cosets have roughly the same mass.

Lemma 2.1 ([26, Lemma 2.4]). Given a la ice Λ, ε ∈ (0, 1) and Σ η ε (Λ) 2 I n , then, for any

c ∈ Λ R , ρ Σ (Λ + c) ∈ [ 1-ε 1+ε , 1] ρ Σ (Λ).
e following result recalls that cosets' mass has exponential decay from the origin. A useful consequence is to express the Gaussian mass by means of a subla ice and its corresponding projection.

Lemma 2.2. Let Λ ⊂ R m be a la ice and x ∈ R m . For Σ 0, let P be the orthogonal projection onto Λ ⊥ R , where orthogonality is taken with respect to the inner product x t Σ -1 y. en we have ρ

Σ (x + Λ) ρ Σ (P (x)) • ρ Σ (Λ). If moreover Λ is primitive in Λ , we have ρ Σ (Λ ) ρ Σ (Λ)ρ Σ (P (Λ )
). e equality case occurs when Λ = Λ ⊥ P (Λ ).

2.3. On root lattices. So-called root la ices are families of special la ices with nice geometry deriving from root systems. ey enjoy, for instance, good decoding properties (see [START_REF] Conway | Fast quantizing and decoding and algorithms for la ice quantizers and codes[END_REF][START_REF] Conway | A fast encoding method for la ice codes and quantizers[END_REF],

or more recently and closely related to this work, see [START_REF] Ducas | e closest vector problem in tensored root la ices of type a and in their duals[END_REF][START_REF] Wessel Pj Van Woerden | e closest vector problem in cyclotomic la ices[END_REF]). Most of their fundamental quantities are well-understood, and general exposition can be found in [START_REF] Martinet | Perfection and Eutaxy[END_REF]Chapter 4] or [START_REF] Conway | Sphere Packings, La ices and Groups. Grundlehren der Mathematischen Wissenscha en 290[END_REF].

We only recall here the de nitions of three types of root la ices (A n , E n and D n ), and highlight some properties of the A n family.

De nition 2.1 (Root la ices). For integer n > 0, the root la ices A n , D n of rank n are respectively de ned as

A n = {v ∈ Z n+1 | v 1 + • • • + v n+1 = 0}, D n = {v ∈ Z n | v 1 + • • • + v n ∈ 2Z}.
We also let

E n = D n ∪ 1 2 , . . . , 1 2 + D n .
When n is even, E n is a la ice and an important special case is the Gosset la ice E 8 . If we let (e i ) i denotes the canonical basis of R n+1 , the A n la ices admit the basis (e i -e i+1 ) i . is basis has Gram matrix

(1)

G n =           2 -1 0 0 • • • 0 0 -1 2 -1 0 • • • 0 0 . . . . . . . . . . . . . . . . . . . . . 0 0 0 • • • -1 2 -1 0 0 0 • • • 0 -1 2           ∈ Z n×n .
e dual la ice A ∨ n admits the basis ( n n+1 e i -1 n+1 1 i =j p e j ) i , with associated Gram matrix

(2)

G ∨ n = 1 n + 1        n -1 • • • -1 -1 -1 n • • • -1 -1 . . . . . . . . . . . . . . . -1 -1 • • • -1 n        .
As we will particularly focus on the A n la ices, we collect also some of their geometric properties. Note that they span the hyperplane 1 ⊥ , where 1 = (1, . . . , 1).

eir volume is √ n + 1, and λ 1 (A n ) = √ 2. eir dual is A ∨ n = π 1 ⊥ (Z n+1 ), with λ 1 (A ∨ n ) = n/(n + 1), and A n has index n + 1 in A ∨ n .
Noticeably, A 2 identi es with the famous hexagonal la ice.

2.3.1. On cyclotomic rings. In Section 9, we need some background on cyclotomic rings and their geometry. Most of the used material is relatively standard.

We let Z * m be the multiplicative group of the φ(m) integers invertible modulo m, where φ is Euler's totient function. Let ζ m be a primitive m-th root of unity.

e m-th cyclotomic

polynomial Φ m (X) = i∈Z * m (X -ζ i m ) ∈ Z[X]. e degree of Φ m (X) is d = φ(m). We call R m = Z[ζ m ] Z[X]/(Φ m (X)) the m-th cyclotomic ring and K m = Q[ζ m
] the m-th cyclotomic eld. Any f ∈ K m can be uniquely wri en as f = n-1 i=0 f i ζ i m with f i ∈ Q. e coe cient embedding identi es f to its vector of coe cients (f 0 , . . . , f d-1 ).

e cyclotomic eld K m has exactly d embeddings xing elements of Q. Concretely, the

embedding ψ i for i ∈ Z * m is de ned by ψ i (ζ m ) = ζ i m . Let ψ(f ) = (ψ i (f )) i∈Z * m ∈ K d m be the canonical embedding of f ∈ K m .
We can use it to de ne the conjugate of f as f * = (ψ 1 (f ), . . . , ψ d (f )). e trace is the Q-linear map de ned as Tr(f ) = i∈Z * m ψ i (f ). It gives an inner product as Tr(f g * ) = ψ(f ), ψ(g) and an euclidean norm ψ(f ) 2 = Tr(f f * ). is product can be extended to vectors in a way that gives a positive de nite hermitian form over K k m , compatible with the geometry. We only need the case of k = 2. e form is de ned as (f, g), (F, G) = f * F + g * G. In particular, elements (f, g), (f, g) = f f * + gg * have all their embeddings real and positive. us for all pairs (f, g), (F, G) of vectors in

K 2 m , (F, G) * := (F, G) - (f, g), (F, G) (f, g), (f, g) (f, g)
is well-de ned. One checks that (f, g), (F, G) * = 0, which gives a notion of orthogonality over K 2 m and accordingly, (F, G) * is the Gram-Schmidt orthogonalization of (F, G) with respect to (f, g) for the trace product.

V m =        1 ζ m,1 ζ 2 m,1 . . . ζ φ(m)-1 m,1 1 ζ m,2 ζ 2 m,2 . . . ζ φ(m)-1 m,2 . . . . . . 1 ζ m,φ(m) ζ 2 m,φ(m) . . . ζ φ(m)-1 m,φ(m)        .
We have ψ(x) = V m (x 1 , . . . , x φ(m)-1 ) t . When m is a prime p, it is known that the largest and smallest singular values are s 1 (V p ) = √ p and s p-1 (V p ) = 1. e corresponding Gram matrix

V p V p t has determinant ∆ K = p p-2
, which is the discriminant (or the squared discriminant sometimes) of the eld K p .

2.4.

Identi cations between cyclotomic ideals and root lattices. Most of the next facts are well-known, and can be found e.g. in [START_REF] Ducas | e closest vector problem in tensored root la ices of type a and in their duals[END_REF][START_REF] Lyubashevsky | A toolkit for ring-LWE cryptography[END_REF][START_REF] Wessel Pj Van Woerden | e closest vector problem in cyclotomic la ices[END_REF]. A rst interesting decomposition arises when m = p q k for primes p = q: we have

R m = R p ⊗ R q k . Additionally, we have R p k = p k-1 i=1 R p ,
τ : R p -→ A ∨ p-1 , de ned by τ (ζ i p ) = b i+1 for 0 i p -2,
with normalization for the isometry seen here as ψ(x) 2 = p τ (x) 2 .

A second identi cation involves the co-di erent ideal R ∨ p of R p : it is the principal ideal

R ∨ p = 1-ζp p
, and acts the dual la ice to R p . From what precedes, we get a map τ ∨ : R ∨ p → A p-1 sending the dual basis of 1, ζ p , . . . , ζ p-1 p for the trace product, also called decoding basis by [START_REF] Lyubashevsky | A toolkit for ring-LWE cryptography[END_REF], to the basis (e 1 -e i ) 2 i p of A p-1 . We now have p ψ(x) 2 = τ ∨ (x) 2 . is map turns out to be mildly less interesting for our purpose. Nevertheless, the ideal

1 -ζ p admits the Z-basis (1 -ζ p ), . . . , ζ p-2 p -ζ p-1 p . Le ing u i = ζ i p -ζ i+1
p , we have:

tr(u i u * i ) = ψ(u i ) 2 = 2p and tr(u i u * j ) = ψ(u i ), ψ(u j ) =    -p if |i -j| = 1 0 else.
We recognize a scaling by p of the Gram matrix (1) of A p-1 when described by the basis (e ie i+1 ) i . Hence, if we de ne

φ : 1 -ζ p -→ A p-1 by φ(u i-1 ) = e i -e i+1 for 1 i p -1,
it identi es both la ices and we have ψ(x) 2 = p φ(x) 2 . For modularity, we gather this observation in the following result.

Proposition 1 (Adapted from [START_REF] Wessel Pj Van Woerden | e closest vector problem in cyclotomic la ices[END_REF]Chap.1]). Let p be a prime, ζ p a primitive p-th root of 1, and ψ the canonical embedding of R p . ere exists a linear map φ :

1 -ζ p -→ A p-1 such that we have ψ(x) 2 = p φ(x) 2 , for all x ∈ 1 -ζ p .
e map ψ can be computed using the Vandermonde matrix V p associated with the p-th primitive roots of 1. We have (3)

s 1 (V p ) = √ p and s p-1 (V p ) = 1, where s p-1 is the smallest singular value. is implies 1 p x 2 φ(x) 2 x 2 for all x ∈ 1 -ζ p .
0 -→ Λ -→ Λ -→ Λ Λ -→ 0.
Exactness means that the kernel of each arrow is exactly the image of the arrow preceding it.

It implies that Λ identi es to a submodule of Λ and that the map Λ → Λ/Λ is surjective. We do not assume that Λ, Λ have the same rank, nor that we have an exact sequence of la ices, nor that it splits (which would mean that Λ ∼ = Λ × Λ/Λ as Z-modules).

Recall from Section 2 that Λ/Λ decomposes as the direct sum T ⊕ Λ f of its torsion part T and its free part. e free part can be seen as Λ/Λ , where Λ is the la ice spanned by Λ and a set of representative of T. is denser la ice can be understood as a "primitivation" of Λ .

Hence, Λ/Λ identi es 6 to the la ice π (Λ R ) ⊥ (Λ). Let us give a concrete exemple.

3.1.1. An example of torsion in quotient of la ices. Let Λ = Z 2 be the square la ice of rank 2.

• Simple Torsion, or "full rank". Let Λ = (2Z) 2 be its index-4 subla ice consisting of vectors with even coe cients. en Λ/Λ = Z 2 /(2Z) 2 = (Z/2Z) 2 is the Klein group, a nite group of order 4, and its free part is {0}. Representative for the torsion are for instance (0, 0), (1, 0), (0, 1) and (1, 1).

• Torsion-free. Let Λ ∼ = Z be its subla ice of rank 1 consisting of vectors with null rst coe cient.

en Λ/Λ ∼ = Z is a la ice of rank 1: the set of vectors with second coe cient equal to zero.

• Mixed case. Let Λ ∼ = 2Z be its subla ice of rank 1 consisting of vectors with their second coe cient even. en we have: Λ/Λ ∼ = Z × Z/2Z, encoding the coset space as choosing the parity of the second coe cient (i.e., the torsion part Z/2Z) and then choosing the rst coe cient without conditions (i.e., the free part Z). A non trivial representative for the torsion is (0, 1), and indeed the la ice spanned by Λ and (0, 1) is Z.

e measure D decomposes into two components, which can then be normalized to probability distributions:

• the restriction: over the subla ice Λ , which identi es as D = ρ/ρ(Λ ).

• the pushforward: π D onto the quotient Λ/Λ . By de nition, for any witness x of a

Λ -coset in Λ, we have π D(x) = D(x + Λ ).
6 e important catch here is about which orthogonality we are considering: in our proof, the orthogonality must be with respect to the norm induced by the covariance matrix of the target Gaussian, that is,

x → x t Σ -1 x. is allows us to use that x, y ∈ Λ R such that x t Σ -1 y = 0, we have ρΣ(x + y) = ρΣ(x) • ρΣ(y).
Understanding the la er is the focus of the next lemma. In the lemma below, we distinguish the quotient map π : Λ → Λ/Λ from the orthogonal projection π := π (Λ R ) ⊥ . For the sake of notational clarity, we restrict to the case of centered distributions but the proof readily adapts to the general case.

Proof. Our rst goal is to describe the coset x + Λ , and recall that we denoted π the orthogonal projection from Λ to Λ/Λ . Consider a section 7 s : Λ/Λ → Λ, that is, a linear map such that π • s = Id. From its properties, we see that x ∈ s(π(x)) + Λ . Let now T = {t + Λ } t be a system of representative of the torsion points. Since Λ is the disjoint union of cosets t + Λ , there is a unique one such that x ∈ s(π(x))+t+Λ , and it follows that x+Λ = s(π(x))+t+Λ . By de nition and orthogonality, the pushforward of the discrete Gaussian under π therefore acts as

(4) D(x + Λ ) = ρ(s(π(x)) -π(x) + t + Λ ) • D(π(x)).
Similarly, the total measure of the quotient Λ/Λ can be wri en

(5) D π -1 Λ Λ = (t,π(x)) ρ(s(π(x)) -π(x) + t + Λ )D(π(x)).
By assumption on the covariance parameter, we are above the smoothing of Λ , so all the Λcosets have roughly the same Gaussian mass as Λ . More precisely, taking ratio between Equalities ( 4) and ( 5) and using Lemma 2.1, we get our claim:

(6) π D(x mod Λ ) π D(Λ/Λ ) ∈ 1 -ε 1 + ε , 1 + ε 1 -ε • 1 |T| • ρ(π(x)) ρ(π(Λ)) .
Lemma 3.1 satisfyingly recovers the extreme cases which are frequently encountered in the literature:

7 Such a map always exists: indeed, as Λ is primitive, one can always nd a subla ice Λ0 such that Λ = Λ0 ⊕ Λ and the section can be de ned by identifying the vectors of a basis of Λ0 with their projections by π.

• If Λ is full-rank, we have |T| = [Λ : Λ ] and the projection sends all points to 0, so that π D is statistically close to the uniform distribution over the nite group of Λ -cosets.

• If Λ is primitive, the quotient is torsion-free, π = π and we recover that π D is essentially the orthogonal projection of the discrete distribution, that is, a discrete Gaussian distribution over π(Λ).

An interesting subcase happens when an orthogonal decomposition Λ = Λ ⊥ Λ is known.

We then have a short exact sequence 0 → Λ → Λ → Λ → 0. But now, the Gaussian measure splits perfectly, so that the pushforward is exactly the projected distribution.

Lemma 3.2. Let Λ , Λ be two la ices, Λ = Λ ⊥ Λ , and π the orthogonal projection onto Λ R

⊥

.

If D = D Λ,t,s 2 , then we have π D = D Λ ,π(t),s 2 .
Proof. e assumptions give π(Λ) = Λ . Decompose z ∈ Λ as z = z + π(z) and similarly t = t + π(t). We use orthogonality twice: on the one hand, it gives

ρ s 2 (π(z) -t + Λ ) = ρ s 2 (π(z)-π(t))ρ s 2 (Λ -t ). On the other hand, it also gives ρ s 2 (Λ-t) = ρ s 2 (Λ -t )ρ s 2 (Λ - π(t)).
Taking ratios gives the result.

Smoothing parameter and short sequences.

e decomposition induced by the quotient translates into a generic bound on the smoothing parameter:

Proposition 2 (Modularity of smoothing parameter). Let Λ be a la ice and

0 < ε < √ 17 -4, then η 3ε (Λ) min Λ ⊂Λ max η ε (Λ ), η ε Λ Λ ,
where the minimum ranges over all possible subla ices of Λ.

Proof. For completeness, we recall the Poisson Summation Formula for Gaussian functions. For any rank n la ice Λ, we have

(7) ρ s (Λ) = s n det Λ • ρ 1/s (Λ ∨ ).
Let Λ be any subla ice of Λ and s max(η ε (Λ ), η ε (Λ/Λ )). Now, consider the orthogonal projection π of Λ onto the orthogonal space to Λ R , for the standard inner product.

Lemma 2.2 gives that ρ s (Λ) ρ s (Λ ) • ρ s (π(Λ)). Using Identity [START_REF] Conway | Sphere Packings, La ices and Groups. Grundlehren der Mathematischen Wissenscha en 290[END_REF] and the fact that

det(Λ) = det(π(Λ)) det(Λ ), this is equivalent to ρ 1/s (Λ ∨ ) ρ 1/s (Λ ∨ )ρ 1/s (π(Λ) ∨ ). Because they have the same rank, Λ ⊂ Λ is equivalent to Λ ∨ ⊂ Λ ∨ , so we have ρ 1/s (Λ ∨ ) ρ 1/s (Λ ∨ )
. By assumption on s, this implies ρ 1/s (Λ ∨ ) (1 + ε) 2 , and we conclude by noting that our choice of subla ice was arbitrary.

Note that the bound makes appear Λ and not Λ itself in the quotient. e intuition behind this, maybe surprising, detail stems from the fact that the pushforward measure is driven only by Λ and the torsion-free part of the quotient. Indeed, we can geometrically interpret the smoothing parameter to be the minimal width to smooth out the la ice structure i.e., the pushforward over Λ R /Λ is the uniform distribution. But then remark that (Λ/Λ ) R = (Λ/Λ ) R as real spaces, making all the torsion elements geometrically irrelevant w.r.t. the smoothing.

3.1.3. Towards a Gaussian sampler. e bound of Proposition 2 can be turned into a natural sampler built from given samplers over Λ/Λ and Λ , or oracles for them. First, sample in the quotient with the appropriate distribution, li the result to the full la ice, and sample around this point in the subla ice Λ . Remark that all x ∈ Λ write uniquely as x = x + π(x) with x ∈ Λ and x = t + x , since it also belongs to a unique coset t + Λ with t ∈ T. Above the smoothing of Λ , sampling according to the pushforward selects such a coset and π(x) with essentially the correct distribution. Similarly, above the smoothing of π(Λ) we cannot really distinguish in which coset of π(Λ) a Gaussian around π(x) belongs.

All-in-all, this strategy leads to Algorithm 2, where we even allow sampling approximatively in the sets Λ and Λ/Λ -this will be proved useful to recursively chain calls of this sampler, as we do in Section 4.2.

e proof relies on Lemma 3.1 and the examination of the samples. Two smoothing arguments over Λ are used: once to apply Lemma 3.1, and once to trade cosets for larger ε.

eorem 1 (Correctness of the short exact sampler). When Σ η ε (Λ ), Algorithm 2 is correct.

Moreover, let D be the distribution of its output. For ε < 1 2 , we have

sup v∈Λ D(v) D Λ,t,Σ (v) -1 6(δ + ε).
In particular, D is within statistical distance 3(δ + ε) of D Λ,t,Σ .

Proof. Let ε > 0 and v ∈ Λ, and as usual denote by T the torsion subgroup of Λ/Λ . Independence of the sampling oracles of lines 3 and 4 and law of total probability yields:

D(v) = Pr(u = v -u q | q = π(v)) Pr(q = π(v)).
By hypothesis on the oracle O q and Lemma 3.1, we have:

(8) Pr(q = π(v)) ∈ 1 -δ 1 + δ 1 -ε 1 + ε , 1 + δ 1 -δ 1 + ε 1 -ε • 1 |T| • D π(Λ),π(t),Σ (π(v)).
On the other hand we have π(u q ) = q and thus: ( 9)

Pr(u = v -u q |q = π(v)) = ρ Σ (v -u q -(Id -π)(t -u q )) ρ Σ (Λ -(Id -π)(t -u q )) = ρ Σ ((Id -π)(v -t)) ρ Σ (Λ -(Id -π)(t -u q ))
.

Because Σ η ε (Λ ) η ε (Λ ), we obtain that ρ Σ (Λ -(Id -π)(t -u q )) ∈ 1, 1 + ε 1 -ε • 1 |T| ρ Σ (Λ -(Id -π)(t -u q )) ∈ 1 -ε 1 + ε , 1 + ε 1 -ε 2 • 1 |T| ρ Σ (Λ -(Id -π)(t))
We then nd that:

D(v) ∈ 1 -δ 1 + δ 1 -ε 1 + ε 3 , 1 + δ 1 -δ 1 + ε 1 -ε 2 • ρ Σ (π(v -t)) ρ Σ (π(Λ) -π(t)) • ρ Σ ((Id -π)(v -t)) ρ Σ (Λ + (Id -π)(t))
Routine calculations conclude the proof.

Algorithm 2 Short exact sequence sampler

Input:

• A subla ice Λ ⊂ Λ, a centre t • an oracle O for D Λ , * ,Σ • an oracle O q over Λ Λ , 1+δ 1-δ -close to the pushforward of D Λ, ,Σ Output: v ∈ Λ following distribution statistically close to D Λ,t,Σ 1 if Λ = {0} then return 0 2 Compute π : Λ R → Λ R Λ R
, the orthogonal projection onto Λ ⊥ R for the norm induced by Σ -1

3 q ← O q Λ Λ , π(t), Σ ; u q ← Li (q, Λ) 4 u ← O (Λ , (Id -π)(t -u q ), Σ) 5 return u q + u 4. G
We now present two generic applications of this abstract sampler: domain extensions and restrictions, and a broad generalization of the so-called Klein/GPV sampler [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF]. e formers are simple, elementary but important illustrations of the use of the pushforward distribution; the la er extends the toolbox for Gaussian sampling in cryptography. In Section 8, we will present several concrete samplers in remarkable la ices using these generic constructions, reaching closer to the smoothing than the approaches used previously.

4.1. Domain extension and restriction.

4.1.1. Extension to an overla ice. Let Λ be a full-rank subla ice of Λ, so that the quotient Λ/Λ is of torsion (i.e. the free part of this quotient is reduced to {0}) and suppose that we have access to an oracle O for D Λ , ,Σ for a parameter Σ η ε (Λ ). By Lemma 3.1, the pushforward π D Λ, ,Σ is at distance at most ε 1-ε of the uniform distribution over Λ/Λ . Hence specializing Algorithm 2 with O and a uniform sampler for O q yields the following:

Corollary 1 (Domain extension). Let ε > 0 and Λ be a la ice, Λ one of its subla ices of nite index. For any oracle O realizing a discrete Gaussian sampling in Λ at any center and covariance Σ η ε (Λ ), there exists an algorithm sampling at distance at most 6ε of D Λ, ,Σ using at most one oracle call to O .

In a nutshell, the ability to sample in Λ and Λ/Λ enables to reconstruct samples in Λ: we do a domain extension of the discrete Gaussian over Λ to the overla ice Λ. Proposition 3 (Domain restriction). Let ε > 0 and Λ be a la ice and Λ one of its subla ices of nite index. For any oracle O realizing a discrete Gaussian sampling in Λ with covariance Σ η ε (Λ ), there exists a Gaussian sampler (for the same covariance) in Λ using on expectation

[Λ : Λ ] calls to O.
Proof. e procedure is as follows: get a sample x from O and return it if x ∈ Λ , otherwise restart. e probability of x ∈ Λ is exactly p = ρ Σ (Λ )/ρ Σ (Λ) by de nition of O. As such the expected number of repetitions before a success is (as the expectation of a geometric distribution)

1 p . Since Σ η ε (Λ ), Lemma 3.1 implies that p ∈ 1 [Λ:Λ ] [1, 1+ε 1-ε ], bounding 1/p by [Λ : Λ ].
e correctness of the process follows from conditional probabilities.

Remark. We point out the possible connection with the averaging recombination technique used in [START_REF] Aggarwal | Just take the average! an embarrassingly simple 2ˆn-time algorithm for svp (and cvp)[END_REF], where a domain restriction is performed, and samples are then combined with a domain extension from 2Λ to Λ (using exponentially many vectors).

4.2.

A ltration sampler. We now show how our short exact sequence sampler naturally extends to ltrations and allows to retrieve and generalize samplers appearing in cryptography, such as those in [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF][START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF][START_REF] Omas Prest | Gaussian Sampling in La ice-Based Cryptography[END_REF]. For example, in the most natural case where one would sample "coordinate-by-coordinate", our algorithm recovers Klein/GPV sampler. More generally it gives a family of new samplers for a given la ice, depending on how one decides to sort and "cut in subspaces" its input basis, o ering larger freedom in the design of sampling algorithms8 . 4.2.1. Smoothing parameter bound over a ltration. We rst highlight a new smoothing parameter bound deduced from a given ltration

{0} = Λ 0 ⊂ Λ 1 ⊂ • • • ⊂ Λ k = Λ of a la ice Λ.
It relies on repeatedly applying the splits of the smoothing parameter over the short sequences (Proposition 2) stemming from the ltration. Starting from the penultimate term Λ k-1 , we bound (ignoring here the exact values of ε to ease the exposition) the smooth-

ing parameter of Λ by max(η(Λ k-1 ), η(Λ/Λ k-1 )). Applying Proposition 2 to Λ k-1 , we have η(Λ k-1 ) max(η(Λ k-1 /Λ k-2 ), η(Λ k-2 )
). We go down in the ltration inductively until we reach Λ 1 . All in all, the smoothing parameter is dominated by the biggest term appearing in the spli ing.

Lemma 1. Let k 1 be an integer, Λ a la ice and ε 2 k . We have

η ε (Λ) min (Λ i ) i max i η ε k+1 Λ i Λ i-1 ,
where the minimum is taken over all possible ltrations of length k of Λ.

Proof. Let V i be the real space spanned by Λ i , and P i be the orthogonal projection onto V ⊥ i , where the orthogonality is for the quadratic form

x → x t Σ -1 x. Lemma 2.1 gives ρ Σ (Λ) ρ Σ (P k-1 (Λ)) • ρ Σ (Λ k-1
). Le ing P 0 be the identity, we obtain by induction

ρ Σ (Λ) k i=1 ρ Σ (P i-1 (Λ i )) = k i=1 ρ Σ (Λ i /Λ i-1 ).
Using the Poisson Summation Formula (7) and taking

Σ max i η ε/(k+1) (Λ i /Λ i-1 ) gives ρ Σ -1 (Λ ∨ ) k i=1 ρ Σ -1 Λ i Λ i-1 ∨ 1 + ε k + 1 k .
Calculations concludes the proof, using the fact that (1 + ε/(k + 1)) k < 1 + ε e term k + 1 is chosen to obtain a compact, readable statement with an identical smoothing quality for each quotient la ice. 9 e idea behind the above bound allows to mildly relax the smoothness condition over la ice cosets: instead of the whole la ice, it is only needed to smooth the "worst" of the successive quotients deduced from the ltration for the cosets of the whole la ice to have essentially the same mass.

For example, it was shown 10 in [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF], and subsequently used at the core of several practical constructions, that for any rank n la ice Λ,

η ε (Λ) min (b 1 ,...,bn) basis of Λ max 1 i n η ε n (Zb * i ),
where the b * i 's are the Gram-Schmidt vector of the corresponding basis. is bound corresponds to restricting Lemma 1 to ltrations of length n stemming from the b i 's as

Λ i = L(b 1 , . . . , b i )
. Indeed, we have that for any 0 i < n, Λ i+1 /Λ i is isometric to Zb * i (see also Section 2.1.2). While it could seems more likely that such a ne-grained ltration would give in general be er smoothing bounds, we actually show that there are practical cryptographic cases where one can improve the situation by carefully selecting a di erent and a priori coarsergrained ltration. 9 What ma ers in the proof is that i (1 + εi) 1 + ε, where εi is a given smoothing quality for Λi/Λi-1 and ε is the target quality for Λ.

10

In its usual form for a xed basis, the bound is ηε(Λ) Assume that we are given approximate oracles to sample discrete Gaussians in the sequence of la ices (Λ i+1 /Λ i ) i , and a deterministic li the rst call considers the short exact sequence

max 1 i n b * i • ηε(Z n ).
0 → Λ 1 → Λ → Λ Λ 1 → 0.
Algorithm 2 requires a pushforward oracle on Λ/Λ 1 , so since we do not have a priori an explicit access to it, we instantiate it as a recursive call over the quotient ltration

{0} = Λ 1 Λ 1 ⊂ Λ 2 Λ 1 ⊂ • • • ⊂ Λ Λ 1 .
Hence the callee now deals with the sequence 0

→ Λ 2 /Λ 1 → Λ/Λ 1 → Λ/Λ 2 → 0.
is is done until we reach the trivial sequence. en, the algorithm climbs its way back in the recursion tree, providing samples in the la ices Λ i+1 /Λ i .

Algorithm 3

Filtered sampler

Input: A filtration {0} ⊂ Λ 1 ⊂ • • • ⊂ Λ k = Λ, a parameter Σ > max 0 i<k η ε Λ i+1 Λ i and a center t ∈ Λ ⊗ R.
Output: v ∈ Λ following distribution statistically close to D Λ,t,Σ

1 if Λ = {0} then return 0 2 Compute π : Λ → Λ Λ 1 3 z ← FilteredSampler Λ i Λ 1 i , π(t), Σ 4 u ← Li (z, V 1 ) 5 u ← D Λ 1 ,(Id-π)(t-u),Σ 6 return u + u
eorem 2 (Correctness of the ltered sampler). Algorithm 3 is correct. Moreover, let D be the distribution of its output. For any ε < 1/k 2 , we have

sup v∈Λ D(v) D Λ,t,Σ (v) -1 (2k + 1)ε.
In particular, D is within statistical distance (k + 1)ε of D Λ,t,Σ .

It su ces to proceed by induction along the ltration repeatedly calling Algorithm 3.

Proof. At Step 5, the algorithm recalls itself on the ltration obtained by quotienting by its rst element. e rst time it happens, the input ltration is then

{0} ⊂ Λ 2 /Λ 1 ⊂ • • • ⊂ Λ/Λ 1 . Let V i = Λ i ⊗ R.
By isomorphism theorems, the quotient is then (isometric to) Λ/Λ 2 , and by induction, at the i-th call, the input ltration is therefore

{0} ⊂ Λ i+1 /Λ i ⊂ • • • ⊂ Λ/Λ i ,
with a corresponding ag of subspaces

(V i+1 ∩ V ⊥ i ) ⊂ . . . ⊂ (V ∩ V ⊥ i ).
By assumptions, the Gaussian oracle is always able to sample in the rst element Λ i+1 /Λ i of its input ltration. e standard deviation is always above the smoothing parameter of such la ices, Algorithm 3 outputs an element in the la ice thanks to the properties of Algorithm 1.

We now analyze the distribution of the outputs. Let ε > 0 and set δ = 1-ε 1+ε . We use the following loop invariant: if the input ltration contains k -1 elements and the target center is t , then the probability that Algorithm 3 outputs some vector v belongs to δ k-1 , δ 1-k • D Λ ,t ,Σ (v), where Λ is the la ice spanned by the input ltration. is hypothesis is satis ed for any ltration with 1 element. Let us assume now that it is true up to some k 1. By construction, we can write u = z+v for some v ∈ V 1 . In particular, we have

(Id-π)(t-u) = (Id -π)(t) -v.
Next, let P (z) resp. P (u ) the probability to obtain z resp. u . Orthogonality

gives us ρ Σ (u + u -t) = ρ Σ (z -π(t))ρ Σ (u -(Id -π)(t) + v
). e induction hypothesis then yields

P (z)P (u ) ∈ δ k-1 , δ 1-k • ρ Σ (z -π(t)) ρ Σ (Λ/Λ 1 -π(t)) • ρ Σ (u -(Id -π)(t) + v) ρ Σ (Λ 1 -(Id -π)(t) + v) = δ k-1 , δ 1-k • D Λ,t,Σ (u + u ) • ρ Σ (Λ -t) ρ Σ (Λ/Λ 1 -π(t))ρ Σ (Λ 1 -(Id -π)(t) + v) . Since Σ η ε (Λ 1 ), we have ρ Σ (Λ 1 -(1-π)(t)+v) ∈ [δ, δ -1 ]•ρ Σ (Λ 1 -(Id-π)(t))
. With a last orthogonality argument, we obtain our claim on the distribution, using that 1+ε

1-ε k-1 < 1+kε 1-kε when ε < 1 k 2 .
4.3. Recovering some known samplers.

max i η ε (Λ i+1 /Λ i ) = max i η ε (b * i Z) = η ε (Z) • max i ( b * i ).
0 -→ m 1 O K -→ Λ -→ Λ m 1 O K -→ 0
where once again the submodule m 1 O K shall be understood as a subla ice through the canonical embedding map. Now remark that an oracle call is made on the modules of rank 1 m 1 O K and Λ/m 1 O K . However, these modules are also modules of rank 2 over the cyclotomic eld of conductor 2 k-1 . As such, for each of them we can apply the same technique recursively, requiring samples in modules of rank 2 over smaller and smaller elds, until we eventually reach Q, where we know how to sample.

4.3.4.

A ltered tensor sampler. Let A be a la ice given with a complete ltration {0} ⊂ A 1 ⊂ . . . ⊂ A ⊂ A and another la ice B. Suppose that we have a gaussian sampler O in B. en remark that the tensor ltration

{0} ⊂ A 1 ⊗B ⊂ • • • ⊂ A ⊗B ⊂ A⊗B is a ltration of A⊗B and that since each quotient A i+1 /A i is of dimension 1, the quotients (A i+1 ⊗ B)/(A i ⊗ B)
are actually isometrics to scalings of B -the scaling factor being exactly the covolume of the line A i+1 ⊗ /A i . Hence, from the sampler O, we can sample in A ⊗ B by the calls generated when applying the Filtered Sampler to our ltration. 11 We make a slight abuse of notations here by silently identifying a submodule with the corresponding subla ice of the la ice a ached to the module. To be perfectly formal, we shall understand the elements of the ltration as viewed under the canonical embedding map recalled in Section 2.3.1. iteratively corrects the transformation to the space a ached to the ltration one subspace at a time. A global approach to the problem consists in considering any la ice as a linear transformation of another la ice, but not always Z n . is gives the following bound on the smoothing parameter, possibly implicit in previous works.

Lemma 2. Let Λ be a la ice of rank n in R m , then η ε (Λ) inf s 1 (T) • η ε (L(C)),
where the in mum is taken over all pair (T, C) such that Λ = L(TC) and C ∈ R n is invertible.

Proof. Let T, C be any such decomposition of a given basis B of Λ. e basis of the dual la ice Λ ∨ is then B ∨ = B(B t B) -1 , and as such for any vector z ∈ R m we have

(B ∨ z) t (B ∨ z) = z t (B t B) -1 z = (C -t z) t (T t T) -1 (C -t z)
. is implies that for any s > 0, we have ρ 1

s 2 (Λ ∨ ) = ρ T t T s 2 (L(C) ∨ ). Asking s η ε (Λ) is thus equivalent to asking that s 2 (T t T) -1 η ε (L(C)) 2 •
I n , as stated.

Sampling by linear transformation.

e global approach is an algorithmic formulation of the proposition of Peikert [26, eorem 3.1]. For the sake of simplicity, we will restrict ourselves to the case of continuous perturbations in our presentation. As explained, on a high level the transformation of a xed la ice distorts the geometry in the initial space and consequently any ellipsoid in that space. e bias can be corrected to any target ellipsoidal shape by adding a large enough perturbation, and up to rescaling.

Going formal, one can prove the correctness of the approach thanks to the nice properties of Gaussian distributions, and the scaling factor appears implicitly as a condition of positivede niteness involving the smoothing parameter of the initial la ice.

eorem 3 (Correctness of the linear sampler). Let r η

ε (Λ(C)). If s n (∆) > r 2 • s 1 (T) 2 ,
then Algorithm 4 is correct. Moreover, let D be the distribution of its output. For ε < 1/2, we have

sup v∈Λ D(v) D Λ,t,∆ (v) -1 4ε.
In particular, D is within statistical distance 2ε of D Λ,t,∆ .

Proof. e support of the output distribution is correct by construction. By construction, the probability of sampling some p ∈ C R := span R (C), x ∈ L(C) and outpu ing y is the marginalized distribution

P (y) = det(Σ p ) -1/2 • C R ρ Σp (p) • ρ r 2 (x -T t -p) ρ r 2 (L(C) -T t -p) dp.
Gaussian functions have also good multiplicative properties (see for instance [26, Fact 2.10]):

there exists 12 a positive de nite matrix Σ and a vector t , both over C R , such that:

ρ Σp (p)ρ r 2 (x -T t -p) = ρ Σ (x -T t)ρ Σ (p -t ),
where we also use that Σ p + r 2 = Σ. Combining these two equalities, we rewrite the distribution of the output as

P (y) = det(Σ p ) -1/2 • ρ Σ (x -T t) • C R ρ Σ (p -t ) ρ r 2 (L(C) -T t -p) dp.
By de nition of the pseudo-inverse, we have that T y = x and that TT is the orthogonal projection P onto Λ R . is gives(x -T t) t Σ -1 (x -T t) = (y -t) t P t ∆ -1 P(yt) and we obtain

ρ Σ (x -T t) = ρ ∆ (y -t).
Observe that if m = n, we have T = T -1 so that P = I n and the result holds as well. By assumptions on r and thanks to Lemma 2.1, we now have

P (y) ∈ 1, 1 + ε 1 -ε • det Σ det Σ p 1/2 • ρ ∆ (Λ -t) ρ r 2 (L(C)) • D Λ,t,∆ (y),
and summing over all y to handle the normalization constants, we deduce

P (y) ∈ 1 -ε 1 + ε , 1 + ε 1 -ε • D Λ,t,∆ (y).
Our claims on the maximum relative error and the statistical distance follow. Lastly, we show that the condition on the singular values is su cient. e algorithm is correct as soon as Σ r 2 I n , or equivalently when s 1 (T t ∆ -1 T) < r -2 . Using standard properties of operator norms, we see that s 1 (T t ∆ -1 T) s 1 (T) 2 • s n (∆) -1 , and the results follow.

Algorithm 4 Linear sampler

Input:

• Two matrices T ∈ R m×n , C ∈ R n×n with m n and C invertible such that TC = B is a basis of a la ice Λ;

• a center t ∈ Λ ⊗ R;

• a parameter r 0 and a positive definite matrix ∆ ∈ R m×m such that

Σ := (T t ∆ -1 T) -1 r 2 I n ;
Output: y ∈ Λ with distribution statistically close to D Λ,t,∆ .

1 Σ p ← Σ -r 2 I 2 p ← N Σp 3 x ← D L(C),T t+p,r 2 /* T is the pseudo-inverse */ 4 ; return y := Tx
Remark. is sampler also relies on a continuous Gaussian sampler, but fundamentally, the required property is that the product of the density functions of the perturbation and the la ice sampler can be understood: this is the core fact used to ensure the correctness of the output.

Example of elementary instantiations.

is abstract framework allows to easily recover known samplers and extend them in few directions. We already highlighted that using C = I n and full-rank la ices retrieves Peikert's sampler [START_REF] Peikert | An e cient and parallel Gaussian sampler for la ices[END_REF].

• In particular, U is upper triangular with 1's on its diagonal, and therefore its own Gram-Schmidt orthogonalization corresponds to the identity matrix. By Lemma 1, we thus have η ε (L(U)) η ε/(n+1) (Z). Using the standard bound η ε (Z) ln(2(1 + 1/ε)/π, the sampler with that decomposition reaches standard deviations very close to Algorithm 4,[START_REF] Conway | Fast quantizing and decoding and algorithms for la ice quantizers and codes[END_REF] in an approximate version.

(R) • η ε (Z n ) = s 1 (B) • η ε (Z n ). Alternatively, as s 1 (Q) = 1,
s 1 ( B) • η ε (Z n ). is sampler is used in [15,
• Hybrid sampler: More generally, one can decompose the ambient space of Λ in orthogonal subspaces, use a sampler in each subspaces and obtain a discrete Gaussian in Λ by multiplying by a block-orthogonal matrix. is approach is similar to the hybrid sampler of [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF][START_REF] Omas Prest | Gaussian Sampling in La ice-Based Cryptography[END_REF], when decomposing the la ice.

A :

As a direct application of Section 5, we present a novel (up to our knowledge) approach to sample in tensor products of la ices. ey appear naturally with rings of cyclotomic integers of smooth conductors. In particular, one could use the algorithm of this section to sample in R p q k for p = q prime, in several ways depending on how the ring is embedded in a euclidean space.

6.1. Tensors and related bounds.

Let A ∈ R m 1 ×n 1 and B ∈ R m 2 ×n 2 . Recall that L(A) ⊗ L(B) = L(A ⊗ B),
where A ⊗ B is the Kronecker product between these matrices:

A ⊗ B =     a 1,1 B a 1,2 B • • • a 1,n 1 B . . . . . . . . . . . . a m 1 ,1 B a m 1 ,2 B • • • a m 1 ,n 1 B .    
e mixed product property states that

A ⊗ B = (A ⊗ I m 2 )(I n 1 ⊗ B) = (I m 1 ⊗ B)(A ⊗ I n 2 ).
Tensoring with identities preserves geometric properties.

Lemma 3. Let A ∈ R m×n of full column rank, k = positive integers, and ε < 1/2. We have:

(1) s 1 (A ⊗ I k ) = s 1 (I ⊗ A) = s 1 (A); (2) η ε (L(I k ⊗ A)) η ε/k (L(A)) η 2ε (L(I k ⊗ A)). (3) η ε (L(I k ⊗ A)) = η ε (L(A ⊗ I k )); Proof. Since I k ⊗ A = diag(A, . . . , A), we have s 1 (I k ⊗ A) = s 1 (A). Next, the dual basis of I k ⊗ A is I k ⊗ A ∨ . We then have ρ 1/s (L(I k ⊗ A) ∨ ) = ρ 1/s i k L(A) ∨ = ρ 1/s (L(A) ∨ ) k . Taking s = η ε (L(I k ⊗ A)) gives ρ 1/s (L(A)) (1 + ε) 1/k 1 + ε/k, so s η ε/k (L(A))
.

Similarly, taking s = η ε/k (L(A)) gives ρ 1/s (L(I k ⊗ A)) (1 + ε/k) k 1 + 2ε
, and the second property follows. To conclude, one checks that for all k, there always exist permutations

P ∈ R km×km , Q ∈ R kn×kn such that P(A ⊗ I k )Q = I k ⊗ A.
Since permutations matrices are isometries of the standard Euclidean norm, we have but its e ectiveness does not rely on Gram-Schmidt orthogonalization. In essence, this is the same tradeo as between Peikert's randomized round-o approach [START_REF] Peikert | An e cient and parallel Gaussian sampler for la ices[END_REF] and Klein's randomized nearest plane (e.g., [START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF]).

P(A ⊗ I k )Qx = (A ⊗ I k )Qx for all x ∈ R kn . Adding that Q is an invertible transformation of R kn that stabilizes Z kn , we obtain s 1 (A ⊗ I k ) = s 1 (I k ⊗ A) and ρ 1/s (L(I k ⊗ A)) = ρ 1/s (L(A ⊗ I k )).
Lemma 6.1. Let Λ = L(A) ⊗ L(B) for matrices A ∈ R m 1 ×n 1 and B ∈ R m 2 ×n 2 of full rank,
where m i n i . We have

η ε (Λ) min s 1 (A) • η ε/(2n 1 ) (L(B)), s 1 (B) • η ε/(2n 2 ) (L(A)) .

6.2.

A sampling algorithm for tensor lattices. Using Algorithm 4, this bound directly translates into Algorithm 5, where it is assumed that oracles for discrete Gaussian sampling in L(A)

and L(B) are given.

Algorithm 5

Tensor sampler

Input: Two matrices A ∈ R m 1 ×n 1 , B ∈ R m 2 ×n 2 with m i n i , giving a basis of Λ = L(A ⊗ B); a center t ∈ Λ ⊗ R; r 0; a positive definite matrix ∆ ∈ R m 1 m 2 ×n 1 n 2
Output: y ∈ Λ with distribution statistically close to the discrete Gaussian

D Λ,t,∆ . 1 Select (T, C) ∈ {(A ⊗ I m 2 , I n 1 ⊗ B), (I m 1 ⊗ B, A ⊗ I n 2 )} minimizing s 1 (T) • η ε (L(C)) 2 Σ ← (T t ∆ -1 T) -1 3 return Algorithm 4(T, C, t, ∆, Σ, r) Corollary 2 (of eorem 3). Let Λ = L(A)⊗L(B) for matrices A ∈ R m 1 ×n 1 and B ∈ R m 2 ×n 2 of full rank, where m i n i . Let (T, C) ∈ {(A ⊗ I m 2 , I n 1 ⊗ B), (I m 1 ⊗ B, A ⊗ I n 2 )} be the pair minimizing s 1 (T) • η ε (L(C))
, and let also r η ε (C). Algorithm 5 is correct when

s n (∆) r 2 • s 1 (T) 2 .
Moreover, let D be the distribution of its output. For ε < 1/2, we have

sup v∈Λ D(v) D Λ,t,∆ (v) -1 4ε.
In particular, D is within statistical distance 2ε of D Λ,t,∆ .

e above statement is formulated to achieve the "smallest possible" covariance matrix, which is o en the goal in practice for security reasons. In other contexts, it might happen that the other decomposition is chosen or needed. e choice of ε in our formulation somewhat hides a dimensional factor coming from tensoring A or B with an identity matrix, as expressed in the second property in Lemma 3.

A .

As we will be dealing with remarkable la ices, it is o en possible to have a very accurate understanding of their meaningful quantities. e smoothing parameter is no exception and is the topic of this section, of independant interest. Our main ingredient here is the general identi cation of the Gaussian mass with the theta series of a la ice:

ρ 1/s 2 (Λ ∨ ) = 1 + κ(Λ ∨ ) • exp(-πs 2 ) λ 1 (Λ ∨ ) 2 + κ 2 exp(-πs 2 ) n 2 2 + • • • = θ Λ ∨ (exp(-πs 2 )), (10)
where we have sorted the vectors of Λ ∨ by their increasing squared norm 13 , and κ(Λ ∨ ) is the kissing number of Λ ∨ . Let now q = exp(-πs 2 ), then determining the smoothing parameter of a la ice amounts to nd q such that θ Λ ∨ (q)-1 = ε. is can always be done by series reversion: there exists a series S such that S(θ Λ ∨ (q) -1) = q. Routine calculations then show

s = 1 π ln 1 S(ε)
.

Note that this is an exact expression, and formulae from formal series theory even give the coe cients of S. Of course, calculating the actual value for some la ice Λ requires knowing those of θ Λ ∨ .

Let us give more details about series reversion. As mentioned, a standard fact is that if

h(z) = h 1 z + h 2 z 2 + • • •
is a power series, then there always exists another power series

g(z) = g 1 z + g 2 z 2 + • • • such that g(h(z)) = z.
In other words, the existence of the reversion is no concern. Plugging the expression of h and equating the coe cients gives an explicit formula for the coe cient of g from those of h. In the general case, the ones on the expansion of g are:

g 1 = h -1 1 g 3 = -h -5 1 (2h 2 2 -h 1 h 3 ) g 2 = -h -3 1 h 2 g 4 = -h -7 1 (5h 1 h 2 h 3 -h 2 1 h 4 -5h 3 2 ) (11)
e interested reader can nd a general expression for the n-th coe cient with Morse-Feshbach's formula. In the general case, the Gaussian mass does not exactly correspond to a power series, even up to renormalization. is is not a concern as one can extend the reversion approach to rational exponents, see the lemma below.

Lemma 4. Let Λ ⊂ Q m be any la ice, and let T Λ (q) = θ Λ (q) -1 = κ 1 q λ 1 (Λ ∨ ) 2 + . . . . ere exists a unique series S(q) = (q/κ 1 ) 1/λ 1 (Λ ∨ ) 2 + . . . such S(T Λ (q)) = q.

Proof. Since Λ is rational, there exists an integer d > 0 such that dΛ ∨ ⊂ Z m . By considering T (q) = T Λ (q d 2 ), we can assume without loss of generality that T Λ is a power series, that is, all exponents are positive integers. We let n = d 2 λ 1 (Λ ∨ ) 2 , and we consider now the formal series T (X) = κX n + . . .

= κX n (1 + T (X)) ∈ R[[X]
] de ned by the coe cients of T Λ . We can de ne formally the n-th root of 1 + T (X) using the coe cients of the Taylor expansion of x → x 1/n . en, the formal series

U (X) = κ 1/n X(1 + T (X)) 1/n ∈ R[[X]
] is such that U (X) n = T (X), and its rst term is κ 1/n X. We can apply formal series reversion: there exists

a formal series U -1 (X) such that U -1 (U (X)) = X. Now, the series S(X) = U -1 (X 1/n ) ∈ R[[X 1/n ]] satis es that S(T (X)) = X.
ankfully, for all exceptional la ices, the rst terms of the theta series are well-known (the minima and kissing numbers of remarkable la ices are o en found in [START_REF] Conway | Sphere Packings, La ices and Groups. Grundlehren der Mathematischen Wissenscha en 290[END_REF], among others). We can use them with the previous discussion to obtain the following estimates.

Lemma 5. For any la ice Λ, we have the following estimate, valid for ε > 0:

η ε (Λ) = 1 λ 1 (Λ ∨ ) • 1 π ln κ(Λ ∨ ) ε 1 + o(1) .
In particular, we have the following approximations:

• η ε (Z n ) ≈ 1 π ln( 2n ε ) and for n 5, η ε (D n ) ≈ 1 π (ln( 2n ε ); • η ε (A n ) ≈ 1 λ 1 (A ∨ n ) • 1 π ln 2(n+1) ε ≈ n+1 n • η ε (Z n ); • η ε (E 8 ) ≈ 1 √ 2 • 1 π ln( 240 ε ) and η ε (L) ≈ 1 2 • 1 π ln( 196560 ε )
, where L is the Leech la ice.

Proof. All these estimates are obtained following the same pa ern: identify the theta series θ of the dual, nd the reversion series S such that S(θ(z) -1) = z; then set z = exp(-πs 2 ) and the smoothing is reached when θ(z) -1 = ε. In our context where z = exp(-πs 2 ), we only really care about the rst few terms in the expansion. As explained earlier in the section, if S is the reversion of

ρ 1/s (Λ ∨ ) -1 = κz λ 2 1 + • • • , where κ = κ(Λ ∨ )
is the kissing number of the dual and λ 1 = λ 1 (Λ ∨ ) its minimum in the Euclidean norm, then the smoothing parameter is obtained as

η ε (Λ) = 1 π ln 1 S(ε)
.

From the expression of the coe cient in the reversion, one checks that

S(ε) = κ -1 ε 1 λ 2 1 1 + o(1) ,
which gives our rst claim:

S(ε) -1 = κε -1 λ 2 1 1 + o(1) -1 = κε -1 λ 2 1 1 + o(1) .
Checking the well-known theta series of these exceptional la ices in [START_REF] Conway | Sphere Packings, La ices and Groups. Grundlehren der Mathematischen Wissenscha en 290[END_REF] is enough to obtain our estimates.

In Lemma 5, the estimate of η ε (Z n ) is not new, but the proof strategy we give is. e second result can be understood intuitively as follows: D ∨ n is the disjoint union of Z n and Z n + 1 2 1. It tells us that D n and Z n have almost equivalent smoothing, as the rst term in the theta series of their duals is the same. Additionally,

λ ∞ 1 (D ∨ n ) = 1 2
, so that the usual bound 14 obtained from the shortest vector of the dual in the ∞ norm would give an overestimate by a factor ≈ 2.

S is section collects various approaches to e ciently sample Gaussian in the remarkable

la ices A n , D n and E 8 (i.e., root la ices) and the Barnes-Walls, Leech, and Nebe la ices. On the one hand, some of them will appear to be important building blocks for sampling cyclotomic integers, be incorporated in cryptographic gadget constructions, and can be seen as base cases or elementary functions to construct samplers on arbitrary la ices by combination (in the same way Klein's and Peikert's samplers are built around one-dimensional samplers). On the other hand, they are also a good way to illustrate practical use cases of our generic samplers from the previous sections. 8.1. Sampling in root lattices. Our ad-hoc samplers for the root la ices rely on exceptional orthogonal decompositions involving such la ices, and their close relationship in general. We will use properties of root la ices gathered in Section 2.3. 8.1.1. Sampling in roots. We start with samplers for the root la ices of small dimensions, as well as the D n family. ey are based on the ability to juggle between restrictions and extensions of la ices using Proposition 3 and Corollary 1, and exceptional isometries and geometric relations between them [START_REF] Martinet | Perfection and Eutaxy[END_REF]Chap. 4.6]. 14 From e.g. [25, Lemma 3.5], we have ηε(Λ) λ ∞ 1 (Λ ∨ ) -1 • ηε(Z n ) for all rank n la ices. While out of the scope of the present paper, it is possible to give a bound depending on λ1(Λ ∨ ) in the 2-norm instead, without a √ n loss as in [START_REF] Peikert | Limits on the hardness of la ice problems in lp norms[END_REF]Lemma 3.5], unconditionnally on ε contrary to [START_REF] Peikert | Pseudorandomness of ring-LWE for any ring and modulus[END_REF]Lemma 2.6], but involving the kissing number of the dual. eorem 4. We can sample e ciently and at a standard deviation right above the smoothing parameter in the following root la ices:

D n for all n > 1, A 2 , A 3 , A 4 , A 5 , A 6 , A 8 , E 6 , E 7 , E 8 .
We now detail these samplers.

8.1.2. Sampling in the face-centered la ice D n . e D n la ice can be described as the vectors of Z n with coordinates in the canonical basis (e i ) i n summing to an even number. Its index

in Z n is 2.
is congenial de nition leads to a very natural rejection-based approach from samples over Z n : a sample either belongs to D n or either to its non-zero coset (with almost equiprobability above the smoothing parameter). In other words, it is an instantiation of the domain restriction approach of Proposition 3, from which Proposition 8.1 is obtained.

Algorithm 6 Face centered cubic sampler

Input: A parameter σ η ε (D n ) and a center t = t i e i ∈ R n .

Output: v ∈ D n following distribution statistically close to D Dn,σ,t ere exists an isometry between D 3 and A 3 (coming from the exceptional Lie isomorphisms in small dimensions), which allows us to transfer the previous sampler on D 3 into a sampler for A 3 . One possible isometry consists in sending (1, 1, 0) to (1, -1, 0, 0), (1, 0, 1) to (1, 0, -1, 0) and (0, 1, 1) to (1, 0, 0, -1). Indeed, one checks that both these bases have the same Gram matrix by direct computation. Hence we can sample in A 3 with standard deviation above σ η ε (A 3 ) using (an expected number of) three samples in Z 4 .

1 repeat 2 z 1 ← D Z,σ,t 1 , . . . , z n ← D Z,σ,tn 3 until z i ∈ 2Z 4 return z = z i e i

Remark.

A similar algorithm would enable to sample in the dual la ice e E 8 la ice (also known as the Gosset la ice) is an unimodular la ice in R 8 . It belongs to the class of Barnes-Wall la ices, as one of its rst non-trivial member. It is not isometric to Z 8 , and realizes the densest la ice sphere packing in dimension 8. As seen e.g. in [START_REF] Conway | Fast quantizing and decoding and algorithms for la ice quantizers and codes[END_REF][START_REF] Martinet | Perfection and Eutaxy[END_REF], it can be wri en as a disjoint union of cosets as

D ∨ 3 = D 3 ∪((1/2, 1/2, 1/2)+ D 3 ) (disjoint union).
E 8 = D 8 ∪ (1/2, . . . , 1/2) + D 8
, where D 8 is the la ice of integer vectors with coordinates summing to an even number. is leads to the following sampling algorithm, where we let h = (1/2, . . . , 1/2).

is time, it is an instantiation of the domain extension sampler of Corollary 1, from which Proposition 8.2 is obtained.

Algorithm 7 E8 sampler

Input: A parameter σ η ε (D 8 ) and a center t ∈ R 8 .

Output: v following distribution statistically close to D D 8 ,σ,t

1 b ← Bernoulli 2 z ← Algorithm 6(σ, t -b • h) 3 return b • h + z Proposition 8.2.
ρ σ (v-t) ρσ(v-t)
otherwise restarts. It can be veri ed that the output distribution is close to

σ ≈ η ε (E 8 )
and the average number of repetitions is ere exists a special isometry between A 8 and a subla ice of E 8 . Indeed, if (e i ) i denotes the canonical basis of R 8 , the vectors h = ( 1 2 , . . . 1 2 ) and b i = e i + e i+1 for 1 i 7 all belong to E 8 , and their Gram matrix is identical to the Gram matrix of the basis (f 1 -f i ) 1 i 8 of A 8 , where (f i ) i is the canonical basis of R 9 . As det A 8 = 3 and E 8 is unimodular, we expect only 3 tries in average for a sample in E 8 to belong in the la ice isometric to A 8 , which leads to the following algorithm. e acceptance criteria is obtained by identifying the subla ice isometric to A 8 , and the rest is the domain restriction approach from Section 4.1.

N = ρσ(E 8 -t) ρ σ (E 8 -t) ≈ ( σ σ ) 8 . For practical parameters (σ = η ε (D 8 ), σ = η ε (E 8 )) with ε = 2 -36 ,

Algorithm 8 A8 sampler

Input: A parameter σ max(η ε (D 8 ), η ε (A 8 )) and a center t ∈ R 3 .

Output: v following distribution statistically close to D A 8 ,σ,t show that Λ = {x ∈ E 8 : x, u ∈ 3Z}, which means that Algorithm 8 outputs vectors in the correct la ice. at Λ is included in this set is clear from its basis vectors. For the reverse inclusion, let x be in the set, and let a 1 = x, u /3 ∈ Z. As x ∈ E 8 in particular, we also know that x is either in D 8 either in h + D 8 . In the rst case, we can write x = i x i e i with x i ∈ Z for all i, and such that x i = 2k for some k ∈ Z. and then we have

1 repeat 2 z ← E8sampler(σ, t) 3 until z 1 -z 2 -• • • -z 8 ∈ 3Z
x 1 -k = 3 2 a 1 ∈ Z, so that a 1 is even. erefore, for 2 i 8, a i = x i -a 1 /2 is an integer. In the second case, x = i (x i + 1
2 )e i with x i ∈ Z such that i x i = 2k for some k ∈ Z. en we have e Gosset la ice E 8 contains copies of A 2 . As explained in [7, Chap. 4, Sec. 8.6], this is the case for example of the la ice generated by the vectors u 1 = e 1 +e 8 and u 2 = 1 2 1, where (e i ) i is the canonical basis for R 8 -it shares indeed the same Gram matrix as A 2 -but there are many others. is choice yields a linear isometry de ned by φ 1 (u i ) = b i , where b 1 = (-1, 1, 0) and b 2 = (-1, 0, 1) is known as the Korkine-Zolotarev basis of A 2 . is serves as a de nition for the root la ice E 6 as the set of vectors in E 8 orthogonal to Λ.

x 1 -k = 3 2 (a 1 + 1) ∈ Z, so that a i is odd, which means that a i = x i -(a 1 + 1)/2 is an integer. In each cases, we nd that x = a 1 h + a 2 b 1 + • • • a 8 b 7 ,
In other words, we have a subla ice E 6 ⊥ A 2 in E 8 , where the containment has index 3.

Combining the restriction sampler from Proposition 3 with Lemma 3.2, we can obtain a sample in each la ice E 6 and A 2 every three tries in average. First use the map φ 1 to sent the target center in span(u 1 , u 2 ), then sample from Algorithm 7 until the output is in E 6 ⊥ A 2 , and map the result back.

Although simple and e cient, this approach rather ine ciently uses the available randomness. In our applications, we need large batches of samples of A 2 . We show how to amortize the randomness expenses by using an additional exceptional decomposition. From [22, eorem 4.6.10], there is another index 3 containment as A 2 ⊥ A 2 ⊥ A 2 ⊂ E 6 . More precisely, there are isometries φ 2 , φ 3 , φ 4 from A 2 to some pairwise-orthogonal subla ices of E 6 . en the procedure is as follow: map the target center t to t = i φ i (t), and sample around t with Algorithm 7. In the orthogonal decomposition of R 8 given by the four copies of A 2 , the resulting sample can be wri en x = i x i , and we may keep any x i belonging to (a copy of) A 2 . e correctness proof is again obtained by combining Proposition 3 with Lemma 3.2. Every 9 tries in average, we now obtain 4 samples. Expressed in terms of the underlying samples in Z, this improves the randomness loss from 1 every 48 to 1 every 36, a bit be er than a 30% improvement. Below we give the version that be er amortizes its randomness usage.

Algorithm 9 A2 sampler

Input: A parameter σ max(η ε (D 8 ), η ε (A 8 )) and a center t ∈ R 3 .

Output: (x 1 , . . . , x 4 ), each following a distribution statistically close to D A 2 ,σ 2 ,t

1 Compute the isometries φ 1 , . . . , φ 4

2 c ← φ 1 (t) + • • • + φ 4 (t) 3 repeat 4 z ← E8sampler(σ 2 , c) 5 until z = z 1 + . . . + z 4 ∈ A 2 ⊥ A 2 ⊥ A 2 ⊥ A 2 6 return (φ -1 1 (z 1 ), . . . , φ -1 4 (z 4 ))
Lastly, we deal with the question of the actual width reach by the sampler. ere are no smoothing condition coming from Lemma 3.2, so we can focus our a ention on the subla ice

E 6 ⊥ A 2 .
Using Lemma 2.2 and the de nition of the smoothing parameter, we obtain η ε (E 6 ⊥

A 2 ) max η 3ε (E 6 ), η 3ε (A 2 ) . For small enough ε, we have η ε (E 6 ) η ε (A 2 ), which means that we can sample in A 2 at optimal width with Algorithm 9.

8.1.7. Sampling in the E 7 la ice. We make use of the (dual covering) [START_REF] Martinet | Perfection and Eutaxy[END_REF]Chap.4,p.118]). Hence using Algorithm 7 we can use our E 8 sampler to sample into L and project orthogonally onto E ∨ 7 . We now use the fact that since E 7 is integral it is contained in its dual and use the Proposition 3. As

L = (E ∨ 7 ⊥Z) = E 8 ∪ 1 2 f + E 8 where f = (0. . . . , 0, 1, 1) T ∈ Z 8 (see
|E 7 | = 2,
the quotient E ∨ 7 /E 7 is of cardinality 4, meaning that we expect 4 repetitions of this process on average.

Sampling in A ∨

n . e following algorithm is described for the sake of masochist pleasure, as a hurtful reminder that proofs are never checked enough. It simply uses the identi cation

A ∨ n = π 1 ⊥ (Z n+1
), where 1 = (1, . . . , 1) More precisely, the identi cation above leads to the short exact sequence 0

→ Z • 1 → Z n → A ∨ n → 0. We readily see that η ε (Z • 1) = √ n • η ε (Z),
giving the reachable Gaussian width. e correctness and quality follow from Lemma 3.1.

Algorithm 10 A ∨ n sampler

Input: A parameter σ > 0 and a center t ∈ 1 ⊥ .

Output: v ∈ A ∨ n following distribution statistically close to D A ∨ n ,t,σ 2 1 z ← D Z n+1 ,t ,σ 2 2 y ← z -( 1 n+1 j z j ) n+1 i=1 3 return y
For completeness, we succinctly describe an algorithm in the special case n = 2, where we actually reach optimal width. As any rank 2 la ice, A 2 is similar to its dual A ∨ 2 (we also say that they are isodual). In this case, the similarity has scaling factor 1 e rotation preserves the norm of the scaled sample, and by standard argument on discrete Gaussians, the resulting width is ese improvements also stem from an additional ingredient: the ltrations we highlight are close to being block-orthogonal. A practical bene t yielded by such ltrations is the more parallelizable nature of the resulting processes. While the next result is straightforward, we highlight it for the sake of reusability.

1 √ 3 η ε (A 2 ) = η ε (A ∨ 2 ) ≈ 1 √ 2 η 2ε/3 (Z 2 ).
Proposition 5. Let n > k be integers and n = (k +1)q +r the euclidean division of n by (k +1).

en A n admits a ltration as

0 = Λ 0 ⊂ Λ 1 ⊂ Λ 2 ⊂ • • • ⊂ Λ q ⊂ A n ,
where for all 1 i q, Λ i is isometric to an orthogonal direct sum of i copies of A k .

e proof amounts to identifying several copies of smaller A k la ices, orthogonal to each other, in the standard basis of A n , by appropriately permuting the columns (for instance the rst two vectors in the usual basis of A 3 generate a copy of A 2 ) and packing the remaining vectors all together in the nal part of the ltration.

Proof. Recall that for any n > 1, the A n la ice admits the basis

A n =              1 0 0 • • • 0 -1 1 0 • • • 0 . . . -1 . . . . . . . . . 0 0 . . . 1 0 0 0 • • • -1 1 0 0 • • • 0 -1              ∈ Z (n+1)×n .
By assumption on q and k, we have in particular n = (k + 1)q + r = kq + q + r. ere exists a permutation on the columns of A n that gives a reordered basis

B n =           A k C 1 A k C 2 . . . . . . A k C q • • • C q+1 A r           ∈ Z (n+1)×n ,
where

C 1 = (ε (1)
i,j ) ∈ Z (k+1)×q : ε

(1) i,j =    1 (i, j) = (k + 1, 1)
0 otherwise,

C t = (ε (t) i,j ) ∈ Z (k+1)×q for 1 < t q : ε (t) i,j =          -1 (i, j) = (1, t -1) 1 (i, j) = (k + 1, t) 0 otherwise, C q+1 = (ε (q) i,j ) ∈ Z (r+1)×q : ε (q) i,j =    -1 (i, j) = (1, q) 0 otherwise.
. Immediately, the result follows.

e remaining vectors have to be dealt with, but it turns out not to impact what follows. is allows to sample over the A n la ice using Algorithm 3. Let us call B n the basis corresponding to the ltration of Proposition 5. At the deepest level of recursion, we sample in the la ice Λ/Λ q , using for example Klein sampler, or equivalently, Algorithm 3 with the ltration corresponding to the projection of the last q + r columns of B n orthogonally to V ⊥ q = Span(Λ q ) ⊥ . en, all subsequent samplings happen in (a copy of) A k , and for example, when k = 8, one calls Algorithm 8 for these last q steps. For the sake of clarity, we restrict ourselves to k = 8 and give an equivalent iterative algorithm. and D be the distribution of the A n sampler, for σ max{ 9/8 • η ε (Z 8 ), η ε (A 8 )}. en for a small enough ε, the statistical distance between D and D An,t,σ 2 is at most (q + 1)ε.

Proof of eorem 5.

Let 0 = Λ 0 ⊂ Λ 1 ⊂ Λ 2 ⊂ • • • ⊂ Λ q ⊂
A n be the ltration given by Proposition 5. Since we use the Klein sampler as a base sampler in the quotient Λ q , the result holds using eorem 2 when

σ max σ , η ε (A k ), max 1 i q+r b * kq+i η ε (Z)
where σ is required by the sampling over A k and b * i is the i-th vector in the Gram-Schmidt orthogonalization of B n . We implement the sampling over A k with the tailored A 8 sampler Algorithm 8 that just needs σ η ε (A 8 ). erefore it su ces to estimate b * i . A routine computation veri es that the Gram-Schmidt orthogonalization of A n is

A n =           1 1 2 • • • 1 n -1 1 2 • • • 1 n 0 -1 • • • 1 n . . . . . . . . . 1 n 0 0 • • • -1           ∈ Q (n+1)×n ,
thus the last Gram-Schmidt norm is (n + 1)/n. Since orthogonal projections shrink norms, we have b * kq+i (ki + 1)/(ki) for 1 i q and b * kq+i (kq + i)/(kq) for q + 1 i q + r. Immediately the minimal achieved quality factor for the nal block is bounded by (k + 1)/k • η ε (Z q+r ).

Algorithm 11

A n sampler Input: σ max 9 8 η ε (Z 8 ), η ε (A 8 ) , a center t ∈ Span R (A n ), a filtration (Λ i ) i of A n in the form of B n , as in Proposition 5.

Output: v following distribution statistically close to D An,t,σ 2

1 Compute c i = π V ⊥ q (b i+kq ) for 1 i q + r 2 t q+1 ← π V ⊥ q (t) 3 x q+1 ← Algorithm 3({c 1 , . . . , c q+r }, σ, t q+1 ) 4 u ← Li (x q+1 , V q ) 5 t ← t -x q+1
6 Compute the orthogonal projections t j of t on Span(b jk+1 , . . . b jk ) for 0 j < q 7 x 1 , . . . , x q ← Algorithm 8(σ, t 1 ), . . . , Algorithm 8(σ, t q ) / * can be done in parallel * / Fixing coset representatives to identify the quotients A = N/M and B = M/L, de ne the king construction Γ(L, A, B, k) as follows, starting from its parity check subla ice is:

8 return x 1 + • • • + x q + x q+1
(12) Γ(L, B, k) P = (t 1 , . . . , t k ) t i ∈ L + B, i t i ∈ L .
and its de nition as the coset decomposition: Sampling in parity check la ices. To leverage the extension results presented in Section 3 once again, we will now focus on describing M k /Γ(L, B, k) P in a concise manner. By considering the map tr : (x 1 , . . . , x k ) → i x i over B, we can express this quotient as B k / ker(tr). e proof is a ma er of elementary commutative algebra. Just as we have the chain of abelian groups L ⊂ M ⊂ N , we have a chain L k Γ M k where Γ denotes the parity check la ice, for ease of notations. Recall that B = M/L, so by standard isomorphism theorems, we readily see

M k /L k (M k /L k )/(Γ/L k ) B k /(Γ/L k ).
Also recall that we considered the group homomorphism tr : (x 1 , . . . , x k ) → i x i over B. As we have Γ/L k = {(t 1 , . . . , t k )| i t i = 0} = ker tr, we conclude by identi cation.

Consequently, by utilizing the short exact sampler (Algorithm 2), we can e ectively reduce the task of sampling within the parity check la ice Γ(L, B, k) P to two main steps: sampling a uniform element in B/ ker(tr) and sampling an element in L. It is worth noting that sampling within the aforementioned group is equivalent to sampling a uniform k-tuple of elements with a zero-sum. is particular distribution can be accurately simulated by independently and uniformly sampling the rst k -1 elements, followed by se ing the nal element to be the negation of the sum of these previously sampled elements.

Algorithm 12 king sampler

Input:

• A chain of (full-rank) la ices L M N

• Sets of representants for A = N/L and B = M/L

• A sampler D L,•,Σ at covariance Σ > η ε (N ). • a center c ∈ N k ⊗ R Output: v following a distribution close to D Γ(L,A,B,k),c,Σ 1 α ← U(A)
2 m ← (α, . . . , α)

3 for i = 1 to k -1 do t i ← U(B) 4 t k ← -k-1 i=1 t i 5 t ← (t 1 , . . . , t k ) 6 u ← D L k ,c-t-m,Σ 7 return (u + t + m)
Pu ing all together. By these two steps, we reduced the sampling in the king construction to samples in the small subla ice L.

e complete pseudo-code is given in Algorithm 12 when expanding all steps of the short exact sequence technique and using direct set of representants to avoid li ing: e correctness of the king sampler can be derived from the proven correctness of the short exact sampler ( eorem 1). It is important to note that in this context, the selection of a suitable covariance Σ greater than the smoothing of the rst la ice in the chain is mandatory (L)

However, an interesting observation is that if we possess a direct sampler for the parity check la ice Γ(L, B, k) P , we have the opportunity to optimize lines 3-4-5-6 by directly sampling from this la ice, centered at the vector cm. By employing this optimization, the condition can be weakened, requiring only that Σ exceeds the smoothing of the parity check la ice. is modi cation not only simpli es the algorithm but also enhances its precision.

8.2.3.

Recovering remarkable la ices. Following [START_REF] Corlay | On the decoding of la ices constructed via a single parity check[END_REF] we have recursive descriptions when k = 2, 3, with a slight abuse on notation where we allow the la ices in the chain to be rotated or scaled. e corresponding decoding/sampling algorithms are adapted mutatis mutendis 15 .

• Barnes-Walls: is family can be de ned as BW 2n = Γ(φ • BW n , B, 2) for B = BW n /(1 + i)BW n and the bootstrap BW 2 = Z[i] ∼ = Z 2 , where φ represents the multiplication by (1 + i) (which translates to a rotation and scaling, when looking at the underlying Z-la ice.

• Leech: e celebrated Leech la ice can be constructed as a 3-construction (also called Turyn construction) from the E 8 root la ice. For this, we select the chain 2E 8 ⊆ T θ ⊂ T where T θ ∼ = T ∼ = E 8 , for a phase such that [START_REF] Corlay | On the decoding of la ices constructed via a single parity check[END_REF] for a complete description). Other variants of the same approach exist.

√ 2e iθ = 1 2 (1 + i √ 7) (see

A I: I S M

[15] is a variant of o ering simpler implementations and exible parameters.

It can be theoretically instantiated over arbitrary cyclotomic elds. While concrete parameters and security estimates are provided, the preliminary implementation of only covers the case of power-of-2 cyclotomics. e instantiation over other cyclotomic rings R m relies on how the Gaussian sampling over R m is performed. is is non-trivial as the canonical basis of these rings of integers fails to be orthogonal when the conductor m is not a power-of-2.

In this section, we present two novel approaches relying on our ad-hoc, explicit samplers for root la ices: one for cyclotomic rings with prime conductor, one for smooth conductor m = 2 3 k . We believe that the techniques introduced in this section could nd further use in designs, providing more exible parameters, more e cient samplers, and tighter security.

= (f, g) t , b 1 = (F, G) t ∈ R 2 m of the NTRU module M ntru = (f, g) t R m ⊕ (F, G) t R m .
e signing amounts to sampling a discrete Gaussian in M ntru close to an arbitrary target (a hashed message), which is accomplished by the hybrid sampler [START_REF] Ducas | Fast Fourier Orthogonalization[END_REF][START_REF] Omas Prest | Gaussian Sampling in La ice-Based Cryptography[END_REF]. Let σ sig be the standard deviation of the sampled la ice Gaussian. For be er sizes and security against forgery, one wants to minimize σ sig . 15 We don't describe the construction of the Nebe here as it will not be used in the following practical applications. However, we point out that it is based also on 3-ing construction upon the Leech la ice, and as such our framework readily applies.

As seen in Section 4.3, the hybrid sampler leverages the ltration {0} ⊂ ψ(b 0 R m ) ⊂ ψ(M ntru ), where ψ denotes the canonical embedding extended to vectors.

e calls to Algorithm 4 consider b 0 R m and M ntru /b 0 R m as linear transformations 16 of R m . Under this identi cation, Lemma 1 and Lemma 2 show that the sampler of reaches standard deviation as

σ sig max s 1 (ψ(b 0 )), s 1 (ψ(b * 1 )) • α • η ε (ψ(R m )),
where α > 1 encodes how close we are able to sample from the smoothing parameter of the base ring R m . For Algorithm 3 to reach the stated covariance, it requires two elliptic samples in R m . In [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF], this is handled by Peikert's sampler in ψ(R m ), or equivalently, Algorithm 4

with C being the (canonical embedding of) the power basis -equivalently, the Fourier domain of this basis. is choice comes from the use of a well-chosen continuous perturbation, which has diagonal covariance in this representation so that its square root can be computed in quasilinear time, avoiding costly Cholesky decompositions.

e next requirement of Algorithm 4 is a spherical, discrete sample in R m . For power-of-two cyclotomics, the canonical embedding ψ(R m ) is essentially a scaling of Z m/2 , and so α = 1.

e situation is less favorable for more general cyclotomic rings. For example in prime cyclotomic, sampling directly the coe cients of x = j x j ζ j as spherical Gaussians means that ψ(x) has covariance (proportional to) V p V p t , a matrix far from being diagonal. In other words, going back and forth the canonical embedding distorts severely the resulting sample in M ntru .

Another approach is to sample directly in the Fourier domain; for prime or smooth conductors, the current best approaches yield α = √ p -1 and α = √ 2 losses, respectively [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF].

Changing the construction of the basis of M ntru is not the topic of this paper. We focus instead on decreasing the contribution of α. Our goal is to show that a di erent representation of R m can signi cantly reduce this parameter. e hero of the story is the principal ideal 17 with m = 2 • 3 k and , k > 0, as suggested in [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF]. To our knowledge, very few works focus 18 on such conductors. From e.g. [START_REF] Lyubashevsky | A toolkit for ring-LWE cryptography[END_REF][START_REF] Wessel Pj Van Woerden | e closest vector problem in cyclotomic la ices[END_REF], the tensor decomposition R m = R 2 ⊗ R 3 k leads to an orthogonal decomposition (tied to the powerful basis [START_REF] Lyubashevsky | A toolkit for ring-LWE cryptography[END_REF])

R m ∼ = Z 2 ⊗ 3 k-1 i=1 R 3 ∼ = m 6
i=1 R 3 . Alternatively, we have an orthogonal decomposition ( 14)

1 -ζ m/3 m = m 2 R ∨ m ∼ = m/6 i=1 1 -ζ 3 .
(see also [START_REF] Lyubashevsky | A toolkit for ring-LWE cryptography[END_REF]Cor. 2.18]). We can use Algorithm 9 with this decomposition: sampling in R 3 is done by m/6 independent sampling in A 2 , by orthogonality. 9.2.1. E ciency and signature quality. From Algorithm 9, we obtain samples in A 2 of width at least η ε (D 8 ), for some chosen ε. We observe using the estimates of Lemma 5 that η ε (D 8 ) η ε (A 2 ), so we can sample each component in the decomposition ( 14) at the smoothing of A 2 .

Taking into account the entire ltration, the resulting sampler reaches standard deviation starting

(15) σ = η 6ε/m (A 2 ) ≈ • 3 2 • η 2ε/3 (Z m 3
).

e running time is linear in the conductor m. As we need large batches of samples, the alternate approach of Algorithm 9 that amortizes randomness is a good choice here. While still a bit randomness-hungry, the resulting sampler is completely parallelizable and also memorye cient: we only need to store a table for integer Gaussians of small width. Moreover, thanks to the small Gaussian parameter, the constant-time implementation is easy and e cient. 9.2.2. Comparisons with other methods. On the one hand, the basis b 0 , b 1 is not changed between our methods and the previous ones. On the other hand, previous approaches such as [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF] could only sample representants of R m to a standard deviation of σ

√ 2 • η ε (Z m/3 ).
is translates quantitatively into a NIST security 19 level-up for each 3-smooth conductors parameter sets proposed in [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF], as reported in Table 1.

Another generic method for low-dimensional la ices with a small width is tabulated sampling. Concretely, one precomputes a CDT-like table for all short vectors of A 2 and then outputs 18

showcased an FFO-style sampler over cyclotomic rings of conductor 3 • 2 in the round 1 of the NIST call. It was abandoned because of its high technicality. Such rings are also the focus of the implementation in [START_REF] Lyubashevsky | NTTRU: Truly fast NTRU using NTT[END_REF]. 19 We use here the same security estimates as in [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF], in the so-called Core-SVP model for a fair comparison. √ p -1, which drives the quality of a Klein/GPV approach (as done in [START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF]). An approach à la Peikert with Algorithm 4 is driven by the Vandermonde matrix V p , and we have s 1 (V p ) = √ p.

Considering now the decoding basis as a matrix A p with Gram matrix G p (1) (equivalently, using the map φ), we have identi ed the meaningful quantities in Section 8.1.9. Comparisons between all approaches are displayed in Table 2, showing that our ltration choice improves on the state-of-the-art. 9.3.3. Practical impact. e improvement over is signi cant, as seen in Table 3. On the one hand, we can use nely tailored conductors to match the requirements of the NIST level, which allows working in smaller dimensions. But we can also use NTT-friendly moduli q that are smaller than the traditional q = 12289 used for power-of-two cyclotomics, which also allows for reducing both the public key and signature sizes -however the improvement is mild, therefore we focus on the security.

A II: N C L G

La ice gadgets are an important ingredient to build e cient la ice trapdoors. Very recently, Yu, Jia, and Wang developed a new gadget framework [START_REF] Yu | Compact la ice gadget and its applications to hash-and-sign signatures[END_REF] and proposed practical signature schemes based on it. In their scheme, the gadget can be in principle any square matrix supporting e cient decoding and Gaussian sampling. However, the concrete instantiations only use the simplest (scaled) integer la ice Z n as the gadget. To design more e cient gadgets, one is not only required to explore new la ice structures but also to develop specialized decoding and/or sampling algorithms. which allows be er size and security than the Z n -based instantiation.

10.1. e Yu-Jia-Wang compact gadget framework. In a general gadget-based trapdoor scheme, the preimage sampling is converted to the gadget sampling by using the trapdoor, following the idea of the Micciancio-Peikert trapdoor [START_REF] Micciancio | Trapdoors for la ices: Simpler, tighter, faster, smaller[END_REF]. In the Yu-Jia-Wang framework, the gadget is a square matrix G ∈ Z n×n along with H ∈ Z n×n such that GH = qI n , and the gadget sampling is implemented by the so-called semi-random sampler. Given a target u, the semi-random sampler outputs a Gaussian preimage v such that Gv = ue mod q for a small error e. e sampler proceeds in two steps:

(1) Deterministic decoding over L(G). e sampler rst computes an error e such that ue ∈ L(G). Let ue = Gc for some c ∈ Z n .

(2) Gaussian sampling over L(H).

e sampler then samples v ← D L(H)+c,r with r η ε (L(H)). It holds that Gv = ue mod q. • η ε (Z 8 ) (scaled by q/p). As shown in Table 4, the E 8 gadget gains 56 (resp. 113) bytes of the signature size and 3 (resp. 9) bits of security against forgery for (the Ring-LWE-based scheme). e comparisons follow the suggested parameters in [START_REF] Yu | Compact la ice gadget and its applications to hash-and-sign signatures[END_REF] where the secret standard deviation is 1/2. We note that the presented parameters may not be optimal: there seems a few bits of gap between the key recovery and the forgery security. Finding optimal parameters and closing this gap could be interesting future work.

Towards improving LIP based schemes. e La ice Isomorphism Problem has been introduced in [START_REF] Ducas | On the la ice isomorphism problem, quadratic forms, remarkable la ices, and cryptography[END_REF] and is a promising class of problems to construct e cient cryptography. More precisely the LIP-based hash-and-sign signature of [START_REF] Ducas | On the la ice isomorphism problem, quadratic forms, remarkable la ices, and cryptography[END_REF] instantiates with any la ice for which we can sample e ciently at small Gaussian widths, and for which la ice a acks are as hard as they can be. e preliminary analysis of the problem by the authors of [START_REF] Ducas | On the la ice isomorphism problem, quadratic forms, remarkable la ices, and cryptography[END_REF] has revealed that the Barnes-Walls la ices could be good candidates if a sharp sampler is available. Using the 2-ing sampler Section 8.2 recursively allows us to instantiate the LIP scheme with any of the BW 1024 or BW 2048 la ice. e precise optimization and benchmark of the resulting scheme would be totally out of the scope of this paper and we let it as very promising future work.

9. 3 .

 3 Sampling over prime cyclotomic elds 10. Application II: New Compact La ice Gadgets 10.1. e Yu-Jia-Wang compact gadget framework 10.2. Compact gadget from the E 8 la ice Towards improving LIP based schemes. References 1. I

2. 1 .

 1 Euclidean lattices. A (real) la ice Λ is a nitely generated free Z-module, endowed with a Euclidean norm . on the real vector space Λ R := Λ ⊗ Z R. By de nition, there exists a nite family (b 1 , . . . , b n ) ∈ Λ n of linearly independent elements such that Λ = n i=1 b i Z, and we write Λ = L(B), with the matrix B = [b 1 , . . . , b n ]. It is called a basis of Λ. Every basis has the same number of elements rk(Λ), called the rank of the la ice. We let λ 1 (Λ) be the Euclidean norm of a shortest non-zero vector in Λ. e volume is det Λ = √ det B t B, for any basis B of Λ.

  with the restriction of the norm to that space. If P is a matrix representation of π V ⊥ , we have P 2 = P and P t = P. Given a basis B = (b 1 , . . . , b n ) of a la ice Λ, we denote its Gram-Schmidt orthogonalization by B * = (b * 1 , . . . , b * n ), where b

e

  Vandermonde matrix associated to the m-th primitive roots ζ m,1 , . . . , ζ m,φ(m) of 1 is

1 p e i - 1 p 1 i

 111 which is an orthogonal sum under the canonical embedding. Recall the basis b i := p-=j p e j of A ∨ p-1 , seen in Section 2.3. e key fact for what follows is the isometry between R p and A ∨ p-1

3 . A 3 . 1 .

 331 Gaussian measures over short sequences of groups. For a la ice Λ, we want to study the behavior of the Gaussian measure D = D Λ,c,Σ with regards to exact sequences of Zmodules 5 :

Lemma 3 . 1 .

 31 Let Λ ⊂ Λ be la ices and T the torsion part of Λ/Λ . If Σ η ε (Λ ) and D = D Λ,c,Σ , then the pushforward distribution proportional to π D is at total variational distance ε 1-ε of the distribution de ned by |T| -1 • D π(Λ),π(c),Σ , where |T| is the cardinality of T.

4. 1 . 2 .

 12 Restriction to a subla ice. Conversely, it is easy to sample in a subla ice Λ when we already know how to sample in Λ, and Λ has nite index [Λ : Λ ]: sample in Λ and reject all samples not landing in Λ . e number of tries is of course driven by [Λ : Λ ], which can be proven when sampling above the smoothing of Λ . In fact, it makes it a speci c case of the rejection sampling technique, with trivial rejection probabilities. In the upcoming Section 8, we showcase some practical examples with root la ices.

4. 2 . 2 .

 22 e ltered sampler. Following our mo o -smoothing bounds and sampling are built on the same underlying principles -we can transform Lemma 1 into a Gaussian sampler. In essence, the process corresponds to k successive calls of Algorithm 2, recursively progressing along the ltration.

4. 3 . 1 .

 31 Klein/GPV sampler. As we saw, this sampler corresponds to taking the full ltration associated to a la ice basis (b 1 , . . . , b n ) giving a lower bound on the width in

4. 3 . 2 . 4 . 3 . 3 .

 32433 Klein/GPV sampler over a ring. is sampler works at the ring level of a module over some ring of integer O K in a number eld K (for example on la ices which are rank two module over a cyclotomic ring). More precisely given a module basis (m 1 , . . . , m d ) overO K , we make use of the full ltration11 m 1 O K ⊂ m 1 O K ⊕ m 2 O K ⊂ • • • . Each recursivecall thus consists in calling the oracles over the quotients m i+1 O K /m i O K , which are scaling by an algebraic number of O K ∼ = Z deg K . When instantiating this oracle with subsequently described Algorithm 4 (or Peikert's[START_REF] Peikert | An e cient and parallel Gaussian sampler for la ices[END_REF] for instance), it retrieves the so-called hybrid sampler used in[START_REF] Omas Espitau | MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON[END_REF]. Fast Fourier Orthogonalization sampler. Introduced in[START_REF] Ducas | Fast Fourier Orthogonalization[END_REF][START_REF] Omas Prest | Falcon: Submission to the NIST's post-quantum cryptography standardization process[END_REF], this sampler reaches the same quality as Klein's sampler but run in quasi-linear time in the dimension, by exploiting the structure of tower of sub elds in power-of-two cyclotomic elds. It is retrieved as the ltered sampler where the oracle over the ring is the sampler itself, called recursively. More precisely given a basis m 1 , m 2 of a module Λ over the ring of integers O K of the cyclotomic eld of conductor 2 k , we have the short exact sequence:

1 .

 1 Smoothing parameters and linear transformations. e algorithms presented in Section 3 sample without leaving the ambient space of the la ice. However, in certain cases, it is of interest to transfer the problem to another space -where the local geometry eases the sampling process -and transfer the result back to the original la ice. In a sense, as all la ices can be seen as a transformation of the integer la ice Z n , and as most practical Gaussian samplers rely on the ability to sample integral Gaussians, this observation is already implicit in previous works. As expected, such back and forth between di erent spaces will generate bias because of the distortion incurred by the underlying linear transformation. To enforce the correctness of the output distribution, it must be corrected. For example, the ltered sampler of Section 4.2.2

  SVD based sampler:: e singular value decomposition gives B = X∆Y t with X, Y orthogonal matrices and ∆ diagonal. It amounts to a diagonalisation of the Gram matrix B t B, or in other words to work in a basis of eigenvectors. As X and Y are orthogonal, the sampler reaches standard deviations starting s 1 (B) • η ε (Z n ), and gives a quality equivalent to the one of Peikert. • QR-based sampler:: Using the QR decomposition B = QR, one can use e.g. the above procedure to sample in L(R) with coordinate domain Z d , and then obtains a discrete Gaussian in L(B). Since Q is orthogonal, the sampler reaches standard deviations starting s 1

  if one knows how to sample in L(R) then the linear sampler can reach standard deviations greater than η ε (L(R)). • Gram-Schmidt based sampler: Let B = BU be the Gram-Schmidt decomposition of B.

6. 1 . 1 .

 11 Smoothing bound for tensors. Combining these properties with Lemma 2 gives a bound on the smoothing parameter of a tensor product of la ices. Our bound involves singular values of the le factor T in the mixed-product decomposition of A ⊗ B, whereas the bound given in[START_REF] Micciancio | Hardness of SIS and LWE with small parameters[END_REF] Corollary 2.7] is associated to the maximal length B GS of the Gram-Schmidt vectors of that factor. It is known that B GS s 1 (B), so that our bound is generally of worse quality,

Proposition 8 . 1 . 8 . 1 . 3 .

 81813 Let D the distribution of outputs of Algorithm 6. en D is at statistical distance at most ε of D Dn,σ,t . Moreover, we havesup z∈Dn D(z) D Dn,σ,t (z) -1 2ε,and it requires two tries in average. Sampling in the A 3 la ice.

8. 1 . 4 .

 14 Sampling in the E 8 la ice.

8 . 1 . 5 .

 815 the expected repetition times is N ≈ 11 and the gain is σ σ ≈ 0.74. Sampling in the A 8 la ice.

4 return z Proposition 4 . 8 D

 448 let D(z) the distribution of outputs of Algorithm 8. en D(z) is at statistical distance at most 10ε of D A 8 ,σ,t . Moreover, we have sup z∈A (z) D A 8 ,σ,t (z) -1 20ε Proof. Let Λ be the subla ice of E 8 generated by (h, b 1 , . . . , b 7 ) and u = e 1 -e 2 -• • • e 8 . We

8 . 1 . 6 .

 816 or equivalently, x ∈ Λ. e rest of the proof comes from from Proposition 3. Sampling in the A 2 la ice.

√ 3

 3 and the rotation xes R • 1, turning the hyperplane 1 ⊥ by π/2. e algorithm obtains an A 2 sample from Algorithm 7 at η ε (A 2 ), scales it and rotates it. If the target distribution has a non-trivial center, one just needs to transform it accordingly before sampling in A 2 .

eorem 5 .

 5 Let n > 8 be an integer and n = 9q + r the Euclidean division of n by 9. Let t ∈ R n

8. 2 .

 2 e king sampler. 8.2.1. e iterated parity-check construction. In[START_REF] Corlay | On the decoding of la ices constructed via a single parity check[END_REF], a unifying construction is introduced to generalize the parity-check la ices. Notably, this so-called king-construction recovers some constructions of famous remarkable la ices, including the Barnes-Walls, Leech and Nebe lattices. By leveraging a recursive combination of the conventional parity-check construction, this technique provides a convenient coset decomposition, which the authors turn into novel decoding algorithms. In line with the philosophy that a Gaussian sampler serves as a randomized decoding algorithm, we further demonstrate how our domain extension techniques blend into the creation of new samplers for the king-based la ices. e king construction starts from a double inclusion L ⊂ M ⊂ N of full-rank la ices.

( 13 )

 13 Γ(L, A, B, k) = m∈A Γ(L, B, k) P + (m, . . . , m) 8.2.2. Towards a sampler.Reduction to subla ice sampling. is decomposition then translates to a sampler, by plugging the bricks described in Section 4.1: if we denote by Γ 0 the quotient of the king construction by its parity-check subla ice, the short sequence 0 → Γ(L, B, k) P → Γ(L, A, B, k) → Γ 0 → 0 underlying the decomposition of Equation (13) allows with the results of Section 3 to reduce the problem to sampling in the parity-check Γ(L, B, k) P .

9. 1 .

 1 Hybrid sampling and representation of cyclotomic numbers. is an NTRUbased instantiation of the framework[START_REF] Gentry | Trapdoors for hard la ices and new cryptographic constructions[END_REF]. Its secret key is a short basis b 0

√ n slightly larger than n/ 12 ≈ 0. 29 √

 1229 n the one in the Z-based instantiation. e sampling on L(H) is tighter than that in the Z-base gadget: by using the ad-hoc sampler shown in Section 8.1.4, one can sample with a Gaussian width η ε (E 8 ) ≈ 1 √ 2

T 4 .

 4 Parameters for the compact gadget-based signatures. (p, q/p) Forgery security (C/Q) |Sig.| (bytes)

  8.1.9. Sampling in A n la ices. We now study the Gaussian sampling problem for arbitrary A n Trivial instantiations: Peikert and Klein samplers. Unrolling the Cholesky algorithm on the Gram-matrix G n (1) of the standard basis (e i -e i+1 ) 1 i n of A n is reveals that the maximal value of its diagonal coe cients is achieved on its rst element, which value is π 2 2n 2 , a worse reachable standard deviation. e other classic basis (e 1 -e i ) 2 i n+1 of A n has a largest singular value of

	la ices.	e generic case is trickier, as there is no known direct isomorphisms or decompo-
	sitions involving other exceptional la ices. A possible approach consists in instantiating our
	framework of Section 4.2.2 and Section 5.2 using the base cases we just constructed. As a point
	of comparison, we rst brie y give the results given by the generic use of standard Klein and
	Peikert samplers.
	8.1.10. √ Klein sampler allows performing Gaussian sampling at standard deviation above	2. Hence, the √ 2η ε (Z). As
	G n is a tridiagonal Toeplitz matrix with pa ern (-1, 2, -1), its eigenvalues are of the form
	2 + 2 cos(kπ/(n + 1)) for 1 k n [19]. Consequently, the largest singular value of this basis
	is (2 + 2 cos(π/(n + 1))) 1/2	2 1 √	n + 1, which has an even
	worse geometry.
	8.1.11. Constructing a be er ltration. To showcase possible trade-o s using Algorithm 3, we
	now describe di erent ltrations for A n la ices. Our approach here is to rely on samplers in
	larger exceptional la ices from the previous section-such as the A 8 sampler (Algorithm 8)-
	as subroutines.	is new family of algorithms allows sampling very close to the smoothing
	parameter of the A 8 .

  1 -ζ p . Using Algorithm 3 over the ltration induced by the so-called decoding basis [20] Sampling over cyclotomic elds of conductor 2 • 3 k . Here, we work in R m = Z[ζ m ]

	9.2.
	ζ i p -ζ i+1 p	of the ideal 1 -ζ p , one can achieve generally, α =	√	2, which is the length of the
	largest Gram-Schmidt vector of this basis. We will now push further thanks to Proposition 1
	and other identi cations.

  T 1. Concrete values for forgery compared to Mitaka base sampler. the sample through table look-up. However, the size of the table for D A 2 ,σ 2 is much larger than the one for D Z,σ 2 /3 in our algorithm, which signi cantly lowers the speed of the constant-time implementation. 9.3. Sampling over prime cyclotomic elds. e sampler results from a combination of Proposition 1 with our e cient Algorithm 11 instantiated over A p-1 . 9.3.1. E ciency and signature quality. Both approaches are linear in p, with Algorithm 11's main cost coming from the sampling in A 8 (Algorithm 8), achieving a width max(η ε (D 8 ), η ε (A 8 )). Using the approximation of Lemma 5, we see that η ε (D 8 ) η ε (A 8 ): we can sample the components at the smoothing of A 8 . e resulting standard deviation in Algorithm 11 is thus(16) σ = η ε/q (A 8 ) ≈ 9 8• η 2ε/9 (Z 8q ) with q = p/9 .e isochronous implementation for both approaches is easy and e cient, as the involved algorithms only rely on an integer sampler of a xed width and simple rejection samplings. ey are both highly parallelizable, thanks to the ltration shown in Proposition 5; and memorye cient, as the base sampling has small width 9/8 • η ε (Z) and it does not need to store many intermediate values due to the parallelism. 9.3.2. Comparisons with other methods. In [20, Sec. 6.3], the ideal 1 -ζ p and the identi cation of prime-power cyclotomic rings were used to sample continuous Gaussians, by mean of the so-called "decoding basis", which is the Z-basis of the ideal. From the map φ, we can directly identify the Gram matrix of R p as a scaling by p of that of A ∨ p-1 to be the circulant matrix G p of rst line (p -1, -1, . . . , -1). e largest element in the diagonal of the Cholesky of G p is T 2. Comparisons with other samplers over prime cyclotomics.

			ality	This work Running time
	Classical 117 Peikert, canonical basis antum NIST Level Classical d = 648 103 I -137 √ p • η ε (Z p-1 ) Klein, canonical basis √ p -1 • η ε (Z p-1 )		antum NIST Level 121 II O(p 2 ) O(p 2 )
	d = 768 d = 864 Peikert, decoding basis 147 129 168 148 Klein, decoding basis	II III ≈ 2 1 -π 2p 2 • η ε (Z p-1 ) 170 195 √ 2 • η ε (Z p-1 )	150 171	O(p) O(p)	III IV
	d = 972 Coe cient embedding 194 170	IV	224 η ε (Z p-1 )		197	O(p)	V
	Ours (φ)	η ε/q (A 8 ) ≈ 9 8 • η 2ε/9 (Z 8q )		O(p)

  T 3. Intermediate parameters and security levels for prime-Mitaka. is section showcases a new practical construction based on the E 8 la ice. As shown in Section 8.1.4, the E 8 la ice has an e cient sampler achieving the Gaussian width η ε (E 8 ) < η ε (Z 8 ),

	Conductor Modulus	ality	Security
	m : ϕ(m)	q	α	(C/Q/NIST level)
	2304 : 768	18433	2.20	167/151/NIST-II
	This work 683 : 682	1367	2.125	157/138/NIST-II
	2592 : 864	10369	2.25	192/174/NIST-III
	This work 857 : 856	6857	2.215 207/182/NIST-III
	2916 : 972	17497	2.30	220/199/NIST-IV
	This work 919 : 918	3677	2.247 223/196/NIST-IV
	2048 : 1024	12289	1.17	285/258/NIST-V
	2048 : 1024	12289	2.33	233/211/NIST-V
	This work 1009 : 1008	10091	2.30	250/219/NIST-V

Most of the prior literature uses s or √ Σ, that is, an analog of standard deviation instead of the covariance.

We highlight that this is a short sequence of groups and not necessarily of la ices.

In the same way that Klein/GPV sampler is a randomized version of Babai's nearest plane algorithm, our technique can be interpreted as a randomized version of the nearest-cola ice algorithm of Espitau and Kirchner[START_REF] Omas | e nearest-cola ice algorithm[END_REF].

e parameters κ2 and n2 are placeholders for the number κ2 of vectors of norm n2, the smallest possible norm in the la ice that is larger than λ1.

In practice, this second call is encoded by the orthogonalization b * 1 of b1 in the cyclotomic eld

Acknowledgments: We thank the anonymous reviewers for their valuable suggestions and pointing out a awed proof in an earlier version of this work. Alexandre Wallet was supported by PEPR quantique France 2030 programme (ANR-22-PETQ-0008) and by the ANR ASTRID project AMIRAL (ANR-21-ASTR-0016). R