Thomas Espitau
email: thomas.espitau.ax@hco.ntt.co.jp

Pierre-Alain Fouque
email: pa.fouque@gmail.com

François Gérard
email: francois.gerard@uni.lu

Mélissa Rossi
email: melissa.rossi@ssi.gouv.fr

Akira Takahashi
email: takahashi@cs.au.dk

Mehdi Tibouchi
email: mehdi.tibouchi.br@hco.ntt.co.jp

Alexandre Wallet
email: alexandre.wallet@inria.fr

Yang Yu

MITAKA: A Simpler, Parallelizable, Maskable Variant of FALCON

This work describes the MITAKA signature scheme: a new hash-and-sign signature scheme over NTRU lattices which can be seen as a variant of NIST finalist FALCON. It achieves comparable efficiency but is considerably simpler, online/offline, and easier to parallelize and protect against sidechannels, thus offering significant advantages from an implementation standpoint. It is also much more versatile in terms of parameter selection.

We obtain this signature scheme by replacing the FFO lattice Gaussian sampler in FALCON by the "hybrid" sampler of Ducas and Prest, for which we carry out a detailed and corrected security analysis.

In principle, such a change can result in a substantial security loss, but we show that this loss can be largely mitigated using new techniques in key generation that allow us to construct much higher quality lattice trapdoors for the hybrid sampler relatively cheaply. This new approach can also be instantiated on a wide variety of base fields, in contrast with FALCON's restriction to power-of-two cyclotomics.

We also introduce a new lattice Gaussian sampler with the same quality and efficiency, but which is moreover compatible with the integral matrix Gram root technique of Ducas et al., allowing us to avoid floating point arithmetic. This makes it possible to realize the same signature scheme as MITAKA efficiently on platforms with poor support for floating point numbers.

Finally, we describe a provably secure masking of MITAKA. More precisely, we introduce novel gadgets that allow provable masking at any order at much lower cost than previous masking techniques for Gaussian sampling-based signature schemes, for cheap and dependable side-channel protection.

, but they tend not to be competitive.

Introduction

The third round finalists for signatures in the NIST postquantum standardization process consist of just three candidates: Rainbow [START_REF] Ding | Rainbow. Tech. rep[END_REF], a multivariate scheme, Dilithium [START_REF] Ducas | CRYSTALS-Dilithium: A lattice-based digital signature scheme[END_REF][START_REF] Lyubashevsky | CRYSTALS-DILITHIUM[END_REF], a latticebased scheme in the Fiat-Shamir with aborts framework, and FALCON [START_REF] Prest | [END_REF], a hash-and-sign signature over NTRU lattices. They occupy fairly different positions within the design space of post-quantum signature schemes, and it is therefore important to understand, for each of them, to what extent they could possibly be improved by exploring similar designs that overcome some of their limitations. This paper aims at doing so for the FALCON signature scheme.

Hash-and-sign lattice-based signatures. FALCON fits within the long and hectic history of hashand-sign signatures based on lattices. In those schemes, the signing key is a "good" representation of a lattice, the trapdoor, which makes it possible, given an arbitrary point in the ambient space, to find lattice points that are relatively close to it (i.e. solve the approximate closest vector problem, ApproxCVP 7 ); the verification key, on the other hand, is a "bad" representation: it allows anyone to check if a point is in the lattice, but not to solve ApproxCVP. In order to sign a message, it is then hashed to a random point in the ambient space, and the signature is a lattice point close to it, obtained using the trapdoor. To verify, one checks that the signature is in the lattice and sufficiently close to the hash digest.

Early constructions along those lines, such as the GGH signature scheme [START_REF] Goldreich | Public-key cryptosystems from lattice reduction problems[END_REF] and multiple iterations of NTRUSign [START_REF] Hoffstein | NTRUSIGN: Digital signatures using the NTRU lattice[END_REF][START_REF] Hoffstein | Performance improvements and a baseline parameter generation algorithm for NTRUSign[END_REF], were later shown to be insecure due to a common critical vulnerability: the lattice points obtained as signatures would leak information about the trapdoor used to compute them, which could then be recovered using more or less advanced statistical techniques [START_REF] Nguyen | Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures[END_REF][START_REF] Ducas | Learning a zonotope and more: Cryptanalysis of NTRUSign countermeasures[END_REF]. One of the first round NIST candidates was in fact broken using the same idea [START_REF] Yu | Learning strikes again: The case of the DRS signature scheme[END_REF].

It is thus crucial for security to prove that signatures are sampled according to a distribution that is statistically independent of the trapdoor. The first approach to do so, which remains the state of the art, 8 is due to Gentry, Peikert and Vaikuntanathan (GPV) [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]: sample the ApproxCVP solution according to a discrete Gaussian distribution centered at the target point and supported over the lattice, with covariance independent from the trapdoor (usually spherical). This type of lattice discrete Gaussian sampling can be carried out by randomizing known deterministic algorithms for ApproxCVP, like Babai rounding and Babai's nearest plane algorithm.

Within the overall GPV framework, specific signature schemes vary according to the lattices over which they are instantiated, the construction of the corresponding trapdoors, and the lattice Gaussian sampling algorithms they rely on based on those trapdoors. The security level achieved by such a scheme is then essentially determined by the quality of the trapdoor and of the Gaussian sampling algorithm, defined as the minimal standard deviation achievable in Gaussian sampling, while still preserving the statistical independence of the output.

A complete overview of existing proposals for each of those elements is beyond the scope of the current work. We focus instead on the particular case of NTRU lattices with the usual NTRU trapdoors first considered in NTRUSign, as those lattices appear to offer the most efficient implementations by a significant margin, thanks to their compact trapdoors.

Hash-and-sign signatures over NTRU lattices. NTRU lattices are, in essence, free rank 2 module lattices over cyclotomic rings, and the NTRU designers showed how to construct good trapdoors for them, even though the original signature schemes based on them proved insecure.

They were brought within the GPV framework (and thus gained provable security) thanks to the work of Ducas, Lyubashevsky and Prest (DLP) [START_REF] Ducas | Efficient identity-based encryption over NTRU lattices[END_REF], who combined them with the Gaussian sampling algorithm obtained by randomizing Babai's nearest plane algorithm (this randomization is sometimes called the Klein sampler for lattice Gaussians). They analyzed the security of the construction and provided what became the first reasonably efficient implementation of a signature scheme in the GPV framework. This DLP signature scheme offers relatively compact keys and signatures, but suffers from a relatively long signing time, quadratic in the Z-rank of the underlying lattice. This is because the nearest plane computation is carried out after descending to Z, essentially ignoring the module structure of the lattice.

FALCON is a direct improvement of this scheme, obtained by replacing this quadratic Gaussian sampling by a quasilinear one, derived from the quasilinear nearest plane algorithm described in the Fast Fourier Orthogonalization paper of Ducas and Prest [START_REF] Ducas | Fast Fourier orthogonalization[END_REF] (and refining the parameter selection using a tighter statistical analysis based on the Rényi divergence). The computation still ultimately descends to Z, but takes advantage of the tower field structure of the underlying number field (assumed to be a power-of-two cyclotomic) to achieve a better complexity.

These two approaches are equivalent in terms of the quality of the resulting Gaussian sampler, which is essentially the best possible for the given NTRU lattice. However, DLP does so at the cost of a slow signing algorithm, whereas FALCON, while fast, suffers from a very complex signing algorithm that is hard to implement, poorly suited for parallelization and difficult to protect against side-channel attacks. On the last point, both schemes have been shown to suffer from potential vulnerabilities with respect to side-channel leakage [START_REF] Fouque | Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices[END_REF][START_REF] Karabulut | Falcon down: Breaking Falcon post-quantum signature scheme through side-channel attacks[END_REF], and even though the most recent implementation of FALCON appears to be protected against timing attacks [START_REF] Pornin | New efficient, constant-time implementations of Falcon[END_REF][START_REF] Howe | Isochronous gaussian sampling: From inception to implementation[END_REF], countermeasures against stronger side-channel attacks like DPA seem difficult to achieve. FALCON is also limited to NTRU lattices over power-of-two cyclotomic fields, which limits its flexibility in terms of parameter selection. That latter limitation can be overcome to some extent by extending the construction to higher rank modules, as done in MODFALCON [START_REF] Chuengsatiansup | ModFalcon: Compact signatures based on module-NTRU lattices[END_REF], but the other drawbacks remain.

Another possibility is to instantiate the randomized ApproxCVP algorithm directly over the underlying ring, instead of doing so over Z. For the randomized version of Babai rounding, this gives rise to (the ring version of) Peikert's sampler, as introduced in [START_REF] Peikert | An efficient and parallel Gaussian sampler for lattices[END_REF]. This can also be done for Babai's nearest plane algorithm, leading to what Ducas and Prest call the hybrid sampler. The resulting algorithms consist of a constant number of ring multiplications, so that quasilinear complexity is obtained "for free" as long as the underlying ring has a fast multiplication algorithm (as certainly holds for arbitrary cyclotomics). This makes them highly versatile in terms of parameter selection. They are also much simpler than FALCON, easy to parallelize, and support fairly inexpensive masking for side-channel protection.

Their downside, however, is the lower quality of the corresponding samplers compared to FALCON and DLP. Indeed, by not descending to Z but only to the ring itself, the ApproxCVP algorithm achieves less tight of a bound compared to the Klein sampler, and hence the Gaussian sampling has a larger standard deviation. This is analyzed in details in Prest's Ph.D. thesis [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF] (although certain heuristic assumptions are incorrect), and results in a substantially lower security level than FALCON and DLP.

Our contributions: the MITAKA signature scheme. In this work, we revisit in particular the hybrid sampler mentioned above, and show that the security loss compared to FALCON can be largely mitigated using a novel technique to generate higher quality trapdoors. The resulting scheme, MITAKA, 9 offers an attractive alternative to FALCON in many settings since:

it is considerably simpler from an algorithmic and an implementation standpoint, while keeping the same complexity (in fact, it is likely faster at the same dimension due to better cache locality); signature generation is parallel(izable); like Peikert's sampler, it has an online/offline structure, with the online part requiring only one-dimensional discrete Gaussian sampling with very small, constant standard deviation and simple linear operations; it can be instantiated over arbitrary cyclotomic fields 10 , which makes it quite versatile in terms of parameter selection; it is easier to protect against side-channels and can be cheaply masked even at high order.

The main idea that allows us to achieve higher security than previously expected is as follows. It is well-known that, given NTRU generators (f, g), it is easy to compute the quality of the corresponding NTRU trapdoor for the hybrid sampler (in particular, it can be done without computing the whole trapdoor). It is thus very easy to check whether a given (f, g) reaches a certain threshold in terms of bit security, and as a result, the costly part of key generation is the sampling of the random ring elements f and g themselves (with discrete Gaussian coefficients). One can therefore achieve a greatly improved security level at the same cost in terms of randomness and not much more computation time if one can "recycle" already sampled ring elements f and g.

We propose several ways of doing so. The simplest one is to generate lists {f i }, {g j } of candidate elements for f and g, and test the pairs (f i , g j ): this increases the space of candidates quadratically, instead of linearly, in the amount of generated randomness. One can also generate the f i 's, g j 's themselves as sums of Gaussians with smaller standard deviation (as long as it remains above the smoothing parameters), and consider the Galois conjugates of a given g j . By combining these techniques appropriately, we achieve a substantial security increase, of around 15 bits for typical parameter sizes. Concretely, we achieve the same security level as Dilithium-II [START_REF] Ducas | CRYSTALS-Dilithium: A lattice-based digital signature scheme[END_REF] (which was argued to reach NIST Level-I) in dimension d = 512, and attain roughly NIST Level-V in dimension d = 1024, with intermediate parameter settings possible.

We also provide a detailed security analysis of our construction, and while most of the presentation focuses on power-of-two cyclotomics for simplicity's sake and easier comparison with previous work, we also show that intermediate NIST security levels can be conveniently achieved using other base fields, e.g. of dimension 648 (same security as FALCON-512), 768 (NIST Level-II), 864 (NIST Level-III) and 972 (NIST Level-IV).

As an additional contribution, we also introduce a novel, alternate lattice Gaussian sampler for MITAKA that achieves the same complexity and the same quality as the hybrid sampler, but has a different structure, closer to Peikert's sampler. The advantage of that alternate sampler is that it is compatible with the integral lattice Gram root technique of Ducas et al. [START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF], making it possible to instantiate it without floating point arithmetic. We call the resulting construction MITAKA Z . We stress that MITAKA and MITAKA Z are two different approaches to implement the same signature scheme (in the sense that the generated signatures have statistically close distributions), and one can choose one or the other as preferred depending on whether the target platform has fast floating point arithmetic or not.

Finally, we introduce a new, concrete approach to mask those signature generation algorithms efficiently. In previous work, efficiently masking signature schemes using Gaussian sampling has proved quite challenging: even for the case of 1-dimensional centered discrete Gaussians, as in the BLISS signature scheme [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF], this is far from straightforward [START_REF] Barthe | GALACTICS: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited[END_REF]. Since MITAKA and MITAKA Z , like FALCON and DLP, require discrete Gaussian sampling with variable centers, a naive approach to masking is unlikely to yield fast results. Instead, we introduce and prove a novel gadget for sampling Gaussian distribution with an arithmetically masked center and a fixed standard deviation. This allows us to completely avoid masking Gaussian sampling operations in the online phase: 11this works for a masked center, because picking a uniform center in [0, M ) with fixed denominator and sampling a discrete Gaussian around that center results in a close to uniform distribution modulo M . Carrying out this share-by-share sampling directly causes a slight decrease in the quality of the resulting sampler (depending on the number of shares), but this can be overcome completely with careful use of rejection sampling. Combining these statistical techniques with usual provable masking methodology, we achieve very efficient side-channel protection for both MITAKA and MITAKA Z .

Preliminaries

For any a ∈ R and q > 0, let [a] q = aq /q ∈ (1/q)Z.

Linear algebra and lattices

Write A t for the transpose of any matrix A. Let s 1 (A) = max x =0

Ax

x the largest singular value of A. Let Σ ∈ R n×n be a symmetric matrix. We write Σ 0 when Σ is positive definite, i.e. x t Σx > 0 for all non-zero x ∈ R n . We also write

Σ 1 Σ 2 when Σ 1 -Σ 2 0. It holds that Σ 0 if and only if Σ -1 0 and that Σ 1 Σ 2 0 if and only if Σ -1 2 Σ -1 1 0. A lattice L is a discrete

Power-of-two cyclotomic fields

For the sake of simplicity and readability, we focus in the rest of this article on the case where the number field is a cyclotomic field of conductor a power of 2. In any case, the content of this section generalizes straightforwardly to other cyclotomic number fields, as well as most of our results. Besides, the use of cyclotomic fields is nowadays pervasive in lattice-based cryptography. In this section we therefore keep only the minimum amount of notation and definitions to follow the article. More details can be found in Appendix A.

Let d = 2 for some integer 12 with its coefficient vector (f 0 , . . . , f d-1 ) ∈ R d . The adjoint operation extends naturally to K R , and K + R is the subspace of elements satisfying f * = f .

R := K ⊗ R R[x]/(x d + 1). Each f = d-1 i=0 f i ζ i d ∈ K R can be identified
The cyclotomic field K comes with d complex field embeddings ϕ i : K → C which map f seen as a polynomial to its evaluations at the odd powers of ζ d . This defines the so-called canonical embedding ϕ(f ) := (ϕ 1 (f ), . . . , ϕ d (f )). It extends straightforwardly to K R and identifies it to the space

H = {v ∈ C d : v i = v d/2+i , 1 i d/2}. Note that ϕ(f g) = (ϕ i (f )ϕ i (g)) i d .
When needed, this embedding extends entry-wise to vectors or matrices over K R . We let K ++ R be the subset of K + R which have all positive coordinates in the canonical embedding.

2.3 Matrices of algebraic numbers and NTRU modules 2.3.1 2 × 2 K -valued matrices. This work deals with free R-modules of rank 2 in K 2 , or in other words, groups of the form Rx + Ry where x = (x 1 , x 2 ), y = (y 1 , y 2 ) span K 2 . There is a natural K -bilinear form over K 2 defined by x, y

K := x * 1 y 1 + x * 2 y 2 ∈ K . It can be checked that for all x ∈ K 2 , x, x K ∈ K ++ R .
This form comes with a corresponding notion of orthogonality. In particular, the well-known Gram-Schmidt orthogonalization procedure for a pair of linearly independent vectors b 1 , b 2 ∈ K 2 is defined as

b 1 := b 1 , b 2 := b 2 - b 1 , b 2 K b 1 , b 1 K • b 1 .
One readily checks that b 1 , b 2 K = 0. The Gram-Schmidt matrix with columns b 1 , b 2 is denoted by B and we have det

B = det B. For Σ ∈ K 2×2 R
, we write Σ * its conjugate-transpose, where * is the conjugation in K R . We extend the notion of positive definiteness for matrices with entries in K R : Σ ∈ K 2×2 R is positive definite when Σ = Σ * and all the d matrices induced by the field embeddings are positive definite. We then write Σ 0. For example, B * B is a positive definite matrix for all B ∈ K 2×2 R . Positive definite matrices admit "square roots", that is, matrices

√ Σ such that √ Σ √ Σ * = Σ.
This work uses fundamental quantities for matrices over K . The first is defined as

|B| K := max 1 i 2 ϕ( b i , b i K ) 1/2
∞ . Since the eigenvalues λ 1 , λ 2 of B * B are all in K ++ , coordinatewise square roots are well-defined. The largest singular value of (the embeddings of) B is recovered as s 1 (B) := max

1 i 2 ϕ( √ λ i ) ∞ .
NTRU Modules. Given f, g ∈ R such that f is invertible modulo some prime q ∈ Z, we let h = f -1 g mod q. The NTRU module determined by h is

L NTRU = {(u, v) ∈ R 2 : uh -v = 0 mod q}.
Two bases of this free module are of particular interest for cryptography:

B h = 1 0 h q and B f,g = f F g G ,
where F, G ∈ R are such that f G -gF = q. This module is usually seen as a lattice of volume q d in R 2d thanks to the coefficient embedding. From the explicit description of B f,g , one can derive formulas for the associated quality parameters. These are proven in Appendix A.

Lemma 1 ([42], adapted). Let B f,g be a basis of an NTRU module. We have

√ q |B f,g | K s 1 (B f,g ) and : |B f,g | 2 K = max ϕ(f f * + gg * ) ∞ , q 2 ϕ(f f * + gg * ) ∞ , s 1 (B f,g ) 2 = 1 2 ϕ T + T 2 -4q 2 ∞ ,
where

T := f f * + gg * + F F * + GG * . We have |B f,g | K = s 1 ( B)
, where B is the Gram-Schmidt orthogonalization (over K ) of B f,g .

Gaussians over rings

The Gaussian function on R d centered at c and with covariance matrix Σ 0 is defined as

ρ c,Σ (x) = exp(-1 2 (x-c) t Σ -1 (x-c)). If Σ = s 2 I d , we write also ρ c,s = exp(-x-c 2 /(2s 2
)) and call the associated Gaussian spherical. We omit c if it is 0. The normal distribution N Σ of covariance Σ then has density probability function ((2π

) d • det Σ) -1/2 ρ Σ . When we write N K R ,s , we mean that (z 1 , . . . , z d ) ← (N s/ √ d ) d is sampled and (z 1 + iz 2 , . . . , z d-1 + iz d ) is outputted.
The discrete Gaussian distribution over a full rank lattice L , centered at c and with covariance matrix Σ 0 has density function given by

∀ x ∈ L , D L ,c,Σ (x) = ρ c,Σ (x) ρ c,Σ (L ) .
For c ∈ K R and s > 0, we also use the notation c s to denote the distribution D ϕ(R),ϕ(c),s . It extends coordinate-wise to vectors in K 2 R . For ε > 0, the smoothing parameter of a lattice L is η ε (L ) = min{s > 0 : ρ 1/s (L ∨ ) 1 + ε}, where L ∨ is the dual lattice. The exact definition of the lattice dual is not needed in this work, and when L = L (B) ⊂ R d , it is enough to know the matrix B -t encodes it. We say that

√ Σ η ε (L ) when ρ 1 ( √ Σ * L ∨ ) = ρ Σ -1 (L ∨ ) 1 + ε.
In particular, one checks that rB η ε (ϕ(BR 2 )) when r η ε (R 2 ). We use the following bound.

Lemma 2 (Adapted from [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]). Let BR 2 be free R-module, and let L = M(B)Z 2d be the associated rank d lattice in R 2d . For all ε > 0,

η ε (L ) |B| K • 1 π log(2d(1 + 1/ε)) 2 .
3 Sampling discrete Gaussians in R-modules

We present three approaches to sample discrete Gaussian over rings. The first two are respectively Peikert's perturbative approach adapted from [START_REF] Peikert | An efficient and parallel Gaussian sampler for lattices[END_REF], and the hybrid sampler of Ducas and Prest [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF], which is core to MITAKA and uses the first as a subroutine. Then we describe a new sampler based on [START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF] which can involve integer arithmetic only and combines the ideas of the other two others.

In Appendix H, we also explicitly specify a set of operations that can be precomputed during the offline phase, as well as where FFT or NTT should be performed in practice.

Peikert's sampler

In [START_REF] Peikert | An efficient and parallel Gaussian sampler for lattices[END_REF], Peikert presented an efficient algorithm to sample discrete Gaussians in a target lattice, using small continuous Gaussian perturbation. On a high level, it can be thought of as a randomized version of Babai's round-off algorithm, using random (normal) perturbations to hide the lattice structure, and can be formulated directly over the algebra K R . The pseudo-code in Algorithm 1 outputs discrete Gaussians in a free rank 2 R-module L described by a basis B ∈ K 2×2 , with an arbitrary center in K 2 R . When Σ r 2 BB * , the existence of Σ 0 below is guaranteed.

Algorithm 1: RingPeikert sampler

Input: A matrix B ∈ K 2×2 such that L = ϕ(BR 2
) and a target center c ∈ K 2 R . Result: z ∈ L with distribution negligibly far from D L ,c,Σ .

1 Precomputed: a parameter r ηε(R 2 ), and

Σ0 ∈ K 2×2 R such that Σ0Σ * 0 = Σ -r 2 BB * 2 x ← Σ0 • (N K R ,1 ) 2 3 z ← B -1 (c -x) r 4 return Bz Algorithm 2: RingPeikert, one-dimensional version Input: A target center c ∈ K R .
Result: z ∈ R with distribution negligibly far from D R,c,Σ .

1 Precomputed: a parameter r ηε(R), and σ0

∈ K R such that σ * 0 σ0 = Σ -r 2 2 x ← σ0 • N K R ,1 3 return c -x r Theorem 1 ([39], adapted). Let D be the output distribution of Algorithm 1. If ε 1/2 and √ Σ s 1 (B) • η ε (R 2 )
, then the statistical distance between D and D L ,c,Σ is bounded by 2ε. Moreover, we have

sup x∈BR 2 D(x) D L (B),c,Σ (x) -1 4ε.
Theorem 1 is reproved in Appendix E for the sake of completeness, where fundamental parameters for its implementation are also analyzed. From Lemma 1 and Lemma 2, note that the condition in the statement ensures that we are above the smoothing parameter of the target lattice. In practice, the covariance parameter is a scalar multiple of the identity matrix, or a positive real "constant" if seen in K ++ R . We highlight in Algorithm 2 the one-dimensional version of Peikert's sampler, that is, outputting discrete Gaussians in R, because it appears as a subroutine of the hybrid sampler in the next section.

Ducas & Prest's hybrid sampler

In [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF], a so-called hybrid sampler is presented that outputs discrete Gaussians in free R modules of finite rank. On a high level, this hybrid sampler follows Klein's approach, which is a randomized version of the Nearest Plane algorithm. In the ring context, the randomization subroutine happens "at the ring level" thanks to a ring Gaussian sampler, instead of "at the integer level". To again hide the lattice structure, perturbations are also involved but their distribution now depends on the target center. The hybrid sampler is described in Algorithm 3, which makes use of floating-point arithmetic, and is core to the MITAKA scheme.

It relies on a ring sampler which can be instantiated by Algorithm 2. For the sake of clarity, these "Peikert sampling" steps are made explicit in lines 4-6 and 9-11. We restrict to "totally spherical" standard deviation parameters (that is, scalar matrices) as they are the main use-case of this work.

The next result is proved in Appendix F, where we also analyze the necessary floating-point precision to preserve enough bits of security.

Algorithm 3: Hybrid Gaussian sampler

Input: A target center c ∈ K 2 R , a matrix B = [b1, b2] such that L = ϕ(BR 2
) and its GSO [ b1, b2] over K , a parameter σ > 0 (corresponding to (σ, . . . , σ) ∈ K R ). Result: z with distribution negligibly far from D L ,c,σ 2 I 2d .

1 Precomputed: σi := σ 2 b i , b i -r 2 ∈ K ++ R . 2 c2 ← c, v2 ← 0 3 d2 ← b 2 ,c 2 K b 2 , b 2 K 4 u2 ← N K R ,1 5 y2 ← σ2 • u2 6 x2 ← d2 -y2 r 7 c1 ← c2 -x2b2, v1 ← x2b2 8 d1 ← b 1 ,c 1 K b 1 , b 1 K 9 u1 ← N K R ,1 10 y1 ← σ1 • u1 11 x1 ← d1 -y1 r 12 v0 ← v1 + x1b1 13 return v0
Algorithm 4: Hybrid Gaussian sampler, U version Input: A target center c = (c1, c2) ∈ K 2 , an upper triangular matrix U = [(1, 0), (u, 1)] with u ∈ K , a parameter r > 0 (corresponding to (r, . . . , r) ∈ K R ). Result: z with distribution negligibly far from D L (U),c,r . In our integer arithmetic friendly sampler presented in the next section, we rely on a specific variant where the target lattice is described by an upper triangular matrix U, or equivalently, when the Gram-Schmidt orthogonalization is the identity matrix. It is presented in Algorithm 4, and is core to MITAKA Z . In particular, in MITAKA Z the ring sampler becomes a discrete Gaussian sampler that can be emulated in integer arithmetic. This is emphasized below by RingSampler Z .

1 z2 ← RingSampler Z (c2, r) 2 c 1 ← c1 -z2u 3 z1 ← RingSampler Z (c 1 , r) 4 return z = U(z1, z2).
As a simpler version of Algorithm 3, Algorithm 4 deviates less from the discrete Gaussian it emulates; the proof can be found in Appendix F.

An integer arithmetic friendly sampler

To clarify the presentation, in this section we identify matrices over K to their structured version over Q. Fundamentally, our new sampler for D L (B),c,s combines Peikert's approach of Algorithm 1 and hybrid sampling in the case where the Gram-Schmidt is the identity. What allows us to restrict to integer arithmetic is to rely on the work of [START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF]. There, the authors showed how to generate small integral perturbation vectors, relying on a generalization of the Cholesky decomposition that can be also computed purely in integer arithmetic.

On the "hybrid side", as observed in the previous section, it is enough for us to have access to a discrete Gaussian sampler in integer arithmetic. Multiplying the output of Algorithm 4 by the Gram-Schmidt orthogonalization B = BU -1 of the target lattice basis, one would obtain vector with the correct support. The Gram-Schmidt basis may however contain entries in K that may have very large denominators. We avoid this thanks to an approximation B ∈ (1/(pq))R 2×2 of B, obtained by p-rounding of the upper right coefficient of U. The quality of this approach is essentially driven by |B f,g | K = s 1 ( B).

Algorithm 5 describes this approach. The notation U û denotes that the upper-right coefficient of the matrix is û. The procedure IntGram is fully described in [START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF], and impacts the choice of parameters for the algorithm to be actually correct. The determination of its parameters is discussed in Appendix F.3. On a high level, given in input a positive definite matrix Σ ∈ R 2×2 , it outputs a matrix A ∈ R 2×m such that AA t = Σ, and where m 2. In our context, the input is a small perturbation covariance matrix Σ p = s 2 I -B B t , where s is a large enough integer.

The offline sampler in Algorithm 6 is adapted from [START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF] and outputs from the expected distribution as long as A has been suitably computed. In terms of notation, recall that Λ(A) ⊥ ⊂ R m is the lattice of integer solutions of Ax = 0. Its analysis is given in Appendix F. [START_REF] Barthe | Masking the GLP latticebased signature scheme at any order[END_REF].

We now state the correctness of Algorithm 5, stressing that the statement is correct as long as the integral root decomposition could be carried out. In particular, the proof assumes at least that p d, and can be found in Appendix F.3.

Asymptotic security of the samplers

Hash-and-sign signatures over lattices are constructed, following the GPV framework [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], by hashing a message to the ambient space of the lattice, and returning as a signature a lattice point close to that hash digest. This is done using a "good" representation of the lattice, called the trapdoor, that enables the signer to solve the ApproxCVP problem with a relatively small approximation factor. Moreover, to prevent signatures from leaking information about the secret trapdoor, the close lattice points need to be sampled according to a distribution that is statistically independent of the trapdoor: usually a spherical discrete Gaussian distribution supported over the lattice and centered at the hash digest. This is where the algorithms from the previous sections come into play.

The security of the resulting signature scheme depends on the standard deviation of the discrete Gaussian distribution output by the sampler: the smaller the standard deviation, the closer the distance to the hash digest, the harder the corresponding ApproxCVP problem, and hence the higher the security level. As we have seen, however, there is a lower bound (depending on the trapdoor) to how small of a standard deviation the sampler can achieve while remaining statistically close to the desired spherical Gaussian: lower than that, and the distribution may start to deviate from that Gaussians in ways that could expose information about the secret trapdoor, and thus compromise the security of the signing key.

In the case of NTRU lattices, the trapdoor is the secret basis:

B f,g = f F g G ,
and the standard deviation of the discrete Gaussian obtained from this trapdoor varies depending on the sampling algorithm, as discussed in particular in [42, §6]. It can be written as:

σ = α • η ε (R 2 ) • √ q (1)
where the factor α 1, which we call the quality, depends on the sampler for a given trapdoor.

For the so-called Klein sampler used in DLP and FALCON, α √ q is the Gram-Schmidt norm

B f,g GS := max 1 i 2d b Z i 2 of B f,g over the integers.
For the Peikert sampler over K , Theorem 1 shows that α √ q = s 1 (B f,g ). Finally, for the hybrid sampler, Theorem 2 shows that

α √ q = |B f,g | K .
For a given sampler, the generators f, g should be sampled appropriately to minimize the corresponding α. In his thesis [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF], Prest analyzed the optimal choices both theoretically (under suitable heuristics) and experimentally. The resulting optimal choices for α are as follows (after correcting the flawed heuristic analysis of Prest in the case of the hybrid sampler: see our discussion in Appendix C):

heuristically, the quality of the Peikert sampler satisfies α = O(d

α √ q Best achievable α Peikert s1(B f,g ) O(d 1/4 √ log d) [42, §6.5.2] Hybrid (MITAKA) |B f,g | K O(d 1/8 log 1/4 d) [Appendix C] Klein (FALCON) B f,g GS O(1) [42, §6.5.1]
for the Klein sampler (used in DLP, and in modified form, FALCON), the heuristic analysis in [42, §6.5.1] show that it can be taken as low as e/2 ≈ 1.17 independently of the dimension, and in particular α = O(1).

These properties are summarized in Table 1.

The MITAKA signature scheme

The previous samplers can be plugged directly into the GPV framework [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] to construct secure hash-and-sign signature schemes in the random oracle model. The idea is to sign a message by first hashing it as a point in the ambient space of the lattice, and then using the sampler to construct a lattice point close to that target. The signature is then the difference between the target and the lattice point (a small vector in the lattice coset defined by the target). This is described more precisely in Algorithm 7. Both MITAKA and MITAKA Z are specific instantiations of this paradigm, using the samplers of Algorithms 3 and 5 respectively. In Algorithm 7, the acceptance bound γ for signatures is chosen slightly larger than σ √ d, for σ the standard deviation of the sampler given by Eq. ( 1) above, in order to ensure a low repetition rate for signature generation. (In the concrete security evaluation of Section 5, γ is selected so as to ensure < 10% rejection; this gives e.g. γ = 1.042σ

√

2d for d = 512). Signature verification simply recovers the second component s 2 = s 1 •h+c mod q and checks that the vector s = (s 1 , s 2 ) is of length at most γ.

The security argument of Gentry, Peikert, and Vaikuntanathan reduces the security of the signature scheme to the hardness of SIS in the underlying lattice up to bound 2γ. It is therefore invalidated if an attacker can obtain two distinct outputs of the sampler with the same center (since their difference would be a solution to this SIS problem) [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Section 6.1]. This is avoided in the signature scheme by randomizing the hash value associated with the message using a sufficiently long random salt r ∈ {0, 1} k . To avoid collisions, it suffices to pick k λ + log 2 q s for λ bits of security and q s signature queries. The choice of k = 320 as in [START_REF] Prest | [END_REF][START_REF] Chuengsatiansup | ModFalcon: Compact signatures based on module-NTRU lattices[END_REF] suffices for up to 256 bits of security.

Improved Trapdoor Generation

The Peikert, hybrid and FALCON samplers for an NTRU basis B f,g all have essentially the same complexity, and the first two are significantly simpler, easier to implement, slightly faster in the same dimension, and offer better avenues for parallelization and side-channel resistance (see Section 7). It would therefore be desirable to adopt one of the first two for practical implementations.

However, as seen in Section 3.4, the FALCON sampler has a substantial advantage in terms of security, since its Gaussian standard deviation is proportional to B f,g GS , whereas the Peikert and hybrid samplers are proportional to s 1 (B f,g ) and |B f,g | K respectively, which are both larger.

1 do 2 r $ ← {0, 1} k 3 c ← H(r m) 4 z ← Sampler(sk, (0, c)) / * Algorithm 3 or 5 * / 5 s ← (s1, s2) = (0, c) -z / * s1 • h -s2 ≡ -c mod q * / 6 while s 2 > γ 2 7 return sig = (r, s1).
This results in a significant difference in asymptotic terms, as shown in Table 1, and also in bit security terms as will become apparent in the next section.

To increase the security level achievable using the first two samplers, and in particular the hybrid sampler, we propose a new technique to significantly improve the quality of NTRU trapdoors. We note in passing that it also applies to FALCON: while it cannot yield significant improvements in terms of security, since the standard deviation it achieves is already a very small factor away from the theoretical optimum, it can be used to speed up key generation substantially. The idea is as follows.

Recall that NTRU trapdoor generation for FALCON, say, works by sampling f, g with discrete Gaussian coefficient, computing the B f,g GS of the resulting NTRU basis, and checking if this value is below the desired quality threshold. If not, we try again, and if so, the NTRU basis is completed and kept as the secret key. Trapdoor sampling for the hybrid sampler is similar. (On the other hand, for Peikert, completion has to be recomputed at each step to evaluate s 1 (B f,g )).

In this process, the costly operations are, on the one hand, the generation of the discrete Gaussian randomness, which has to be repeated several dozen times over in order to reach the desired threshold (this is not explicitly quantified by the authors of FALCON, but experiments suggest that, in many instances, upwards of 50 iterations are necessary), and, on the other hand, the completion of the basis (still costly despite recent optimizations [START_REF] Pornin | More efficient algorithms for the NTRU key generation using the field norm[END_REF]), which is only carried out once at the end and not for each iteration 13 .

To optimize the process, our idea is to amortize the cost of discrete Gaussian sampling, by constructing several candidate trapdoors from the same randomness. We propose three main ideas to do so.

Lists of candidates for f and g. The usual key generation algorithm for FALCON, as already mentioned, normally ends up generating many pairs (f i , g i ), and tests each of them as a candidate first vector for the NTRU lattice.

Since we are generating Gaussian vectors f i and g i anyway, we can easily recycle this generated randomness by testing all the mixed pairs (f i , g j ) instead: this results in a set of possible candidates which increases quadratically with the number of random vectors we generate, instead of just linearly.

Generating the Gaussian vectors as linear combinations. Independently, one can generate each candidate vector f as a linear combination k=1 f (k) where each f (k) is sampled from a discrete Gaussian of standard deviation σ 0 / √ , for σ 0 the desired standard deviation of f . It is well-known that this results in the correct distribution provided that σ 0 / √ remains above the smoothing parameter of Z [START_REF] Micciancio | Gaussian sampling over the integers: Efficient, generic, constant-time[END_REF]. In fact, the FALCON implementation already does so for d = 512, where the candidate vectors are sums of two Gaussians vectors of standard deviation √ 2 times lower. Now, when generating several f i 's, one obtains lists

L k = {f (k)
i } i of Gaussian vectors. It is again possible to recycle this generated randomness by mixing and matching among those lists, and constructing candidates f of the form f (k) i k for varying indices i k , so that the total set of candidates is in bijection with k L k . Its size increases like the -th power of the size of the lists.

Using the Galois action. Finally, one can expand the set of candidates for g, say, by applying the action of the Galois group. In principle, other unitary transformations of g, even less structured ones like randomly permuting the coefficients in the power basis, could also be considered, but the Galois action in particular is convenient as it is expressed as a circular permutation on the embeddings ϕ i (g) of g (i.e., the Fourier coefficients), and for the hybrid sampler, the computation of the quality is entirely carried out in the Fourier domain.

Concretely, recall from Lemma 1 that the quality parameter α of the hybrid sampler associated with B f,g satisfies:

α 2 = |B f,g | 2 K q = max max i z i q , q min i z i where z i = ϕ i (f f * + gg * ) = |ϕ i (f )| 2 + |ϕ i (g)| 2 ∈ R + .
It is easy to compute the embeddings z τ i associated to B f,τ (g) for some Galois automorphism τ of K simply by applying the corresponding permutation on the components of ϕ(g). Moreover, we see from this representation that the conjugation τ * : g → g * leaves this quality invariant, so the relevant Galois elements to consider are a set of representatives of Gal(K /Q)/ τ * . For power-of-two cyclotomics, one can for example use τ Security considerations. The techniques above can potentially skew the distribution of f and g somewhat compared to the case when each tested (f, g) that fails to pass the security threshold is thrown away. However, this is not really cause for concern: the precise distribution of f and g is not known to affect the security of the signature scheme other than in two ways:

the extent to which it affects the geometry of the trapdoor, as encoded in the quality parameter α already; and the length of (f, g) itself as it affects key recovery security, but this length is always at least as large in our setting as in FALCON.

This indicates that our optimized secret keys do not weaken the scheme.

Concrete example.

In Algorithm 8, we describe an example key generation procedure that combines all three techniques presented above: we construct lists of candidates for f and g and test all possible pairs. Moreover, each f and g itself is sampled as a sum of = 2 narrower Gaussians, and the list of g's is expanded using the Galois action. Of course, different combinations of the techniques are also possible, but this particular one offers a good balance between efficiency and achievable security. Input: Desired standard deviation σ0 of f and g, target quality α of the Gaussian, number of samples m to generate, set G of Galois automorphisms to apply. The total search space is of size #G • m 4 for 4m generated discrete Gaussian vectors. Result: NTRU first trapdoor vector (f, g) with quality better than α.

1 for i ∈ [1, m] do 2 f i ← D R,σ 0 / √ 2 , f i ← D R,σ 0 / √ 2 3 g i ← D R,σ 0 / √ 2 , g i ← D R,σ 0 / √ 2 4 end for 5 L f ← {f i + f j | i, j ∈ [1, m]} 6 Lg ← {τ (g k + g ) | k, ∈ [1, m], τ ∈ G} 7 Lu ← {(f, ϕ(f f * )) | f ∈ L f } 8 Lv ← {(g, ϕ(gg * )) | g ∈ Lg} 9 for (f, u) ∈ Lu, (g, v) ∈ Lv do 10 z ← u + v 11
if q/α 2 zi α 2 q for all i then return (f, g)

12 end for 13 restart
Using this approach, as shown in Fig. 1, we are able to efficiently generate trapdoors with α 2.04 for d = 512, and α 2.33 for d = 1024 by m ≈ 16 (corresponding to generating 64 narrow Gaussian vectors to select one candidate (f, g), largely in line with FALCON).

Improved search via early aborts and filtering. Key generation using the technique above involves an exhaustive search in a relatively large set of candidates L u × L v , and testing each candidate involves O(d) comparisons:

q/α 2 u i + v i α 2 q for 1 i d/2,
as done in Step 11 of Algorithm 8. One can of course reject a candidate immediately as soon as one of the comparison fails, but this can happen arbitrarily late in the loop through the indices.

However, it results from the analysis of Appendix C that the lower bound condition is much more likely to fail than the upper bound for a given candidate. Moreover, if we fix u, then it is more likely to fail on any given v for the indices i such that u i is small. One can therefore improve the algorithm by a wide margin by carrying out a simple precomputation on u: extract the list of indices S u (w) of the w smallest elements of u for some w d/2 (this can be done without sorting, in time O(d)). Then, for each corresponding candidate v, first check in time O(w) whether the lower bound condition holds on the indices in S u (w): if so, the comparison is carried out normally, and otherwise v is rejected early.

Picking for example w = 25, we find that around 99.8% of candidates are rejected early in that way for our parameters, greatly reducing the number of full-fledged comparisons. All in all, this lets us achieve a speed-up of more than 5-to 10-fold as d ranges from 512 to 1024.

An additional, very simple optimization is to filter out values u, v such that u ∞ > α 2 q (and similarly for v) from the lists L u and L v , since such candidates clearly cannot satisfy the comparison.

Security analysis of MITAKA

Concrete security. In order to assess the concrete security of our signature scheme, we proceed using the usual cryptanalytic methodology of estimating the complexity of the best attacks against key recovery attacks on the one hand, and signature forgery on the other. The detailed analysis is carried out in Appendix G. For the parameter choices relevant to our scheme (in which the vectors of the trapdoor basis are not unusually small), key recovery is always harder than signature forgery, and therefore the cost of signature forgery is what determines the security level. Using the condition of Eq. ( 12), we see that the security of the forgery is a function of the standard deviation of the lattice Gaussian sampler used in the signature function, which itself depends on the quality α of the trapdoor, as discussed in Section 3.4. This analysis translates into concrete bit-security estimates following the methodology of NEWHOPE [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF], sometimes called "core-SVP methodology". In this model [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF][START_REF] Laarhoven | Search problems in cryptography[END_REF], the bit complexity of lattice sieving (which is asymptotically the best SVP oracle) is taken as 0.292β in the classical setting and 0.265β in the quantum setting in dimension β. The resulting security in terms of α is given in Fig. 2 in dimensions 512 and 1024. This allows us to compare MITAKA with FALCON as well as with a "naive" version of the hybrid sampler that would omit the optimizations of Section 4; the results are presented in Table 2.

In addition, as mentioned earlier, our construction can be instantiated over more general base fields than power-of-two cyclotomics, which enables us to choose security level in a much more flexible way than FALCON. This is analyzed in Appendix B. Example security levels which can be reached in this way are presented in Table 3. For such fields, we can choose the modulus q to be the first prime which is congurant to 1 modulo the conductor.

Asymptotic security.

As for all signature schemes in the GPV framework, the EUF-CMA security of our scheme in an asymptotic sense reduces, both in the classical [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] and quantum random oracle models [START_REF] Boneh | Random oracles in a quantum world[END_REF], to the SIS problem in the underlying lattice (in this case, an instance of Module-SIS [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]). However, as is the case for FALCON (and as holds, similarly, for Dilithium), the SIS bound in Euclidean norm for the standard parameter choice (q = 12289) makes the underlying assumption vacuous. This is not known to lead to any attack, and can be addressed by increasing q if so desired, or reducing to the SIS problem in infinity norm instead.

Implementation Results

In order to assess the practicality of MITAKA, we carried out a preliminary, pure C implementation 14 of the scheme (using the sampler described in Algorithm 3). For easier and fairer comparison, we reused the polynomial arithmetic and FFT of the reference implementation of FALCON, as well as its pseudorandom generator (an implementation of ChaCha20). An important caveat is that the current version of our code includes direct calls to floating point transcendental functions, and therefore cannot be guaranteed to run in constant time as is. It is well-known that this can be addressed using the polynomial approximation techniques used e.g. in [START_REF] Zhao | FACCT: Fast, compact, and constant-time discrete gaussian sampler over integers[END_REF][START_REF] Barthe | GALACTICS: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited[END_REF][START_REF] Howe | Isochronous gaussian sampling: From inception to implementation[END_REF], but full precision estimates for the required functions are left as future work. 14 It will soon be available on a public repository. Nevertheless, in our tests run on a single core of an Intel Core i7-1065G7 @ 1.30GHz laptop, this implementation is more than twice as fast as the reference implementation of FALCON: about 6300 signatures per second for our code using d = 512 (resp. 3100 signatures per second for d = 1024), compared to 2800 for FALCON-512 (resp. 1400 for FALCON-1024). We believe that these preliminary results are quite promising for MITAKA.

Furthermore, performance is mainly driven by the cost of the continuous and discrete 1D Gaussian samplers. Since signature generation can be split in an offline part and an online part (see Algorithm 13), MITAKA can offer even better speed results if some computations can be performed between signatures. While these results are favorable to MITAKA, optimized implementations on specific architectures would be needed for a definitive comparison to FALCON.

Side-channel Countermeasure

First, our signature scheme can be easily made isochronous. According to [START_REF] Howe | Isochronous gaussian sampling: From inception to implementation[END_REF], isochrony ensures independence between the running time of the algorithm and the secret values. For our signature, the absence of conditional branches implies that one can implement our signature isochronously using standard techniques.

In a second step, we turn our signature scheme into an equivalent one which is protected against more powerful side-channel attacks that exploit the leakage of several executions. More precisely, following the seminal work due to Ishai, Sahai, and Wagner [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF], we aim to protect our samplers for MITAKA and MITAKA Z alternative described in Section 3 from the so-called t-probing side-channel adversary, who is able to peek at up to t intermediate variables per each invocation of an algorithm. The masking countermeasure is a technique to mitigate such attacks, by additively secret-sharing every sensitive variables into t + 1 values in R. The integer t is often referred to as masking order. Essentially, we will provide two functionally equivalent alternative algorithms for MITAKA and MITAKA Z where any set of at most t intermediate variables is independent from the secret. In this paper, we consider the masking order as a-potentially largearbitrary variable t. Clearly, high masking order allows a side-channel protected implementation to tolerate stronger probing attacks with larger number of probes. For a ring element a ∈ R, we say that a vector (a i ) 0 i t ∈ R t+1 is an arithmetic masking of a if a = i∈[0,t] a i . For readability, we often write a := (a i ) 0 i t .

The masking of our signature presents three unprecedented difficulties in masked lattice-based schemes.

1. Compared to Fiat-Shamir with aborts, masking the Gaussian sampling is unavoidable. We here present a novel technique to efficiently mask Gaussian sampling in Section 7.2.1. Notably, our approach only requires arithmetic masking, allowing us to avoid any conversion between arithmetic and Boolean shares during the online phase. 2. The computations are performed in Z instead of a modular ring. This feature does not appear in any other lattice-based scheme. Thus, we need to fix a bound on the size of the masks and make sure that the computations will never pass this bound. Let Q mask be the bound on the largest manipulated integer, the shares of a are implicitly reduced modulo Q mask . Sometimes we refine the notation • into • M to explicitly specify a modulus M < Q mask for secret-sharing. 3. Some polynomial multiplications need both inputs to be masked. This unusual operation does not appear in LWE-based schemes where the multiplications are performed between a public matrix of polynomial and a masked vector. We handle this problem with a function in Section 7.2.2.

Preliminaries on masking countermeasure

The most basic security notion for a masking countermeasure is the t-privacy of a gadget G [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF]. This notion guarantees that any set of at most t intermediate variables observed during the computation is independent of the secret input. While the idea behind the notion is relatively simple, t-private gadgets are unfortunately not composable, meaning that a gadget consisting of multiple t-private sub-gadgets may not be necessarily secure. Hence in this work we rely on the following more handy security notions introduced by Barthe et al. [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF].

Definition 1 (t-NI, t-SNI). Let G be a gadget with inputs (x i ) 0 i t ∈ R t+1 and outputs (y i ) 0 i t ∈ R t+1 . Suppose that for any set of t It is easy to check that t-SNI implies t-NI which implies t-probing security. The above notion can be naturally extended for a gadget with multiple input and output sharings. Note that linear operations performed share-wise (such as addition of two sharings, or multiplication by a constant) are trivially t-NI, as each computation on share i can be simulated from the input share x i . Building blocks satisfying either NI or SNI can be easily composed with each other, by inserting the Refresh gadgets at suitable locations to re-randomize shares [2, Proposition 4]. It is also internally used in the Unmask gadget before taking the sum of shares, so that a probe on any partial sum doesn't leak more information than one input share [START_REF] Barthe | Masking the GLP latticebased signature scheme at any order[END_REF]. Typically, the non-interference notions only deal with gadgets where all of the inputs and outputs are sensitive. To also handle public, non-sensitive values, a weaker notion called NI with public output (t-NIo) was proposed in [START_REF] Barthe | Masking the GLP latticebased signature scheme at any order[END_REF]. As stated in [3, Lemma 1], if a gadget G is t-NI secure it is also t-NIo secure for any public outputs.

In the sequel, we use the SecMult gadget that computes the multiplication of two masked inputs. It is one of the key building blocks of masking theory and has been introduced in [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF][START_REF] Rivain | Provably secure higher-order masking of AES[END_REF] and proved t-SNI in [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF].

We also use the MaskedCDT gadget that generates a masked sample that follows a tabulated Gaussian distribution of a fixed center c and a fixed standard deviation r. The table values are not sensitive so they are the same as for the unmasked implementation. This masked CDT algorithm was introduced in [START_REF] Barthe | GALACTICS: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited[END_REF][START_REF] Gérard | An efficient and provable masked implementation of qtesla[END_REF] and proved t-NI.

Two new gadgets

In Table 4, we introduce the known and new gadgets necessary for our sampler along with their properties. These properties will be proved in the following subsections.

Share-by-share Gaussian sampling

In this section, we present a novel technique for generating a masked Gaussian sampling with an arbitrary masked center c of c ∈ 1/C • Z for some fixed integer C. Note that 1/C •Z is not a ring, and thus the multiplication is not well-defined for shares in 1/C •Z. This is not an issue in our application, since we never carry out multiplication of two sharings in this form. We aim at considering a share by share generation. A direct and fast approach is to generate z i ← D Z,c i ,r/ √ t+1 for each share of c and to output (z 0 , • • • , z t ) as z . To ensure z ∼ D Z,c,r , it requires r ≥ 2(t + 1)η (Z) according to [START_REF] Micciancio | Hardness of SIS and LWE with small parameters[END_REF], which yields a considerable security loss. To overcome this issue, we propose a different approach sampling shares over 1/B • Z with B := 2(t + 1) and utilizing rejection sampling to keep the masked output over Z. Our masked Gaussian sampling algorithm is presented in Algorithm 9.

Correctness We now show that Algorithm 9 is correct for r ≥ η (Z). Since r ≥ η (Z) ≥ √

2(t+1) B η (Z), by [35, Theorem 3], in step 4, z = t i=0 z i follows D 1/B•Z,c,r
. Thanks to the rejection sampling, the support of the final output z is Z and noticing that the probability of each output z is proportional to ρ r,c (z), it follows that the distribution of z is D Z,c,r . The rejection rate is

ρr,c(Z) ρr,c(1/B•Z) ≈ 1/B as r ≥ η (Z) ≥ η (1/B • Z).
All in all, we have shown that Algorithm 9 provides z ∼ D Z,c,r at the cost of about 2(t + 1) average rejections.

Masking security Let z = i zi mod 1. As the Unmask gadget is only NIo secure with public output z, we need to show that z does not leak sensitive information, i.e. the output z and the center c. Indeed, the output only occurs when z = 0, hence z is independent of the output. The support of z is

1 B {0, 1, • • • , B -1} and Pr[z = i B ] ∝ ρ c,r (Z + i B ) = ρ c-i B ,r (Z) ∈ [ 1- 1+
, 1]ρ r (Z) due to the smoothness condition r ≥ η (Z). Therefore the distribution of z is negligibly close to uniform independent of c. Consequently, z can be securely unmasked. As all the operations are performed share by share and assuming uniformly distributed shares of the input center c, we can deduce the following lemma. Lemma 3. The gadget GaussShareByShare is t-NIo secure with public output z.

In the implementation, one needs to instantiate an unmasked Gaussian sampling with arbitrary center and fixed standard deviation (line 2 of Algorithm 9). We chose a table based approach and follow the technique of [START_REF] Micciancio | Gaussian sampling over the integers: Efficient, generic, constant-time[END_REF] to use a reduced number of tables.

Polynomial multiplication

In some lattice-based schemes such as Kyber or Dilithium, polynomial multiplication is always performed between a sensitive and a public polynomial. This means that, using polynomials protected with arithmetic masking, one can multiply each share independently by the public unmasked polynomial and obtain an arithmetic sharing of the result of the multiplication. In this work, we have polynomials multiplications with both operand in arithmetic masked form. Given a and b ∈ R t+1 , we want to compute c ∈ R t+1 such , v , A ) and a masked vector c for a center c ∈ R 2 , both arithmetically masked mod Q mask . Result: An unmasked sample z ∼ D L (B),s,c .

1 Offline 2 p ← MaskedOfflineSampling( A ) 3 Online 4 c pert ← c -p 5 c pert ← SecNTTMult( B * -1 , c pert ) 6 v ← MaskedOnlineSampling( v , c pert ) 7 z ← SecNTTMult( B * , v )
8 return t i=0 zi mod Q mask observation from steps 3 to 7 can be perfectly simulated with at most δ 3 shared (polynomials) of â and b. The linearity of the NTT with arithmetic masking allows to finish proving that every set of size at most t observations containing 4 i=1 δ i (resp. δ 5 ) intermediate (resp. returned) polynomial shares can be perfectly simulated with at most 4 i=1 δ i polynomial shares of each input. In the following, we extrapolate this polynomial multiplication technique to matrices of polynomials and keep the same notation SecNTTMult. We also remark that although SecNTTMult are sometimes called back-to-back in the masked samplers, this can be further optimized in practice: to minimize the number of NTT/NTT -1 invocations in an implementation, one could keep the NTT representation as much as possible, and then bring it back to the coefficient domain whenever it encounters GaussShareByShare, as explicitly described in H.

Masking the MITAKA Z sampler

The detailed overall structure of the sampler is presented in Algorithm 10; the algorithms for the online and offline samplings are detailed in Appendix I.1. We remark that Algorithm 10 consists in a linear succession of gadgets with no dependency cycle, i.e. each line depends on freshly computed masked inputs. Thus, one can show that this algorithm is t-NI, as proved in Theorem 4 below. The proof is detailed in Section I.2. Theorem 4. The masked MITAKA Z sampler (Alg. 10) is t-NIo with public output z.

Masking the MITAKA samplers

Algorithm 17 (resp. Algorithm 18) corresponds to our masked version of the RingPeikert sampler of Algorithm 1 (resp. the Hybrid sampler of Algorithm 3). Although masked MITAKA is instantiated with the MaskedHybrid sampler, we also include MaskedRingPeikert for completeness because the former can be essentially obtained by extending the basic masking paradigm outlined in the latter.

Contrary to MITAKA Z , one can remark that we here need to mask floating-point arithmetic. However, we can avoid it by representing each sensitive variable from K R as a fixed-point number. Concretely, an element x ∈ K R is approximated by x ∈ K R such that every coefficient of q k x is an integer, where k is a parameter determining the precision. Then we can secret-share q k x in Z d Q mask for Q mask q k . Since we do not perform many multiplication operations, an accumulated scaling factor does not break the correctness of sampler if we choose sufficiently large Q mask .

We also remark that a secret-shared center in fixed-point representation must be divided by a scaling factor q k for the following 1-dimensional discrete Gaussian sampling to work share-byshare (i.e. division of q k v i,j at line 9-12 of Alg. 17, and of q k z i,j at lines 12-14 and 19-21 of Alg. 18, respectively). This division can be performed in floating-point arithmetic in practice. For the sum of shares to represent the correct center in the MaskedRingPeikert sampler, we further set Q mask = q k+ for some > 0. The resulting shares after division form a sharing of v = [(v 1,j ) j∈[0,d-1] , (v 2,j ) j∈[0,d-1] ] over (Q/q Z) 2d . Thanks to our GaussShareByShare introduced earlier, we are able to perform the discrete Gaussian sampling independently w.r.t each share of the center, while avoiding a factor of √ t + 1 overhead incurred in the standard deviation. As a result we obtain shares of discrete Gaussian samples z i,j q such that the distribution of z i,j is statistically close to D Z,v i,j ,r mod q for every i = 1, 2 and j ∈ [0, d -1]. Since the output values of the signature are defined mod q we can further map the shares to • q and the remaining computations can be performed mod q.

Since we invoke the above routine twice in the MaskedHybrid sampler, the initial masking modulus needs to be increased so that no wrap-around occurs during the masked computation of the second nearest plane. Concretely, the first nearest plane operations are computed with modulus Q mask = q 2k+ ; the second nearest plane operations are performed on • q k+ , with corresponding arithmetic shares of sensitive inputs; the output values can be represented in • q as in the MaskedRingPeikert.

Although a naive implementation of the MITAKA sampler should rely on floating-point arithmetic and thus naturally carry out FFT-based polynomial multiplications (as presented in Alg. 12), we instead make use of NTT in our masked algorithms. Notice that the masked instances only deal with a multiplication between polynomials mapped to Z Q mask [x]/(x d + 1) (or Z q +k [x]/(x d + 1) during the second nearest plane of the Hybrid sampler) thanks to the fixed-point representation. This allows us to exploit SecNTTMult as in MaskedMITAKA Z Sampler. One caveat is that in the current setting Q mask is restricted to a power of q, but we are able to show such a choice is indeed NTT-friendly. Recall that the prime q is usually chosen such that q = 1 mod 2d, so that x d + 1 has exactly d roots (ζ, ζ 3 , . . . , ζ 2d-1 ) over Z q . Now thanks to the Hensel lifting, one can construct another set of d roots (ω, ω 3 , . . . , ω 2d-1 ) over Z q 2 , such that ω = ζ mod q. By iterating this procedure until the roots for a sufficiently large modulus Q mask are obtained, we can indeed utilize the NTT for evaluating f (x) ∈ Z Q mask [x]/(x d + 1) on the primitive 2d-th roots of unity.

We are able to prove that both masked samplers meet the standard security notion (t-NIo) for masked signature schemes. The proof is detailed in Section I.3 and I.4.

Theorem 5. The masked MITAKA sampler (Alg. 18) is t-NIo secure with public output v 0 .

A Additional background

In the coefficient representation, the adjoint is given by f * = (f 0 , -f d-1 , . . . , -f 1 ). We have √ d f = ϕ(f ) , where both norms are 2 norm over the coefficients of the elements. All f ∈ K R can also be represented by the nega-circulant matrix M(f ) ∈ R d×d of multiplication by f in the power basis 1, x, . . . , x d-1 of R[x]/(x d + 1). This extends block-wise to matrices over K R .

H K ⊂ K R ϕ : : coeff $ $ R d DFT O O
For this work, there are two useful representations of K R , and embeddings of K extend straightforwardly to this algebra. The coefficient embedding directly identifies a real polynomial in R[x]/(x d + 1) with its coefficient vector in R d endowed with the standard dot product, while the embedding ϕ identifies it to the space

H = {v ∈ C d : v i = v d/2+i , 1 i d/2}
. The standard Hermitian product on C d induces a real inner product on H. The Discrete Fourier Transform (DFT) gives a linear isomorphism between the coefficient embedding space and H, which is depicted by the commutative diagram on the left. In practice, it can be computed in quasilinear time using the Fast Fourier Transform (FFT) algorithm. In this work we also consider implicitly a version of NTRU lattices under the embedding ϕ, which can be described thanks to the matrices

ϕ i (B f,g ) := ϕ i (f ) ϕ i (F ) ϕ i (g) ϕ i (G) , and
ϕ(B f,g ) :=    ϕ 1 (B f,g ) . . . ϕ d (B f,g )    ∈ C 2d×2d . Noting that det ϕ i (B f,g ) = ϕ i (det B f,g ) = q, the lattice ϕ(B f,g R 2 ) has volume q d ∆ K in H. Let B f,g = [b 1 |b 2 ] and b 2 = ( F , G) the second Gram-Schmidt vector of B f,g . For all i d/2, note that ϕ i ( b 1 , b 1 K ) = |ϕ i (f )| 2 + |ϕ i (g)| 2 and ϕ i ( b 2 , b 2 K ) = |ϕ i ( F )| 2 + |ϕ i ( G)| 2 .
In particular, the Euclidean norm of the largest Gram-Schmidt vector of ϕ

(B f,g ) is |B f,g | K . Proof (Proof of Lemma 1). With a basis B f,g = [b 1 |b 2 ], we have b 1 = (f, g) of squared norm f f * + gg * = b 1 , b 1 K , and det B * B = q 2 = b 1 , b 1 K b 2 , b 2 K .
Both the left side of the claimed inequality and the expression of

|B f,g | K follow. The K R -spectrum of B * B is { b 1 , b 1 K , b 2 , b 2 K }.
In particular, we get

s 1 ( B) 2 = max( ϕ( b 1 , b 1 ) ∞ , ϕ( b 2 , b 2 ) ∞ ),
which gives the last claimed equality.

Let e 1 , . . . , e 2d be the canonical basis of C 2d . Consequently, we have

ϕ(B f,g )e 2i-1 2 = |ϕ i (f )| 2 + |ϕ i (g)| 2 and ϕ(B f,g )e 2i 2 = |ϕ i (F )| 2 + |ϕ i (G)| 2 . By definition of the operator norm, this gives max( ϕ( b 1 , b 1 K ) ∞ , ϕ( b 2 , b 2 K ) ∞ ) s 1 (B) 2 .
We check that ϕ i ( b 2 ) is the Gram-Schmidt orthogonalization of ϕ i (b 2 ) with respect to ϕ i (b 1 ), hence we have

ϕ i ( b 2 ) 2 = ϕ i ( b 2 , b 2 K ) ϕ i (b 2 ) 2 = ϕ i ( b 2 , b 2 K ),
for all i. This implies the right side of the inequality. Next, the trace of B * f,g B f,g is T ∈ K ++ , so that its characteristic polynomial is χ = X 2 -T X + q 2 with totally real discriminant ∆ = T 2 -4q 2 . If there was an embedding K → C where ∆ is negative, this would contradict that the corresponding embedding of B * f,g B f,g is positive definite in the usual sense. Hence ∆ ∈ K ++ , and this also means that (each embedding of) T +

√

∆ is larger than (the corresponding embedding of) T -√ ∆. The last claim follows.

In matrix form, one can write the Gram-Schmidt orthogonalization as

B = BU u with u = b 1 ,b 2 K b 1 ,b 1 K and U u := 1 u 1 ∈ K 2×2 .
For all u, u ∈ K , one has

U -1 u = U -u and U u U u = U u+u .

B Finer-grained selection parameter using cyclotomic fields of composite conductors

As mentioned earlier, a strength of the MITAKA scheme lies in the possibility to instantiate it over any number fields K . To remain practically competitive, one needs to be sable to sample efficiently discrete Gaussian over its ring of integers R = O K . We saw that on cyclotomic of conductor 2 n , this is trivially the case as the power basis is orthogonal; and as a result sampling over R boils down to perform a coefficient wise sampling. In this section, we show that we can efficiently sample in cyclotomic fields of smooth enough conductor. ). As Q(ζ m ) is the compositum of the primepower cyclotomic fields Q(ζ 2 a and Q(ζ 2 b , its ring of integers is the tensor product of the ring of integers of these two fields, so that a routine computation ensures that the Gram-matrix of a well chosen reordering of B in the canonical embedding is:

B.1 Geometry of the power basis

ϕ(m) p -1 G(p, b) ⊗ Id ϕ(m) p-1
, where

G(p, b) = Circ p-1 (p -1, -1, . . . , -1) if b = 0 Circ p-1 (p -1, 1, -1, . . . , -1, 1) if b > 0 ,
for Circ p-1 (X) designating the circulant matrix of size p -1 × p -1 and coefficients following the (p -1)-uple X.

B.2 Sampling

As a consequence, we can use the hybrid sampler to reduce the sampling over R to a module sampling over a module of rank p -1, which Gram-matrix is G(p, B), defined over a subring isometric to ϕ(m) p-1 Z ϕ(m) p-1 . Let us study this matrix in more details. Its principal minor G i of order i is the circulant matrix Circ i (p -1, -1, . . . , -1). Elementary theory of Toeplitz-like matrices ensures that this minor have for spectrum:

Sp(G i ) = {p -i, p, . . . , p i-1-times },
so that its determinant is det(G i ) = (p -i)p i-1 . Henceforth a direct induction ensures that the (square of the) diagonal of the Cholesky decomposition of

G(p, b) is p -1, (p -2)p p -1 , (p -3)p (p -2) , . . . , p 2 ,
which is a decreasing sequence. Hence the maximum value of the diagonal elements of the Cholesky decomposition of

G(p, b) is √ p -1.
As it is also the norm of the corresponding Gram-Schmidt vectors. As such, the hybrid sampler induces an additional √ p -1 compared to the sampling over the power-of-two cyclotomic fields.

B.3 Practical impact on the parameter selction

Using this analysis, we get a wider range of parameters for instantiating the MITAKA scheme. In particular, the 3-smooth conductors are of particular interest as they only induce a loss of a factor √ 2 in the sampler quality and allows sampling which is asymptotically as fast as the sampling in power-of-two conductors, using the hybrid sampler. In Fig. 3, we show the impact of the base field on the bit-security with regards to the parameter α. Moreover, achievable quality parameters α for the MITAKA hybrid sampler when using the key generation algorithm of Section 4 are displayed in Fig. 4 (for each individual degree) and summarized in Fig. 5 based on the median output of Algorithm 8.

C Concentration bounds for Gamma distributions

Let X ∼ Γ (α, β) be a Gamma-distributed random variable. Its logarithmic moment generating function is as follows for all λ < β:

Φ X (λ) = log E e λX = log +∞ 0 e λx • β α Γ (α) x α-1 e -βx dx = log β α Γ (α) +∞ 0 x α-1 e (λ-β)x dx = log β α Γ (α) +∞ 0 z α-1 (β -λ) α-1 e -z dz β -λ = log β α Γ (α) • Γ (α) (β -λ) α = -α log 1 - λ β .
In particular, Φ X (λ) = α β-λ , and thus the map λ → tλ -Φ X (λ) is maximal at λ 0 such that:

t = α β -λ 0 , namely λ 0 = β - α t
(assuming t > 0; otherwise the function is unbounded on (-∞, β)). Therefore, the Cramér transform of X is given by: (d) Degree 972 Fig. 5. Quality α reached in 3-powersmooth degrees by the optimized sampler of Algorithm 8 for various choices of m (50 trials each, σ0 = 1.17 q/2d, G coset representatives of Gal(K /Q)/ τ * ).

Φ * (t) = sup λ<1 tλ -Φ X (λ) = tλ 0 -Φ X (λ 0 ) = βt -α -α log βt α 1
for t > 0. Noting that E[X] = Φ X (0) = α/β, the Cramér-Chernoff inequality then yields:

Pr[X > t] e α-βt βt α α eβt α α for t > α β , (2)
Pr[X < t] e α-βt βt α α (2e) α e -βt/2 for 0 < t < α β , (3)
where the second inequalities in the two cases follow from e -βt 1 and βt/α 2e βt/2α respectively. Now we consider X 1 , . . . , X k ∼ Γ (α, β) independent gamma-distributed random variables, and want to estimate the tail bound on max(X 1 , . . . , X k , γ/X 1 , . . . , γ/X k ) for some constant γ > 0.

On the one hand, by the union bound and Eq. ( 3), we have, for 0 < γ/t < α/β:

Pr max γ X 1 , . . . , γ X k ) > t = Pr min(X 1 , . . . , X k ) < γ t k eβγ αt α .
In particular, we have Pr[max(γ/X 1 , . . . , γ/X k ) > t] δ min as soon as:

k eβγ αt α δ min ⇐⇒ eβγ αt δ min k 1/α ⇐⇒ t eβγ α k δ min 1/α .
On the other hand, by the union bound and Eq. ( 2), we also have, for t > α/β:

Pr[max(X 1 , . . . , X k ) > t] k(2e) α e -βt/2 .
In particular, we have Pr[max(X 1 , . . . , X k ) > t] δ max as soon as:

k(2e) α e -βt/2 δ max ⇐⇒ α log(2e) - β 2 t -log k δ max ⇐⇒ t 2 β log k δ max + α log(2e) .
This results in the following theorem.

Theorem 6. Let X 1 , . . . , X k ∼ Γ (α, β) independent gamma-distributed random variables, and fix γ > 0, δ min ∈ (0, 1) and δ max ∈ (0, 1). We have:

Pr max X 1 , . . . , X k , γ X 1 , . . . , γ X k < max(t min , t max ) δ min + δ max
where:

t min = eβγ α k δ min 1/α and t max = 2 β log k δ max + α log(2e) .
This simply follows from the union bound applied to the previous inequalities, together with the observation that t min and t max always satisfy the required bounds 0 < γ/t min < α/β and t max > α/β. We can then apply this result to estimate the quality of the hybrid sampler obtained from an NTRU basis B f,g , which is given by the norm |B f,g | K , where (as recalled in Lemma 1):

|B f,g | 2 K = max ϕ(f f * + gg * ) ∞ , q 2 ϕ(f f * + gg * ) ∞ . (4)
The ring elements f, g have all their coefficients sampled independently according to the centered discrete Gaussian of standard deviation σ 0 = νq 4d for some ν > 0. Then, all the embeddings ϕ i (f ), ϕ i (g) ∈ C are (statistically close to) 2-dimensional discrete Gaussian of standard deviation νq/4, which we heuristically assume behave like normal vectors of the same standard deviation. 15 Then, the

ϕ i (f f * ), ϕ i (gg * ) (1 i d/2) are independent scaled χ 2 (2) dis- tributed random variables, or equivalently Γ 1, 2
νq -distributed random variables. As a result, the

X i = ϕ i (f f * + gg * ) (1 i d/2) are independent Γ 2, 2
νq -distributed random variables. Now, by Eq. ( 4), we have:

|B f,g | 2 K = max X 1 , . . . , X d/2 , q 2 X 1 , . . . , q 2 X d/2 ,
which is of the form considered in Theorem 6 with α = 2, β = 2 νq , γ = q 2 and k = d/2. Therefore, it follows that for any choice of δ min , δ max ∈ (0, 1), Pr |B f,g | 2 K < max(t min , t max ) δ min + δ max , where:

t min = eq ν d 2δ min
and t max = νq log 2e 2 d δ max .

We can moreover choose ν in key generation in such a way that t min = t max , by setting:

ν = e log(2e 2 d/δ max ) • 4 d 2δ min .
Picking e.g.

δ max = δ min = 1/4, we get Pr[|B f,g | 2 K < t] 1/2
, where:

t = q e log(8e 2 d) 4 √ 2d = O(q • d 1/4 log 1/2 d).
Thus, the quality of the hybrid sampler scales as O(d 1/8 log 1/4 d), and not √ log d as incorrectly claimed in [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF]. The error in that work was due to the overly optimistic assumption that the q 2 /ϕ i (f f * + gg * ) components had the same tail behavior as the ϕ i (f f * + gg * ), which is not the case, since they are Inverse-Gamma distributed, and thus not sub-Gamma; in fact, they do not even have finite variance.

D Security arguments from Renyi divergence

Let D, D be two distributions sharing the same support. Their relative error is defined as

∆ RE (D, D ) = sup x∈Supp(D) D(x) D (x) -1 .
Lemma 5 ([43], adapted). Assume that for two distributions D, D with the same support, we have ∆ RE (D, D ) δ for some δ > 0. Then we have

R 2λ (D D ) 1 + λ(2λ -1)δ 2 (1 -δ) 2λ+1 1 2λ-1 .
Additionally, if λ ∈ {128, 256} and δ < 2 -10 , then:

R 2λ (D D ) 1 + 2λδ 2 .
In practice, the parameter δ is quite smaller than the bound in the statement (which ensures the correctness of the second inequality). As argued in [START_REF] Prest | Sharper bounds in lattice-based cryptography using the Rényi divergence[END_REF], when trying to solve a search problem, one cannot distinguish if one queried D or D up to Q times as long as 2λδ 2 (4Q) -1 . In practice for signature algorithms, it is often the case that Q = 2 64 and λ is a target security level, e.g. 128 or 256. The value for Q can be larger if rejection sampling happens, as the target sampler will definitely be queried more time. Contrary to, say, BLISS, this does not happen for the lattice samplers considered in this work.

E Analysis of Peikert's sampler.

The following lemma can be identified as an intermediate step when calculating that the convolution of two Gaussians distribution is again a Gaussian distribution. It is very useful in analyzing Peikert's sampler and more generally, perturbative arguments for sampling discrete Gaussian distributions.

Lemma 6. [e.g. [39, Fact 2.1]] Let Σ 1 , Σ 2 be positive definite d × d matrices and x, c 1 , c 2 ∈ R d . We have ρ Σ 1 (c 1 -x)ρ Σ 2 (x -c 2 ) = ρ Σ 1 +Σ 2 (c 1 -c 2 )ρ Σ (x -c ),
where

Σ = (Σ -1 1 + Σ -1 2 ) -1 and c = Σ (Σ -1 1 c 1 + Σ -1 2 c 2 ).
In our work, the second factor on the right-hand side will lead to the Gaussian mass of a lattice coset "above smoothing", which means that the mass is essentially that of the lattice itself. In particular, we rarely need explicit expressions for either c or Σ .

E.1 Correctness of Algorithm 1, smoothing parameter choice

Proof (of Theorem 1, adapted from [START_REF] Peikert | An efficient and parallel Gaussian sampler for lattices[END_REF]). Let Y be a random variable of distribution

N Σ 0 Σ * 0 . If x ← D R 2 ,B -1 (c-y),r 2 , then by composition z := Bx ← D BR 2 ,c-y,r 2 BB * .
Denoting by Out the output of Algorithm 1, we then have:

P[Out = z ∧ Y = y] = ρ Σ 0 Σ * 0 (y) det Σ 0 • ρ r 2 BB * (z -(c -y)) ρ r 2 BB * (BR 2 -(c -y))
.

Next recall that Σ = Σ 0 Σ * 0 + r 2 BB * , and use Lemma 6 to obtain the identity

ρ Σ 0 Σ * 0 (y)ρ r 2 BB * (z -(c -y)) = ρ Σ (z -c)ρ Σ (y -c ),
where the exact expressions for c and Σ are actually not needed. Let D(z) the probability of Algorithm 1 to output z, and we obtain:

D(z) = ρ Σ (z -c) det Σ 0 R n ρ Σ (y -c ) ρ r 2 BB * (BR 2 -(c -y))
dy.

Because all matrices here are positive definite over K R we also have det(Σ * 0 ) = det(Σ 0 ) (it could have been equal to (det Σ 0 ) * ). Note that this gives det(Σ ) = det(rB) 2 det(Σ) -1 det(Σ 0 ) 2 . As we are above η ε (BR 2 ) in the denominator of the integral, we get

D(z) ∈ 1, 1 + ε 1 -ε • det(rB) (det Σ) 1/2 • ρ Σ (z -c) ρ r 2 BB * (BR 2 )
,

By definition of discrete Gaussians, it is equivalent to

D(z) ∈ 1, 1 + ε 1 -ε • α • D BR 2 ,c,Σ (z),
where we let α = det(rB)

(det Σ) 1/2 • ρ Σ (BR 2 -c) ρ r 2 BB * (BR 2 )
. Summing both the left-hand side and right-hand side over all possible z's we see that α

1 1+ε 1-ε α, or equivalently, that α ∈ [ 1-ε 1+ε , 1]. We thus obtain D(z) ∈ 1 -ε 1 + ε , 1 + ε 1 -ε • D BR 2 ,c,Σ (z). (5)
Using that ε 1/2, we see that the statistical distance between D and D BR 2 ,c,Σ is bounded by 2ε, as well as

D(z) D BR 2 ,c,Σ (z) -1 4ε.
Following the discussion in Appendix D, we see that the Rényi divergence of order 2λ is bounded by 32λε 2 . To preserve up to λ = 128, resp. 256 bits of security for Q = 2 64 queries, it is then enough to set ε 2 -39 , resp. 2 -40 . This allows us to set accordingly an upper bound on the needed smoothing parameter.

Floating point precision analysis

In practice, one can want to use floating point arithmetic to instantiate the Peikert sampler. This means that a sufficiently high precision of computation must be selected to avoid an adversary to distinguish between an "ideal" (infinite precision) sampler and the one that is implemented.

We now turn to the precision analysis of Algorithm 1. To make the analysis simpler, we in fact consider its variant in Algorithm 11, where one checks that

Σ 1 = B -1 Σ 0 is a valid choice.
Observe that in practice, c is usually an integer vector (outputted by some hash function with range in R 2 ) and since B = B f,g , qB -1 is in R 2×2 . Hence, we may assume that B -1 c is known exactly. However Σ 0 and vectors sampled from N 1,K 2 R have real entries and therefore only approximations of their values can be known. In the statement below, one may think of the technical assumptions as analyzing alternative versions of Algorithm 11 which aborts if both the continuous and discrete Gaussian sampler output a large element. Assuming both these samplers are close to perfect (which can be done in practice), Gaussian tail bounds tell us that the probability that both output large elements can be made smaller than 2 -λ , where λ is a target security level. Hence, for suitable parameters and by a hybrid argument, it makes no difference to consider such versions. 1 Precomputed: a parameter r ηε(R 2 ), and

Σ1 ∈ K 2×2 R such that Σ1Σ * 1 = B -1 ΣB - * -r 2 . 2 y ← Σ1 • (N K R ,1 ) 2 3 x ← B -1 c -y r 4 return z ← Bx
Proposition 1. Let r, δ, ε > 0, and let Σ 1 as in Algorithm 11. For u ∈ K 2 R with u 2 √ d, let y = Σ 1 u. Assume that we are given û, Σ1 and ŷ = Σ1 û satisfying

• u -û δ • u ; • s 1 (Σ 1 -Σ1 ) δ • s 1 (Σ 1 ). • max( x -t , x -t ) 2r √ πd,
where we let

t = B -1 c -y, t = B -1 c -ŷ. Let ∆ := 15d•δ•s 1 (Σ 1 ) r • 1 + ε 2(1-ε) √ πd , then we have exp(-∆) D R 2 ,B -1 c-y,r (x) D R 2 ,B -1 c-ŷ,r (x) exp(∆).
We note that requiring a relative error at most δ on each complex embedding of u, that is, |ϕ i (u j )ϕ i ( ûj )| δ • |ϕ i (u j )| for i 2d and j 2, implies the first relative error bound.

Proof. Note that by assumptions we also have s 1 ( Σ) (1+δ)s 1 (Σ 1 ). Moreover, we have y-ŷ = Σ 1 u -Σ1 (û -u) -Σ1 u, which gives us

ŷ -y s 1 ( Σ1 -Σ 1 ) u + s 1 ( Σ1 ) û -u (2 + δ)δ • s 1 (Σ 1 ) • u . (6)
Lemma 9 states that

exp ψ(x) -Ex←D R 2 ,t,r [ψ(x)] D R 2 ,t,r (x) D R 2 , t,r (x) exp ψ(x) -Ex←D R 2 , t,r [ψ(x)] .
Let us call A(x) the quantity in the left-hand exponential in the inequality above. Thanks to Lemma 9, Lemma 8 and Inequality (6), we have

|A(x)| (2 + δ)δ • s 1 (Σ 1 ) • u r 2 • x -t + r • ε 1 -ε 15 • d • δ • s 1 (Σ 1 ) r • 1 + ε 2(1 -ε) √ πd ,
where our assumptions gives that 4 √ π(2 + δ) 15, which is used for the second line. The righthand side is identical. This gives our claim.

We will now deduce the minimal precision δ needed for our finite precision samplers to be indistinguishable from the ideal one. The assumptions below reflect the practical situation for the NTRU lattices we consider. In the statement below, discrete Gaussian tail bounds tell us that only an exponentially small portion of x's are outside Ω. For example, the first sampled vector u is normal, its norm follows a chi-squared law of dimension 2d. Hence the probability that u > 2 √ d is less 16 than exp(-d/5). The constant α is defined in Section 3.4 as the quality of the basis for sampling.

Corollary 1. Let ε, δ such that 0 max(ε, δ) 2 -40 . Keep the notation of Theorem 1 with

Σ 1 = B -1 Σ 0 . Let Ω = {x ∈ Supp D R 2 ,t,r : x-t 2r √ πd}, where r = (1/π) (1/2) log(4d(1 + 1/ε)). Assume ϕ(BR 2
) is a lattice of rank 2d 512 with s 1 (B) < c √ q for some constants 1 α < 16

and q > 2 10 , and let Σ = (αr) 2 qI 2 ∈ K 2×2 R . Let IP(x) resp. FP(x) be the probability that the infinite, resp. the finite precision version of Algorithm 11 outputs Bx. Then we have

sup x∈Ω IP(x) FP(x) -1 17d • α 2 • δ.
Proof. We want an upper bound on ∆ defined in the previous proposition. Let s + (B -1 ), s -(B -1 ) ∈ K R be the singular values of B -1 . They satisfy s + (B -1 ) • s -(B -1 ) = 1/q so for each complex embedding we have |ϕ i (s

+ (B -1 ))| • |ϕ i (s -(B - 1
))| = 1/q as well. By construction, this means that there are d pairs of the singular values of ϕ(B -1 ) with a product equal to 1/q. In particular, we deduce that

s 1 (B -1 ) • s 2d (B -1 ) = s 1 (B -1 )s 1 (B) -1 1 q .
Using properties of the spectral norm of matrices, we then obtain

s 1 (Σ 1 ) s 1 (B -1 )s 1 (Σ 0 ) α • s 1 (Σ 0 ) √ q .
By assumptions, the spectrum of ϕ(BB * ) is contained in the interval ( 1 α 2 , α 2 )q, Σ -r 2 BB * = Σ 0 Σ * 0 and Σ and BB * commute, so we have s 1 (Σ 0 ) αr √ q. With the definition of ∆ and our assumptions again, we can now write

∆ 16d • α 2 • δ.
The result follows using that exp(16d • α 2 δ) 1 + 17d • α 2 δ for our choice of parameters, Proposition 1 and the definition of the set Ω.

The last corollary follows with Lemma 5.

Corollary 2. For ε 2 -40 and δ 2 -51-2 log 2 (α) (resp. δ 2 -52-2 log 2 (α) ), Algorithm 11 in finite precision preserves up to 128 (resp. 256) bits of security if queried less than 2 64 times over an NTRU lattice L (B) of rank 1024 (resp. 2048) and with s 1 (B) = α √ q.

F Analysis of the hybrid samplers

F.1 Useful results on Gaussian functions

The next lemmata are well-known.

Lemma 7 ( [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF], implicit in Lemma 4.4). Let L be a rank d lattice, and Σ 0 such that √ Σ η ε (L ). Then we have ρ c,Σ (L ) ∈ 1-ε 1+ε ; 1 • ρ Σ (L ).

Lemma 8 ([36]). For any d dimensional lattice L , any c and unit vector u in R d , and for all 0 < ε < 1 and r 2η ε (L ), we have

E x←D L ,c,r [ x -c, u ] εr 1 -ε .

Gaussian ratios

The following results and inequalities can be found in [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF], but we rework them for the sake of diffusion.

Lemma 9 ( [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF], adapted from Lemma 3.10). Let k ∈ N * and r > 0. For fixed t, t ∈ K k R , let ψ(x) := 1 2r 2 ( xt 2 -xt 2 ). For all x ∈ K k R , we have ρr(x-t) ρr(x-t) = exp(ψ(x)), and also:

exp -Ex←D R k ,t,r [ψ(x)] ρr(R k -t) ρr(R k -t) exp -Ex←D R 2 , t,r [ψ(x)] , (7)
exp ψ(x) -Ex←D R k ,t,r [ψ(x)] D R k ,t,r (x) D R k , t,r (x) exp ψ(x) -Ex←D R k , t,r [ψ(x)] . (8)
With v = t-t t-t , we also have

ψ(x) -Ex←D R k ,t,r [ψ(x)] t -t r 2 • x -t + Ex←D R k ,t,r [ x -t, v ] , ψ(x) -Ex←D R k , t,r [ψ(x)] t -t r 2 • x -t + Ex←D R k , t,r [ x -t, v ] .
Proof. The claimed equality amounts to unrolling the definitions. Since x, t, t have all their coordinates in K R , their Hermitian inner products are all real valued, so that 2r 2 ψ(x) = t 2 + t 2 + 2 x, tt . In particular, ψ is an affine function of x, and as such is convex, as well as the composition exp • ψ. The left-hand side of the first inequality comes from

ρ r (x -t) ρ r (R k -t) = exp(-ψ(x))D R k ,t,r (x),
summing over all x's and using Jensen's inequality. The right-hand side is obtained mutatis mutandis. The discrete Gaussian version of the inequality then amounts to unrolling the definition of the density function conjointly with Inequality [START_REF] Box | A note on the generation of random normal deviates[END_REF] to bound the ratio of the total masses over R k . By linearity of the expectation, we then have

r 2 ψ(x) -E x←D R k ,t,r [ψ(x)] = x -t, t -t -t -t • E x←D R k ,t,r [ x -t, v ] .
Using Cauchy-Schwarz inequality, we thus obtain the next claim, and the other one follows by observing that the above can also be unrolled for x ← D R k , t,r .

F.2 Correctness of Algorithm 3, smoothing parameter choice

For the sake of readability of the following proof, let us recall some notations of Algorithm 3.

The target standard deviation of the algorithm is some σ > 0, seen (by abuse of notation) as "the constant" σ ∈ K ++ R . Steps 4 -6 and 9 -11 are actually explicit Peikert's sampling with target covariance

Σ i = σ 2 bi , bi ∈ K ++ R . When σ |B| K • η ε (R 2 ) as in Theorem 2's assumptions, we let σ i = √ Σ i -r 2 ∈ K ++ R .
Proof (of Theorem 2, adapted from [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF]). Let D(v) the probability that we obtain v = x 1 b 1 + x 2 b 2 at Step 9, and P (x i ) be the probability that the "Peikert steps" outputs x i ∈ R at Steps 4 -6 and 9 -11 of Algorithm 3. By construction and Identity (5), we see that

D(v) = P (x1)P (x2) ∈ 1 -ε 1 + ε 2 , 1 + ε 1 -ε 2 • D R 2 ,d 1 ,Σ 1 (x1)D R 2 ,d 2 ,Σ 2 (x2).
Our choices for the Σ i 's and the Gram-Schmidt decomposition B = BU gives us that

ρ σ (v - c) = ρ Σ 1 (x 1 -d 1 )ρ Σ 2 (x 2 -d 2 )
. Note that the sampling covariances Σ 1 and Σ 2 "are above" η ε (R), so that using the definitions of discrete Gaussians and Lemma 7, we obtain

D(v) ∈ 1 -ε 1 + ε 2 , 1 + ε 1 -ε 4 • α • D BR 2 ,c,Σ (v),
where we let R) . Similarly as for Identity [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF], we see that α ∈ [( 1-ε 1+ε ) 4 , ( 1+ε 1-ε ) 2 ], which leads us to

α = ρ Σ (BR 2 -c) ρ Σ 1 (R)ρ Σ 2 (
D(v) ∈ 1 -ε 1 + ε 6 , 1 + ε 1 -ε 6 • D BR 2 ,c,Σ (v). (9)
We now differ mildly from [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF] for the sake of parameter tuning. With our choice for ε, we see that 6(log(1+ε)-log(1-ε)) 13ε, and also that (13ε) 2 ε and 13ε 1/2, so that exp(13ε)-1 14ε. This means that

|D(v) -D BR 2 ,c,Σ (v)| 14ε • D BR 2 ,c,Σ (v),
from which we get our claims.

Using the same method for the Peikert sampler, setting ε 2 -40 , resp. 2 -41 preserves up to λ = 128, resp. 256 bits of security for Q = 2 64 queries.

Correctness of Algorithm 4

For the sake of completeness, we analyze Algorithm 4. We assume that we have a perfect routine to sample discrete Gaussians in R inside Algorithm 4. Proof. Since r η ε (R), we have by definition of the discrete Gaussian distribution.

D(a) = D R,c 2 ,r (u 2 )D R,c 1 ,r (u 1 ) ∈ 1, 1 + ε 1 -ε 2 ρ r,c 2 (u 2 )ρ r,c 1 (u 1 ) ρ r (R 2 )
Calculations give ρ r,c 2 (u 2 )ρ r,c 1 (u 1 )/ρ r (R 2 ) = D UR 2 ,c,r (a). Using that (1 + ε) 2 /(1 -ε) 2 1 + 6ε, we obtain the claim on the relative error. A routine computation gives the claim on the statistical distance.

Floating point precision for Algorithm 3 Since the hybrid sampler relies on the ring version of the Peikert sampler, it is no surprise that the precision analysis is quite similar. As we are interested in the particular case of NTRU lattices, the situation is a bit simpler than in [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF]. Indeed, here the different sampling centers are known exactly because in practice the starting center c and the b i , b i 's are in K . Also, it is enough to target a scalar covariance matrix. Steps 4 to 6 and 9 to 11 are the explicit steps done in the Peikert sampler; in particular, x 2 and x 1 are essentially discrete Gaussians in R with standard deviation parameter σ. Again, we implicitly consider versions of the algorithm that abort whenever the continuous Gaussian sampler or the discrete Gaussian sampler within the Peikert sampler output too large elements.

Proposition 2. Let r, δ, ε > 0, and keep the notation of Algorithm 3. For u 1 , u 2 ∈ K R with u i √ 2d, let y i = σ i u i . Assume that we are given ûi , σi 's and ŷi = σi ûi such that for i = 1, 2:

-u i -ûi δ • u i ; -σ i -σi ∞ δ • σ i ∞ . Further, let t i = d i -y i and ti = d i -ŷi . Assume that x 1 , x 2 are such that max( x i -t i , x i - ti ) r √ 2πd for i = 1, 2, and let ∆ := 15d•δ•max( σ 1 ∞, σ 2 ∞) r • 1 + ε (1-ε) √ 2πd . Then we have exp(-∆) D(x) D(x) exp(∆), where D(x) = D R,t 2 ,r (x 2 )D R,t 1 ,r (x 1 ), D(x) = D R, t2 ,r (x 2 )D R, t1 ,r (x 1 ).
Proof. With our assumptions, we have

y i -ŷi σi -σ i ∞ u i + σ i ∞ u i -ûi δ(2 + δ) σ i ∞ • u i .
Then the proof amounts to using twice Lemma 9 with k = 1 and our assumptions, in an identical way as in the proof of Proposition 1.

Corollary 3. Let ε, δ such that 0 max(ε, δ) 2 -40 . Keep the notation of Proposition 2. For r = (1/π) (1/2) log(4d(1 + 1/ε)), let Ω i = {x i ∈ Supp D R,t i ,r : x i -ti r √ 2πd}. Assume ϕ(BR 2
) is a lattice of rank 2d 512 with |B| K α √ q for some constants 1 α < 16 and q > 2 10 , and let σ = αr √ q ∈ R. Let IH(x 1 , x 2 ) resp. FH(x 1 , x 2 ) be the probability that the infinite, resp. the finite precision version of Algorithm 3 outputs v = B(x 1 , x 2 ). Then we have sup

(x 1 ,x 2 )∈Ω 1 ×Ω 2 IH(x 1 , x 2 ) FH(x 1 , x 2 ) -1 17d • α 2 • δ.
Proof. By construction and because

q 2 = b 1 , b 1 b 2 , b 2 , we have σ i 2 ∞ σ 2 q 2 |B| 2 K -r 2 α 4 r 2 .
√ Σ η ε (R 2 ) and r √ I -Σ -1 η ε (R 2 )
, then the statistical distance between D and D R 2 ,0,r 2 Σ is bounded by 5ε. Moreover, we have

sup p∈R 2 D(p) D R 2 ,r 2 Σ (p) -1 10ε.
Proof. Inspecting the proof of [START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF], we see that the probability to obtain

p at Step 3 is in [ 1-ε 1+ε , 1+ε 1-ε ]• D (1/pL)R 2 ,0,r 2 (Σ-I) (p )
. This means that the probability D(p) to output p satisfies

D(p) ∈ 1 -ε 1 + ε , 1 + ε 1 -ε • p ∈R 2 D (1/pL)R 2 ,0,r 2 (Σ-I) (p )D R 2 ,p ,r 2 (p).
By Lemma 6 one gets that D(p) is proportional to a quantity in the interval

[ 1 -ε 1 + ε , 1 + ε 1 -ε ] • p ∈R 2 ρ r 2 Σ (p)ρ Σ (p -Σ p -p),
where an exact expression of Σ is not needed for the rest of the proof. Using that both r √ Σ and √ Σ are greater than η ε (R 2 ), and handling proportionality constants as in the previous sections, we may rewrite with Lemma 7 that

D(p) ∈ 1 -ε 1 + ε 4 , 1 + ε 1 -ε 4 • D R 2 ,r 2 Σ (p). (10)
Our claims follow.

Correctness of Algorithm 5

Proof. We first show that our assumption on s implies that Σ p -I = (s 2 -1)I -B B t is positivedefinite. Thanks to Lemma 1, note that |B f,g | K = B 2 so that we have s

1 ( B) = B 2 B 2 V 2 = |B f,g | K s 1 (V), where V = U û-u . Let v = û -u, so that the positive definite matrix V * V ∈ K 2×2 has for characteristic polynomial χ = X 2 -(2 + vv * )X + 1, with totally positive discriminant ∆ = vv * (vv * + 4). Let λ + λ -∈ K ++ R
its two eigenvalues, and we find that λ + = 1 + (vv * + √ ∆)/2. The coefficient of v (as a polynomial) are between -1/(2p) and 1/(2p), so that ϕ so that Σ p -I is indeed positive definite. Let D(z) the probability that Algorithm 5 outputs a vector z, and OFF(p) that the offline sampling outputs p. We will again make use of Lemma 6. For the sake of clarity, we now explicit the parameters that will be used. Let

(v) ∞ d/(2p). Using ϕ(v) 2 ∞ = ϕ(vv * ) ∞ , one finds the upper bounds √ ∆ ∞ ϕ(v) ∞ 4 + ϕ(v) 2 ∞ and ϕ(vv * ) ∞ d 2 /(4p 2 ). Using √ 1 + a 2 1 + a and p > d, this gives us s 1 (V) = λ + ∞ 1 + d 2p 1 + 1 + 16p 2 d 2 1 + d 2p 2 + 4p d 1 + 2d p ,
Σ 1 = r 2 B B t , Σ 2 = r 2 Σ p and Σ = Σ 2 (Σ 1 + Σ 2 ) -1 Σ 1 . One checks that Σ -1 = Σ -1 1 + Σ -1 2 = (1/r 2 )(( B B t ) -1 + (s 2 I -B B t ) -1
). Combining our analysis of Algorithm 4 with Equation (10), we have

D(z) ∈ 1 -ε 1 + ε 2 , 1 + ε 1 -ε 2 p OFF(p) • D U -û R 2 ,ĉ,r (z ) ∈ 1 -ε 1 + ε 6 , 1 + ε 1 -ε 6 p D R 2 ,Σ 2 (p) • D BR 2 ,c-p,Σ 1 (z).
As det( B B t ) -1 = q -2d , we see that ( B B t ) -1 ≺ (1/q)I. With our choice of s, we also have

Σ -1 p ≺ (1/4)I. We obtain that √ Σ η ε (R 2 )
, and r B η ε (L (B)) as well thanks to B -1 B f,g being an upper triangular matrix. Hence, using Lemma 6 and Lemma 7, we find that D(z) is proportional to a quantity in

[( 1-ε 1+ε ) 7 , ( 1+ε 1-ε ) 7 ] • ρ (rs) 2 (c -z).
Dealing with the constant, one finds for all z ∈ R 2 that

D(z) ∈ 1 -ε 1 + ε 14 , 1 + ε 1 -ε 14 • D L (B),c,rs (z).
Our claims follow from the same routine computations as usual.

With the discussion of Appendix D, we preserve λ bits of security if 2λ(30ε) 2 2 -66 . In particular, setting ε = 2 -43 preserves both 128 and 256 bits of security in Algorithm 5

Parameter analysis for Gram root decomposition in the NTRU case It is worth recalling some notation. Recall that B = B f,g U û, and fix some integer p 6d. Let s |B f,g | K (1+ 2d/p) s 1 ( B) and let B = ps . Note that |B f,g | K = α √ q, where α is deduced from Table 1. To set parameters, we allow ourselves some slack s = 1.1s for the target standard deviation. From the requirements of [12, Algorithm 6] using their eigenvalue reduction technique, the integral Gram root is correctly computed for integers b (the gadget decomposition base), p such that

b 3 B d(d + 1) + d(d + 1) 8 + 3(2d -1)b 2 p 2 (s 2 -1) (b 4 + b 2 + 1) log 2 (d) + b 3 + B 2 + 1.
This leads to the parameters in Table 5.

G On the security of MITAKA

In all of the following, we follow the so-called Geometric series assumption (GSA), asserting that a reduced basis sees its Gram-Schmidt vectors' norm decrease with geometric decay. More formally, it can be instantiated as follows for self-dual BKZ (DBKZ) reduction algorithm of Micciancio and Walter [START_REF] Micciancio | Gaussian sampling over the integers: Efficient, generic, constant-time[END_REF]: an output basis (b 1 , . . . , b n ) yielded by DBKZ algorithm with block size β on a lattice L of rank n satisfies

b i = δ n-2(i-1) β covol(L ) 1 n , where δ β = (πβ) 1 β • β 2πe 1 2(β-1)
.

G.1 Key recovery attack

The key recovery consists in finding the private secret key (i.e. f, g ∈ R 2 ) from the sole data of the public elements q and h. The most powerful attacks are up-to-our-knowledge realized through lattice reduction. It consists in constructing the algebraic lattice over R spanned by the vectors (q, 0) and (h, 1) (i.e. the public basis of the NTRU key) and retrieve the lattice vector s = (g, f ) among all possible lattice vectors of norm bounded by s = √ 2nσ (or a functionally equivalent vector, for instance (µg, µf ) for any unit µ of the number field).

We make use of the so-called projection trick to avoid enumerating over all the sphere of radius √ 2nσ (which contains around 2nσ 2 q n vectors under the Gaussian heuristic). More precisely we proceed as follows. Set β to be the block size parameter of the DBKZ algorithm and start by reducing the public basis with this latter algorithm. Call [b 1 , . . . , b 2n ] the resulting vectors. Then if we can recover the projection of the secret key onto P, the orthogonal space to Span(b 1 , . . . , b 2n-β-1 ), then we can retrieve in polynomial time the full key by Babai nearest plane algorithm to lift it to a lattice vector of the desired norm. Hence it suffices to be able find the projection of the secret key among the shortest vector of the lattice generated by the last β vectors projected onto P. Classically, sieving on this projected lattice will recover all vectors of norm smaller than 4 3 , where is the norm of the 2n -β-th Gram-Schmidt vector b 2m-β of the reduced basis. Under the GSA assumption we have:

= √ qδ -2n+2β+2 β ≈ β 2πe 1-n β .
Moreover, considering that s behaves as a random vector of norm √ 2nσ, and using the GSA to bound the norm of the Gram-Schmidt vectors [ b 1 , . . . , b 2n-β ], that the norm of its projection over P is roughly

β 2n s = β 1 2 σ.
Hence, we will retrieve the projection among the sieved vectors if β 1 2 σ 4 3 , that is if the following condition is fulfilled:

σ 2 4q 3β δ 4(β+1-n) β (11)
G.2 Signature forgery by ApproxCVP reduction.

As a Hash-and-Sign paradigm signature, forging a signature stems to feeding a lattice point v at a bounded distance from a random space point x. This ApproxCVP problem can be solved using the so-called Nearest-Cospace framework developed in [START_REF] Espitau | The nearest-colattice algorithm: Time-approximation tradeoff for approx-cvp[END_REF]. Under the Geometric Series assumption, Theorem 3.3 of [START_REF] Espitau | The nearest-colattice algorithm: Time-approximation tradeoff for approx-cvp[END_REF] states that under the condition:

x -v δ 2n β q 1 2
, the decoding can be done in time Poly(n) calls to a CVP oracle in dimension β.

As mentioned in [START_REF] Chuengsatiansup | ModFalcon: Compact signatures based on module-NTRU lattices[END_REF] a standard optimization of this attack consists only considering the lattice spanned by a subset of the vectors of the public basis and perform the decoding within this sublattice. The only interesting subset seems to consists in forgetting the k n first vectors. The dimension is of course reduced by k, at the cost of working with a lattice with covolume q k 2(2n-k) bigger. Henceforth the global condition of decoding becomes the (slightly more general) inequality xv min k n δ 2n-k

β q n 2n-k
As such, we need to enforce the condtion:

γ min k n δ 2n-k β q n 2n-k (12)

G.3 On the other attacks on MITAKA

In this section, we list the other possible type of attacks on the signature, which are nonetheless irrelevant for the set of parameters we are using.

G.3.1 Algebraic attacks

As remarked in the design of NTRU-based schemes (such as for instance FALCON or MODFALCON signatures), there exists a rich algebraic structure in the modules over the convolution ring R used in MITAKA. However, there is no known way to improve all the algorithms previously mentioned with respect to their general lattice equivalent by more than polynomial factors (see for instance the speedup on lattice reduction of [START_REF] Kirchner | Fast reduction of algebraic lattices over cyclotomic fields[END_REF]).

G.3.2 Overstretched NTRU-type

As observed in [START_REF] Kirchner | Revisiting lattice attacks on overstretched NTRU parameters[END_REF], when the modulus q is significantly larger than the magnitudes of the NTRU secret key coefficients, the attack on the key based on lattice reduction recovers the secret key better than the results presented above. This so-called "overstretched NTRU" parameters occurs when q > n 2.83 for binary secrets, implying that, as it is the case for Falcon and other NTRU based NIST candidates, that even very significant improvements of this attack would still be irrelevant for the security of the scheme.

G.3.3 Hybrid attacks

Odlyzko's meet on the middle attack, or more recently the hybrid attack of Howgrave-Graham [START_REF] Howgrave-Graham | A hybrid lattice-reduction and meet-in-the-middle attack against NTRU[END_REF] which combines a meet-in-the-middle algorithm with a key recovery by lattice reduction were used effectively against NTRU, mainly due to its design using sparse polynomials. As it is not the case (secrets are dense elements in the ring R), their impact is not sufficient to be a problem on the parameter selection of MITAKA.

H More explicit steps to compute samplers

See Algorithm 12 and 13 for more explicit procedures to compute the RingPeikert and Hybrid samplers, respectively. Note that sampling from a continuous Gaussian distribution can be preprocessed since these operations are independent of the input center c. We also specify where the FFT or NTT-based polynomial multiplications happen. We present the masked online and offline parts of Algorithm 10 in Algorithms 14 and 15. The masked polynomial multiplication routine SecNTTMult is also described in Algorithm 16.

I.2 Proof of Theorem 4

Proof. Only a proof for each line of Algorithm 10 is necessary. Line 2 is a linear operation thus it is t-NI. Lines 3 and 5 are proved t-NI in 7.2. Line 6 does not manipulate any sensitive value. So it remains to prove that the algorithms MaskedOnlineSampling (Alg. 14) and MaskedOfflineSampling (Alg. 15) are t-NI. First, Alg. 15 is directly t-NI because it is a linear succession of t-NI gadgets. Secondly, let us prove the t-NI security of Alg. 14. We consider that the attacker made δ ≤ t observations during the execution of MaskedOnlineSampling. In the following, we prove that all these δ observations can be perfectly simulated with at most δ shares of v , c 1 and c 2 . We consider the following distribution of the attacker's δ observations: δ 1 made during the first call to GaussShareByShare, δ 2 made during the call to SecNTTMult, δ 3 made during the subtraction, δ 4 made during the second call to GaussShareByShare, and δ 5 made during the final addition. We have

5 i=1 δ i ≤ δ ≤ t.
We build the proof classically from right to left. Since the addition is linear with respect to the arithmetic masking type, the final step is t-NI. It is also an affine gadget. In other words, each observation can be simulated with exactly either one share of x or one share of u 1 . Thus, all the observations from its call can be simulated with at most δ 5 shares among all the shares of x and u 1 . More precisely, all the observations from its call can be simulated with δ 1 5 shares of x and δ 2 5 shares of u 1 such that δ 1 5 + δ 2 5 = δ 5 . By Table 4 properties, GaussShareByShare is t-NI. Hence, all the observations from its call can be simulated with δ 1 5 + δ 4 shares of c 1 and δ 2 5 shared of x . Next, the subtraction is also a linear operation (we can ignore its affine property here). Thus, all the observations from its call can be simulated with δ 1 5 + δ 4 + δ 3 shares of c 1 and δ 1 5 + δ 2 5 + δ 4 + δ 3 = δ 5 + δ 4 + δ 3 shares of x . Still by Table 4 properties, SecNTTMult is t-NI. Hence, the observations from its call can be simulated with δ 5 + δ 4 + δ 3 + δ 2 shares of u 2 and v (and still δ 1 5 + δ 4 + δ 3 shares of c 1 ). Finally, by the t-NI property of GaussShareByShare, the observations from the whole algorithm can be simulated with δ 5 + δ 4 + δ 3 + δ 2 + δ 1 ≤ t shares of c 2 ; δ 5 + δ 4 + δ 3 + δ 2 ≤ t shares of v ; δ 1 5 + δ 4 + δ 3 ≤ δ 5 + δ 4 + δ 3 ≤ t shares of c 1 ; which concludes the proof.

I.3 Masking Peikert's sampler

See Alg. 17 for our masked version of the RingPeikert sampler (see Alg. 1 and 12). Although it relies on MaskedCDT, one could instantiate the offline sampling in a different manner, depending q k y2 ← SecNTTMult( q k 2 σ2 , q k 1 u2 ) Online / * first nearest plane * / 9 c2 ← c, v2 ← 0 10 q k d2 ← SecNTTMult( q k β2,1 , c2,1) + SecNTTMult( q k β2,2 , c2,2) 11 q k z2 ← q k d2 -q k y2 12 for j ∈ [0, d -1] do 13 x2,j q +k ← GaussShareByShare( q k z 2,j q k ) 14 end for / * second nearest plane * / 15 v1 q +k ← SecNTTMult( x2 q +k , b2 q +k ) 16 c1 q +k ← c2 -v1 q +k 17 q k d1 q +k ← SecNTTMult( q k β1,1 q +k , c1,1 q +k ) + SecNTTMult( q k β1,2 q +k , c1,2 q +k ) 18 q k z1 q +k ← q k d1 q +k -q k y1 q +k 19 for j ∈ [0, d -1] do 20 x1,j q ← GaussShareByShare( q k z 1,j q +k q k ) 21 end for 22 x1 q := x1 q , v1 q := v1 q +k / * compute every share mod q * / 23 v 1 q ← Refresh( v1 q ) 24 v0 q ← v 1 q + SecNTTMult( x1 q , b1 q ) 25 v0 ← Unmask( v0 q ) 26 return v0

  additive subgroup of a Euclidean space. When the space is R m , and if it is generated by (the columns of) B ∈ R m×d , we also write L (B) = {Bx | x ∈ Z d }. If B has full column rank, then we call B a basis and d the rank of L . The volume of L is Vol(L ) = det(B t B)

1 and ζ d to be a 2d-th primitive root of 1 .

 1 Then for a fixed d, K := Q(ζ d ) is the d-th power-of-two cyclotomic field, and its ring of algebraic integers is R := Z[ζ d ]. The field automorphism ζ d → ζ -1 d = ζ d corresponds to the complex conjugation, and we write the image f * of f under this automorphism. We have K Q[x]/(x d + 1) and R Z[x]/(x d + 1), and both are contained in K

Theorem 2 ( 2 D

 22 [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF], Theorem 5.10, adapted). Let D be the output distribution of Algorithm 3.If ε 2 -5 and √ Σ |B| K • η ε (R 2 ),then the statistical distance between D and D L ,c,Σ is bounded by 7ε. Moreover, we have sup x∈BR (x) D L ,c,Σ (x) -1 14ε.

Theorem 3 .

 3 Keep the notation of Algorithm 5, assuming also that IntGram correctly computes A. For ε ∈ (0, 1), let s > |B f,g | K (1 + 2d/p) + 1 be an integer and r η ε (Z 2d ). Then the distribution D of the output of Algorithm 5 is at statistical distance at most 15ε from D L (B),c,sr . Moreover, we have sup z∈L (B) D(z) D L (B),c,sr (z) -1 30ε.

Algorithm 7 :

 7 Signature schemeInput: A message m, a secret key sk, a bound γ. Result: A signature sig of m.

  k 5 for k = 0, . . . , d/2-1, where τ 5 (ζ d ) = ζ 5 d .

Algorithm 8 :

 8 MITAKA optimized key generation

Fig. 1 .

 1 Fig.1. Quality α reached by the optimized sampler of Algorithm 8 for various choices of m (50 trials each, σ0 = 1.17 q/2d, G coset representatives of Gal(K /Q)/ τ * ). Reachable α in dimension 512 (left) and 1024 (right).

Fig. 2 .

 2 Fig. 2. Security (classical and quantum) against forgery as a function of the quality 1 α 3 of the lattice sampler (left: dimension 512 and right: dimension 1024).

Algorithm 10 :

 10 MaskedMITAKA Z Sampler Input: A masked secret key in the following form: ( B * , B * -1

  Let Q(ζ m ) be the cyclotomic field of conductor m = p a 2 b for an odd prime number p and nonnegative integers a, b. Set B = (1, ζ m , . . . , ζ ϕ(m)-1 m

Algorithm 11 :

 11 RingPeikert sampler, variantInput: A matrix B ∈ K 2×2 such that L = ϕ(BR 2) and a target center c ∈ K 2 R . Result: z ∈ L with distribution negligibly far from D L ,c,Σ .

Theorem 7 . 2 D

 72 Let D be the output distribution of Algorithm 4. If ε 2 -5 and r η ε (R), then the statistical distance between D and D L (U),c,r is bounded by 3ε. Moreover, we have sup x∈UR (z) D L (U),c,r (z) -1 6ε.

Algorithm 12 : 2 y1 5 y

 1225 RingPeikert with explicit FFT/NTTInput: A target center c ∈ K 2 R ; a matrix B ∈ K 2×2 such that L = ϕ(BR 2 ); a parameter r ηε(R 2 ); canonical embeddings B = FFT(B), B -1 = FFT(B -1 ) and Σ0 = FFT(Σ0), where Σ0 ∈ K 2×2 R is precomputed such that Σ0Σ * 0 = Σ -r 2 BB * ; NTT representation B = NTT(B). Result: z ∈ L with distribution negligibly far from D L ,c,Σ . Offline 1 for i ∈ [0, d -1] do := (y1,0, . . . , y 1,d-1 , y2,0, . . . , y 2,d-1 ) 6 ŷ ← FFT(y) 7 x ← Σ0 ŷ Online 8 ĉ ← FFT(c) 9 z ← iFFT( B -1 (ĉ -x)) r 10 z ← NTT(z) 11 return iNTT(B z mod q)

Algorithm 13 : 3 ui 5 ui 7 ŷi ← σi ûi 8

 133578 Hybrid Gaussian sampler with explicit FFT/NTTInput: A target center c ∈ K 2 R ; a matrix B = [b1, b2] such that L = ϕ(BR 2) and its GSO [ b1, b2] over K ; a parameter r ηε(R); a parameter σ > 0 (corresponding to(σ, . . . , σ) ∈ K R ); σi := σ 2 b i , b i -r 2 ∈ K ++ R ; precomputed canonical embeddings σi = FFT(σi), bi = FFT(bi), and βi = FFT( b * i b i , b i K ) for i = 1, 2.Result: z with distribution negligibly far from D L ,c,σ 2 I 2d .Offline 1 for i = 1, 2 do 2 for j ∈ [0, d -1] do := (ui,0, . . . , u i,d-1 ) 6 ûi ← FFT(ui) / *Can be omitted by scaling the N . * / end for Online / * first nearest plane * / 9 ĉ2 ← FFT(c), v2 ← 0 10 d2 ← β2,1 ĉ2,1 + β2,2 ĉ2,2 11 x2 ← iFFT( d2 -ŷ2) r / * second nearest plane * / 12 x2 ← FFT(x2) 13 v1 ← x2 b2 14 ĉ1 ← ĉ2 -v1 15 d1 ← β1,1 ĉ1,1 + β1,2 ĉ1,2 16 x1 ← iFFT( d1 -ŷ1) r 17 x1 ← FFT(x1) 18 v0 ← v1 + x1 b1 19 return iFFT(v0) mod q

Table 1 .

 1 1/4 √ log d) [42, §6.5.2]; for the hybrid sampler, following Appendix C, we show α = O(d 1/8 log 1/4 d) (and not Comparison of the best achievable trapdoor quality α for the various Gaussian samplers over NTRU lattices.

	Sampler

O( √ log d) contrary to what was claimed in [42, §6.5.2] based on flawed heuristics);

Table 2 .

 2 Concrete values for sampler quality and associated bit security level. Key generation with the same median amount of randomness as MITAKA Algorithm 8 with m = 16, but without the optimizations of Section 4. b Taking into account the heavy memory cost of sieving. This is the same level as Dilithium-II; see[32, §5.3].

			d = 512			d = 1024
		Quality α	Classical	Quantum	NIST Level	Quality α	Classical	Quantum	NIST Level
	FALCON	1.17	124	112	I	1.17	285	258	V
	Naive Hybrid a	3.03	90	82	below I	3.58	207	188	IV
	MITAKA	2.04	102	92	I b	2.33	233	211	V

a

Table 3 .

 3 Intermediate parameters and security levels for MITAKA.

		d = 512	d = 648	d = 768	d = 864	d = 972	d = 1024
	Conductor	2 10	2 3 • 3 5	2 8 • 3 2	2 5 • 3 4	2 2 • 3 6	2 11
	Security (C/Q)	102/92	136/123	167/151	192/174	220/199	233/211
	NIST level	I a	I b	II	III	IV	V
	Modulus q	12289	3889	18433	10369	17497	12289
	Quality α	2.04	2.13	2.20	2.25	2.30	2.33
	Sig. size (bytes)	713	827	1080	1176	1359	1405

a Slightly above Dilithium-II. b Above FALCON-512; arguably reaches level II.

  1 intermediate variables and any subset of O ⊆ [1, t] of output indices with t 1 +|O| t, there exists a subset of indices I ⊆ [1, t] such that the output distribution of the t 1 intermediate variables and the output variables (y i ) i∈O can be simulated from (x i ) i∈I . Then 1. if |I| t 1 + |O| we say G is t-non-interfering (t-NI), and 2. if |I| t 1 we say G is t-strong-non-interfering (t-SNI).

Table 4 .

 4 Masking properties of known and new gadgets

	Gadget name	Security property	Reference
	SecMult	t-SNI	[26,45,2]
	Refresh	t-SNI	[9,2]
	Unmask	t-NIo	[3]
	MaskedCDT	t-NI	[4,20]
	SecNTTMult	t-SNI	This work, Lemma 4
	GaussShareByShare	t-NIo	This work, Lemma 3

  Security of the MITAKA scheme for different choices of cyclotomic fields with 3-powersmooth conductors. Median quality α reached in the same cyclotomic fields by the optimized sampler of Algorithm 8 for various choices of m (50 trials each, σ0 = 1.17 q/2d, G coset representatives of Gal(K /Q)/ τ * ).

		270													512	648
		250													768	864
		230													972	1024
		210
		190
		170
	2.4	150							2.45
	2.35	130					Worst of 50 Upper quartile		2.4									Worst of 50 Upper quartile
	2.3	110					Median Lower quartile		2.35									Median Lower quartile
	2.25	90					Best of 50		2.3									Best of 50
	2.15 2.2	70		1.2	1.4	1.6	1.8		2 2.25 2.2		2.2		2.4		2.6	2.8	3
	2.1								2.15
	2.05								2.1
	Fig. 3. 4 2 2.05 2.1 2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 8 2 4 6 8 2.05 2.1 2.15 2.2 2.25 2.3 2.55 Fig. 4. 6 2.35 2.5 2.45 2.4	10 10	6 12 (a) Degree 648 8 14 16 12 14 16 (c) Degree 864	10 18 18	12 22 22 Worst of 50 20 20 Upper quartile Median Lower quartile Best of 50	24 24	14 2.05 2.15 2.2 2.25 2.3 2.35 2.55 2.5 2.45 2.4	4 4	16 6 6	8 8	18	10 10	20 512 768 972 12 (b) Degree 768 22 648 864 1024 14 16 12 14 16	18 18	24	20 20 Worst of 50 22 22 Upper quartile Median Lower quartile Best of 50	24 24

  With the definition of ∆ and our assumptions again, we can now write∆ 16d • α 2 • δ,and we conclude as in Corollary 1. Algorithm 11 in finite precision preserves up to 128 (resp. 256) bits of security if queried less than 2 64 times over an NTRU lattice L (B) of rank 1024 (resp. 2048) and with |B| K = α √ q.Lemma 10 ([START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF], adapted). Assume that A ∈ R 2×m is such that AA t = p 2 (Σ -I), and let ε 2 -5 Let D be the probability distribution of outputs from Algorithm 6. If r

	F.3 Analysis of the integer friendly sampler
	Correctness of Algorithm 6
	Corollary 4. For ε	2 -40 (resp. ε	2 -41 ) and δ	2 -50-2 log 2 (α) (resp. δ	2 -52-2 log 2 (α) ),

Table 5 .

 5 Parameters for Algorithm 5, for the power-of-two cyclotomic case.

	d	ε	r	α	√ q	s	s	p	b	L
	512	2 -43	1.39	227.3	233	256	2 21	8192	2 35
	1024	2 -43	1.39	260.5	265	292	2 23	16384	2 35

Trivia: Mitaka is a neighborhood in Tokyo, Japan whose name means "the three falcons". It sounded fitting considering the maskable, parallelizable nature of our scheme and its strong points compared to FALCON.

In principle, even more general number fields are possible as well, provided a good basis is known for their canonical embedding. The corresponding security analysis is cumbersome, however.

The same idea can be adapted to the offline phase by masking the zero center. This is a bit less compelling, however, as it requires more shares, and replaces centered Gaussian sampling by variable center sampling.

This is the so-called coefficient embedding.

This is the case at least for FALCON and for the hybrid sampler, as for both of them, one can compute the quality of the trapdoor given only (f, g). This is especially fast for the hybrid sampler. For the Peikert sampler, however, doing so without also obtaining (F, G) seems difficult, and is left as an open problem.

We can do away with this heuristic assumption in the analysis by generalizing Theorem 6 to sub-Gamma random variables.

Acknowledgements

This work was partly supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701) for Pierre-Alain Fouque and Yang Yu.

with • the coefficient-wise product between two vectors in Z Q mask . Since the NTT is linear, it can be applied on each share independently and we only have to mask the coefficient-wise multiplication between elements of Z Q mask using the technique of [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF]. While a naive multiplication algorithm would require d 2 ISW multiplications, we only need d of them. Since we want to multiply the polynomials in Z and not in Z Q mask , we need to work with a modulus large enough to avoid any reduction in the result. Recall that it is also possible to use several Q mask with CRT techniques to reduce the size.

Let us define SecNTTMult, the masked product of two polynomials a , b arithmetically masked in

This product is detailed in algorithm 16.

Lemma 4. SecNTTMult (Alg. 16) is t-SNI secure.

Note that here the shares are entire polynomials containing d coefficients. So, t probes actually provide t × d coefficients to the attacker.

Proof. Let δ ≤ t be the number of observations made by the attacker. Assume the following distribution of the attacker δ observations of intermediate shared polynomials: δ 1 observations on the first NTT computation on â, δ 2 observations on the first NTT computation on b, δ 3 observations on the SecMult part (which provides the knowledge of the d × δ 3 coefficients of the probed polynomials), δ 4 observations on the last NTT -1 computation, and δ 5 observations of the returned values. Finally, we have 5 i=1 δ i ≤ δ. The algorithm NTT -1 is linear, thus it is t-NI and all the observations on steps 6 and 7 can be perfectly simulated with at most δ 4 + δ 5 shares of ĉ. The algorithm SecMult is applied coefficient-wise, thus each i-th execution has δ 3 observations of intermediate values (here coefficients) and δ 4 +δ 5 observations on the outputs (here coefficients too). By applying d times the t-SNI property for each SecMult operation, we can conclude that every Result: An arithmetically masked u .

6 return u Algorithm 15: MaskedOfflineSampling Input: An arithmetically masked mod Q mask matrix A .

Result: An arithmetically masked p for p ∈ R 2 .

on the required precision of samples. One plausible option would be to employ a secure gadget computing the Box-Muller transform [START_REF] Box | A note on the generation of random normal deviates[END_REF]. Since masking the Box-Muller transform amounts to evaluating a few non-linear functions (i.e. cos, sin, log, √ •) on random Boolean shares representing values in R ∩ [0, 1], one could easily achieve such a gadget using the existing polynomial approximation techniques [START_REF] Barthe | GALACTICS: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited[END_REF]. The same remark applies to the MaskedHybrid sampler.

I.3.1 Security Proof

Theorem 8. Assuming t-NI security of GaussShareByShare, SecNTTMult and MaskedCDT, and t-NIo security of Unmask, the MaskedRingPeikert sampler (Alg. 17) is t-NIo secure with public output z.

Proof. Let us assume that an attacker has access to δ t observations on the whole sampler. Our goal is to prove that all these δ observations can be perfectly simulated with at most δ shares of each secret among B q , q k B -1 , and q k 2 Σ 1 . We consider an attacker who peeks at internal computations as follows: δ 1 observations during line 15; δ 2 observations during line 14; δ 3 observations during line 9-12; δ 4 observations during line 8; δ 5 observations during line 7; δ 6 observations during line 6; δ 7 observations during line 1-4. Suppose i δ i δ.

-Since Unmask is t-NIo secure with public output z, all the observations at line 15 can be simulated with at most δ 1 shares of z q and z. -Since SecNTTMult is t-NI secure, all the observations at line 14 can be simulated with at most δ 1 + δ 2 shares of z q and B q . -Since line 9-12 consists of independent local operations on each share of q k v and GaussShareByShare is t-NI secure, all the observations during line 9-12 can be simulated with at most δ 1 + δ 2 + δ 3 shares of q k v . be simulated with at most δ 1 + δ 2 + δ 3 + δ 4 shares of q k B -1 c and q k x . -Since SecNTTMult is t-NI secure, all the observations at line 7 can be simulated with at most

-Since SecNTTMult is t-NI secure, all the observations at line 6 can be simulated with at most δ 1 + δ 2 + δ 3 + δ 4 + δ 6 shares of q k 2 Σ 1 and q k 1 y . -Since MaskedCDT is t-NI secure, all the observations during line 1-4 can be simulated with at most δ 1 + δ 2 + δ 3 + δ 4 + δ 6 + δ 7 shares of randomness as input to MaskedCDT.

Clearly, the number of total observations for each sensitive input does not exceed δ.

I.4 Masking Ducas & Prest's hybrid sampler

See Alg. 18 for our masked variant of the hybrid sampler (see Alg. 3 and 13), which can be seen as a straightforward extension of the masked RingPeikert sampler. Notice that the only variable used more than once is v 1 , so by applying the SNI-secure Refresh gadget [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF] to its shares we can prove NIo-security of the algorithm.

I.4.1 Proof of Theorem 5

Following Table 4, the proof below relies on t-NI security of GaussShareByShare, SecNTTMult and MaskedCDT, t-SNI security of Refresh, and t-NIo security of Unmask.

Proof. Below we omit the subscripts of masked variables denoting modulus for the sake of readability. Let us assume that an attacker has access to δ t observations on the whole sampler. Our goal is to prove that all these δ observations can be perfectly simulated with at most δ shares of each secret among b 1 , b 2 , q k 2 σ 1 , q k 2 σ 2 , q k β 1 and q k β 2 . We consider an attacker who peeks at internal computations as follows: δ 1 at line -Since Unmask is t-NIo secure with public output v 0 , the observations during line 25 can be simulated with at most δ 1 shares of v 0 and v 0 . -Due to the linear operations, the observations during addition at line 24 can be simulated with at most δ 1 + δ 2 shares of v 1 and x 1 b 1 .

Algorithm 17: MaskedRingPeikert sampler Input: An arithmetic masking modulus Q mask = q k+ such that k = k1 + k2 and > 0; a masked secret bases B q , q k B -1 such that B ∈ K 2×2 , L = ϕ(BR 2 ); a target center c ∈ R; a precomputed parameter r ηε(R 2 ) and masked matrix q k 2 Σ1 such that

) 12 end for 13 z q := z q / * compute every share mod q * / 14 z q ← SecNTTMult( B q , z q ) 15 z ← Unmask( z q ) 16 return z a As the input center is not sensitive this is in practice a simpler variant of SecNTTMult where the second input is unmasked.

-Since SecNTTMult is t-NI secure, the observations during SecNTTMult at line 24 can be simulated with at most δ 1 + δ 2 + δ 3 shares of x 1 and b 1 . -Since Refresh is t-SNI secure, the observations during line 23 can be simulated with at most δ 4 shares of v 1 . -Since line 19-21 consists of independent local operations on each share of q k z 1 and GaussShareByShare is t-NI secure, all the observations during line 19-21 can be simulated with at most δ 1 + δ 2 + δ 3 + δ 5 shares of q k z 1 . -Due to the linear operations, the observations during addition at line 18 can be simulated with at most δ 1 + δ 2 + δ 3 + δ 5 + δ 6 shares of q k d 1 and q k y 1 . -Due to the combination of linear operations and t-NI secure SecNTTMult, the observations during line 17 can be simulated with at most δ 1 + δ 2 + δ 3 + δ 5 + δ 6 + δ 7 + δ 8 shares of q k β 1,1 and c 1,1 , and δ 1 + δ 2 + δ 3 + δ 5 + δ 6 + δ 7 + δ 9 shares of q k β 1,2 and c 1,2 . -Since SecNTTMult is t-NI secure, the observations at line 15 can be simulated with at most i∈ [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Ding | Rainbow. Tech. rep[END_REF] δ i shares of x 2 and b 2 .

-Since line 12-14 consists of independent local operations on each share of q k z 2 and GaussShareByShare is t-NI secure, all the observations during line 12-14 can be simulated with at most i∈ [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF] δ i shares of q k z 2 . -Due to the linear operations, the observations during addition at line 11 can be simulated with at most i∈ [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF] δ i shares of q k d 2 and q k y 2 .

-Due to the combination of linear operations and t-NI secure SecNTTMult, the observations during line 10 can be simulated with at most i∈ [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Ducas | Efficient identity-based encryption over NTRU lattices[END_REF] δ i shares of q k β 2,1 , and i∈ [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Ducas | CRYSTALS-Dilithium: A lattice-based digital signature scheme[END_REF] δ i + δ 15 shares of q k β 2,2 . -Since SecNTTMult is t-NI secure, the observations during SecNTTMult at line 7 (resp. line 8) can be simulated with at most δ 1 + δ 2 + δ 3 + δ 5 + δ 6 + δ 16 shares of q k 2 σ 1 and q k 1 u 1 (resp. i∈ [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF] δ i + δ 17 shares of q k 2 σ 2 and q k 1 u 2 ). -Since MaskedCDT is t-NI secure, all the observations during line 1-4 can be simulated with at most i∈ [START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Ducas | Integral matrix gram root and lattice gaussian sampling without floats[END_REF] δ i + δ 16 + δ 17 + δ 18 shares of randomness as input to MaskedCDT.

Clearly, the number of total observations for each sensitive input does not exceed δ.

Algorithm 18: MaskedHybrid Gaussian sampler

Input: An arithmetic masking modulus Q mask = q 2k+ such that k = k1 + k2 and > 0; a target center c ∈ R 2 ; a masked secret matrix [ b1 q , b2 q +k ] such that L = ϕ(BR 2 ); a masked covariance q k 2 σ1 q +k and q k 2 σ2 such that σi :=

; a masked precomputed elements q k β 1 q +k and q k β 2 such that

, where [ b1, b2] is GSO of B over K . Result: z with distribution negligibly far from D L ,c,σ 2 I 2d . Offline 1 for j ∈ [0, d -1] do 2 q k 1 u1,j q +k ← MaskedCDT(t, q ) 3 q k 1 u2,j ← MaskedCDT(t, Q mask ) 4 end for 5 q k 1 u1 q +k := ( q k 1 u1,j q +k ) j∈[0,d-1] 6 q k 1 u2 := ( q k 1 u2,j ) j∈[0,d-1] 7 q k y1 q +k ← SecNTTMult( q k 2 σ1 q +k , q k 1 u1 q +k )