<figure><img src="image_1.png" /></figure>

HAL
open science

# On the Hardness of Module Learning with Errors with Short Distributions

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen

► To cite this version:

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen. On the Hardness of Module Learning with Errors with Short Distributions. Journal of Cryptology, 2023, 36 (1), pp.1-70. 10.1007/s00145-022-09441-3. hal-04028217

HAL Id: hal-04028217

https://hal.science/hal-04028217

Submitted on 14 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Hardness of Module Learning With Errors with Short Distributions

Katharina Boudgoust¹, Corentin Jeudy²,³, Adeline Roux-Langlois⁴, and
Weiqiang Wen⁵

katharina.boudgoust@cs.au.dk, corentin.jeudy@irisa.fr,
adeline.roux-langlois@cnrs.fr, weiqiang.wen@telecom-paris.fr

¹ Dept. Computer Science, Aarhus University, Aarhus, Denmark

² Univ Rennes, CNRS, IRISA, Rennes, France

³ Orange Labs, Applied Crypto Group, Cesson-Sévigné, France

⁴ Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France

⁵ LTCI, Telecom Paris, Institut Polytechnique de Paris, Paris, France

**Abstract.** The *Module Learning With Errors* (M-LWE) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a *secret* distribution as well as an *error* distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE, i.e., uniform secret modulo *q* and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress towards narrowing this gap. More precisely, we prove that M-LWE with uniform *η*-bounded secret for any $1 \le \eta \ll q$ and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE, provided that the module rank *d* is at least logarithmic in the ring degree *n*. We also prove that the search version of M-LWE with large uniform secret and uniform *η*-bounded error is at least as hard as the standard M-LWE problem, if the number of samples *m* is close to the module rank *d* and with further restrictions on *η*. The latter result can be extended to provide the hardness of search M-LWE with uniform *η*-bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.

**Keywords:** Lattice-Based Cryptography · Module Learning With Errors · Short Distributions · Bounded Secret · Bounded Error

This paper contains novel results and generalizations of existing ones already published in [12,13].

© IACR 2022. This article is the final version submitted by the authors to the IACR and to Springer-Verlag on Oct. 27th, 2022. The version published by Springer-Verlag is available at https://doi.org/10.1007/s00145-022-09441-3.
# 1 Introduction

The *Learning With Errors* (LWE) problem, introduced by Regev [46], is one of the main computational assumptions for lattice-based cryptographic schemes. Given two positive integers $d$ and $q$, and a secret vector $\mathbf{s} \in \mathbb{Z}_q^d$, an LWE$_{d,q,\psi}$ sample is defined as $(\mathbf{a}, b = q^{-1}\langle\mathbf{a},\mathbf{s}\rangle+e \bmod \mathbb{Z})$, where $\mathbf{a}$ is sampled from the uniform distribution over $\mathbb{Z}_q^d$, and $e$ an error term sampled from a distribution $\psi$ over $\mathbb{R}$. The *search* version of LWE asks to recover the secret $\mathbf{s}$ given arbitrarily many samples of the LWE distribution. Its *decision* counterpart asks to distinguish between LWE samples and the same number of samples drawn from the uniform distribution over $\mathbb{Z}_q^d \times \mathbb{T}$, where the torus is defined by $\mathbb{T} = \mathbb{R}/\mathbb{Z}$. When the number of samples $m$ is fixed, we use a matrix representation of the LWE$_{d,m,q,\psi}$ samples as $(\mathbf{A}, q^{-1}\mathbf{A}\mathbf{s} + \mathbf{e} \bmod \mathbb{Z})$, with $\mathbf{A}$ uniform over $\mathbb{Z}_q^{m \times d}$, and $\mathbf{e}$ sampled from $\psi^m$. From a theoretical standpoint, LWE is interesting for its ties with well-known lattice problems. Lattices are discrete additive subgroups of $\mathbb{R}^d$ and arise in many different areas of mathematics, such as number theory, geometry and group theory. There are several problems on lattices that are proven to be computationally hard to solve, such as the problem of finding a set of *shortest independent vectors* (SIVP). A standard relaxation of the latter, which is more suitable for building cryptography upon, consists in solving it only up to an approximation factor $\gamma$ and is denoted by $SIVP_\gamma$. The caveat of this relaxation is that the hardness is only conjectured. The seminal work of Regev [46,47] proves a worst-case to average-case quantum reduction from $SIVP_\gamma$ to LWE. It means that if there exists an efficient solver for LWE, then it can be used to construct a quantum solver for $SIVP_\gamma$ in the worst case, i.e., in any Euclidean lattice. The subsequent work of Peikert [42], then generalized to any polynomial modulus $q$ by Brakerski et al. [17], dequantized the reduction to obtain fully classical worst-case to average-case reductions to LWE.

**Structured Variants.** Cryptographic schemes whose security proofs rely on the hardness of LWE inherently suffer from large public keys and quite intensive computations, both quadratic in the security parameter. Structured variants of LWE have been proposed in order to gain in efficiency [51,30]. In this paper, we focus on the *Module Learning With Errors* (M-LWE) problem, first defined by Brakerski et al. [16] and then thoroughly studied by Langlois and Stehlé [24]. The formulation is similar to that of LWE where the set of integers $\mathbb{Z}$ is replaced by the ring of algebraic integers $\mathcal{R}$ of a number field $K$. This introduces a new parameter, which is the degree $n$ of the number field. The integer $d$ now denotes the module rank, and $q$ still denotes the modulus. Further, let $\psi$ be a distribution on the field tensor product $K_\mathbb{R} = K \otimes_{\mathbb{Q}} \mathbb{R}$, and let $\mathbf{s} \in \mathbb{Z}_q^d$ be a secret vector, where $R_q = R/qR$. An M-LWE$_{n,d,q,\psi}$ sample is given by $(\mathbf{a}, q^{-1}\langle\mathbf{a},\mathbf{s}\rangle + \mathbf{e} \bmod \mathbb{R})$, where $\mathbf{a}$ is uniform in $\mathbb{Z}_q^d$, and $\mathbf{e}$ is sampled from $\psi$. The search version asks to find $\mathbf{s}$ given arbitrarily many samples, while the decision version asks to distinguish such samples from uniformly random ones over $\mathbb{Z}_q^d \times \mathbb{T}$, where the torus is $\mathbb{T} = K_\mathbb{R}/R$. We can also use a matrix formula-
tion when the number of samples *m* is fixed by considering the M-LWE$_{n,d,m,q,\psi}$ distribution ($\mathbf{A}, q^{-1}\mathbf{A}\mathbf{s} + \mathbf{e} \bmod R$) with $\mathbf{A}$ uniform in $R_q^{m \times d}$ and $\mathbf{e}$ from $\psi^m$. When the module rank is $d=1$, the problem is called *Ring-LWE (R-LWE)* [30]. Just like LWE, the M-LWE problem enjoys worst-case to average-case connections from lattice problems such as SIVP$_\gamma$ [24]. Whereas the hardness results for LWE start from general lattice problems, the set has to be restricted to *module lattices* in the case of M-LWE, which correspond to finitely generated *R*-modules. Since its introduction, the M-LWE problem has attracted more and more interest as it offers a fine-grained trade-off between concrete security and efficiency, mostly by tweaking the parameters *n* and *d*. It is also extremely versatile in the sense that it allows for constructing a wide variety of cryptographic schemes. As an example, within the ongoing NIST standardization process [40], several finalist candidates relying on the hardness of M-LWE have recently been chosen for standardization, e.g., the signature scheme Dilithium [18] and the key encapsulation mechanism Kyber [10]. However, these efficient schemes use different parameter settings, and in particular different distributions for the secret and error, that are not yet encompassed by theoretical proofs of hardness. In these cases, the hardness of M-LWE is argued based on the state of the art cryptanalysis and attacks on M-LWE.

**Short Distributions.** The standard formulation of LWE considers a large uniform secret and a Gaussian error, but in practice we tend to consider short distributions, i.e., secret or error with coefficients bounded by $\eta \ll q$. This corresponds to choosing the secret $\mathbf{s}$ or a discrete error distribution $\psi$ to be over $\{0, \dots, \eta - 1\}$ (or $\{-\eta, \dots, -1\}$) instead of $\mathbb{Z}_q$. Besides gaining in efficiency, choosing a small secret plays an important role in some applications like fully homomorphic encryption [19] or modulus switching techniques [17,1,56] as it keeps the noise blowup to a minimum. The LWE problem with uniform bounded secret has been well studied in the case of binary secrets (i.e., secrets in $\{0, 1\}^d$), denoted by bin-LWE, but the different approaches easily generalize to slightly larger secrets. A first study of bin-LWE was provided by Goldwasser et al. [21] in the context of leakage-resilient cryptography. Although their proof structure has the advantage of being easy to follow, their result suffers from a large error increase. Informally, they show a reduction from $LWE_{k,q,D_\alpha}$ to bin-$LWE_{d,q,D_\beta}$, where $\beta/\alpha = d^{\omega(1)}$ (super-polynomial) and $d \ge k \log_2 q + \omega(\log_2 d)$. The distribution $D_r$ denotes a Gaussian distribution with standard deviation $r$ (up to a factor of $\sqrt{2\pi}$). It was later improved by Brakerski et al. [17] and Micciancio [35] using more technical proofs. Both of them achieve a similar dimension increase between $k$ and $d$, but only increase the error by roughly $\beta/\alpha = \Omega(\sqrt{d})$ (polynomial). The dimension increase from $k$ to roughly $k \log_2 q$ is reasonable as it essentially preserves the number of possible secrets. Recent work by Brakerski and Döttling [14] extends the hardness results to more general secret distributions based on entropic arguments.

The hardness of LWE with error uniformly distributed below $\eta$ with $\eta \ll q$ was first studied by Micciancio and Peikert [38]. They proved that the LWE
function $(\mathbf{s}, \mathbf{e}) \mapsto \mathbf{As} + \mathbf{e} \bmod q$ is one-way with respect to inputs $\mathbf{e}$ uniform over $\{0, \dots, \eta - 1\}^m$, provided that the number of samples $m$ is at most $d(1 + O(\log_2 \eta / \log_2 d))$. The one-wayness is proven under the hardness of general lattice problems over lattices of rank $O(d \log_2 \eta / \log_2 d)$. It was recently extended to non-uniform binary errors by Sun et al. [52], proving that the maximum number of samples must be $m = d(1 + O(p(d)/\log_2 d))$, where $p(d)$ is the probability of getting 1 from the error distribution. The proof of [38] corresponds to $p(d) = 1/2$.

The question of whether these hardness results carry over to structured variants, and in particular to the module case, was left open. The work on LWE with entropic secrets was extended to the R-LWE case by Brakerski and Dötting [15], and the module case by Lin et al. [26]<fnref n="1" />. However, no results on the hardness of M-LWE with small uniform error were known, even though they serve as hardness assumptions for most efficient M-LWE-based schemes. For example, the signature scheme Dilithium [18] samples the secret and error from the uniform distribution over vectors with coefficients between −2 and 2 (security levels I and III) or between −4 and 4 (security level II).

**Our Contributions.** In this paper, we provide three main contributions on the hardness of M-LWE with small secret and/or error, i.e., with coefficients bounded by some positive integer $\eta$. The first two contributions study the hardness of the M-LWE problem with centered $\eta$-bounded secret, which we denote by $\eta$-M-LWE, in both its search and decision versions, for any $\eta \ge 1$. They are generalizations of the results published in our previous conference papers [12] and [13] respectively, only dealing with the special case bin-M-LWE with secret coefficients in $\{0, 1\}$, which is already mentioned in one of the author's thesis [11]. As opposed to [12,13], we decide to work in the primal ring $R$ and with a centered representation of secrets with coefficients in $\{-\eta, \dots, \eta\}^2$ to show that the proofs still work and also to match practical uses of the M-LWE assumption like [10,18]. The third and new contribution concerns the hardness of the search version of M-LWE with $\eta$-bounded error, under more specific restrictions on $\eta$. The latter contribution can then be used to deduce the hardness of search M-LWE with small secret and error. To the best of our knowledge, it is the first result for the hardness of M-LWE with small uniform error. The results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.

*Contribution 1: Computational hardness of $\eta$-M-LWE.* We show a first reduction for the hardness of the search version of $\eta$-M-LWE. The formal statement can be found in Theorem 3.1. It follows the original proof structure of Goldwasser et al. [21] in the case of LWE, while achieving much better noise parameters by

<footnote n="1">¹ Note that at the time of writing, the paper by Lin et al. is only accessible on ePrint and has not yet been peer-reviewed.</footnote>

<footnote n="2">² Setting $\eta = 1$ gives ternary secrets instead of binary. We however observe that the parameters covered by the reductions for $\eta = 1$ in the centered representation match those of [12,13], and it has the upside of a larger secret space. This leads to smaller ranks $d$ by a factor of $\log_2 3$.</footnote>
using the Rényi divergence instead of the statistical distance to measure the dis-
tance between two distributions. The improvement on the noise rate compared
to [21] stems from the fact that the Rényi divergence only needs to be constant
for the reduction to work, and not necessarily negligibly close to 1 (compared
to negligibly close to 0 for the statistical distance). A similar effect arises with
respect to the rank condition in comparison with Contribution 2 below. More
precisely, as we use the leftover hash lemma (over rings) with respect to the
Rényi divergence, we can have a rank that is logarithmic in the ring degree $n$,
instead of super-logarithmic. However, using the Rényi divergence as a mea-
sure of distribution closeness only allows us to prove the hardness of the *search*
variant, denoted by $\eta$-M-SLWE. Additionally, its use asks to fix the number of
samples a priori.

The result consists in a reduction from M-SLWE and M-LWE with rank $k$
and Gaussian width $\alpha$ to $\eta$-M-SLWE with rank $d$ and width $\beta$. The reduction
preserves the ring degree $n$, the number of samples $m$ and the modulus $q$, where $q$
only needs to be prime. The ranks must satisfy $d \log_2(2\eta + 1) \ge k \log_2 q +
\Omega(\log_2 n)$, which is due to the use of the leftover hash lemma over rings. The
Gaussian noise parameter $\alpha$ is also increased to $\beta$ by a factor $\beta/\alpha = d\sqrt{m} \cdot
n^{3/2}\eta \log_2(n)$ in general cyclotomic fields, which can be further improved by a
factor of $\sqrt{n}$ in the specific case of power-of-two cyclotomic fields.

Contribution 2: Pseudorandomness of η-M-LWE. We then provide a more in-
volved proof of hardness for the *decision* version of η-M-LWE through a reduc-
tion from M-LWE to η-M-LWE. The thorough statement is provided in Theo-
rem 3.2. Not only does this reduction apply to the decision versions, but it also
slightly improves the noise rate of the reduction in certain parameter regimes.
In particular, the noise rate no longer depends on the number of samples *m*, as
opposed to Contribution 1. The technique follows the idea of [17] by introduc-
ing the two intermediate problems first-is-errorless M-LWE and ext-M-LWE. We
start by reducing the M-LWE problem to the first-is-errorless M-LWE variant,
where the first sample is not perturbed by an error. We then reduce the latter
to ext-M-LWE, which can be seen as M-LWE with an extra information on the
error vector **e** given by ⟨**e**,*z*⟩ for a uniformly chosen **z** in the set of η-bounded ring
vectors. Two other formulations of ext-M-LWE were proposed by Alperin-Sheriff
and Apon [4], and more recently by Lyubashevsky et al. [33], but neither suits
our reduction due to our lossy argument in Lemma 3.5. We discuss further these
differences in Section 3.2.2. Then, to reduce ext-M-LWE to η-M-LWE, we use a
lossy argument, similar to that of Contribution 1 but now relying on the newly
derived ext-M-LWE hardness assumption, as well as the leftover hash lemma.

The main challenge is the use of matrices composed of ring elements. The
proof in [17, Lem. 4.7] requires the construction of unimodular matrices which
is not straightforward to adapt in the module setting because of invertibility
issues. The construction in Lemma 3.2 relies on units of the quotient ring $R/qR$,
which are much harder to explicitly describe than the units of $\mathbb{Z}/q\mathbb{Z}$ in the sense
that we do not have practical closed-form expressions. This is the reason why we
need to control the splitting structure of the cyclotomic polynomial modulo $q$.
Lemma 2.4 [32, Thm. 1.1] solves this issue but requires $q$ to satisfy certain number-theoretic properties and to be sufficiently large so that all the non-zero small norm ring elements are units of $R_q$.

In the whole reduction, the ring degree $n$, number of samples $m$ and modulus $q$ are preserved, where $m$ needs to be larger than $d$ and $q$ needs to be a prime satisfying the said number-theoretic properties. With the help of the modulus-switching technique of Langlois and Stehlé [24, Thm 4.8], we can then relax the restriction on the modulus $q$ to be any polynomially large modulus, at the expense of a loss in the Gaussian noise parameter. The ranks must satisfy $d \log_2(2\eta+1) \ge (k+1) \log_2 q + \omega(\log_2 n)$, in the same manner as in Contribution 1, except that the asymptotic term is now super-logarithmic. The noise rate is now given by $n\eta\sqrt{2d}\sqrt{4n^2\eta^2+1} = \Theta(\eta^2n^2\sqrt{d})$ for cyclotomic fields. This reduction removes the dependency in $m$ in the noise rate of Contribution 1, which can be more advantageous in certain cases as we usually take $m = \Theta(n \log_2 n)$. In the special case of $\eta = 1$ and $n = 1$, we recover the same noise-ratio $\Theta(\sqrt{d})$ as in the original LWE result from Brakerski et al. [17].

**Contribution 3: One-wayness of M-LWE with small error.** Our last contribution focuses on the hardness of M-SLWE when the error distribution is uniform over $\eta$-bounded elements instead of Gaussian. The complete result can be found in Theorem 4.1. It uses a different proof method from Contributions 1 and 2 by following the idea of Micciancio and Peikert [38] of proving the one-wayness of the M-LWE function $(\mathbf{s}, \mathbf{e}) \mapsto \mathbf{A}\mathbf{s} + \mathbf{e}$ mod $qR$, with $\mathbf{e}$ uniform in $S_{\eta}^m$ (i.e., $\eta$-bounded vectors over $R$ of dimension $m$). To do so, we prove the one-wayness of the M-ISIS function $\mathbf{e} \mapsto (\mathbf{A}')^T\mathbf{e}$ mod $qR$ and use the duality between both functions to conclude. This function is inspired from the *Module Short Integer Solution* (M-SIS) problem [24] which asks to find a short non-zero vector $\mathbf{e} \in R^m$ such that $(\mathbf{A}')^T\mathbf{e} = \mathbf{0}$ mod $qR$ for a public random matrix $\mathbf{A}' \in R_q^{m \times d}$. It can be generalized to an inhomogeneous version by replacing $\mathbf{0}$ by a public syndrome $\mathbf{u}$. The one-wayness of the function is ensured by two properties, namely the unpredictability and the second preimage resistance, which we prove using statistical arguments.

We obtain similar results to [38] in terms of the number of samples using the asymptotic approach. However, the asymptotic approach is not suited for very small values of $d$. To overcome this problem, we use a more fine-grained approach using tighter calculations rather than hiding constants in asymptotic notations. This leads to more complicated conditions on the parameters, especially the link between the size of the error $\eta$ and the number of samples $m$. We thus evaluate this condition numerically to determine the concrete parameters that are encompassed by the result. It shows that in order to reach very small errors, e.g. ternary, the module rank $d$ has to be large enough. We can still reach a small error size $\eta$ for constant module ranks, but not arbitrarily small. The reduction also gives a condition on the maximal number of samples $m$ we can provide with such small uniform error. In particular, we have $m \le d(1 + o(\log_2 \eta))$ which is similar to what is obtained in [38]. Then, to prove the hardness of M-SLWE with small error and secret with $m''$ samples, we need to have the hardness
of M-LWE with small error and $m' + m''$ samples for $m' \ge d$. This restriction makes it difficult to achieve small error and secret at the same time for a large enough $m''$. We discuss this transformation in more details in Section 4.3.

The M-SLWE problem can be seen as a linear system of equations ($d$ variables and $m$ equations over $R_q$ or $nd$ variables and $nm$ equations over $\mathbb{Z}_q$) with noise. The presence of noise or error is what makes the problem difficult to solve. The motivation is therefore to determine the threshold of noise to add to the equations above which the problem is proven hard. Note that the number of equations characterized by $m$ and the distribution of the error need to be chosen carefully with respect to one another. For example, an attack by Arora and Ge [6] uses the $m$ samples to build noiseless polynomial equations of degree $\eta$, where $\eta$ is a bound on the error coefficients. If $m$ is sufficiently large, root finding algorithms can perform well on the latter. In particular, if $\eta = 1$ (ternary), then $m \approx d^3$ samples is enough to solve LWE in polynomial time. The attack can also be applied to M-LWE as one equation over $R_q$ gives $n$ equations over $\mathbb{Z}_q$. We discuss the consequences on the parameters in Section 4.4.

**Open Problems.** In this paper, several results are limited to special classes of number fields, e.g. cyclotomic fields or fields $K = \mathbb{Q}(\zeta)$ for which the ring of integers is $R = \mathbb{Z}[\zeta]$. Although it covers the fields that are used in practice, it may be of independent interest to extend our results to more general fields.

The first two contributions imply the hardness of M-LWE with a small secret and a moderate rank (e.g., $\Omega(\log_2 n)$ for search and $\omega(\log_2 n)$ for decision) due to the leftover hash lemma over rings. The hardness of $\eta$-M-LWE thus remains open for lower module ranks. Practical M-LWE-based schemes use a constant rank for increased efficiency, like the CRYSTALS suite [10,18] chosen for standardization by NIST.

The hardness proof of $\eta$-M-LWE with $\eta$-bounded error and $m$ samples currently requires the hardness of M-LWE with $\eta$-bounded error and $m+d$ samples. Although there is no subexponential attack for $m = d, d+1$ (even for ternary errors $\eta = 1$) yet, our proof does not encompass this range of parameters. We leave it as a major open problem to prove the hardness of $\eta$-M-LWE with $\eta$-bounded error for $m \gtrsim d$.

Finally, two of our contributions are only proven for the search version of M-LWE. One possibility (of more general interest) would be to find search-to-decision reductions for M-LWE that preserve the secret distribution or the error distribution without reducing the number of samples $m$ too much. For the latter, a sample-preserving search-to-decision for LWE [36] is known, but it is yet to be extended to structured variants.

**Organization.** In Section 2, we introduce the notions and preliminary results that are needed in this work. Section 3 is dedicated to the proofs of Contributions 1 and 2 on the hardness of $\eta$-M-LWE, generalizing that of our earlier conference papers [12,13]. Then, in Section 4, we give the proof of Contribution 3 on the
hardness of M-LWE with $\eta$-bounded error. Finally, Section 5 gives a concise view of the current landscape on the hardness of M-LWE.

# 2 Preliminaries

Throughout the paper, $q$ denotes an odd prime integer, and $\mathbb{Z}_q$ denotes the ring of integers modulo $q$. We may occasionally identify $\mathbb{Z}_q$ with the centered set of representatives $\{-(q-1)/2, \dots, (q-1)/2\}$. In a ring $R$, we write $\langle p \rangle$ for the principal ideal generated by $p \in R$, and $R_p$ for the quotient ring $R/\langle p \rangle = R/pR$. For simplicity, we denote by $[n]$ the set $\{1, \dots, n\}$ for any positive integer $n$. Vectors and matrices are written in bold and their transpose (resp. Hermitian) is denoted by superscript $T$ (resp. $\dagger$). We denote the Euclidean norm and infinity norm of $\mathbb{C}^n$ by $\|\cdot\|_2$ and $\|\cdot\|_{\infty}$ respectively. We also define the spectral norm of any matrix $\mathbf{A} \in \mathbb{C}^{n \times m}$ by $\|\mathbf{A}\|_2 = \max_{\mathbf{x} \in \mathbb{C}^m \setminus \{0\}} \|\mathbf{A}\mathbf{x}\|_2 / \|\mathbf{x}\|_2$, and the max norm as $\|\mathbf{A}\|_{\max} = \max_{i \in [n], j \in [m]} |a_{i,j}|$. The identity matrix of size $n$ is denoted by $\mathbf{I}_n$. We use the standard Landau notations, i.e., $O(\cdot)$, $o(\cdot)$, $\omega(\cdot)$, $\Omega(\cdot)$, $\Theta(\cdot)$, and we say a function $\varepsilon$ is negligible in $n$ if $\varepsilon(n) = n^{-\omega(1)}$. We also say that a probability $p$ is overwhelming if $1-p$ is negligible in $n$. We use the abbreviation PPT for probabilistic polynomial-time.

## 2.1 Algebraic Number Theory

A number field $K = \mathbb{Q}(\zeta)$ of degree $n$ is a finite field extension of the rational number field $\mathbb{Q}$ obtained by adjoining an algebraic number $\zeta$. We define the field tensor product by $K_{\mathbb{R}} = K \otimes_{\mathbb{Q}} \mathbb{R}$. The set of all algebraic integers of $K$ defines a ring, called the ring of integers which we denote by $R$. It is always true that $\mathbb{Z}[\zeta] \subseteq R$, where this inclusion can be strict. Some of the results are restricted to the class of number fields where the equality $R = \mathbb{Z}[\zeta]$ holds<fnref n="3" />. This is the case for some quadratic extensions (i.e., when $\zeta = \sqrt{d}$ with $d$ square-free and $d \neq 1 \pmod 4$), cyclotomic fields (i.e., when $\zeta$ is a primitive root of the unity) and number fields with a defining polynomial $f$ of square-free discriminant $\Delta_f$. In this paper, we assume that for the number fields we consider, the ring of integers is efficiently computable and has a good basis representation. In particular, it is the case for cyclotomic fields.

**Space H.** We use $t_1$ to denote the number of real roots of the minimal polynomial of the underlying number field, and $t_2$ the number of pairs of complex conjugate roots, which yields $n = t_1 + 2t_2$. The space $H \subseteq \mathbb{C}^n$ is defined by $H = \{\mathbf{x} \in \mathbb{R}^{t_1} \times \mathbb{C}^{2t_2} : \forall j \in [t_2], x_{t_1+t_2+j} = \bar{x}_{t_1+j}\}$. We can verify that $H$ is a $\mathbb{R}$-vector space of dimension $n$ with the columns of $U_H$ as orthonormal

<footnote n="3">³ We may sometimes call this class of fields “monogenic fields”, but we note that rigorously a monogenic number field is $K = \mathbb{Q}(\zeta)$ for which $R = \mathbb{Z}[\zeta']$ for a possibly different $\zeta'$.</footnote>
basis, where

$$ U_H = \frac{1}{\sqrt{2}} \begin{bmatrix} \sqrt{2} \mathbf{I}_{t_1} & \mathbf{0} & \mathbf{0} \\ \mathbf{0} & \mathbf{I}_{t_2} & i \mathbf{I}_{t_2} \\ \mathbf{0} & \mathbf{I}_{t_2} & -i \mathbf{I}_{t_2} \end{bmatrix}. $$

**Coefficient embedding.** A number field $K = \mathbb{Q}(\zeta)$ of degree $n$ can be seen as a vector space of dimension $n$ over the rationals with basis $\{1, \zeta, \dots, \zeta^{n-1}\}$, meaning that each element $x \in K$ can be written as $x = \sum_{0 \le j \le n-1} x_j \zeta^j$ with $x_j \in \mathbb{Q}$. The coefficient embedding is the isomorphism $\tau$ between $K$ and $\mathbb{Q}^n$ that maps every $x \in K$ to its coefficient vector $\tau(x) = [x_0, \dots, x_{n-1}]^T$. For simplicity, we use $\tau_k(x)$ to denote $x_k$. For a positive integer $\eta$, we define $S_\eta = \tau^{-1}(\{-\eta, \dots, \eta\}^n)$, which can be seen as the set of polynomials with coefficients in $\{-\eta, \dots, \eta\}$. The embedding $\tau$ can also be extended to $K_\mathbb{R}$, mapping it to $\mathbb{R}^n$.

**Canonical embedding.** Another way to embed $K$ is to use the canonical embedding. $K$ has exactly $n$ field homomorphisms $\sigma_1, \dots, \sigma_n$, which are characterized by the fact that they map $\zeta$ to one of the distinct roots of $f$. We order them so that $\sigma_1, \dots, \sigma_{t_1}$ map to one of the real roots, and $\sigma_{t_1+1}, \dots, \sigma_{t_1+2t_2}$ map to one of the complex roots. The canonical embedding is the ring homomorphism from $K$ to $\mathbb{C}^n$ defined by $\sigma(x) = [\sigma_1(x), \dots, \sigma_n(x)]^T$, and the addition and multiplication are done component-wise. As $f$ has rational coefficients, it holds that the complex embeddings come in conjugate pairs, and therefore the range of $\sigma$ is a subset of $H$. We can thus map $K$ to $\mathbb{R}^n$ with $\sigma_H = U_H^\dagger \sigma$. We extend the embeddings to vectors in $K^d$ in the natural way by concatenating the embedding vectors of each coefficient, i.e., $\tau(\mathbf{x}) = [\tau(x_1)^T, \dots, \tau(x_d)^T]^T$ and similarly for $\sigma$ and $\sigma_H$. For a vector $\mathbf{x} \in K^d$, we define $\|\mathbf{x}\|_\infty = \max_{k \in [n], i \in [d]} |\sigma_k(x_i)|$, and $\|\mathbf{x}\|_{2,\infty} = \max_{k \in [n]} \sqrt{\sum_{i \in [d]} |\sigma_k(x_i)|^2}$. We then define the field norm of $K$ as $N(x) = \prod_{k \in [n]} \sigma_k(x) \in \mathbb{Q}$ for all $x \in K$.

**Distortion between embeddings.** Both embeddings play important roles in this paper, and we recall that the two embeddings are linked by the linear relation

$$ \sigma(x) = \mathbf{V}\tau(x) \text{ for all } x \in K, \text{ where } \mathbf{V} = \begin{bmatrix} 1 & \alpha_1 - \alpha_1^{n-1} \\ 1 & \alpha_2 - \alpha_2^{n-1} \\ \vdots & \vdots \\ 1 & \alpha_n - \alpha_n^{n-1} \end{bmatrix} $$

is the Vandermonde matrix defined by the roots $(\alpha_k)_{k \in [n]}$ of the defining polynomial $f$. This transformation does not necessarily carry the structure from one embedding to the other, e.g., a binary vector in the coefficient embedding need not to be binary in the canonical embedding. Changing the embedding also impacts the norm, which is captured by the inequalities $\|\mathbf{V}^{-1}\|_2^{-1} \|\tau(x)\|_2 \le \|\sigma(x)\|_2 \le \|\mathbf{V}\|_2 \|\tau(x)\|_2$. Hence, $\|\mathbf{V}\|_2$ and $\|\mathbf{V}^{-1}\|_2$ help approximating the distortion between both embeddings. Roşca et al. [50] and Blanco-Chacón [8] give
additional insight on this distortion for specific number fields. Throughout this paper, we are interested in the parameter defined by $B_{\eta} = \max_{x \in S_{\eta}} \|\sigma(x)\|_{\infty}$ for a positive integer $\eta$. This parameter is inherent to the ring and intervenes in the proof of Lemma 3.2, 3.5 and 4.4. Here, we provide an upper-bound on $B_{\eta}$, that is further simplified for cyclotomic number fields. The proof is provided in Appendix B.1 for completeness.

**Lemma 2.1.** Let $K$ be a number field of degree $n$, $R$ its ring of integers, and $V$ the associated Vandermonde matrix. Let $\eta$ be a positive integer. Then, it holds that $1 \le B_{\eta} = \max_{x \in S_{\eta}} \|\sigma(x)\|_{\infty} \le n\eta \|V\|_{\max}$. In particular, for cyclotomic fields, it yields $1 \le B_{\eta} \le n\eta$.

**Multiplication matrices.** The multiplication in $K$ (or $K_{\mathbb{R}}$) translates into a matrix-vector multiplication once embedded with either $\tau$, $\sigma$ or $\sigma_H$. In the canonical embedding, the multiplication matrix can be easily expressed as we have that for all $x$ and $y$ in $K$, $\sigma(x \cdot y) = \sigma(x) \odot \sigma(y) = \text{diag}(\sigma(x)) \cdot \sigma(y)$, where $\odot$ denotes the coefficient-wise product or Hadamard product. Therefore, the multiplication matrix is $M_{\sigma}(x) = \text{diag}(\sigma(x))$. We can then express the multiplication matrix with respect to $\sigma_H$ as $M_{\sigma_H}(x) = U_H^{\dagger} M_{\sigma}(x) U_H$. In the coefficient embedding, we can still write $\tau(x \cdot y)$ as $M_{\tau}(x) \cdot \tau(y)$, but the expression of $M_{\tau}(x)$ is more involved. We defer the proof to Appendix B.1.

**Lemma 2.2.** Let $K = \mathbb{Q}(\zeta)$ be a number field of degree $n$, and $f = x^n + \sum_{k=0}^{n-1} f_k x^k$ the minimal polynomial of $\zeta$. Then for all $x$ in $K$, it holds that

$$M_{\tau}(x) = \sum_{k=0}^{n-1} \tau_k(x) \mathbf{C}^k, \text{ with } \mathbf{C} = \begin{bmatrix} 0 & 0 & -f_0 & \\ & \ddots & -f_1 & \\ & & \ddots & \\ & & & -f_{n-1} \end{bmatrix}$$

the companion matrix of the minimal polynomial $f$.

In power-of-two cyclotomic fields, we have $f = x^n + 1$ yielding that $\mathbf{C}$ is the generating nega-circulant matrix. The expression of $M_{\tau}(x)$ can be simplified to

$$M_{\tau}(x) = \begin{bmatrix} x_0 & -x_{n-1} & -x_1 \\ x_1 & x_0 & | \\ | & | & -x_{n-1} \\ x_{n-1} & x_{n-2} & x_0 \end{bmatrix} \in \mathbb{Q}^{n \times n},$$

which is itself a nega-circulant matrix, with $x_k = \tau_k(x)$. We can also translate the matrix-vector multiplication in $K^d$ to a matrix-vector multiplication in $\mathbb{R}^{nd}$ by extending the multiplication matrix maps $M_{\sigma}, M_{\sigma_H}$ and $M_{\tau}$ to a matrix in $K^{m \times d}$. More precisely, for a matrix $\mathbf{A} = [a_{ij}]_{(i,j) \in K^{m \times d}}$, we define the block matrix $M_{\sigma}(\mathbf{A}) = [M_{\sigma}(a_{ij})]_{(i,j) \in K^{m \times d}}$. We define $M_{\sigma_H}(\mathbf{A})$ and $M_{\tau}(\mathbf{A})$ the same
way. As we need it later in this paper, we provide a way to obtain the singular values of such block matrices. This relies on a unified analysis from [49] which gives conditions to obtain the eigenvalues of a matrix when described by blocks. In our setting, we end up showing that the spectral analysis of the entire block matrix $M_τ(\mathbf{A})$ comes down to finding the singular values of the $n$ embedded matrices $\sigma_k(\mathbf{A})$. For convenience, we write $S(\mathbf{A})$ the set of all singular values of a complex matrix $\mathbf{A}$. The proof can be found in Appendix B.1.

**Lemma 2.3.** Let $K$ be a number field of degree $n$, and $d, m$ positive integers. Let $\mathbf{A}$ be a matrix in $K^{d \times m}$.

$$S(M_{\tau}(\mathbf{A})) = \bigcup_{k \in [n]} S(\sigma_k(\mathbf{A})) = S(M_{\sigma}(\mathbf{A})) = S(M_{\sigma_H}(\mathbf{A})),$$

where $\sigma_k(\mathbf{A}) = [\sigma_k(a_{ij})]_{(i,j) \in [d] \times [m]}$. In particular, it holds that $\|M_τ(\mathbf{A})\|_2 = \max_{k \in [n]} \|\sigma_k(\mathbf{A})\|_2$.

**Ideals, units and modules.** An ideal $\mathfrak{p} \neq R$ is prime if for all $a, b \in R$, $ab \in \mathfrak{p}$ implies that $a$ or $b$ is in $\mathfrak{p}$. In $R$, an ideal $\mathfrak{p}$ is prime if and only if it is maximal, implying that $R/\mathfrak{p}$ is a field. For two ideals $\mathcal{I}$ and $\mathcal{J}$, the sum $\mathcal{I} + \mathcal{J}$ is the set of all $x+y$, where $(x, y) \in \mathcal{I} \times \mathcal{J}$, while the product $\mathcal{I}\mathcal{J}$ is the set of all finite sums of $xy$, where $(x, y) \in \mathcal{I} \times \mathcal{J}$. An integer $q$ is said to be unramified in $R$ if the ideal $\langle q \rangle$ can be factored in a product of distinct prime ideals $\prod_{i \in [\kappa]} \mathfrak{p}_i$. We say that $q$ is fully splitted in $R$ if $\kappa = n$ in the above factorization, where $n$ is the degree of the number field. We also say that $q$ is inert in $R$ if $\langle q \rangle$ is prime. We extend the field norm and define the norm of an ideal $N(\mathcal{I})$ as the index of $\mathcal{I}$ as an additive subgroup of $R$, which corresponds to $N(\mathcal{I}) = |R/\mathcal{I}|$. The norm is still multiplicative and verifies $N(\langle a \rangle) = |N(a)|$ for any $a \in R$.

In the construction of Lemma 3.2, we need a condition for small norm elements of $R_q$ to be invertible for a specific $q$. To do so, we rely on the small norm condition proven in [32, Th. 1.1].

**Lemma 2.4 ([32, Th. 1.1]).** Let $K$ be the $\nu$-th cyclotomic field, with $\nu = \prod_i p_i^{e_i}$ be its prime-power factorization, with $e_i \ge 1$. We denote by $R$ the ring of integers of $K$. Also, let $\mu = \prod_i p_i^{f_i}$ for any $f_i \in [e_i]$. Let $q$ be a prime such that $q = 1 \mod \mu$, and $\mathrm{ord}_\nu(q) = \nu/\mu$, where $\mathrm{ord}_\nu$ is the multiplicative order modulo $\nu$. Then, for any element $y$ of $R$ satisfying $0 < \|\tau(y)\|_\infty < q^{1/\varphi(\mu)}/s_1(\mu)$, it holds that $y \mod qR$ is a unit in $R_q$, where $s_1(\mu)$ denotes the spectral norm of the Vandermonde matrix of the $\mu$-th cyclotomic field.

The number theoretic conditions on $q$ essentially say that $\langle q \rangle$ splits into $\varphi(\mu)$ distinct prime ideal factors, each of algebraic norm $q^{\varphi(\nu)/\varphi(\mu)} = q^{\nu/\mu}$. In the case where $\nu$ is a power of an odd prime, then so is $\mu$ and then [30] states that $s_1(\mu) = \sqrt{\mu}$. For more general cases, we refer to the discussions from Lyubashevsky and Seiler [32, Conj. 2.6]. We also refer the reader to [32, Th. 2.5] that discusses the existence of such primes $q$ for specific values of $\nu$ and $\mu$.
**Remark 2.1 (Instantiation in power-of-two cyclotomics).** This result is simplified in the power-of-two case [32, Cor. 1.2] where it is conditioned on the number $κ > 1$ of splitting factors of $x^n+1$ in $\mathbb{Z}_q[x]$. Choosing $κ$ as a power of two less than $n = 2^ℓ$, the only conditions on $q$ are that $q$ has to be a prime congruent to $2κ + 1$ modulo $4κ$. The invertibility condition then becomes $0 < ||τ(y)||_∞ < q^{1/κ}/\sqrt{κ}$ for any $y$ in $R_q$. The upper bound is decreasing with $κ$ so the smaller $κ$, the more invertible elements. The smallest choice for $κ$ is $κ = 2$, which leads to choosing a prime $q = 5$ mod 8, meaning the ideal $qR$ splits into two prime ideal factors of norm $q^{n/2}$. In our context in Section 3.2.2, having $q^{1/2}/\sqrt{2} > η$ is sufficient as our elements have $η$-bounded coefficients. For the ternary secret case $η = 1$, this leads to $q > 2$, which is subsumed by $q = 5$ mod 8.

We say that $\mathbf{a}_1, \dots, \mathbf{a}_ℓ \in R_q^d$ are $R_q$-linearly independent if and only if for all $(\lambda_i)_{i \in [\ell]} \in R_q^ℓ$, $\sum_{i \in [\ell]} \lambda_i \mathbf{a}_i = 0$ implies $\lambda_i = 0$ in $R_q$ for all $i \in [\ell]$. We now give results on the linear independence of uniform vectors of $R_q^d$ and the singularity of uniformly random matrices. A result similar to Lemma 2.5 is present in [56] but the proof unfortunately relies on a flawed argument. We detail this matter in Appendix A and provide corrected proofs.

**Lemma 2.5.** Let $K$ be a number field, and $R$ its ring of integers. Let $d, q$ be positive integers such that $q$ is an unramified prime which factors as $\langle q \rangle = \prod_{i \in [\kappa]} \mathfrak{p}_i$. Let $ℓ$ be in $\{0, \dots, d-1\}$, and $\mathbf{a}_1, \dots, \mathbf{a}_ℓ \in R_q^d$ be $R_q$-linearly independent vectors of $R_q^d$. Then

$$ \mathbb{P}_{\mathbf{b} \leftarrow U(R_q^d)}[\mathbf{a}_1, \dots, \mathbf{a}_\ell, \mathbf{b} \text{ are } R_q\text{-linearly independent}] = \prod_{i \in [\kappa]} \left(1 - \frac{1}{N(\mathfrak{p}_i)^{d-\ell}}\right). $$

As a result, for any $1 \le k \le d$, it holds that

$$ \mathbb{P}_{(\mathbf{a}_i)_{i \sim U(R_q^d)^k}}[(\mathbf{a}_i)_{i \in [\kappa]} \text{ are } R_q\text{-linearly independent}] = \prod_{\ell=0}^{k-1} \prod_{i \in [\kappa]} \left(1 - \frac{1}{N(\mathfrak{p}_i)^{d-\ell}}\right). $$

**Lemma 2.6.** Let $K$ be a number field, and $R$ its ring of integers. Let $q$ be a prime integer that is unramified in $R$ which splits as $\langle q \rangle = \prod_{i \in [\kappa]} \mathfrak{p}_i$. Let $m \ge d$ be two integers. It holds

$$ \mathbb{P}_{\mathbf{A} \sim U(R_q^{d \times m})}[\mathbf{A} \cdot R_q^m = R_q^d] \ge \prod_{\ell=0}^{d-1} \prod_{i \in [\kappa]} \left(1 - \frac{1}{N(\mathfrak{p}_i)^{m-\ell}}\right). $$

When $R$ and $q$ are clear from the context, for $m \ge d$, we define $\delta(m, d) = 1 - \mathbb{P}_{\mathbf{A} \sim U(R_q^{d \times m})}[\mathbf{A} \cdot R_q^m = R_q^d]$, which we use extensively throughout Section 4. We note that $\delta(m, d)$ can be upper-bounded by $\frac{d \cdot \kappa}{(\min_{i \in [\kappa]} N(\mathfrak{p}_i))^{m-d+1}}$. Hence, if $q$ splits into only high-norm ideal factors so that $\min_{i \in [\kappa]} N(\mathfrak{p}_i) \ge n^{\omega(1/(m-d+1))}$, the probability $\delta(m, d)$ becomes negligible.
We also define $\delta'(k, d)$ to be the probability that among $k \ge d$ independent uniform columns of $R_q^d$, there is no subset of $d$ of those columns that are $R_q$-linearly independent. Formally, we define

$$ \delta'(k, d) = 1 - \mathbb{P}_{(\mathbf{a}_i)_{i \in [k]} \sim U(R_q^d)} [\exists S \subseteq [k], |S| = d \wedge (\mathbf{a}_i)_{i \in S} \text{ are } R_q\text{-l. i.}] $$

We note that if $R_q$ was a field, we would have $\delta(k, d) = \delta'(k, d)$. However, in the general case, $\delta(k, d) \ne \delta'(k, d)$ as a minimal spanning set of an $R_q$-submodule of $R_q^d$ is not necessarily a basis of said submodule. Additionally, note that $\delta'(d, d)$ is given by Lemma 2.5 as

$$ \delta'(d, d) = 1 - \prod_{\ell=0}^{d-1} \prod_{i \in [\kappa]} \left( 1 - \frac{1}{N(\mathbf{p}_i)^{d-\ell}} \right). $$

The probability $\delta'(k, d)$ is discussed in Section 4.3 as it only appears in the latter.

## 2.2 Lattices

A (full-rank) lattice $\Lambda$ of rank $n$ is a discrete additive subgroup of $\mathbb{R}^n$. Since $H$ is isomorphic to $\mathbb{R}^n$, we may consider lattices that are discrete subgroups of $H$. Each lattice can be represented by a basis $\mathbf{B} = [\mathbf{b}_i]_{i \in [n]} \in \mathbb{R}^{n \times n}$ as the set of all integer linear combinations of the $\mathbf{b}_i$, i.e., $\Lambda = \mathbf{B}\mathbb{Z}^n$. We define the dual lattice of a lattice $\Lambda$ by $\Lambda^* = \{\mathbf{x} \in \text{Span}(\Lambda) : \forall \mathbf{y} \in \Lambda, \langle \mathbf{x}, \mathbf{y} \rangle \in \mathbb{Z}\}$. Any ideal $\mathcal{I}$ of $R$ embeds into a lattice $\sigma(\mathcal{I})$ in $H$, and a lattice $\sigma_H(\mathcal{I})$ in $\mathbb{R}^n$, which we call ideal lattices. For an $R$-module $M \subseteq K^d$, $(\sigma, \dots, \sigma)(M)$ is a lattice in $H^d$ and $(\sigma_H, \dots, \sigma_H)(M)$ is a lattice in $\mathbb{R}^{nd}$, both of which are called module lattices. The positive integer $d$ is the module rank. To ease readability, we simply use $\mathcal{I}$ (resp. $M$) to denote the ideal lattice (resp. module lattice).

## 2.3 Probabilities

For a finite set $S$, we define $|S|$ to be its cardinality, and $U(S)$ to be the uniform probability distribution over $S$. The action of sampling $x \in S$ from a distribution $P$ is denoted by $x \leftarrow P$, whereas the notation $x \sim P$ means that the random variable $x$ is distributed according to $P$. We now define two distances for probability distributions, namely the statistical distance $\Delta$, and the Rényi divergence [48,53] RD. The Rényi divergence was thoroughly studied for its use in cryptography as a powerful alternative for the statistical distance measure by Bai et al. [7]. In this paper, it suffices to use the Rényi divergence of order 2 denoted by $RD_2$.

**Definition 2.1.** Consider two discrete probability distributions $P$ and $Q$ over a countable set $S$. The statistical distance between $P$ and $Q$ is defined by $\Delta(P, Q) = \frac{1}{2} \sum_{x \in S} |P(x) - Q(x)|$. If $\text{Supp}(P) \subseteq \text{Supp}(Q)$, we define the Rényi divergence of order 2 as $RD_2(P \| Q) = \sum_{x \in \text{Supp}(P)} \frac{P(x)^2}{Q(x)}$. The two definitions extend to continuous distributions by replacing the discrete sum with an integral.
The two distances enjoy a probability preservation property and a data pro-
cessing inequality, which are essential in proving our results.

**Lemma 2.7 ([25, Lem. 4.1]).** Let $P, Q$ be two probability distributions such that $\text{Supp}(P) \subseteq \text{Supp}(Q)$ and $E \subseteq \text{Supp}(Q)$ be an arbitrary event. Then, we have $P(E) \le \Delta(P, Q) + Q(E)$, and $P(E)^2 \le \text{RD}_2(P\|Q) \cdot Q(E)$. Further, for any (possibly randomized) function $f$, we define $P^f$ (resp. $Q^f$) the distribution obtained by sampling $x \leftarrow P$ (resp. $Q$) and outputting $f(x)$. Then, it holds that $\Delta(P^f, Q^f) \le \Delta(P, Q)$ and $\text{RD}_2(P^f\|Q^f) \le \text{RD}_2(P\|Q)$.

**Leftover Hash Lemma.** In this work, we use a formulation of the leftover hash lemma (LHL) that is an adaptation of the one by Micciancio [34], which, instead of working with vectors over the finite field $\mathbb{Z}_q$, operates over the principal ideal domain $\mathbb{Z}_q[x]$ for $q$ prime. Given a number field $K = \mathbb{Q}(\zeta)$, where the corresponding ring of integers has the form $R = \mathbb{Z}[\zeta]$, and a prime $q$, then the ideals of $R/qR$ can be characterized via the ideals of $\mathbb{Z}_q[x]$, which is needed in the proof. Further, we provide not only a bound on the statistical distance, but also on the Rényi divergence. For completeness, we give the proof in Appendix B.1.

**Lemma 2.8.** Let $n, k, d, q, \eta$ be positive integer with $q$ prime. Further, let $K = \mathbb{Q}(\zeta)$ be a number field of degree $n$ whose ring of integers is given by $R = \mathbb{Z}[\zeta]$. Then, it holds that

$$
\begin{align*}
\text{RD}_2((\mathbf{C}, \mathbf{C}\mathbf{z})\| (\mathbf{C}, \mathbf{s})) &\le \left(1 + \frac{q^k}{(2\eta + 1)^d}\right)^n \quad \text{and} \\
\Delta((\mathbf{C}, \mathbf{C}\mathbf{z}), (\mathbf{C}, \mathbf{s})) &\le \frac{1}{2} \sqrt{\left(1 + \frac{q^k}{(2\eta + 1)^d}\right)^n - 1},
\end{align*}
$$

where $\mathbf{C} \sim U(R_q^{k \times d})$, $\mathbf{z} \sim U(S_\eta^d)$ and $\mathbf{s} \sim U(R_q^k)$.

**Gaussian measures.** For a positive definite matrix $\boldsymbol{\Sigma} \in \mathbb{R}^n$, a vector $\mathbf{c} \in \mathbb{R}^n$, we define the Gaussian function by $\rho_{\mathbf{c},\sqrt{\boldsymbol{\Sigma}}}(\mathbf{x}) = \exp(-\pi(\mathbf{x} - \mathbf{c})^T \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \mathbf{c}))$ for all $\mathbf{x} \in \mathbb{R}^n$. We then define the continuous Gaussian probability distribution by its density $D_{\mathbf{c},\sqrt{\boldsymbol{\Sigma}}}(\mathbf{x}) = (\det(\boldsymbol{\Sigma}))^{-1/2} \rho_{\mathbf{c},\sqrt{\boldsymbol{\Sigma}}}(\mathbf{x})$. By abuse of notation, we call $\boldsymbol{\Sigma}$ the covariance matrix, even if in theory the covariance matrix of $D_{\mathbf{c},\sqrt{\boldsymbol{\Sigma}}}$ is $\boldsymbol{\Sigma}/(2\pi)$. We extend this definition to the degenerate case, i.e., positive semi-definite, and use the same notation for convenience$^4$. If $\boldsymbol{\Sigma}$ is diagonal with diagonal vector $\mathbf{r}^2 \in (\mathbb{R}^+)^n$, we simply write $D_{\mathbf{c},\mathbf{r}}$, and if $\mathbf{c} = \mathbf{0}$, we omit it.

<footnote>$^4$ In the degenerate case, the probability density function cannot be defined with respect to the Lebesgue measure as $\boldsymbol{\Sigma}$ is not invertible. Standard facts on non-singular Gaussian distributions can however be extended to the degenerate case by using the characteristic function which always exists and equals $\varphi_{\mathbf{x}}(\mathbf{t}) = E_{\mathbf{x}}[\exp(i\mathbf{t}^T\mathbf{x})] = \exp(i\mathbf{c}^T\mathbf{t} - \pi\mathbf{t}^T\boldsymbol{\Sigma}\mathbf{t})$. In particular, one can easily show that the sum of two independent (potentially degenerate) Gaussians of covariance $\boldsymbol{\Sigma}_1, \boldsymbol{\Sigma}_2$ is a (potentially degenerate) Gaussian of covariance $\boldsymbol{\Sigma}_1 + \boldsymbol{\Sigma}_2$, as needed in this paper. We also</footnote>
When $\Sigma = \alpha^2 \mathbf{I}_n$, we simplify further to $D_{c,\alpha}$. We also use $\Psi_{\le \alpha}$ to denote the set of Gaussian distributions $D_r$ with $\|\mathbf{r}\|_{\infty} \le \alpha$.

We then define the discrete Gaussian distribution by conditioning $\mathbf{x}$ to be in a lattice coset $\Lambda + \mathbf{v}$ for $\mathbf{v} \in \mathbb{R}^n$, i.e., $D_{\Lambda+\mathbf{v},c,\sqrt{\Sigma}}(\mathbf{x}) = D_{c,\sqrt{\Sigma}}(\mathbf{x})/D_{c,\sqrt{\Sigma}}(\Lambda+\mathbf{v})$ for all $\mathbf{x} \in \Lambda+\mathbf{v}$, and where $D_{c,\sqrt{\Sigma}}(\Lambda+\mathbf{v}) = \sum_{\mathbf{y} \in \Lambda+\mathbf{v}} D_{c,\sqrt{\Sigma}}(\mathbf{y})$.

**Definition 2.2 (Sub-Gaussian Distribution).** Let $n$ be a positive integer, and $\mathbf{x}$ a (discrete or continuous) random vector over $\mathbb{R}^n$. We say that $\mathbf{x}$ is sub-Gaussian with sub-Gaussian moment $\alpha$, if for all unit vector $\mathbf{u} \in \mathbb{R}^n$, and all $t \in \mathbb{R}$, we have $\mathbb{E}[\exp(2\pi t\langle\mathbf{x},\mathbf{u}\rangle)] \le e^{\pi\alpha^2t^2}$.

A standard calculation shows that the discrete Gaussian distribution $D_{\Lambda,\alpha}$ is sub-Gaussian with sub-Gaussian moment $\alpha$ [37, Lem. 2.8], for any lattice $\Lambda$ and $\alpha > 0$. In particular, we have the following spectral bound on a discrete Gaussian matrix. The result is stated in [37, Lem. 2.9] and is derived from the works of Vershynin [54] on the non-asymptotic random matrix theory.

**Lemma 2.9 ([37, Lem. 2.9]).** Let $\ell, k$ be positive integers, and $\alpha > 0$. Let $\Lambda$ be a lattice of rank $\ell$. Then, there exists a universal constant $C > 0$ such that for any $t \ge 0$, it holds $\mathbb{P}_{\mathbf{Y} \sim D_{\Lambda,\alpha}^k}[\|\mathbf{Y}\|_2 > C\alpha(\sqrt{\ell} + \sqrt{k} + t)] \le 2e^{-\pi t^2}$. Empirically, $C \approx 1/\sqrt{2\pi}$.

The smoothing parameter of a lattice $\Lambda$ denoted by $\eta_{\varepsilon}(\Lambda)$ for some $\varepsilon > 0$, introduced in [39], is the smallest $\alpha > 0$ such that $\rho_{1/\alpha}(\Lambda^*) \le 1+\varepsilon$. It represents the smallest Gaussian parameter $\alpha > 0$ such that the discrete Gaussian $D_{\Lambda,c,\alpha}$ behaves like a continuous Gaussian distribution. We now give a few results related to discrete Gaussian distributions that we need in this paper. The first is due to Micciancio and Regev [39] and shows that above the smoothing parameter, a continuous Gaussian coset is statistically close to uniform.

**Lemma 2.10 ([39, Lem. 4.1]).** Let $\Lambda$ be lattice of rank $n$, $\varepsilon > 0$, and $\alpha \ge \eta_{\varepsilon}(\Lambda)$. Then the distribution of the coset $\mathbf{e}+\Lambda$, where $\mathbf{e} \sim D_{\alpha}$, is within statistical distance $\varepsilon/2$ of the uniform distribution over the cosets of $\Lambda$.

We also need the following result on the sum of convoluted Gaussian distributions. Note that the distribution of $\mathbf{y}$ depends on $\mathbf{x}$.

**Lemma 2.11 ([17, Lem. 2.10] & [43, Thm. 3.1]).** Let $\Lambda$ be lattice of rank $n$. Let $\varepsilon \in (0,1/2]$, and $\alpha, \beta > 0$ be such that $\alpha \ge \eta_{\varepsilon}(\Lambda)$. Then the distribution of $\mathbf{x}+\mathbf{y}$, obtained by first sampling $\mathbf{x}$ from $D_{\beta}$, and then $\mathbf{y}$ sampled from $D_{\Lambda-\mathbf{x},\alpha}$, is within statistical distance $8\varepsilon$ of $D_{\Lambda,\sqrt{\alpha^2+\beta^2}}$.

Finally, we need the Rényi divergence between two shifted discrete Gaussians.

<footnote>note that one can still define a density, but with respect to a degenerate measure as $D_{c,\sqrt{\Sigma}}(\mathbf{x}) = (\det^+(\Sigma))^{-1/2} \exp(-\pi(\mathbf{x} - \mathbf{c})^T\Sigma^{-1}(\mathbf{x} - \mathbf{c}))$, where $\Sigma^+$ is the Moore-Penrose pseudo-inverse, and $\det^+$ the pseudo-determinant.</footnote>
**Lemma 2.12 (Adapted from [25, Lem. 4.2]).** Let $\Lambda$ be lattice of rank $n$, $\varepsilon \in (0, 1)$, $\alpha \ge \eta_{\varepsilon}(\Lambda)$, and $\mathbf{c}$ a vector of $\mathbb{R}^n$. Then,

$$ \mathrm{RD}_2(\mathcal{D}_{\Lambda, c, \alpha} \| \mathcal{D}_{\Lambda, \alpha}) \le \left( \frac{1 + \varepsilon}{1 - \varepsilon} \right)^2 \exp \left( \frac{2\pi \|\mathbf{c}\|_2^2}{\alpha^2} \right). $$

**Gaussians over number fields.** In this section we define Gaussian distributions over $R$-modules $M \subseteq K_{\mathbb{R}}^d$, where $K = \mathbb{Q}(\zeta)$ is a number field, $R$ its ring of integers, and $K_{\mathbb{R}} = K \otimes_{\mathbb{Q}} \mathbb{R}$. We need to consider the field tensor product $K_{\mathbb{R}}$ as the canonical embedding is an isomorphism between $K_{\mathbb{R}}$ and $H$ but not between $R$ and $H$, nor $K$ and $H$. Gaussian distributions over $K_{\mathbb{R}}$ have been introduced alongside the R-LWE problem in [30], and then generalized and used in most papers dealing with structured variants of LWE. We define general Gaussian distributions over $K_{\mathbb{R}}^d$ through their embedding to $\mathbb{R}^{nd}$, namely sampling $\mathbf{x}^{(H)} \in \mathbb{R}^{nd}$ according to $D_{\sigma_H(c), \sqrt{\Sigma}}$, for some $\mathbf{c} \in K_{\mathbb{R}}^d$ and positive semi-definite matrix $\Sigma$ in $\mathbb{R}^{nd \times nd}$, and then mapping it back to $K_{\mathbb{R}}^d$ by $\mathbf{x} = \sigma_H^{-1}(\mathbf{x}^{(H)})$. To ease readability, we denote the described distribution of $\mathbf{x} \in K_{\mathbb{R}}^d$ by $D_{c, \sqrt{\Sigma}}$.

We first provide an upper bound on the spectral norm of a discrete Gaussian matrix, once embedded via $M_{\sigma_H}(\cdot)$. This combines a bound on the spectral norm of a block matrix from the spectral norm of each block, with a discrete Gaussian tail bound. Although it seems folklore, we weren't able to find a Gaussian tail bound on $\sigma(x)$ in the infinity norm for $x \sim D_{\mathcal{I},s}$. We therefore derive such a bound, which is based on [41, Cor. 5.3] proving that $\|\sigma(x)\|_{\infty} \le s \log_2 n$ with overwhelming probability. The proof can be found in Appendix B.1.

**Lemma 2.13.** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $\mathcal{I}$ be any (fractional) ideal of $R$. Let $m, d$ be positive integers, and $\alpha > 0$. Then, for all $t \ge 0$ it holds that

$$ \mathbb{P}_{\mathbf{N} \sim \mathcal{D}_{\mathcal{I}, \alpha}^{m \times d}} \left[ \| M_{\sigma_H}(\mathbf{N}) \|_2 \ge \sqrt{md} \cdot \alpha t \right] \le 2nmd \cdot e^{-\pi t^2}. $$

Choosing $t = \log_2 n$ gives $\|M_{\sigma_H}(\mathbf{N})\|_2 \le \alpha \log_2(n) \sqrt{md}$ with overwhelming probability if $m, d$ are polynomial in $n$.

In the proof of Lemma 3.3, we also need the distribution of $\mathbf{y} = \mathbf{Ue}$ for an arbitrary matrix $\mathbf{U}$ and a Gaussian vector $\mathbf{e} \in K_{\mathbb{R}}^d$ for which the components are independent of each other. The proof is in Appendix B.1 for completeness.

**Lemma 2.14.** Let $K$ be a number field of degree $n$, and $m, d$ positive integers. Let $\mathbf{S} \in \mathbb{R}^{nd \times nd}$ be a positive semi-definite matrix, and $\mathbf{U} \in K_{\mathbb{R}}^{m \times d}$. We denote $\Sigma = M_{\sigma_H}(\mathbf{U})\mathbf{S}M_{\sigma_H}(\mathbf{U})^T \in \mathbb{R}^{nm \times nm}$, Then, the distribution of $\mathbf{y} = \mathbf{Ue}$, where $\mathbf{e} \in K_{\mathbb{R}}^d$ is distributed according to $D_{\sqrt{\Sigma}}$, is exactly $D_{\sqrt{\Sigma}}$ over $K_{\mathbb{R}}^m$.

We also need another lemma related to the inner product of $K_{\mathbb{R}}^d$ (which results in an element of $K_{\mathbb{R}}$) between a discrete Gaussian vector and an arbitrary one. In particular, we use Lemma 2.15 in the proof of Lemma 3.5 in order to decompose a
Gaussian noise into an inner product. It generalizes [47, Cor. 3.10] to the module case. A specific instance is proven in the proof of [24, Lem. 4.15], which is later mentioned (without proof) in [50, Lem. 5.5]. We defer the proof in Appendix B.1.

**Lemma 2.15 (Adapted from [47, Cor. 3.10]).** Let $M \subseteq K^d$ be an $R$-module (yielding a module lattice), let $\mathbf{u}, \mathbf{z} \in K^d$ be fixed, and let $\beta, \gamma > 0$. Assume that $(1/\beta^2 + \|\mathbf{z}\|_{2,\infty}^2/\gamma^2)^{-1/2} \ge \eta_\varepsilon(M)$ for some $\varepsilon \in (0, 1/2)$. Then the distribution of $\langle \mathbf{z}, \mathbf{v} \rangle + e$ where $\mathbf{v}$ is sampled from $D_{M+\mathbf{u},\beta}$ and $e \in K_\mathbb{R}$ is sampled from $D_\gamma$, is within statistical distance at most $2\varepsilon$ from the elliptical Gaussian $D_\mathbf{r}$ over $K_\mathbb{R}$, where $r_j = \sqrt{\beta^2 \sum_{i \in [d]} |\sigma_j(z_i)|^2 + \gamma^2}$ for $j \in [n]$.

## 2.4 Function Families

In Section 4, we prove that certain families of functions are hard to invert, or whose output are hard to distinguish from uniformly random ones. As such, we give in this section the notion of function families as well as the standard security properties that we desire from them. A function family $\mathcal{F}$ over a set of functions $F$ is a probability distribution over $F$, where each function of $F$ has domain $X$ and range $Y$. In this paper, we only deal with functions that have an unambiguous and public description in some specified format. In our case, they can be represented by a public matrix $\mathbf{A}$. Hence, when we say that an adversary is given a function $f$ as input when it is given its public representation.

**Definition 2.3.** Let $X, Y$ be two sets, and $F$ a set of functions from $X$ to $Y$. Let $\mathcal{F}, \mathcal{G}$ be two function families over $F$. Let $\mathcal{X}$ be a probability distribution over $X$, and $\varepsilon \in (0, 1)$.

**Indistinguishability.** $\mathcal{F}$ and $\mathcal{G}$ are $\varepsilon$-indistinguishable if for all PPT algorithm $\mathcal{A}$, it holds $|\mathbb{P}_{f \sim \mathcal{F}}[\mathcal{A}(f) = 1] - \mathbb{P}_{g \sim \mathcal{G}}[\mathcal{A}(g) = 1]| \le \varepsilon$.

**Pseudorandomness.** $(\mathcal{F}, \mathcal{X})$ is $\varepsilon$-pseudorandom if for all PPT algorithm $\mathcal{A}$, it holds $|\mathbb{P}_{(f,x) \sim \mathcal{F} \times \mathcal{X}}[\mathcal{A}(f, f(x)) = 1] - \mathbb{P}_{(f,y) \sim \mathcal{F} \times U(Y)}[\mathcal{A}(f, y) = 1]| \le \varepsilon$.

**Second preimage resistance.** $(\mathcal{F}, \mathcal{X})$ is $\varepsilon$-second preimage resistant if for all PPT algorithm $\mathcal{A}$, it holds $\mathbb{P}_{(f,x) \sim \mathcal{F} \times \mathcal{X}}[x \ne x' \wedge f(x) = f(x')] \le \varepsilon$.
$x' \leftarrow \mathcal{A}(f,x)$

**Uninvertibility.** $(\mathcal{F}, \mathcal{X})$ is $\varepsilon$-uninvertible if for all PPT algorithm $\mathcal{A}$, it holds that $\mathbb{P}_{(f,x) \sim \mathcal{F} \times \mathcal{X}}[\mathcal{A}(f, f(x)) = x] \le \varepsilon$.

**One-wayness.** $(\mathcal{F}, \mathcal{X})$ is $\varepsilon$-one-way if for all PPT algorithm $\mathcal{A}$, it holds that $\mathbb{P}_{(f,x) \sim \mathcal{F} \times \mathcal{X}}[f(\mathcal{A}(f, f(x))) = f(x)] \le \varepsilon$.

If $\varepsilon$ is negligible, we omit it. We then give sufficient conditions to ensure some of these security properties.

**Lemma 2.16 ([38, Lem. 2.2]).** Let $\mathcal{F}$ be a family of functions computable in polynomial time. Let $\mathcal{X}$ be a distribution on $X$. If $(\mathcal{F}, \mathcal{X})$ is $\varepsilon$-uninvertible and $\varepsilon$-second preimage resistant, then it is also $(\varepsilon + \varepsilon')$-one-way.
**Lemma 2.17 ([38, Lem. 2.4]).** Let $\mathcal{F}$ be a function family with finite domain $X$. For $\varepsilon = \mathbb{E}_{f \sim \mathcal{F}}[|f(X)|]/|X|$, it holds that $(\mathcal{F}, U(X))$ is $\varepsilon$-uninvertible, even against unbounded adversaries.

**Lemma 2.18 ([38, Lem. 2.5]).** Let $\mathcal{F}$ be a function family with domain $X$ and range $Y$, and $\mathcal{G}$ be an efficiently sampleable family of efficiently computable functions with domain $X' \supseteq Y$. Let $\mathcal{X}$ be a distribution on $X$. If $(\mathcal{F}, \mathcal{X})$ is uninvertible, then so is $(\mathcal{G} \circ \mathcal{F}, \mathcal{X})$.

We now recall the notion of *lossy function family* from [38]. Note that by an indistinguishability argument, if $(\mathcal{F}, \mathcal{G}, \mathcal{X})$ is a lossy function family, then so is $(\mathcal{G}, \mathcal{F}, \mathcal{X})$. In particular, by Lemma 2.16, both $(\mathcal{F}, \mathcal{X})$ and $(\mathcal{G}, \mathcal{X})$ are one-way.

**Definition 2.4.** Let $X, Y$ be two sets, and $F$ a set of efficiently computable functions from $X$ to $Y$. Let $\mathcal{F}, \mathcal{G}$ be two function families over $F$. Let $\mathcal{X}$ be an efficiently sampleable probability distribution over $X$. Then $(\mathcal{F}, \mathcal{G}, \mathcal{X})$ is a lossy function family if it holds that

- $\mathcal{F}$ and $\mathcal{G}$ are indistinguishable;

- $(\mathcal{F}, \mathcal{X})$ is uninvertible;

- $(\mathcal{G}, \mathcal{X})$ is second preimage resistant.

## 2.5 Module Learning With Errors

The module variant of LWE was first defined by Brakerski et al. [16] and thoroughly studied by Langlois and Stehlé [24]. As opposed to [24], we decide to use the primal formulation of the problem to match practical uses of the M-LWE assumption. It describes the following problem. Let $K$ be a number field of degree $n$ and $R$ its ring of integers. Further, let $d$ denote the rank and let $\psi$ be a distribution on $K_\mathbb{R}$ and $s \in R_q^d$ be a vector. We also define the torus $T = K_\mathbb{R}/R$. We let $A_{s,\psi}^M$ denote the distribution on $R_q^d \times T$ obtained by sampling a vector $\mathbf{a} \leftarrow U(R_q^d)$, an element $e \leftarrow \psi$ and returning $(\mathbf{a}, q^{-1}\langle\mathbf{a}, \mathbf{s}\rangle + e \bmod R)$.

**Definition 2.5 (Module Learning With Errors).** Let $q, d$ be positive integers with $q \ge 2$. Let $\Psi$ be a family of distributions on $K_\mathbb{R}$. The search version M-SLWE$_{n,d,q,\Psi}$ is as follows: Let $s \in R_q^d$ be secret and $\psi \in \Psi$. Given arbitrarily many samples from $A_{s,\psi}^M$, the goal is to find $s$. Let $\Upsilon$ be a distribution on a family of distributions on $K_\mathbb{R}$. Its decision version M-LWE$_{n,d,q,\Upsilon}$ is as follows: Sample $s \leftarrow U(R_q^d)$ and $\psi \leftarrow \Upsilon$. The goal is to distinguish between arbitrarily many independent samples from $A_{s,\psi}^M$ and the same number of independent samples from $U(R_q^d \times T)$.

To be thorough, we should use the subscript $K$ instead of $n$ since there can be several number fields having the same degree $n$. However, to ease readability and since most of the other parameters are functions of $n$, we use the subscript $n$ and keep the number field implicit. Although our results are mainly theoretical,
we note that throughout the paper $n$ must be larger than a given security pa-
rameter, and the hardness and negligible advantages are thus expressed in terms
of $n$ rather than a proper security parameter. The advantage of an adversary $\mathcal{A}$
against M-SLWE is defined by $\mathrm{Adv}[\mathcal{A}] = \mathbb{P}[\mathcal{A}(A_{s,\psi}^{\mathcal{M}}) = \mathbf{s}]$ and the advantage
against M-LWE by $\mathrm{Adv}[\mathcal{A}] = \left| \mathbb{P}[\mathcal{A}(A_{s,\psi}^{\mathcal{M}}) = 1] - \mathbb{P}[\mathcal{A}(U(\mathrm{Supp}(A_{s,\psi}^{\mathcal{M})))) = 1] \right|$. We
say that the corresponding problems are $\varepsilon$-hard if for any PPT adversary $\mathcal{A}$, it
holds that $\mathrm{Adv}[\mathcal{A}] \le \varepsilon$. We say it is hard if $\varepsilon$ is negligible in $n$.

The M-LWE problem encompasses its preceding variants LWE, correspond-
ing to a field of degree $n = 1$, and R-LWE, corresponding to the module
rank $d = 1$. We describe here the several variants and notations that we consider
in this paper.

**Fixed number of samples.** When using the Rényi divergence as a tool to measure the distance between two probability distributions, we need to fix the number of requested samples a priori. Let $m$ be the number of requested M-LWE samples $(\mathbf{a}_i, q^{-1}\langle\mathbf{a}_i, \mathbf{s}\rangle + e_i \bmod R)$ for $i \in [m]$, then we consider the matrix $\mathbf{A} \in \mathbb{R}_q^{m \times d}$ whose rows are the $\mathbf{a}_i$'s and we set $\mathbf{e} = [e_1, \dots, e_m]^T$. We obtain the representation $(\mathbf{A}, q^{-1}\mathbf{A}\mathbf{s} + \mathbf{e} \bmod R)$. We denote it by $\mathrm{M-LWE}_{n,d,m,q,\mathcal{R}}$.

**Multiple secrets.** Let $k, m$ be positive integers, where $m$ denotes the number of requested samples. In the multiple secrets version, the secret vector $\mathbf{s} \in \mathbb{R}_q^d$ is replaced by a secret matrix $\mathbf{S} \in \mathbb{R}_q^{d \times k}$ and the error vector $\mathbf{e} \sim \psi^m$ by an error matrix $\mathbf{E} \sim \psi^{m \times k}$. There is a simple polynomial-time reduction from M-LWE using a secret vector to M-LWE using a secret matrix for any $k$ polynomially large in $d$ via a hybrid argument, as given for instance in [35, Lem. 2.9]. We denote the corresponding problem by $\mathrm{M-LWE}_{n,d,m,q,\mathcal{R}}^k$.

**Discrete version.** As pointed out by Lyubashevsky et al. [30], sometimes it
can be more convenient to work with a discrete variant, where the second
component $b$ of each sample $(\mathbf{a}, b)$ is taken from a finite set, and not from
the continuous torus $\mathbb{T}$. Indeed, for the case of M-LWE, if the rounding func-
tion $\lfloor \cdot \rfloor: K_{\mathbb{R}} \to \mathbb{R}$ is chosen in a suitable way, see e.g. [31, Sec. 2.6], then every
sample $(\mathbf{a}, b = q^{-1}\langle\mathbf{a}, \mathbf{s}\rangle + e \bmod R) \in \mathbb{R}_q^d \times \mathbb{T}$ from $A_{\mathbf{s},\psi}^{\mathcal{M}}$ can be transformed
to $(\mathbf{a}, \lfloor q \cdot b \rfloor \bmod qR) = (\mathbf{a}, \langle\mathbf{a}, \mathbf{s}\rangle + \lfloor q \cdot e \rfloor \bmod qR) \in \mathbb{R}_q^d \times \mathbb{R}_q$. We use the latter
representation in Section 3.1 and 4.

**Bounded secret.** Another possibility is to choose a *small* secret, i.e., whose coefficients are bounded by $\eta \ll (q-1)/2$. Note that the bound $\eta$ is with regard to the coefficient embedding $\tau$, meaning that the secret is in $S_{\eta}^d$. We denote the corresponding problem by $\eta$-M-LWE$_{n,d,q,\tau}$.

**Worst-case error.** We also define the problem with worst-case error distribu-
tion when the error distribution is $D_r \in \Psi_{\le \alpha}$ for some possibly unknown (and
possibly secret-dependent) $\mathbf{r} \in (\mathbb{R}^+)^n$. We then denote it by $\mathrm{M-LWE}_{n,k,m,q,\Psi_{\le \alpha}}$.
We reduce to this variant in Section 3.2. Note that when the number of samples is
fixed, one can use the reduction of [45, Lem. 7.2], generalizing [30, Lem. 5.16], to
go to an average-case error with spherical Gaussian $D_{\xi}$. The reduction increases
the noise from $\alpha$ to $\xi = \alpha(nm/\log_2(nm))^{1/4}$. The result is stated for R-LWE
but naturally extends to the module setting, and we therefore do not consider
it new and do not include this extra step in the overall reduction.

**M-LWE and M-ISIS function families.** We now introduce two function families that are relevant for Section 4.

**Definition 2.6.** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $d, q, m$ be positive integers, and $X \subseteq \mathbb{R}^m$. The M-ISIS$(n, d, m, q, X)$ function family is the distribution obtained by sampling a matrix $\mathbf{A} \in \mathbb{R}_q^{m \times d}$ uniformly at random, and outputting $f_{\mathbf{A}}$ defined by $f_{\mathbf{A}}(\mathbf{x}) = \mathbf{A}^T \mathbf{x} \bmod qR$ for all $\mathbf{x} \in X$. The M-LWE$(n, d, m, q, X)$ function family is the distribution obtained by sampling $\mathbf{A} \in \mathbb{R}_q^{m \times d}$ uniformly at random and outputting $g_{\mathbf{A}}$ defined by $g_{\mathbf{A}}(\mathbf{s}, \mathbf{e}) = \mathbf{A}\mathbf{s} + \mathbf{e} \bmod qR$ for all $(\mathbf{s}, \mathbf{e}) \in \mathbb{R}_q^d \times X$.

We only define them with discrete inputs (i.e., discrete error for M-LWE) because they are only needed in Section 4 which studies errors in $S_{\eta}^m$. When using the M-LWE function family in Section 4, we assume implicitly that the distribution on the first input $\mathbf{s}$ is always $U(\mathbb{R}_q^d)$ and omit it from the notations.

In most LWE-based schemes, the secret key is $(\mathbf{s}, \mathbf{e})$ and the public key
is $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e})$. Note that it is therefore important to prove one-wayness
and not just uninvertibility because an adversary breaking one-wayness could
compute a different secret key for the same public key, which would allow them
to decrypt messages, or forge signatures. It turns out that if the parameters
are chosen appropriately so that the function is second preimage resistant, the
uninvertibility is then equivalent to the one-wayness. Their uninvertibility or one-
wayness therefore captures the hardness of the corresponding search problem,
while their pseudorandomness captures the hardness of the decision problem.
We denote the problem corresponding to the family M-ISIS$(n, d, m, q, X)$ by
search/decision M-ISIS$_{d,m}$.

**3 Hardness of η-M-LWE**

In this section, we prove the hardness of the $\eta$-bounded secret version of M-LWE, if the module rank is (super-)logarithmic in the degree $n$ of the underlying number field. It improves upon our previously published works of [12,13] which dealt with secret with binary coefficients. To the best of our knowledge, [12] was the first result on the hardness of a structured variant of LWE with small uniform secret. We propose two independent proofs that achieve different results. The first one in Section 3.1 proves the hardness of the search version of $\eta$-M-LWE, using a more direct proof. The second one in Section 3.2 is more involved but allows for proving the hardness of the decision version of $\eta$-M-LWE as well as (slightly) improving the noise parameter.

**3.1 Computational Hardness Using the Rényi Divergence**

We start by proving the hardness of $\eta$-M-SLWE with a quite direct reduction.
To facilitate the understanding, we illustrate the high level idea of the proof in
Figure 3.1. Given an algorithm for instance ($\mathbf{A}$, $\mathbf{Az} + \mathbf{e}$) of $\eta$-M-SLWE, our goal is to transform it into an algorithm for a related instance of M-SLWE defined by ($\mathbf{B}$, $\mathbf{Bs} + \mathbf{e'}$). Note that the secret $\mathbf{z}$ is in $S_{\eta}^d$, while the secret $\mathbf{s}$ is in $R_q^k$. At the core of the proof lies a lossy argument, where the public matrix $\mathbf{A}$ is replaced by a lossy matrix $\mathbf{BC} + \mathbf{N}$, which corresponds to the second part of some multiple-secrets M-LWE sample. Note that the rank of the matrix $\mathbf{B}$ is smaller than the one of $\mathbf{A}$, motivating the description *lossy*. Here, we can see that this argument does not work for R-LWE (which corresponds to M-LWE with rank 1) as it is not possible to replace the public matrix consisting of one column by a matrix of smaller rank. To argue that an adversary cannot distinguish between the two cases, we need to assume the hardness of the *decision* M-LWE problem as well. In a second step, the term $\mathbf{Nz} + \mathbf{e}$ is replaced by the new noise $\mathbf{e'}$, where the R\'enyi divergence between both expressions can be bounded by a constant using properties of the R\'enyi divergence of Gaussian distributions. Finally, the product $\mathbf{Cz}$ is replaced by the uniform secret $\mathbf{s}$, where the R\'enyi divergence between both elements can be bounded by a constant using Lemma 2.8. The use of the leftover hash lemma is also the reason why our reduction only works for module ranks larger than $\log_2 q + \Omega(\log_2 n)$. Informally speaking, it requires the ratio between the number of rows of $\mathbf{C}$ and its number of columns to be logarithmic in order to bound the R\'enyi divergence by a constant. We end up with some standard M-LWE instance, which is hard to solve due to our hardness assumption.

<figure><img src="image_3.png" /><figcaption>Fig. 3.1. Summary of the proof of Theorem 3.1</figcaption></figure>

This consists of a reduction from M-SLWE and M-LWE with rank $k$ to $\eta$-M-SLWE with rank $d \ge k \log_2(q)/\log_2(2\eta+1) + \Omega(\log_2(n)/\log_2(2\eta+1))$. It follows the original proof structure of Goldwasser et al. [21], but achieves better
parameters by using the Rényi divergence, while being as direct and short as the original proof. The improvement on the noise rate $\beta/\alpha$ compared to [21] comes from the fact that the Rényi divergence only needs to be constant for the reduction to work, and not necessarily negligibly close to 1 (compared to negligibly close to 0 for the statistical distance). However, using the Rényi divergence as a measure of distribution closeness requires to move to the search version of M-LWE. Overall, this reduction is restricted to number fields for which the ring of integers is $R = \mathbb{Z}[\zeta]$. Furthermore, the norm of the Vandermonde matrix $\|\mathbf{V}\|_2$ is better understood in cyclotomic fields. We study the M-LWE problem in its discrete version, as presented in Section 2.5.

**Theorem 3.1.** Let $K = \mathbb{Q}(\zeta)$ be a number field of degree $n$ such that its ring of integers is $R = \mathbb{Z}[\zeta]$. Let $k, d, m, \eta$ and $q$ be positive integers with $q$ prime, $m, d = \text{poly}(n)$ and $d \log_2(2\eta+1) \ge k \cdot \log_2 q + \Omega(\log_2 n)$. Further, let $\alpha$ and $\beta$ be positive such that $\beta \ge \alpha \cdot d\sqrt{m} \cdot \|\mathbf{V}\|_2 \eta\sqrt{n} \log_2(n)$, and $\beta q \ge \eta_\epsilon(R^m)$ for some $\epsilon \in (0, 1/2)$. There is a PPT reduction from M-SLWE$_{n,k,m,q,\mathcal{D}_{R,\beta q}}$ and M-LWE$_{n,k,m,q,\mathcal{D}_{R,\alpha q}}^d$ to $\eta$-M-SLWE$_{n,d,m,q,\mathcal{D}_{R,\beta q}}$.

The degree $n$ of $K$, the number of samples $m$ and the modulus $q$ are preserved. The reduction increases the rank of the module from $k$ to $k \log_2 q / \log_2(2\eta + 1) + \Omega(\log_2 n / \log_2(2\eta + 1))$ and the Gaussian width from $\alpha q$ to $\alpha q \cdot d\sqrt{m} \cdot \|\mathbf{V}\|_2 \eta\sqrt{n} \log_2(n)$. In power-of-two cyclotomic fields, $\|\mathbf{V}\|_2 = \sqrt{n}$. In the $p^k$-th cyclotomic field with $p$ an odd prime, we have $\|\mathbf{V}\|_2 = \sqrt{p^k}$. In general cyclotomic fields, we have $\|\mathbf{V}\|_2 \le \|\mathbf{V}\|_F = (\sum_{i,j} |\alpha_i^{j-1}|^2)^{1/2} \le n$ (as $\alpha_i$ is a root of unity). Also, M-LWE$_{n,k,m,q,\mathcal{D}_{R,\alpha q}}$ trivially reduces to M-SLWE$_{n,k,m,q,\mathcal{D}_{R,\beta q}}$, as $\gamma q = q\sqrt{\beta^2 - \alpha^2}$ is above $\eta_\epsilon(R)$ for a negligible $\epsilon$, and sufficiently large so that $\mathcal{D}_{R,\gamma q}$ is efficiently sampleable.

*Proof.* Fix any $n, k, d, m, q, \eta, \alpha, \beta$ and $\epsilon$ as in the statement of the theorem. Given an $\eta$-M-SLWE$_{n,d,m,q,\mathcal{D}_{R,\beta q}}$ sample $(\mathbf{A}, \mathbf{A} \cdot \mathbf{z} + \mathbf{e} \bmod qR) \in \mathbb{R}_q^{m \times d} \times \mathbb{R}_q^m$, with $\mathbf{z} \leftarrow U(S_\eta^d)$ and $\mathbf{e} \leftarrow \mathcal{D}_{R^m, \beta q}$, the search problem asks to find $\mathbf{z}$ and $\mathbf{e}$. In order to prove the statement, we define different hybrid distributions:

- $H_0$: Output $(\mathbf{A}, \mathbf{Az} + \mathbf{e} \bmod qR)$, as in $\eta$-M-SLWE$_{n,d,m,q,\mathcal{D}_{R,\beta q}}$;

- $H_1$: Output $(\mathbf{A}' = \mathbf{BC} + \mathbf{N} \bmod qR, \mathbf{A}'\mathbf{z} + \mathbf{e} \bmod qR)$, where $\mathbf{B} \leftarrow U(\mathbb{R}_q^{m \times k})$, $\mathbf{C} \leftarrow U(\mathbb{R}_q^{k \times d})$, and $\mathbf{N} \leftarrow \mathcal{D}_{R,\alpha q}^{m \times d}$ and $\mathbf{z}, \mathbf{e}$ as in $H_0$;

- $H_2$: Output $(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{BCz} + \mathbf{Nz} + \mathbf{e} \bmod qR)$, where $\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{z}, \mathbf{e}$ as in $H_1$;

- $H_3$: If $\|M_{\sigma_H}(\mathbf{N})\|_2 \le \alpha q\sqrt{md} \log_2 n$, output $(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{BCz} + \mathbf{Nz} + \mathbf{e} \bmod qR)$, where $\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{z}, \mathbf{e}$ as in $H_2$;

- $H_4$: If $\|M_{\sigma_H}(\mathbf{N})\|_2 \le \alpha q\sqrt{md} \log_2 n$, output $(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{BCz} + \mathbf{e}' \bmod qR)$, where $\mathbf{e}' \leftarrow \mathcal{D}_{R,\beta q}^m$ and $\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{z}$ as in $H_3$;

- $H_5$: If $\|M_{\sigma_H}(\mathbf{N})\|_2 \le \alpha q\sqrt{md} \log_2 n$, output $(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{Bs} + \mathbf{e}' \bmod qR)$, where $\mathbf{s} \leftarrow U(\mathbb{R}_q^k)$ and $\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{e}'$ as in $H_4$.

For $i \in \{0, \dots, 5\}$, we denote by $P_i$ the problem of finding the secret $\mathbf{z}$ (resp. $\mathbf{s}$ in $H_5$), given a sample of the distribution $H_i$. Recall that problem $P_i$ is hard if for any PPT attacker $\mathcal{A}$ the advantage of solving $P_i$ is negligible, thus $\text{Adv}_{P_i}[\mathcal{A}] =$
$\mathbb{P}_{X \sim H_i}[\mathcal{A}(X) = \mathbf{z}] \leq n^{-\omega(1)}$, where $n$ is the degree of $K$. The overall idea is to show that if $P_5$ is hard, then $P_0$ is hard as well.

**From $P_0$ to $P_1$:** Assuming the hardness of M-LWE$^d_{n,k,m,q,\mathcal{D}_{R,\alpha q}}$, the distributions $H_0$ and $H_1$ are computationally indistinguishable. We note that the hardness of the latter can be obtained by a hybrid argument, e.g., Lemma 3.4, from that of M-LWE$_{n,k,m,q,\mathcal{D}_{R,\alpha q}}$ with a reduction loss factor of $d$ in the advantage. Thus, if M-LWE$_{n,k,m,q,\mathcal{D}_{R,\alpha q}}$ is Adv$_{M-LWE}$-hard, it holds

$$ \mathrm{Adv}_{P_0}[\mathcal{A}] \leq \mathrm{Adv}_{P_1}[\mathcal{A}] + d \cdot \mathrm{Adv}_{\mathrm{M-LWE}}, $$

where $d$ is the number of secret vectors, i.e., the columns of the matrix $C$.

**From $P_1$ to $P_2$:** Since more information is given in distribution $H_2$ than in distribution $H_1$, the problem $P_1$ is harder than $P_2$. From $P_2$ onwards the adversary is given more elements (namely $\mathbf{B}, \mathbf{C}, \mathbf{N}$ instead of $\mathbf{A}'$) but can simply reconstruct the M-LWE matrix from these elements. Hence, we have

$$ \mathrm{Adv}_{P_1}[\mathcal{A}] \leq \mathrm{Adv}_{P_2}[\mathcal{A}]. $$

**From $P_2$ to $P_3$:** Note that conditioned on $\|M_{\sigma_H}(\mathbf{N})\|_2 \leq \alpha q \sqrt{md} \log_2 n$, the two distributions are identical. Yet, Lemma 2.13 for $\mathcal{I} = R$ yields the spectral bound with overwhelming probability. Hence, we have $\Delta(H_2, H_3) \leq \mathbb{P}[\|M_{\sigma_H}(\mathbf{N})\|_2 > \alpha q \sqrt{md} \log_2 n] =: p_{\mathrm{spectral}} \leq n^{-\omega(1)}$, resulting in

$$ \mathrm{Adv}_{P_2}[\mathcal{A}] \leq \mathrm{Adv}_{P_3}[\mathcal{A}] + p_{\mathrm{spectral}} $$

**From $P_3$ to $P_4$:** By the probability preservation property of the Rényi divergence (Lemma 2.7), we have

$$ \mathrm{Adv}_{P_3}[\mathcal{A}]^2 \leq \mathrm{Adv}_{P_4}[\mathcal{A}] \cdot \mathrm{RD}_2(H_3 \| H_4). $$

We first explain how to bound the Rényi divergence between $\mathbf{N}\mathbf{z} + \mathbf{e}$ and $\mathbf{e}'$ for a fixed $(\mathbf{N}, \mathbf{z})$. First note that $\mathbf{N}\mathbf{z} + \mathbf{e}$ follows the distribution $\mathcal{D}_{R^m + \mathbf{N}\mathbf{z}, \mathbf{N}\mathbf{z}, \beta q}$. Since we have $\mathbf{N}\mathbf{z} \in \mathbb{R}^m$, this distribution is exactly $\mathcal{D}_{R^m, \mathbf{N}\mathbf{z}, \beta q}$. Then, as $\sigma$ and $\sigma_H$ only differ by the unitary transformation $U_H$, we have that $\|\sigma_H(\mathbf{z})\|_2 = \|\sigma(\mathbf{z})\|_2 \leq \|\mathbf{V}\|_2 \|\tau(\mathbf{z})\|_2 \leq \|\mathbf{V}\|_2 \cdot \eta \sqrt{nd}$, as $\mathbf{z} \in S_d^d$. Finally, because of our conditioning, we have $\|M_{\sigma_H}(\mathbf{N})\|_2 \leq \alpha q \log_2 n \sqrt{md}$. It then holds that $\|\sigma_H(\mathbf{N}\mathbf{z})\|_2 = \|M_{\sigma_H}(\mathbf{N})\sigma_H(\mathbf{z})\|_2 \leq \|M_{\sigma_H}(\mathbf{N})\|_2 \|\sigma_H(\mathbf{z})\|_2 \leq \alpha q d \|\mathbf{V}\|_2 \eta \sqrt{nm} \log_2(n)$. Then, using that $\beta q \geq \eta_\epsilon(R^m)$, Lemma 2.12 yields

$$ \mathrm{RD}_2(\mathcal{D}_{R^m, \mathbf{N}\mathbf{z}, \beta q} \| \mathcal{D}_{R^m, \beta q}) \leq \left( \frac{1 + \varepsilon}{1 - \varepsilon} \right)^2 \cdot \exp \left( \frac{2\pi \|\sigma_H(\mathbf{N}\mathbf{z})\|_2^2}{(\beta q)^2} \right). $$

However, it holds that $\exp(2\pi \|\sigma_H(\mathbf{N}\tilde{\mathbf{z}})\|_2^2/(\beta q)^2) \leq \exp(2\pi)$ because of how we chose $\beta$ with respect to $\alpha$. Without loss of generality, assume $\varepsilon < \frac{1}{2}$ resulting in $\mathrm{RD}_2(\mathcal{D}_{R^m, \mathbf{N}\mathbf{z}, \beta q} \| \mathcal{D}_{R^m, \beta q}) = O(1)$.
Next, the data processing inequality of Lemma 2.7 gives $RD_2(H_3\|H_4) \le RD_2((\mathbf{N},\mathbf{z},\mathbf{e}+\mathbf{N}\mathbf{z})\|(\mathbf{N},\mathbf{z},\mathbf{e}'))$. We now bound this divergence by a constant using the previous calculation.

$$
\begin{align*}
RD_2((\mathbf{N}, \mathbf{z}, \mathbf{e} + \mathbf{N}\mathbf{z})\|(\mathbf{N}, \mathbf{z}, \mathbf{e}')) &= \sum_{(\bar{\mathbf{N}}, \bar{\mathbf{z}}, \bar{\mathbf{e}})} \frac{\mathbb{P}[(\mathbf{N}, \mathbf{z}, \mathbf{e} + \mathbf{N}\mathbf{z}) = (\bar{\mathbf{N}}, \bar{\mathbf{z}}, \bar{\mathbf{e}})]^2}{\mathbb{P}[(\bar{\mathbf{N}}, \mathbf{z}, \mathbf{e}') = (\bar{\mathbf{N}}, \bar{\mathbf{z}}, \bar{\mathbf{e}})]} \\
&= \sum_{(\bar{\mathbf{N}}, \bar{\mathbf{z}}, \bar{\mathbf{e}})} \frac{\mathbb{P}[(\mathbf{N}, \mathbf{z}) = (\bar{\mathbf{N}}, \bar{\mathbf{z}})]^2 \mathbb{P}[\mathbf{e} + \bar{\mathbf{N}}\bar{\mathbf{z}} = \bar{\mathbf{e}}]^2}{\mathbb{P}[(\mathbf{N}, \mathbf{z}) = (\bar{\mathbf{N}}, \bar{\mathbf{z}})] \mathbb{P}[\mathbf{e}' = \bar{\mathbf{e}}]} \\
&= \sum_{(\bar{\mathbf{N}}, \bar{\mathbf{z}})} \mathbb{P}[(\mathbf{N}, \mathbf{z}) = (\bar{\mathbf{N}}, \bar{\mathbf{z}})] RD_2(\mathbf{e} + \bar{\mathbf{N}}\bar{\mathbf{z}}\|\mathbf{e}') \\
&\le \left(\frac{1+\varepsilon}{1-\varepsilon}\right)^2 \cdot e^{2\pi} \sum_{(\bar{\mathbf{N}}, \bar{\mathbf{z}})} \mathbb{P}[(\mathbf{N}, \mathbf{z}) = (\bar{\mathbf{N}}, \bar{\mathbf{z}})] \\
&= \left(\frac{1+\varepsilon}{1-\varepsilon}\right)^2 \cdot e^{2\pi} \\
&= O(1),
\end{align*}
$$

as desired.

*From P₄ to P₅:* By the probability preservation property and data processing inequality of the Rényi divergence (Lemma 2.7), we have

$$
\begin{align*}
\mathrm{Adv}_{P_4}[\mathcal{A}]^2 &= \mathbb{P}_{(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{b}) \sim H_4}[\mathcal{A}(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{b}) = \mathbf{z}]^2 \\
&\leq \mathbb{P}_{(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{b}) \sim H_4}[\mathcal{A}(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{b}) = \mathbf{C}\mathbf{z}]^2 \\
&\leq \mathbb{P}_{(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{b}) \sim H_5}[\mathcal{A}(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{b}) = \mathbf{s}] \cdot RD_2(H_4 \| H_5) \\
&\leq \mathrm{Adv}_{P_5}[\mathcal{A}] \cdot RD_2((\mathbf{C}, \mathbf{C}\mathbf{z}) \|(\mathbf{C}, \mathbf{s})).
\end{align*}
$$

The first inequality follows from the fact that if $\mathcal{A}$ can find $\mathbf{z}$ from $(\mathbf{B}, \mathbf{C}, \mathbf{N}, \mathbf{b})$, then they can also find $\mathbf{C}\mathbf{z}$, hence the inclusion of events. The second and third inequalities come from the probability preservation and data processing inequality of Lemma 2.7 respectively. By the leftover hash lemma stated in Lemma 2.8, the Rényi divergence between the distribution $(\mathbf{C}, \mathbf{C}\mathbf{z})$ and the distribution $(\mathbf{C}, \mathbf{s})$ is bounded above by $(1+q^k/(2\eta+1)^d)^n$. As we require $d\log_2(2\eta+1) \ge k\log_2 q + \Omega(\log_2 n)$, we obtain $RD_2(H_4\|H_5) \le (1+1/\Omega(n))^n = O(1)$ asymptotically in $n$.

*Problem P₅:* This problem is exactly the M-SLWE$_{n,k,m,q,\mathcal{D}_{R,\beta q}}$ problem, as $\mathbf{C}$ and $\mathbf{N}$ are independent of $\mathbf{B}, \mathbf{s}$ and $\mathbf{e}'$. So if M-SLWE$_{n,k,m,q,\mathcal{D}_{R,\beta q}}$ is $\mathrm{Adv}_{\mathrm{M-SLWE}}$-hard, it hold that

$$
\mathrm{Adv}_{P_5}[\mathcal{A}] \le \mathrm{Adv}_{\mathrm{M-SLWE}}
$$
Putting all equations from above together, we obtain

$$
\begin{align*}
\mathrm{Adv}_{P_0}[\mathcal{A}] &\le \mathrm{Adv}_{P_1}[\mathcal{A}] + d \cdot \mathrm{Adv}_{\mathrm{M-LWE}} \\
&\le \mathrm{Adv}_{P_2}[\mathcal{A}] + d \cdot \mathrm{Adv}_{\mathrm{M-LWE}} \\
&\le \mathrm{Adv}_{P_3}[\mathcal{A}] + p_{\mathrm{spectral}} + d \cdot \mathrm{Adv}_{\mathrm{M-LWE}} \\
&\le \sqrt{\mathrm{Adv}_{P_4}[\mathcal{A}] \cdot \mathrm{RD}_2(H_3 \| H_4)} + p_{\mathrm{spectral}} + d \cdot \mathrm{Adv}_{\mathrm{M-LWE}} \\
&\le \sqrt{\sqrt{\mathrm{Adv}_{\mathrm{M-SLWE}} \cdot \mathrm{RD}_2(H_4 \| H_5)} \cdot \mathrm{RD}_2(H_3 \| H_4)} \\
&\qquad + p_{\mathrm{spectral}} + d \cdot \mathrm{Adv}_{\mathrm{M-LWE}}.
\end{align*}
$$

The choice of parameters yields RD$_2(H_3\|H_4)$, RD$_2(H_4\|H_5) = O(1)$, $p_{\text{spectral}} \le n^{-\omega(1)}$, and our base assumptions give $\mathrm{Adv}_{\mathrm{M-LWE}}$, $\mathrm{Adv}_{\mathrm{M-SLWE}} \le n^{-\omega(1)}$. It therefore proves that $\mathrm{Adv}_{P_0}[\mathcal{A}(H_0) = \mathbf{z}] \le n^{-\omega(1)}$. $\square$

## 3.2 Pseudorandomness of $\eta$-M-LWE

We now provide a more involved proof of hardness for the decision version of $\eta$-M-LWE. It follows the same idea as in [17] that we extend to modules. More precisely, we show a reduction from M-LWE with rank $k$ to $\eta$-M-LWE with rank $d$ satisfying $d \log_2(2\eta + 1) \ge (k+1) \log_2 q + \omega(\log_2 n)$. The reduction preserves the modulus $q$, that needs to be prime satisfying number-theoretic restrictions, the ring degree $n$ and the number of samples $m$, but the noise is increased by a factor of $n\eta\sqrt{2d}\sqrt{4n^2\eta^2 + 1}$. In the case of general cyclotomic fields, the noise rate slightly improves on the noise rate of $d\sqrt{m} \cdot n^{3/2} \log_2(n)\eta$ from Section 3.1. We indeed improve the noise rate by a factor of roughly $\sqrt{8n\eta/\log_2(n)\sqrt{md}}$, which is advantageous whenever $m > 8n\eta^2/d\log_2^2 n$. As we wish to take $\eta$ as a small constant, the condition can be met when $m$ is sub-linear. However, in the special case of power-of-two cyclotomics, the noise rate from Section 3.1 is improved by $\sqrt{n}$. This means that this new reduction is advantageous (in terms of noise) only if $m > 8n^2\eta/d\log_2^2 n = \Theta(n^2/\log_2^3 n)$, which is now just sub-quadratic. Nonetheless, this reduction allows for proving the hardness of the decision version of $\eta$-M-LWE which is preferable for the security of cryptographic applications. For the reduction, $m$ also needs to be larger than the target module rank $d$, and at most polynomial in $n$ because of the hybrid argument used in Lemma 3.4. The reduction in Theorem 3.2 works for all cyclotomic fields, but most results apply to all number fields $K = \mathbb{Q}(\zeta)$ for which the ring of integers is $R = \mathbb{Z}[\zeta]$, the bottleneck being the construction in Lemma 3.2.

**Theorem 3.2.** Let $\nu = \prod_i p_i^{e_i}$, $K$ be the $\nu$-th cyclotomic field of degree $n = \varphi(\nu)$, and $R$ its ring of integers. Let $\mu = \prod_i p_i^{f_i}$ for some $f_i \in [e_i]$, and $q$ be a prime number such that $q = 1 \pmod \mu$, $\mathrm{ord}_\nu(q) = \nu/\mu$, $q > (\eta\mathfrak{s}_1(\mu))^\varphi(\mu)$, and $q^{\nu/\mu} \ge n^{\omega(1/(k+1))}$, where $\mathfrak{s}_1(\mu)$ denotes the largest singular value of the Vandermonde matrix of the $\mu$-th cyclotomic field, and $\eta$ a positive integer. Further, let $k, d, m$ be positive integers such that $d \log_2(2\eta + 1) \ge (k+1) \log_2 q + \omega(\log_2 n)$, and $d \le m \le \mathrm{poly}(n)$. Let $\alpha \ge \sqrt{n}/q \cdot \sqrt{\ln(2nm(1 + \varepsilon^{-1}))/\pi}$ for
some $\varepsilon \in (0, 1/2)$, and $\beta \ge \alpha \cdot n\eta\sqrt{2d}\sqrt{4n^2\eta^2 + 1}$. Then there is a PPT reduction from M-LWE$_{n,k,m,q,D_\alpha}$ to $\eta$-M-LWE$_{n,d,m,q,\Psi_{\le \beta}}$, such that if $\mathcal{A}$ solves the latter with advantage Adv[$\mathcal{A}$], then there exists an algorithm $\mathcal{B}$ that solves the former with advantage

$$ \text{Adv}[\mathcal{B}] \ge \frac{1}{3m} \left( \text{Adv}[\mathcal{A}] - \frac{1}{2} \sqrt{ \left( 1 + \frac{q^{k+1}}{(2\eta+1)^d} \right)^n - 1 } \right) \\ - \frac{103\varepsilon}{6} - \prod_{i \in [g]} \left( 1 - q^{-(k+1)\nu/\mu} \right), $$

When $\nu = 2^{\ell+1}$, $n = 2^\ell$, one can take any prime $q$ such that $q = 2\kappa + 1 \bmod 4\kappa$ for some $\kappa = 2^l$ with $l \in [\ell]$, and such that $q > (\eta\sqrt{\kappa})^\kappa$ and $q^{\nu/\kappa} \ge n^{\omega(1/(k+1))}$.

The modulus is constrained in terms of its splitting behavior. The conditions essentially mean that $q$ splits into $\varphi(\mu)$ factors, each having algebraic norm $q^{\nu/\mu}$. This norm must be at least $n^{\omega(1/(k+1))}$ for Lemma 3.1 to go through, and $q$ must exceed $(\eta s_1(\mu))^{\varphi(\mu)}$ so that every element of $S_\eta$ is a unit in $R_q$. Then, the noise ratio $\beta/\alpha$ contains three main terms. The factor $n\eta$ encapsulates the norm distortion between the coefficient and the canonical embedding, as well as the actual length of the $\eta$-bounded vectors. The second term $\sqrt{2d}$ stems from the masking of $z$ when introduced in the first hybrid in the proof of Lemma 3.5. The last factor $\sqrt{4n^2\eta^2 + 1}$ solely represents the impact of giving information on the error in the ext-M-LWE problem.

**Proof.** We give an overview of the full reduction in Figure 3.2, and detail here how to combine Lemma 3.1, 3.3, 3.4 and 3.5. For clarity, we define $\delta_1$ the loss incurred by the leftover hash lemma, namely $\delta_1 = \frac{1}{2}\sqrt{\left(1 + \frac{q^{k+1}}{(2\eta+1)^d}\right)^n - 1}$, and $\delta_2 = \prod_{i \in [\varphi(\mu)]} (1 - q^{-(k+1)\nu/\mu})$. Assume there exists a PPT distinguisher $\mathcal{A}$ for $\eta$-M-LWE$_{n,d,m,q,\Psi_{\le \beta}}$ which succeeds with advantage Adv[$\mathcal{A}$]. By Lemma 3.5, one can construct PPT adversaries $\mathcal{B}_1, \mathcal{B}_2$ and $\mathcal{B}_3$ for ext-M-LWE$_{n,k+1,d,q,\psi,S_\eta^d}$, M-LWE$_{n,k+1,m,q,D_\gamma}$ and ext-M-LWE$_{n,k+1,d,q,\psi,\{0\}^d}$ respectively such that

$$ \text{Adv}[\mathcal{B}_1] + \text{Adv}[\mathcal{B}_2] + \text{Adv}[\mathcal{B}_3] \ge \text{Adv}[\mathcal{A}] - 2m\varepsilon - \delta_1, $$

where $\gamma = \alpha B_\eta \sqrt{d} \sqrt{4B_\eta^2 + 1}$ and $\psi = \mathcal{D}_{q^{-1}R_\alpha \sqrt{4B_\eta^2+1}}$. Hence, there exists $i \in \{1, 2, 3\}$ such that $\text{Adv}[\mathcal{B}_i] \ge \frac{1}{3}(\text{Adv}[\mathcal{A}] - 2m\varepsilon - \delta_1)$, otherwise the above inequality yields a contradiction.

**Case i = 1:** By Lemma 3.4, one can use $\mathcal{B}_1$ to construct a distinguisher $\mathcal{B}_1^{(1)}$ for ext-M-LWE$_{n,k+1,d,q,\psi,S_\eta^d}$ such that

$$ \text{Adv}[\mathcal{B}_1^{(1)}] = \frac{1}{m} \text{Adv}[\mathcal{B}_1]. $$

Then, by Lemma 3.3, the latter can be used to construct a distinguisher $\mathcal{B}_1^{(2)}$ for first-is-errorless M-LWE$_{n,k+1,d,q,D_\alpha}$ such that

$$ \text{Adv}[\mathcal{B}_1^{(2)}] \ge \text{Adv}[\mathcal{B}_1^{(1)}] - 33\varepsilon/2. $$
Lemma 3.1 then yields a distinguisher $\mathcal{B}_1^{(3)}$ for M-LWE$_{n,k,d,q,D_\alpha}$ with advantage

$$ \mathrm{Adv}[\mathcal{B}_1^{(3)}] \ge \mathrm{Adv}[\mathcal{B}_1^{(2)}] - \delta_2. $$

Since $m \ge d$, we can consider a distinguisher $\mathcal{B}_1^{(4)}$ for M-LWE$_{n,k,m,q,D_\alpha}$ which simply calls $\mathcal{B}_1^{(3)}$ on the first $d$ samples. By combining it all, we have

$$ \begin{aligned} \mathrm{Adv}[\mathcal{B}_1^{(4)}] &\ge \mathrm{Adv}[\mathcal{B}_1^{(3)}] \\ &\ge \mathrm{Adv}[\mathcal{B}_1^{(2)}] - \delta_2 \\ &\ge \mathrm{Adv}[\mathcal{B}_1^{(1)}] - \delta_2 - 33\varepsilon/2 \\ &= \frac{1}{m}\mathrm{Adv}[\mathcal{B}_1] - \delta_2 - 33\varepsilon/2 \\ &\ge \frac{1}{3m}(\mathrm{Adv}[\mathcal{A}] - \delta_1 - 2m\varepsilon) - \delta_2 - 33\varepsilon/2 \\ &= \frac{1}{3m}(\mathrm{Adv}[\mathcal{A}] - \delta_1) - \delta_2 - 103\varepsilon/6. \end{aligned} $$

**Case i = 2:** We construct the adversary $\mathcal{B}_2^{(1)}$ for M-LWE$_{n,k,m,q,D_\alpha}$ using $\mathcal{B}_2$ as follows. On input $(\mathbf{A}, \mathbf{b}) \in R_q^{m \times k} \times \mathbb{T}^m$, the adversary $\mathcal{B}_2^{(1)}$, samples $\mathbf{a} \leftarrow U(R_q^m)$, $s \leftarrow U(R_q)$ and $\mathbf{e}' \leftarrow D_m^{\sqrt{\gamma^2 - \alpha^2}}$. It then calls $\mathcal{B}_2$ on input $(\mathbf{A}', \mathbf{b}') = ([\mathbf{A}|\mathbf{a}], \mathbf{b} + q^{-1}s \cdot \mathbf{a} + \mathbf{e}' \bmod R)$. If $\mathbf{b} = q^{-1}\mathbf{A}\mathbf{s} + \mathbf{e} \bmod R$, then $\mathbf{b}' = q^{-1}\mathbf{A}' \cdot [\mathbf{s}^T|\mathbf{s}]^T + (\mathbf{e} + \mathbf{e}') \bmod R$, and $\mathbf{e} + \mathbf{e}'$ is distributed as $D_m^m$. Otherwise, if $\mathbf{b}$ is uniform, then so is $\mathbf{b}'$ as $\mathbf{b}$ is independent of $q^{-1}\mathbf{a}\mathbf{s} + \mathbf{e}'$. Hence, we have

$$ \begin{aligned} \mathrm{Adv}[\mathcal{B}_2^{(1)}] &\ge \mathrm{Adv}[\mathcal{B}_2] \\ &\ge \frac{1}{3}(\mathrm{Adv}[\mathcal{A}] - \delta_1 - 2m\varepsilon) \\ &\ge \frac{1}{3m}(\mathrm{Adv}[\mathcal{A}] - \delta_1) - \delta_2 - 103\varepsilon/6. \end{aligned} $$

**Case i = 3:** Since ext-M-LWE$_{n,k+1,d,q,\psi,S_\eta^d}$ reduces to ext-M-LWE$_{n,k+1,d,q,\psi,\{0\}^d}$ without transforming the samples, we can assume without loss of generality that $\mathrm{Adv}[\mathcal{B}_1] \ge \mathrm{Adv}[\mathcal{B}_3]$. It then yields $\mathrm{Adv}[\mathcal{B}_1] \ge \frac{1}{3}(\mathrm{Adv}[\mathcal{A}] - 2m\varepsilon - \delta_1)$ as in Case i = 1.

In any case, we can construct a distinguisher $\mathcal{B}$ for M-LWE$_{n,k,m,q,D_\alpha}$ as claimed. $\square$

<figure><img src="image_4.png" /></figure>

**3.2.1 First-is-errorless M-LWE.** We follow the same idea as Brakerski et al. [17] by gradually giving more information to the adversary while proving that this additional information does not increase the advantage too much. We define the module version of first-is-errorless LWE, from [17], where the first equation is given without error. A similar definition and reduction from M-LWE are given in [4]. The only difference between the two reductions comes from the pre-processing step, which is performed before receiving the M-LWE samples. In our case, this step is simplified and extended to general number fields, provided that the modulus $q$ verifies certain splitting conditions. Further restrictions on $q$ in our reduction encompasses these conditions.
<figure><img src="image_5.png" /><figcaption>**Fig. 3.2.** Summary of the proof of Theorem 3.2, where $B_{\eta} = \max_{x \in S_{\eta}} \|\sigma(x)\|_{\infty}$ and $\sigma$ is the canonical embedding. In cyclotomic fields, we have $B_{\eta} \le n\eta$. Note that Lemma 3.5 uses $d$ samples from ext-M-LWE, where $d$ is the module rank in $\eta$-M-LWE. The assumptions on $q$ concern the splitting behavior of the cyclotomic polynomial in $\mathbb{Z}_q[x]$, and are discussed in Section 3.2.2.</figcaption></figure>

**Definition 3.1 (First-is-errorless M-LWE).** Let $K$ be a number field of degree $n$ and $R$ its ring of integers. Let $q, k$ be positive integers, and $\Upsilon$ a distribution over a family of distributions over $K_{\mathbb{R}}$. The first-is-errorless M-LWE$_{n,k,q,\Upsilon}$ problem is to distinguish between the following cases. On the one hand, the first sample is from $U(R_q^k \times q^{-1}R/R)$ and the rest from $U(R_q^k \times \mathbb{T})$. On the other hand, there is some unknown $\mathbf{s} \leftarrow U(R_q^k)$ and $\psi \leftarrow \Upsilon$ such that the first sample is from $A_{\mathbf{s},\psi}^{\mathcal{M}}$ and the rest are distributed as $A_{\mathbf{s},\psi}^{\mathcal{M}}$, where $\{0\}$ is the distribution that is deterministically 0. When the number of samples $m$ is fixed, we denote it first-is-errorless M-LWE$_{n,k,m,q,\Upsilon}$, where only $m-1$ coefficients contain errors.

**Lemma 3.1 (Adapted from [17, Lem. 4.3]).** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Then, let $k$ be a positive integer, and $\Upsilon$ a distribution over a family of distributions over $K_{\mathbb{R}}$. Let $q$ be an unramified prime integer such that the smallest norm of its prime ideal factors is
at least $n^{\omega(1/k)}$. There is a PPT reduction from M-LWE$_{n,k-1,q,\Upsilon}$ to the variant first-is-errorless M-LWE$_{n,k,q,\Upsilon}$. If the number of samples m is fixed, it gives a PPT reduction from M-LWE$_{n,k-1,m-1,q,\Upsilon}$ to first-is-errorless M-LWE$_{n,k,m,q,\Upsilon}$. The reduction reduces the advantage by at most $1 - \prod_{i \in [\kappa]} (1 - N(\mathfrak{p}_i)^{-k})$, where the $\mathfrak{p}_i$'s are the prime ideal factors of $\langle q \rangle$.

**Proof. Pre-processing:** The reduction first samples $\mathbf{a}' \leftarrow U(R_q^k)$ such that $\mathbf{a}'$ is $R_q$-linearly independent. As a result, $\mathbf{a}'$ is uniform among the $R_q$-linearly independent vectors. We first show that under the conditions of the lemma, the distribution of $\mathbf{a}'$ is statistically close to $U(R_q^k)$. Denote by $S$ the set of vectors of $R_q^k$ that are linearly independent, and $S'$ its complement in $R_q^k$. It then holds that

$$ 
\begin{aligned}
\Delta(U(R_q^k), U(S)) &= \frac{1}{2} \sum_{\mathbf{x} \in S} \left| \frac{1}{|R_q^k|} - \frac{1}{|S|} \right| + \frac{1}{2} \sum_{\mathbf{x} \in S'} \left| \frac{1}{|R_q^k|} - 0 \right| \\
&= \frac{1}{2} \left( |S| \left( \frac{1}{|S|} - \frac{1}{|R_q^k|} \right) + \frac{|S'|}{|R_q^k|} \right) \\
&= \frac{|S'|}{|R_q^k|} \\
&= 1 - \mathbb{P}_{\mathbf{a}' \sim U(R_q^k)}[\mathbf{a}' \text{ is } R_q\text{-linearly independent}]
\end{aligned}
$$

By Lemma 2.5 for $\ell = 0$, we have

$$ 
\begin{aligned}
\mathbb{P}_{\mathbf{a}' \sim U(R_q^k)}[\mathbf{a}' \text{ is } R_q\text{-linearly independent}] &= \prod_{i \in [\kappa]} \left(1 - \frac{1}{N(\mathfrak{p}_i)^k}\right) \\
&\geq 1 - \frac{n}{\min_{i \in [\kappa]} N(\mathfrak{p}_i)^k} \\
&\geq 1 - n^{-\omega(1)},
\end{aligned}
$$

by assumption. Hence $\Delta(U(R_q^k), U(S)) \le n^{-\omega(1)}$. Then, from $\mathbf{a}'$, one can efficiently complete it with $\mathbf{b}_2, \dots, \mathbf{b}_k \in R_q^k$ such that the matrix $\mathbf{U} = [\mathbf{a}'|\mathbf{b}_2|\dots|\mathbf{b}_k]$ is invertible in $R_q$. For example, this can be done by successively sampling the $\mathbf{b}_i$'s uniformly at random in $R_q^k$. By Lemma 2.5, the probability that the newly drawn $\mathbf{b}_{\ell+1}$ is kept is $\prod_{i \in [\kappa]} (1 - N(\mathfrak{p}_i)^{-(k-\ell)}) \ge 1 - n^{-\omega(1)}$. It would thus require at most a polynomial number of sampled vectors.

**Reduction:** Then, sample $s_0$ uniformly in $R_q$. The reduction is as follows. For the first sample, it outputs $(\mathbf{a}', q^{-1} \cdot s_0 \bmod R) \in R_q^k \times q^{-1}R/R$. The other samples are produced by taking $(\mathbf{a}, b) \in R_q^{k-1} \times \mathbb{T}$ from the M-LWE challenger, picking a fresh randomly chosen $a'' \in R_q$, and outputting $(\mathbf{U}[a''|\mathbf{a}^T]^T, b+q^{-1}(s_0 \cdot a'') \bmod R) \in R_q^k \times \mathbb{T}$. We now analyze correctness. First note that the first component is uniform over $R_q^k$. Indeed, $\mathbf{a}'$ is uniform over $R_q^k$ for the first sample, and since $\mathbf{a}$ is uniform over $R_q^{k-1}$, $a''$ is uniform over $R_q$, and $\mathbf{U}$ is invertible in $R_q^{k \times k}$, then $\mathbf{U}[a''|\mathbf{a}^T]^T$ is uniform over $R_q^k$ as well.
If $b$ is uniform, the first sample yields $q^{-1}s_0 \mod R$ uniform over $q^{-1}R/R$. For the other samples, $b+q^{-1}(s_0 \cdot a'') \mod R$ is uniform over $\mathbb{T}$ and independent of $\mathbf{U}[a''|\mathbf{a}^T]^T$ but also independent from the first sample because $b$ masks $q^{-1}(s_0 \cdot a'')$. If $b = q^{-1}\langle \mathbf{a}, \mathbf{s} \rangle + e \mod R$ for some uniform $\mathbf{s} \in R_q^{k-1}$ and $e \leftarrow \psi$ for some $\psi \leftarrow \mathcal{Y}$, then $q^{-1}s_0 = q^{-1}\langle \mathbf{e}_1, [s_0|\mathbf{s}^T]^T \rangle = q^{-1}\langle \mathbf{U}\mathbf{e}_1, \mathbf{U}^{-T}[s_0|\mathbf{s}^T]^T \rangle = q^{-1}\langle \mathbf{a}', \mathbf{U}^{-T}[s_0|\mathbf{s}^T]^T \rangle$, where $\mathbf{e}_1 = [1, 0, \dots, 0]^T$. For the other samples, we have

$$ 
\begin{aligned}
b + q^{-1}(s_0 \cdot a'') \mod R &= q^{-1}\langle \mathbf{a}, \mathbf{s} \rangle + q^{-1}(s_0 \cdot a'') + e \mod R \\
&= q^{-1}\langle [a''|\mathbf{a}^T]^T, [s_0|\mathbf{s}^T]^T \rangle + e \mod R \\
&= q^{-1}\langle \mathbf{U}[a''|\mathbf{a}^T]^T, \mathbf{U}^{-T}[s_0|\mathbf{s}^T]^T \rangle + e \mod R.
\end{aligned}
$$

Note that $[s_0|\mathbf{s}^T]^T$ is uniform over $R_q^k$, which implies that $\mathbf{U}^{-T}[s_0|\mathbf{s}^T]^T$ is also uniform over $R_q^k$ because $\mathbf{U}^{-T}$ is invertible in $R_q$. Therefore the reduction outputs samples according to first-is-errorless M-LWE with secret $\mathbf{s}' = \mathbf{U}^{-T}[s_0|\mathbf{s}^T]^T$. $\square$

<figure><img src="image_6.png" /></figure>

**Remark 3.1.** Later in the reduction, we restrict the modulus $q$ to be a prime that splits into few prime factors in the underlying cyclotomic field to maximize the number of invertible elements, and more precisely to be able to use Lemma A.3 without having to take superpolynomial $q$. In this case, one could use moduli that split into say $\kappa$ factors such that $q^{-n/\kappa} \le n^{-\omega(1)}$.

**3.2.2 Extended M-LWE.** We now define the module version of the Extended LWE problem introduced in [17], where the adversary is allowed a hint on the errors. A first definition of ext-M-LWE was introduced by Alperin-Sheriff and Apon [4] in which the hints were of the form $\mathrm{Tr}(\langle \mathbf{z}_i, \mathbf{e} \rangle)$ for a single error vector $\mathbf{e}$ and several hint vectors $\mathbf{z}_i$. In our case, we allow for multiple secrets (and thus errors) and one single hint vector $\mathbf{z}$, as required by our final reduction of Lemma 3.5. Additionally, as the field trace does not provide enough information to reconstruct $\langle \mathbf{z}, \mathbf{e} \rangle$ from the hint, we instead directly give $\langle \mathbf{z}, \mathbf{e} \rangle$ as the hint. We prove that it does not make the problem easier. Another version of ext-M-LWE was recently introduced in [33] in the context of lattice-based zero-knowledge proofs, where they only provide the sign $\mathrm{Sign}(\langle \mathbf{z}, \mathbf{e} \rangle)$ as an additional hint for the attacker. Again, this is not sufficient for our lossy argument in Lemma 3.5.

**Definition 3.2 (Extended M-LWE).** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $m, q, k, \ell$ be positive integers. Let $\mathcal{Z} \subseteq \mathbb{R}^m$ and $\psi$ a discrete distribution over $q^{-1}R$. The Extended M-LWE problem, denoted by ext-M-LWE$^\ell_{n,k,m,q,\psi,\mathcal{Z}}$, is as follows. The adversary first chooses $\mathbf{z} \in \mathcal{Z}$ and then receives a tuple $(\mathbf{A}, \mathbf{B}, \mathbf{E}^T\mathbf{z})$ over $R_q^{m \times k} \times (q^{-1}R/R)^{m \times \ell} \times (q^{-1}R)^\ell$. Its goal is to distinguish between the following cases.

On one side, $\mathbf{A}$ is sampled from $U(R_q^{m \times k})$, $\mathbf{E}$ is sampled from $\psi^{m \times \ell}$, and define $\mathbf{B} = q^{-1}\mathbf{A}\mathbf{S} + \mathbf{E}$ mod $R$ for some uniformly chosen $\mathbf{S} \in R_q^{k \times \ell}$. On the other side, all is identical except that $\mathbf{B}$ is sampled from $U((q^{-1}R/R)^{m \times \ell})$, independently from $\mathbf{A}$ and $\mathbf{E}$.
The parameter $\ell$ represents the number of given hints on independent noise vectors, and therefore the number of secret vectors (which generalizes the multiple secret version of M-LWE). The set $\mathcal{Z}$ represents the set of hint vectors $\mathbf{z}$ that can be given. The $\ell$ hints are given in form of the inner product of such a fixed *hint vector* $\mathbf{z} \in \mathcal{Z}$ and the corresponding column of $\mathbf{E}$. Later, we are interested in the case where $\mathcal{Z} = S_{\eta}^m$ which is actually the set of secrets for $\eta$-M-LWE. Also, note that if $\mathcal{Z} = \{\mathbf{0}\}$, then we recover the definition of the multiple secret version of M-LWE from Section 2.5.

Similar to the notation from [35], for a matrix $\mathbf{A} \in \mathbb{R}^{m \times m}$, we denote by $\mathbf{A}^{[1]} \in \mathbb{R}^{m \times (m-1)}$ the submatrix of $\mathbf{A}$ obtained by removing the leftmost column. Our reduction from first-is-errorless M-LWE to ext-M-LWE in Lemma 3.3 requires the construction of a matrix $\mathbf{U}_{\mathbf{z}} \in \mathbb{R}^{m \times m}$, for all vectors $\mathbf{z} \in \mathcal{Z} = S_{\eta}^m$, satisfying several properties. This matrix allows us to transform samples from a first-is-errorless M-LWE challenger into samples that we can give to an oracle for ext-M-LWE. The spectral norm of its submatrix $\mathbf{U}_{\mathbf{z}}^{[1]}$ (when embedded with $M_{\sigma}$), controls the increase in the Gaussian parameter. We propose a construction for which we bound the spectral norm above by a quantity independent on $\mathbf{z}$, as needed in the reduction.

**Lemma 3.2.** Let $\nu = \prod_i p_i^{e_i}$, $K$ be the $\nu$-th cyclotomic field of degree $n = \varphi(\nu)$, and $R$ its ring of integers. Let $\mu = \prod_i p_i^{f_i}$ for some $f_i \in [e_i]$, $\eta$ a positive integer and $q$ be a prime such that $q = 1 \bmod \mu$, $\text{ord}_{\nu}(q) = \nu/\mu$ and $q > (\eta\mathfrak{s}_1(\mu))^{\varphi(\mu)}$, where $\mathfrak{s}_1(\mu)$ denotes the spectral norm of the Vandermonde matrix of the $\mu$-th cyclotomic field. Finally, let $m$ be a positive integer, and $\mathcal{Z} = S_{\eta}^m$. For all $\mathbf{z} \in \mathcal{Z}$, there is an efficiently computable matrix $\mathbf{U}_{\mathbf{z}} \in \mathbb{R}^{m \times m}$ that is invertible modulo $qR$ and that verifies the following: $\mathbf{z}$ is orthogonal to the columns of $\mathbf{U}_{\mathbf{z}}^{[1]}$, and $\|M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})\| \le 2B_{\eta}$, where $B_{\eta} = \max_{x \in S_{\eta}} \|\sigma(x)\|_{\infty}$.

When $\nu = 2^{\ell+1}$, $n = 2^{\ell}$, one can take any prime $q$ such that $q = 2\kappa+1 \bmod 4\kappa$ for some $\kappa = 2^l$ with $l \in [\ell]$, and such that $q > (\eta\sqrt{\kappa})^{\kappa}$.

*Proof.* Let $\mathbf{z} \in \mathcal{Z}$. First, we construct $\mathbf{U}_{\mathbf{z}}$ in the case where all the $z_i$ are non-zero. To do so, we define the intermediate matrices $\mathbf{A}$, and $\mathbf{B}$ of $\mathbb{R}^{m \times m}$, all unspecified entries being zeros:

$$ \mathbf{U}_{\mathbf{z}} = \left[ \begin{array}{c} \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}] \node (z1) at (0,0) {$z_1$}; \node (z2) at (0,1) {$z_2$}; \node (z3) at (0,-1) {$z_m$}; \node (z4) at (0,2) {$z_{m-1}$}; \draw[->] (z1) -- (z2); \draw[->] (z1) -- (z3); \draw[->] (z1) -- (z4); \node[above] at (z1) {$-z_m$}; \node[above] at (z2) {$-z_{m-1}$}; \node[below] at (z1) {$0$}; \end{tikzpicture} \\ \mathbf{U}_{\mathbf{z}}^{[1]} \\ \mathbf{A}^{[1]} \\ \mathbf{B}^{[1]} \end{array} \right] = \left[ \begin{array}{c} \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}] \node (z1) at (0,0) {$z_1$}; \node (z2) at (0,1) {$z_2$}; \node (z3) at (0,-1) {$z_m$}; \node (z4) at (0,2) {$z_{m-1}$}; \draw[->] (z1) -- (z2); \draw[->] (z1) -- (z3); \draw[->] (z1) -- (z4); \node[above] at (z1) {$-z_m$}; \node[above] at (z2) {$-z_{m-1}$}; \node[below] at (z1) {$0$}; \end{tikzpicture} \\ \mathbf{A}^{[1]} \\ \mathbf{B}^{[1]} \end{array} \right] + \left[ \begin{array}{c} \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.3, every node/.style={scale=0.8}] \node (z1) at (0,0) {$z_1$}; \node (z2) at (0,1) {$z_2$}; \node (z3) at (0,-1) {$z_m$}; \node (z4) at (0,2) {$z_{m-1}$}; \draw[->] (z1) -- (z2); \draw[->] (z1) -- (z3); \draw[->] (z1) -- (z4); \node[above] at (z1) {$-z_m$}; \node[above] at (z2) {$-z_{m-1}$}; \node[below] at (z1) {$0$}; \end{tikzpicture} \\ \mathbf{A}^{[1]} \\ \mathbf{B}^{[1]} \end{array} \right]. $$

The matrix $\mathbf{U}_{\mathbf{z}}$ is invertible modulo $qR$ only if all the $z_i$ (except $z_m$) are in $\mathbb{R}_q^{\times}$. Yet, since they are all non-zero and $\eta$-bounded elements, we have that for all $i$ in $[m]$, $0 < \|\tau(z_i)\|_{\infty} \le \eta$, where $\tau$ is the coefficient embedding. By Lemma 2.4, since $q$ verifies the algebraic conditions taking all $f_i = 1$ and $q^{1/\varphi(\mu)}/\mathfrak{s}_1(\mu) > \eta$,
all the $z_i$ are in $R_q^\times$.

By construction, the last $m-1$ columns of $U_z$ are orthogonal to $z$. Let $\mathbf{U}_z^{[1]}$ be the submatrix of $U_z$ obtained by removing the leftmost column as shown above. As observed in Lemma 2.3 for example, it holds that
$$ \|M_{\sigma_H}(\mathbf{U}_z^{[1]})\|_2 = \|M_{\sigma}(\mathbf{U}_z^{[1]})\|_2. $$

Then, using the fact that $M_\sigma$ is a ring homomorphism, we have $M_\sigma(\mathbf{U}_z^{[1]}) = M_\sigma(\mathbf{A}^{[1]}) + M_\sigma(\mathbf{B}^{[1]})$. We now need to bound the spectral norm of these two matrices, and use the triangle inequality to conclude. For any vector $\mathbf{x} \in \mathbb{C}^{(m-1)n}$, we have that $\|M_\sigma(\mathbf{A}^{[1]})\mathbf{x}\|_2 = \sqrt{\sum_{i \in [m-1]} \sum_{j \in [n]} |\sigma_j(z_i)|^2 |x_{j+n(i-1)}|^2} \le B_\eta \|\mathbf{x}\|_2$, because each $z_i$ is in $S_\eta$. This yields $\|M_\sigma(\mathbf{A}^{[1]})\|_2 \le B_\eta$. A similar calculation on $\mathbf{B}^{[1]}$ leads to $\|M_\sigma(\mathbf{B}^{[1]})\|_2 \le B_\eta$, thus resulting in $\|M_\sigma(\mathbf{U}_z^{[1]})\|_2 \le 2B_\eta$.

Now assume that $z_{i_0}, \dots, z_m$ are zeros for some $i_0$ in $[m]$. If the zeros do not appear last in the vector $\mathbf{z}$, we can replace $\mathbf{z}$ with $S\mathbf{z}$, where $S \in \mathbb{R}^{m \times m}$ swaps the coordinates of $\mathbf{z}$ so that the zeros appear last. Since $S$ is unitary, it preserves the singular values as well as invertibility. Then, the construction remains the same except that the $z_{i_0}, \dots, z_m$ on the diagonal are replaced by 1. The orthogonality is preserved, and $\|M_\sigma(\mathbf{U}_z^{[1]})\|_2$ can still be bounded above by $2B_\eta$. $\square$

Notice that when the ring is of degree 1 and $\eta = 1$, the constructions in the different cases match the ones from [17, Claim 4.6]. So do the singular values as $B_\eta \le n\eta = 1$ by Lemma 2.1. Also, the construction differs from the notion of quality in [4] due to the discrepancies between the two definitions of ext-M-LWE. The following lemma shows that the extended variant of M-LWE with one hint ($\ell = 1$) is at least as hard as the first-is-errorless variant of M-LWE, for carefully chosen parameters.

**Lemma 3.3 (Adapted from [17, Lem. 4.7]).** Let $\nu = \prod_i p_i^{e_i}$, $K$ be the $\nu$-th cyclotomic field of degree $n = \varphi(\nu)$, and $R$ its ring of integers. Let $\mu = \prod_i p_i^{f_i}$ for some $f_i \in [e_i]$, $\eta$ a positive integer and $q$ be a prime such that $q = 1 \pmod \mu$, $\text{ord}_\nu(q) = \nu/\mu$ and $q > (\eta s_1(\mu))^{\varphi(\mu)}$, where $s_1(\mu)$ denotes the spectral norm of the Vandermonde matrix of the $\mu$-th cyclotomic field. Let $m, k$ be positive integers, $\mathcal{Z} = S_\eta^m$, $\varepsilon \in (0, 1/2)$ and $\alpha \ge \sqrt{n}/q \cdot \sqrt{\ln(2nm(1+\varepsilon^{-1}))/\pi}$. There is a PPT reduction from the variant first-is-errorless M-LWE$_{n,k,m,q,\mathcal{Z}}$ to ext-M-LWE$_{n,k,m,q,\psi,\mathcal{Z}}^1$ that reduces the adversary's advantage by at most $33\varepsilon/2$, where $\psi = \mathcal{D}_{q^{-1}R,\alpha} \sqrt{4B_\eta^2+1}$ and $B_\eta = \max_{x \in S_\eta} \|\sigma(x)\|_\infty$.

When $\nu = 2^{\ell+1}$, $n = 2^\ell$, one can take any prime $q$ such that $q = 2\kappa+1 \pmod{4\kappa}$ for some $\kappa = 2^l$ with $l \in [\ell]$, and such that $q > (\eta\sqrt{\kappa})^\kappa$.

*Proof.* First, we clarify the condition on $\alpha$. Since $K$ is a cyclotomic field, $\mathbf{B} = \mathbf{I}_m \otimes q^{-1}[\sigma_H(1)|\dots|\sigma_H(\zeta^{n-1})]$ is a basis of the lattice $\sigma_H(q^{-1}R^m)$, and each vector has norm $\sqrt{n}/q$. As a result, the max-Euclidean norm of the Gram-Schmidt orthogonalization of $\mathbf{B}$ is at most $\sqrt{n}/q$. By [20, Lem. 3.1, Thm. 4.1], our condition on $\alpha$ ensures that $\alpha \ge \eta_\varepsilon(q^{-1}R^m)$ and that $\mathcal{D}_{q^{-1}R^m,\alpha}$ is efficiently sampleable.
Now, assume we have access to an oracle $\mathcal{O}$ for ext-M-LWE$_{n,k,m,q,\alpha}\sqrt{4B_{\eta}^2+1},\mathbb{Z}$.
We take $m$ samples from the first-is-errorless challenger, resulting in

$$ (\mathbf{A}, \mathbf{b}) \in (R_q)^{k \times m} \times ((q^{-1}R/R) \times \mathbb{T}^{m-1}). $$

Assume we need to provide samples to $\mathcal{O}$ for some $\mathbf{z} \in \mathbb{Z}$. By Lemma 3.2 we can efficiently compute a matrix $\mathbf{U}_{\mathbf{z}} \in \mathbb{R}^{m \times m}$ that is invertible modulo $qR$, such that its submatrix $\mathbf{U}_{\mathbf{z}}^{[1]}$ is orthogonal to $\mathbf{z}$, and that $\|M_{\sigma}(\mathbf{U}_{\mathbf{z}}^{[1]})\|_2 \le 2B_{\eta}$. The reduction first samples $\mathbf{f} \in K_{\mathbb{R}}^m$ from the continuous Gaussian distribution of covariance matrix $\alpha^2(4B_{\eta}^2\mathbf{I}_{mn} - M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})^T) \in \mathbb{R}^{mn \times mn}$. The covariance matrix is well-defined because $\|M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})\|_2 \le 2B_{\eta}$. The reduction then computes $\mathbf{b}' = \mathbf{U}_{\mathbf{z}}\mathbf{b} + \mathbf{f}$ and samples $\mathbf{c}$ from $\mathcal{D}_{q^{-1}R^m - \mathbf{b}',\alpha}$ (as it is efficiently sampleable), and finally gives the following to $\mathcal{O}$

$$ (\mathbf{A}' = \mathbf{U}_{\mathbf{z}}\mathbf{A}, \mathbf{b}' + \mathbf{c} \mod R, \langle \mathbf{z}, \mathbf{f} + \mathbf{c} \rangle). $$

Note that this tuple is in $R_q^{m \times k} \times (q^{-1}R/R)^m \times q^{-1}R$, as required. We now prove correctness. First, consider the case where $\mathbf{A}$ is uniformly random over $R_q^{m \times k}$ and $\mathbf{b} = q^{-1}\mathbf{A}\mathbf{s} + \mathbf{e} \mod R$ for some uniform $\mathbf{s} \in R_q^k$, and $\mathbf{e}$ sampled from $\{0\} \times D_{\alpha}^{m-1}$ where $\{0\}$ denotes the distribution that is deterministically 0. Since $\mathbf{U}_{\mathbf{z}}$ is invertible modulo $qR$, $\mathbf{A}' = \mathbf{U}_{\mathbf{z}}\mathbf{A}$ is also uniform over $R_q^{m \times k}$ as required. From now on we condition on an arbitrary $\mathbf{A}'$ and analyze the distribution of the remaining components. We have

$$ \begin{aligned} \mathbf{b}' &= q^{-1}\mathbf{U}_{\mathbf{z}}\mathbf{A}\mathbf{s} + \mathbf{U}_{\mathbf{z}}\mathbf{e} + \mathbf{f} \\ &= q^{-1}\mathbf{A}'\mathbf{s} + \mathbf{U}_{\mathbf{z}}\mathbf{e} + \mathbf{f}. \end{aligned} $$

Since the first coefficient of $\mathbf{e}$ is deterministically 0, $\mathbf{e}$ is distributed according to $D_{\sqrt{\mathbb{S}}}$ where $\mathbf{S} = \text{diag}(\mathbf{0}_{n \times n}, \alpha^2\mathbf{I}_n, \dots, \alpha^2\mathbf{I}_n)$. By Lemma 2.14, $\mathbf{U}_{\mathbf{z}}\mathbf{e}$ is then distributed according to $D_{\sqrt{\mathbb{S}}'}$ where $\mathbf{S}' = M_{\sigma_H}(\mathbf{U}_{\mathbf{z}})\mathbf{S}M_{\sigma_H}(\mathbf{U}_{\mathbf{z}})$. Due to the specific form of $\mathbf{S}$, we observe that $\mathbf{S} = M_{\sigma_H}(\text{diag}(\mathbf{0}, \alpha^2, \dots, \alpha^2))$. Using the ring homomorphism property and the form of $\mathbf{S}$, it holds that $\mathbf{S}' = M_{\sigma_H}(\alpha^2\mathbf{U}_{\mathbf{z}}^{[1]}(\mathbf{U}_{\mathbf{z}}^{[1]})^T) = \alpha^2 M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})^T$. Hence the vector $\mathbf{U}_{\mathbf{z}}\mathbf{e} + \mathbf{f}$ is distributed as the Gaussian over $K_{\mathbb{R}}^m$ of covariance matrix $\alpha^2 M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})^T + \alpha^2(4B_{\eta}^2\mathbf{I}_{mn} - M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})M_{\sigma_H}(\mathbf{U}_{\mathbf{z}}^{[1]})^T)$ which is identical to $D_{\alpha \cdot 2B_{\eta}}^m$. Since $q^{-1}\mathbf{A}'\mathbf{s} \in q^{-1}R^m$, the coset $q^{-1}R^m - \mathbf{b}'$ is the same as $q^{-1}R^m - (\mathbf{U}_{\mathbf{z}}\mathbf{e} + \mathbf{f})$, which yields that $\mathbf{c}$ can be seen as being sampled from $\mathcal{D}_{q^{-1}R^m - (\mathbf{U}_{\mathbf{z}}\mathbf{e} + \mathbf{f}),\alpha}$. Since $\alpha \ge \eta_{\varepsilon}(q^{-1}R^m)$, Lemma 2.11 gives that the distribution of $\mathbf{U}_{\mathbf{z}}\mathbf{e} + \mathbf{f} + \mathbf{c}$ is within statistical distance $8\varepsilon$ of $\mathcal{D}_{q^{-1}R^m, \alpha}\sqrt{4B_{\eta}^2+1}$, which shows that the second component is correctly distributed up to $8\varepsilon$. Note that $\mathbf{U}_{\mathbf{z}}\mathbf{e} = \sum_{i \in [m]} e_i \cdot \mathbf{u}_i$ is in the space spanned by the columns of $\mathbf{U}_{\mathbf{z}}^{[1]}$ because $e_1 = 0$. This yields $\langle \mathbf{z}, \mathbf{U}_{\mathbf{z}}\mathbf{e} \rangle = 0$ as $\mathbf{z}$ is orthogonal to the columns of $\mathbf{U}_{\mathbf{z}}^{[1]}$, proving that the third component equals $\langle \mathbf{z}, \mathbf{U}_{\mathbf{z}}\mathbf{e} + \mathbf{f} + \mathbf{c} \rangle$ and is thus correctly distributed.
Now consider the case where both **A** and **b** are uniform. Using that $\alpha \ge \eta_{\epsilon}(q^{-1}R^m)$, Lemma 2.10 shows that the distribution of $(\mathbf{A}, \mathbf{b})$ is within statistical distance $\epsilon/2$ of the distribution of $(\mathbf{A}, \mathbf{e}' + \mathbf{e})$ where $\mathbf{e}' \in (q^{-1}R/R)^m$ is uniform and $\mathbf{e}$ is distributed from $\{0\} \times D_{\alpha}^{m-1}$. So we can assume our input is $(\mathbf{A}, \mathbf{e}' + \mathbf{e})$. $\mathbf{A}'$ is uniform as before, and clearly independent of the other two components. Moreover, since $\mathbf{b}' = \mathbf{U}_z\mathbf{e}' + \mathbf{U}_z\mathbf{e} + \mathbf{f}$ and $\mathbf{U}_z\mathbf{e}' \in q^{-1}R^m$, then the coset $q^{-1}R^m - \mathbf{b}'$ is identical to $q^{-1}R^m - (\mathbf{U}_z\mathbf{e} + \mathbf{f})$. For the same reasons as above, $\mathbf{U}_z\mathbf{e} + \mathbf{f} + \mathbf{c}$ is distributed as $D_{q^{-1}R^m, \alpha\sqrt{4B_{\eta}^2+1}}$ within statistical distance of at most $8\epsilon$, and in particular independent of $\mathbf{e}'$. So the third component is correctly distributed again because $\langle \mathbf{z}, \mathbf{U}_z\mathbf{e} \rangle = 0$. Finally, since $\mathbf{e}'$ is independent of the first and third components, and that $\mathbf{U}_z\mathbf{e}'$ is uniform over $(q^{-1}R/R)^m$ as $\mathbf{U}_z$ is invertible modulo $qR$, it yields that the second component is uniform and independent of the other ones as required. $\square$

The condition on the modulus $q$ in Lemma 3.2 and 3.3 stems from the invertibility result by Lyubashevsky and Seiler [32] stated in Lemma 2.4. Recall that these conditions can be simplified in the case of power-of-two cyclotomic fields as discussed in Remark 2.1.

We now use a standard hybrid argument to show that ext-M-LWE with $\ell$ hints is at least as hard as ext-M-LWE with one hint, at the expense of reducing the advantage by a factor of $\ell$. The proof can be found in Appendix B.2 for completeness.

**Lemma 3.4 (Adapted from [17, Lem. 4.8]).** Let $K$ be a number field of degree $n$, $R$ its ring of integers, and $k, m, q, \ell$ be positive integers such that $\ell \le \text{poly}(n)$. Let $\psi$ be a discrete distribution over $q^{-1}R$, and $\mathcal{Z} \subseteq \mathbb{R}^m$. There is a PPT reduction from ext-M-LWE$_{n,k,m,q,\psi,\mathcal{Z}}^1$ to ext-M-LWE$_{n,k,m,q,\psi,\mathcal{Z}}^{\ell}$ that reduces the advantage by a factor of $\ell$.

### 3.2.3 Reduction to $\eta$-M-LWE.
We now provide the final step of the overall reduction, by reducing to the M-LWE problem with $\eta$-bounded secret using a sequence of hybrids. The idea is to use the set $\mathcal{Z}$ of the ext-M-LWE problem as our set of secrets.

To facilitate understanding, we start by illustrating the high level idea of the proof of Lemma 3.5 in Figure 3.3. Given an instance of $\eta$-M-LWE by $(\mathbf{A}, \mathbf{Az}+\mathbf{e})$, our goal is to show that it is computationally indistinguishable from $(\mathbf{A}, \mathbf{b})$, where $\mathbf{b}$ is a uniformly random vector. To do so, we first decompose the error vector $\mathbf{e}$ into $-\mathbf{Nz}+\mathbf{e}'$, by using properties of Gaussian distributions. We then make use of a similar lossy argument as for the previous reduction of Section 3.1 by replacing the random matrix $\mathbf{A}$ by a lossy matrix $\mathbf{A}' = \mathbf{BC}+\mathbf{N}$. As opposed to the proof from Section 3.1, we can't simply argue with the hardness of multiple-secrets M-LWE as the second part of the sample depends on the noise matrix $\mathbf{N}$. This is the motivation for introducing the ext-M-LWE problem, where we allow for additional information with respect to the noise. We then use the same leftover hash lemma as before to replace the product $\mathbf{Cz}$ by a uniformly random vector $\mathbf{s}$. Assuming the hardness of M-LWE, the term $\mathbf{Bs}+\mathbf{e}'$ is computationally
indistinguishable from a uniform vector $\mathbf{u}$. We conclude the proof by re-replacing the lossy matrix $\mathbf{A}'$ by the original uniform matrix $\mathbf{A}$.

<figure><img src="image_7.png" /><figcaption>Fig. 3.3. Summary of the proof of Lemma 3.5</figcaption></figure>

**Lemma 3.5 (Adapted from [17, Lem. 4.9]).** Let $K = \mathbb{Q}(\zeta)$ be a number field of degree $n$, such that its ring of integers is $R = \mathbb{Z}[\zeta]$. Let $k, m, d, \eta$ and $q$ be positive integers with $q$ prime and $d \log_2(2\eta + 1) \ge k \log_2 q + \omega(\log_2 n)$. Let $\varepsilon, \alpha, \gamma, \beta$ be such that $\varepsilon \in (0, 1/2)$, $\alpha \ge \sqrt{2}\eta\varepsilon(q^{-1}R^d)$, $\gamma = \alpha B_\eta \sqrt{d}$, and $\beta = \alpha B_\eta \sqrt{2d}$, where $B_\eta = \max_{x \in S_\eta} \|\sigma(x)\|_\infty$. There is a PPT reduction from the problems ext-M-LWE$^{m}_{n,k,d,q,\psi,S_\eta^d}$, M-LWE$_{n,k,m,q,D_\gamma}$ and ext-M-LWE$^{m}_{n,k,d,q,\psi,\{0\}^d}$ with $\psi = D_{q^{-1}R,\alpha}$ to $\eta$-M-LWE$_{n,d,m,q,\Psi_{\le \beta}}$. Hence, for any distinguishing algorithm $\mathcal{A}$ for the $\eta$-M-LWE$_{n,d,m,q,\Psi_{\le \beta}}$ problem, there exist algorithms $\mathcal{B}_1, \mathcal{B}_2, \mathcal{B}_3$ for ext-M-LWE$^{m}_{n,k,d,q,\psi,S_\eta^d}$, M-LWE$_{n,k,m,q,D_\gamma}$ and ext-M-LWE$^{m}_{n,k,d,q,\psi,\{0\}^d}$ respectively such that the following inequality holds.

$$ \mathrm{Adv}[\mathcal{A}] \le \mathrm{Adv}[\mathcal{B}_1] + \mathrm{Adv}[\mathcal{B}_2] + \mathrm{Adv}[\mathcal{B}_3] + 2m\varepsilon + \frac{1}{2} \sqrt{ \left( 1 + \frac{q^k}{(2\eta+1)^d} \right)^n - 1 } $$

The problem ext-M-LWE$^{m}_{n,k,d,q,\alpha,\{0\}^d}$ mentioned in the lemma statement is trivially harder than ext-M-LWE$^{m}_{n,k,d,q,\alpha,S_\eta^d}$, that is also why it is not specified in Figure 3.2.

*Proof.* Given an $\eta$-M-LWE$_{n,d,m,q,\Psi_{\le \beta}}$ sample $(\mathbf{A}, q^{-1}\mathbf{Az} + \mathbf{e} \bmod R)$, with $\mathbf{A} \leftarrow U(R_q^{m \times d})$, $\mathbf{z} \leftarrow U(S_\eta^d)$ and $\mathbf{e} \in K_\mathbb{R}^m$ sampled from the continuous Gaussian $D_\mathbf{r}^m$ with parameter vector $\mathbf{r}$ with $r_j^2 = \gamma^2 + \alpha^2 \sum_i |\sigma_j(z_i)|^2$. We have $\|\mathbf{r}\|_\infty =$
$\sqrt{\gamma^2 + \alpha^2 \|\mathbf{z}\|_{2,\infty}^2}$, as well as $\|\mathbf{z}\|_{2,\infty}^2 \le \sum_{i \in [d]} \|\sigma(z_i)\|_{\infty}^2$. Recalling the parameter $B_{\eta} = \max_{x \in S_{\eta}} \|\sigma(x)\|_{\infty}$, that can be bounded above by $n\eta$ for cyclotomics by Lemma 2.1, we get $\|\mathbf{r}\|_{\infty} \le \sqrt{\gamma^2 + B_{\eta}^2 d\alpha^2} = B_{\eta}\sqrt{2d\alpha} = \beta$. The objective is to show that $(\mathbf{A}, q^{-1}\mathbf{A}\mathbf{z} + \mathbf{e} \bmod R)$ is computationally indistinguishable from uniform. To do so, we define different hybrid distributions as follows, and prove that each one is indistinguishable from the next.

- $H_0$: Output $(\mathbf{A}, q^{-1}\mathbf{A}\mathbf{z} + \mathbf{e} \bmod R)$ as in $\eta$-M-LWE$_{n,d,m,q,\psi \le \beta}$;

- $H_1$: Output $(\mathbf{A}, q^{-1}\mathbf{A}\mathbf{z} - \mathbf{N}\mathbf{z} + \mathbf{e}' \bmod R)$, where $\mathbf{N} \leftarrow D_{q^{-1}R, \alpha}^{m \times d}$ and $\mathbf{e}' \leftarrow D_{\gamma}^{m}$ and $\mathbf{A}, \mathbf{z}$ as in $H_0$;

- $H_2$: Output $(\mathbf{A}', q^{-1}\mathbf{A}'\mathbf{z} - \mathbf{N}\mathbf{z} + \mathbf{e}' \bmod R) = (\mathbf{A}', q^{-1}\mathbf{B}\mathbf{C}\mathbf{z} + \mathbf{e}' \bmod R)$, where $\mathbf{B} \leftarrow U(R_q^{m \times k})$, $\mathbf{C} \leftarrow U(R_q^{k \times d})$, $\mathbf{A}' = q(q^{-1}\mathbf{C}^T\mathbf{B}^T + \mathbf{N}^T \bmod R)^T$, and $\mathbf{N}, \mathbf{z}, \mathbf{e}'$ as in $H_1$;

- $H_3$: Output $(\mathbf{A}', q^{-1}\mathbf{B}\mathbf{s} + \mathbf{e}' \bmod R)$, where $\mathbf{s} \leftarrow U(R_q^k)$, and $\mathbf{A}', \mathbf{B}, \mathbf{e}'$ as in $H_2$;

- $H_4$: Output $(\mathbf{A}', \mathbf{u})$, where $\mathbf{u} \leftarrow U(\mathbb{T}^m)$, and $\mathbf{A}'$ as in $H_3$;

- $H_5$: Output $(\mathbf{A}, \mathbf{u})$, where $\mathbf{A} \leftarrow U(R_q^{m \times d})$ and $\mathbf{u}$ as in $H_4$.

**From $H_0$ to $H_1$:** We first claim that $\Delta([-\mathbf{N}\mathbf{z} + \mathbf{e}']_i, \mathbf{e}_i) \le 2\varepsilon$ for all $i \in [m]$. Indeed, $(1/\alpha^2 + \|\mathbf{z}\|_{2,\infty}^2/\gamma^2)^{-1/2} \ge \alpha/\sqrt{2}$ and $\alpha/\sqrt{2} \ge \eta_{\varepsilon}(q^{-1}R^d)$. If $\mathbf{n}_i \in q^{-1}R^d$ denotes the $i$-th row of $\mathbf{N}$, Lemma 2.15 yields the claim since we have $[-\mathbf{N}\mathbf{z} + \mathbf{e}']_i = \langle \mathbf{n}_i, -\mathbf{z} \rangle + \mathbf{e}'_i$, thus giving $\Delta(-\mathbf{N}\mathbf{z} + \mathbf{e}', \mathbf{e}) \le 2m\varepsilon$.

$$|\mathbb{P}[\mathcal{A}(H_0) = 1] - \mathbb{P}[\mathcal{A}(H_1) = 1]| \le 2m\varepsilon. \quad (1)$$

**From $H_1$ to $H_2$:** We argue that a distinguisher between $H_1$ and $H_2$ can be used to derive an adversary $\mathcal{B}_1$ for ext-M-LWE$_{n,k,d,q,\alpha,S_{\eta}^d}$ with the same advantage. To do so, $\mathcal{B}_1$ transforms the samples from the challenger of the ext-M-LWE problem to samples defined in $H_1$ or the ones in $H_2$ depending on whether or not the received samples are uniform. In the uniform case, $(\mathbf{C}^T, q^{-1}\mathbf{A}^T, \mathbf{N}\mathbf{z})$ can be efficiently transformed into a sample from $H_1$. Note that $q^{-1}\mathbf{A}^T$ indeed corresponds to the uniform case of ext-M-LWE, because $\mathbf{A}$ is uniform over $R_q$ and $q^{-1}R_q$ can be seen as $q^{-1}R/R$. Additionally, the transpose operator comes from the fact that the hints are $\mathbf{N}\mathbf{z}$, which corresponds to $m$ error vectors of size $d$. So the second component is indeed of size $d \times m$ as required. In the other case, if we apply the same transformation to the ext-M-LWE sample $(\mathbf{C}^T, q^{-1}\mathbf{C}^T\mathbf{B}^T + \mathbf{N}^T \bmod R, \mathbf{N}\mathbf{z})$ where $\mathbf{B}^T$ and $\mathbf{N}^T$ are the secret and error matrix respectively, it leads to a sample from $H_2$. The (randomized) transformation can be described by sampling $\mathbf{e}'$ from $D_{\gamma}^m$ and outputting $f(\mathbf{X}_1, \mathbf{X}_2, \mathbf{x}_3) = (q\mathbf{X}_2^T, \mathbf{X}_2^T\mathbf{z} - \mathbf{x}_3 + \mathbf{e}' \bmod R)$. Hence, $\mathcal{B}_1$ is a distinguisher for ext-M-LWE$_{n,k,d,q,\alpha,S_{\eta}^d}$, and

$$|\mathbb{P}[\mathcal{A}(H_1) = 1] - \mathbb{P}[\mathcal{A}(H_2) = 1]| = \mathrm{Adv}[\mathcal{B}_1]. \quad (2)$$

**From $H_2$ to $H_3$:** The Ring Leftover Hash Lemma stated in Lemma 2.8 yields that $(\mathbf{C}, \mathbf{C}\mathbf{z})$ is within statistical distance at most $\delta = \frac{1}{2}\sqrt{(1 + q^k/(2\eta + 1)^d)^n - 1}$
from (C, s). Note that the condition $d \log_2(2\eta + 1) \ge k \log_2 q + \omega(\log_2 n)$ implies $\delta \le n^{-\omega(1)}$. This yields

$$|\mathbb{P}[\mathcal{A}(H_2) = 1] - \mathbb{P}[\mathcal{A}(H_3) = 1]| \le \delta. \qquad (3)$$

**From $H_3$ to $H_4$:** A distinguisher between $H_3$ and $H_4$ can be used to derive an adversary $\mathcal{B}_2$ for M-LWE$_{n,k,m,q,\gamma}$. For that, $\mathcal{B}_2$ applies the efficient transformation to the samples from the M-LWE challenger, which turns $(\mathbf{B}, \mathbf{u})$ into a sample from $H_4$ in the uniform case, and $(\mathbf{B}, q^{-1}\mathbf{B}\mathbf{s} + \mathbf{e}' \bmod R)$ into a sample from $H_3$ in the M-LWE case. The transformation is given by $g(\mathbf{X}_1, \mathbf{x}_2) = (\mathbf{X}_1\mathbf{C} + q\mathbf{N} \bmod qR, \mathbf{x}_2)$, where $\mathbf{C}, \mathbf{N}$ are sampled as in $H_2$. Therefore, $\mathcal{B}_2$ is a distinguisher for M-LWE$_{n,k,m,q,\gamma}$ such that

$$|\mathbb{P}[\mathcal{A}(H_3) = 1] - \mathbb{P}[\mathcal{A}(H_4) = 1]| = \mathrm{Adv}[\mathcal{B}_2]. \qquad (4)$$

**From $H_4$ to $H_5$:** We now change $\mathbf{A}'$ back to uniform. With the same argument as before, we can construct an adversary $\mathcal{B}_3$ for ext-M-LWE$_{n,k,d,q,\alpha,\{0\}^d}$ (which corresponds to multiple-secret M-LWE without hint) based on a distinguisher between $H_4$ and $H_5$. It transforms $(\mathbf{C}^T, q^{-1}(\mathbf{A}')^T, \mathbf{N} \cdot \mathbf{0})$ into a sample from $H_4$ (M-LWE case) and $(\mathbf{C}^T, q^{-1}\mathbf{A}^T, \mathbf{N} \cdot \mathbf{0})$ into a sample from $H_5$ (uniform case). The transformation samples $\mathbf{u} \leftarrow U(\mathbb{T}^m)$ as in $H_4$ and outputs $h(\mathbf{X}_1, \mathbf{X}_2, \mathbf{x}_3) = (q\mathbf{X}_2^T, \mathbf{u})$. We then get

$$|\mathbb{P}[\mathcal{A}(H_4) = 1] - \mathbb{P}[\mathcal{A}(H_5) = 1]| = \mathrm{Adv}[\mathcal{B}_3]. \qquad (5)$$

Putting Equations (1), (2), (3), (4), (5) altogether yields the result. $\square$

# 4 Computational Hardness of M-LWE with Small Error

In this section, we focus on the hardness of M-LWE when the error distribution is uniform over $S_{\eta}^m$ instead of Gaussian as in the standard formulation of M-LWE. The overall proof strategy follows the idea of Micciancio and Peikert [38], that we adapt to modules. It uses a different proof method as the one we used in Section 3 as it relies on proving that the M-LWE function is one-way with small uniform inputs (errors). On top of that, we provide a more fine-grained analysis to reach concrete parameters. The security of practical schemes is indeed driven by the ring degree $n$ as we wish to use a small rank $d$ for efficiency. The asymptotic approach is then not perfectly suited for achieving very small ranks $d$ and very small error bounds $\eta$ simultaneously. We therefore try to avoid asymptotic results and bounds as much as possible. Even with our approach, we cannot set $d$ and $\eta$ arbitrarily small independently of each other. We first recall the duality between the M-LWE and M-ISIS function families which allows us to switch from one to other at essentially no cost. We then prove our result in terms of M-ISIS as it simplifies the analysis. We briefly discuss the practical implications of our work in Section 4.4.
## 4.1 Duality between M-LWE and M-ISIS

In the following, we adapt the duality results from [36, Sec. 4.2] to the module setting. To the best of our knowledge, this hasn't been formally done before. For completeness, we detail the proofs in Appendix B.3. The idea when going from M-LWE to M-ISIS is to cancel the secret part via a *parity check matrix* **B** that is such that $\mathbf{A}^T\mathbf{B} = \mathbf{0} \bmod qR$. The M-LWE error distribution **e** then becomes the input distribution of the M-ISIS instance with matrix $\mathbf{B}' = \mathbf{BU}$ where **U** simply randomizes **B**. Note that in this paper we are considering a parameter regime such that the function family of M-ISIS is injective. In other words, solutions to M-ISIS are with a very high probability unique. This regime is sometimes referred to as *low-density* ISIS [29] or even more generally as a knapsack problem [36]. For $\mathbf{B}'$ to be well distributed, we need **A** to be non-singular which is characterized by the function $\delta(\cdot, \cdot)$ from Section 2.1. The upper bound derived from Lemma 2.6 for this singularity probability requires $q$ to be unramified in order to have an easier characterization of units of $R_q$. Also, note that the following lemmas are only meaningful if the extra losses incurred by $\delta(\cdot, \cdot)$ are negligible, which may require to restrict the splitting of $q$. We elaborate on the matter in Section 4.2.3.

**Lemma 4.1 (Adapted from [36, Lem. 4.8]).** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $d, q, m$ be positive integers such that $q$ is an unramified prime, and $m \ge d+1$. Let $\mathcal{X}$ be a probability distribution on $R^m$. If (M-LWE($n, d, m, q, R^m$), $\mathcal{X}$) is $\varepsilon$-uninvertible (resp. one-way, pseudorandom), then (M-ISIS($n, m-d, m, q, R^m$), $\mathcal{X}$) is $\varepsilon'$-uninvertible (resp. one-way, pseudorandom), with $\varepsilon' = \delta(m, m-d) + \varepsilon/(1-\delta(m, d))$ (resp. $\varepsilon' = 2\delta(m, m-d) + \varepsilon/(1-\delta(m, d))$ for pseudorandomness).

**Lemma 4.2 (Adapted from [36, Lem. 4.9]).** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $d, q, m$ be positive integers such that $q$ is an unramified prime, and $m \ge d+1$. Let $\mathcal{X}$ be a probability distribution on $R^m$. If (M-ISIS($n, m-d, m, q, R^m$), $\mathcal{X}$) is $\varepsilon$-uninvertible (resp. one-way, pseudorandom), then (M-LWE($n, d, m, q, R^m$), $\mathcal{X}$) is $\varepsilon'$-uninvertible (resp. one-way, pseudorandom), with $\varepsilon' = \delta(m, d) + \varepsilon/(1-\delta(m, m-d))$ (resp. $\varepsilon' = 2\delta(m, d) + \varepsilon/(1-\delta(m, m-d))$ for pseudorandomness).

## 4.2 Hardness of M-LWE with Small Error

We now focus on proving the one-wayness of the M-LWE function family with respect to a short uniform input (i.e., error) distribution, assuming the pseudorandomness of the M-LWE function family with Gaussian input. It therefore implies the hardness of search M-LWE with small uniform error from that of the decision version of M-LWE with Gaussian error. To prove the one-wayness of the M-LWE function, we prove the result in terms of M-ISIS and use Lemma 4.2 to conclude. Recall that by Lemma 2.16, it suffices to prove that M-ISIS is uninvertible and second preimage resistant with respect to this specific input distribution. We actually prove the second preimage resistance of the M-ISIS
function, and the uninvertibility of a decomposition of the M-ISIS function. We
then argue that these two function families are indistinguishable based on the
pseudorandomness of M-ISIS (or M-LWE equivalently). The idea of the proof is
summarized in Figure 4.1.

<figure><img src="image_8.png" /><figcaption>**Fig. 4.1.** Summary of the proof of Theorem 4.1. **S** denotes the search version, while **D** denotes the decision version. The first subscript for M-LWE denotes the rank, while the second subscript denotes the number of samples. For clarity, we removed, for both M-LWE and M-ISIS, the subscripts for the ring degree *n* and the modulus *q* as they are preserved throughout the proof. We have *l* = *m* − *d* + *k*.</figcaption></figure>

**4.2.1 Uninvertibility.** In order to prove the uninvertibility of the function family (M-ISIS($n, m-d, m, q, R^m$), $U(S_\eta^m)$), we decompose it into a linear (Gaussian) function family $\mathcal{L}$ and a smaller M-ISIS($n, m-d, \ell, q, R^\ell$) function family with $\ell \le m$. By Lemma 2.18, it suffices to prove the uninvertibility of $(\mathcal{L}, U(S_\eta^m))$. We first define what we mean by linear (Gaussian) function.

**Definition 4.1.** Let $K$ be a number field, and $R$ its ring of integers. Let $\ell, m$ be positive integers such that $m \ge \ell$, $\alpha > 0$, and $X \subseteq R^m$. We define the function family $\mathcal{L}(\ell, m, \alpha, X)$ obtained by sampling $\mathbf{Y}$ from $\mathcal{D}_{R,\alpha}^{\ell \times (m-\ell)}$, and outputting $h_{\mathbf{Y}}: X \to R^\ell$ defined by $\forall \mathbf{x} \in X$, $h_{\mathbf{Y}}(\mathbf{x}) = [\mathbf{I}_\ell | \mathbf{Y}]\mathbf{x}$, where $|$ denotes the horizontal concatenation.

We now use Lemma 2.17 to prove that $(\mathcal{L}(\ell, m, \alpha, X), U(X))$ is statistically
uninvertible with uniform inputs for carefully chosen parameters. In particu-
lar, the result is only meaningful when $\epsilon_3$ is negligible. This leads to involved conditions on the parameters, which we discuss in Section 4.2.3.

**Lemma 4.3.** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $\ell, m, d$ be positive integers such that $m \ge \max(d, \ell)$, and $\alpha > 0$. Let $\eta$ be a positive integer and $X \subseteq S_{\eta}^m$. We define the function family $\mathcal{F} = \text{M-ISIS}(n, m-d, \ell, q, R^{\ell}) \circ \mathcal{L}(\ell, m, \alpha, X)$. Then, for any $t \ge 0$, $(\mathcal{F}, U(X))$ is (statistically) $\epsilon_3$-uninvertible for

$$ \epsilon_3 = \frac{1}{|X|\sqrt{\pi n \ell}} \left( \eta \sqrt{2\pi e} \left( 1 + \alpha \sqrt{\frac{m-\ell}{\ell}} \left( C\sqrt{\ell} + C\sqrt{m-\ell} + t \right) \right) \right)^{n\ell} + 2ne^{-\pi t^2}, $$

where $C > 0$ is an absolute constant (empirically $C \approx 1/\sqrt{2\pi}$). When $t = \omega(\sqrt{\log_2 n})$, the second term is negligible.

*Proof.* We first bound $\mathbb{E}_{h_Y \sim \mathcal{L}}[|h_Y(X)|]$ and use Lemma 2.17 to conclude. Let $h_Y$ be sampled from $\mathcal{L}(\ell, m, \alpha, X)$. Let $\mathbf{x} = [\mathbf{x}_1^T \mid \mathbf{x}_2^T]^T \in X$, with $\mathbf{x}_1 \in S_{\eta}^{\ell}$, and $\mathbf{x}_2 \in S_{\eta}^{m-\ell}$. Then, $h_Y(\mathbf{x}) = \mathbf{x}_1 + \mathbf{Y}\mathbf{x}_2$. As seen in Section 2.1, it holds that $\tau(h_Y(\mathbf{x})) = \tau(\mathbf{x}_1) + M_{\tau}(\mathbf{Y})\tau(\mathbf{x}_2)$, and therefore

$$ \|\tau(h_Y(\mathbf{x}))\|_2 \le \|\tau(\mathbf{x}_1)\|_2 + \|M_{\tau}(\mathbf{Y})\|_2 \cdot \|\tau(\mathbf{x}_2)\|_2. $$

Since $\mathbf{x}_1$ and $\mathbf{x}_2$ are vectors over $S_{\eta}$, it holds that $\|\tau(\mathbf{x}_1)\|_2 \le \eta\sqrt{n\ell}$ and that $\|\tau(\mathbf{x}_2)\|_2 \le \eta\sqrt{n(m-\ell)}$. By Lemma 2.3, we also have

$$ \|M_{\tau}(\mathbf{Y})\|_2 = \max_{k \in [n]} \|\sigma_k(\mathbf{Y})\|_2. $$

As $\sigma_k(\mathbf{Y})$ is a discrete Gaussian of parameter $\alpha$, Lemma 2.9 gives that for all $k \in [n]$ and all $t \ge 0$

$$ \mathbb{P}_{\mathbf{Y} \sim \mathcal{D}_{R, \alpha}^{\ell \times (m-\ell)}} \left[ \|\sigma_k(\mathbf{Y})\|_2 > C\alpha(\sqrt{\ell} + \sqrt{m-\ell} + t) \right] \le 2e^{-\pi t^2}, $$

for an absolute constants $C > 0$, ($C \approx 1/\sqrt{2\pi}$). A union bound then yields

$$ \mathbb{P}_{\mathbf{Y} \sim \mathcal{D}_{R, \alpha}^{\ell \times (m-\ell)}} \left[ \|M_{\tau}(\mathbf{Y})\|_2 > C\alpha(\sqrt{\ell} + \sqrt{m-\ell} + t) \right] \le 2n \cdot e^{-\pi t^2}. $$

For $t = \omega(\sqrt{\log_2 n})$, the bound becomes negligible. Hence, with probability at least $1 - 2ne^{-\pi t^2}$, we have that $\tau(h_Y(\mathbf{x}))$ is bounded by

$$ r = \sqrt{n\eta} \left( \sqrt{\ell} + C\alpha\sqrt{m-\ell}(\sqrt{\ell} + \sqrt{m-\ell} + t) \right). $$

The number of integer points in the $n\ell$-dimensional ball of radius $r$ is the dimensionless volume of the ball which is $(\sqrt{\pi}r)^{n\ell}/\Gamma(n\ell/2 + 1)$. Yet, it holds
that $\Gamma(x+1) > \sqrt{2\pi x}(x/e)^x$. Therefore, we have that

$$ egin{aligned} |h_{\mathbf{Y}}(X)| & \le \frac{1}{\sqrt{\pi n \ell}} \left( \sqrt{\frac{2\pi e}{n\ell}} \cdot r \right)^{n\ell} \\ & \le \frac{1}{\sqrt{\pi n \ell}} \left( \eta \sqrt{2\pi e} \left( 1 + C\alpha \sqrt{\frac{m-\ell}{\ell}} \left( \sqrt{\ell} + \sqrt{m-\ell} + t \right) \right) \right)^{n\ell} . \end{aligned} $$

As the bound is independent of $\mathbf{Y}$, let us temporarily denote it by $B$. We also define $S = \{\mathbf{Y} \in \mathbb{R}^{\ell \times (m-\ell)} : \|M_{\tau}(\mathbf{Y})\| \le C\alpha(\sqrt{\ell} + \sqrt{m-\ell} + t)\}$, and $S'$ its complement in $\mathbb{R}^{\ell \times (m-\ell)}$. We then have

$$ egin{aligned} \mathbb{E}[|h_{\mathbf{Y}}(X)|] & = \sum_{\mathbf{Y}' \in S} \mathbb{P}_{\mathbf{Y}}[\mathbf{Y} = \mathbf{Y}'] |h_{\mathbf{Y}'}(X)| + \sum_{\mathbf{Y}' \in S'} \mathbb{P}_{\mathbf{Y}}[\mathbf{Y} = \mathbf{Y}'] |h_{\mathbf{Y}'}(X)| \\ & \le B \cdot \mathbb{P}_{\mathbf{Y}}[\mathbf{Y} \in S] + |X| \cdot \mathbb{P}_{\mathbf{Y}}[\mathbf{Y} \in S'] \\ & \le B + |X| \cdot 2ne^{-\pi t^2}, \end{aligned} $$

where the first inequality follows from the above calculations and the fact that for $\mathbf{Y}' \in S'$, we have the trivial bound $|h_{\mathbf{Y}'}(X)| \le |X|$. Lemma 2.17 then yields the $\varepsilon_3$-uninvertibility of $\mathcal{L}$, with $\varepsilon_3 = B/|X| + 2ne^{-\pi t^2}$. By Lemma 2.18, we thus obtain the $\varepsilon_3$-uninvertibility of $\mathcal{F}$. $\square$

### 4.2.2 Second Preimage Resistance of M-ISIS.
We now prove the (statistical) second preimage resistance of the M-ISIS function family with respect to the uniform distribution over an $\eta$-bounded domain.

**Lemma 4.4.** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $k, q, m, \eta$ be positive integers such that $q$ is prime. Let $X \subseteq S_{\eta}^m$. Then (M-ISIS($n, k, m, q, X$), $U(X)$) is (statistically) $\varepsilon_4$-second preimage resistant for

$$ \varepsilon_4 = (|X| - 1) \cdot \left( \frac{B_{2\eta}}{q} \right)^{nk}, $$

where $B_{2\eta} = \max_{x \in S_{2\eta}} \|\sigma(x)\|_{\infty}$.

*Proof.* To prove it statistically, we show that for $\mathbf{A}, \mathbf{x}$ uniformly chosen, the probability that there exists $\mathbf{x}' \ne \mathbf{x}$ such that $\mathbf{A}^T\mathbf{x}' = \mathbf{A}^T\mathbf{x} \bmod qR$ is less than $\varepsilon_4$, namely

$$ p := \mathbb{P}_{\substack{\mathbf{A} \leftarrow U(R_q^{m \times k}) \\ \mathbf{x} \leftarrow U(X)}} [\exists \mathbf{x}' \in X \setminus \{\mathbf{x}\}, \mathbf{A}^T \mathbf{x}' = \mathbf{A}^T \mathbf{x} \bmod qR]. $$
Using the total probability formula and the union bound on $\mathbf{x}'$, we have the following.

$$
\begin{align*}
p &= \sum_{\mathbf{x}^* \in X} \mathbb{P}_{\mathbf{x}}[\mathbf{x} = \mathbf{x}^*] \cdot \mathbb{P}_{\mathbf{A}, \mathbf{x}}[\exists \mathbf{x}' \in X \setminus \{\mathbf{x}\}, \mathbf{A}^T \mathbf{x}' = \mathbf{A}^T \mathbf{x} \bmod qR | \mathbf{x} = \mathbf{x}^*] \\
&= \sum_{\mathbf{x}^* \in X} |X|^{-1} \cdot \mathbb{P}_{\mathbf{A}}[\exists \mathbf{x}' \in X \setminus \{\mathbf{x}^*\}, \mathbf{A}^T (\mathbf{x}' - \mathbf{x}^*) = \mathbf{0} \bmod qR] \\
&\le |X|^{-1} \sum_{\mathbf{x}^* \in X} \sum_{\mathbf{x}' \in X \setminus \{\mathbf{x}^*\}} \mathbb{P}_{\mathbf{A}}[\mathbf{A}^T (\mathbf{x}' - \mathbf{x}^*) = \mathbf{0} \bmod qR].
\end{align*}
$$

Let $\mathbf{x}^* \in X$, $\mathbf{x}' \in X \setminus \{\mathbf{x}^*\}$, and set $\mathbf{z} = \mathbf{x}' - \mathbf{x}^*$. Then, by [34, Lem. 4.4], $\mathbf{A}^T \mathbf{z} \bmod qR$ is uniformly distributed in $(\mathcal{I}_{\mathbf{z}}/qR)^k$ over the randomness of $\mathbf{A}$, where $\mathcal{I}_{\mathbf{z}} = \langle z_1 \rangle + \dots + \langle z_m \rangle + \langle q \rangle$. Hence the probability that $\mathbf{A}^T \mathbf{z} = \mathbf{0} \bmod qR$ is $|\mathcal{I}_{\mathbf{z}}/qR|^{-k}$. As $\mathcal{I}_{\mathbf{z}}$ and $qR$ are ideals of $R$, we have $|\mathcal{I}_{\mathbf{z}}/qR| = N(qR)/N(\mathcal{I}_{\mathbf{z}}) = q^n/N(\mathcal{I}_{\mathbf{z}})$. Yet, for all $i \in [m]$, $\langle z_i \rangle \subseteq \mathcal{I}_{\mathbf{z}}$, meaning that $N(\mathcal{I}_{\mathbf{z}})$ divides $N(\langle z_i \rangle)$. Similarly, $N(\mathcal{I}_{\mathbf{z}})$ divides $N(\langle q \rangle) = q^n$. Hence

$$
N(\mathcal{I}_z) \le \gcd(q^n, N(\langle z_1 \rangle), \dots, N(\langle z_m \rangle)),
$$

which yields the (loose) bound

$$
N(\mathcal{I}_z) \le \min \left( q^n, \min_{i \in [m]: z_i \ne 0} N(\langle z_i \rangle) \right).
$$

Since $\mathbf{z} \ne \mathbf{0}$, there exists $i \in [m]$ such that $z_i \ne 0$. Note that we have $\mathbf{z} \in \{\mathbf{a} - \mathbf{b}; (\mathbf{a}, \mathbf{b}) \in X^2\} \subseteq S_{2\eta}^m$. It thus holds

$$
N(\langle z_i \rangle) = |N(z_i)| = \prod_{j \in [n]} |\sigma_j(z_i)| \le B_{2\eta}^n,
$$

by Lemma 2.1 where $B_{2\eta} = \max_{x \in S_{2\eta}} \|\sigma(x)\|_{\infty}$. Recall that in cyclotomic fields we have $B_{2\eta} \le 2\eta n$. Hence $\mathbb{P}_{\mathbf{A}}[\mathbf{A}^T \mathbf{z} = \mathbf{0} \bmod qR] \le (B_{2\eta}/q)^{nk}$. Going back to our original calculation, we then have $p \le |X|^{-1}|X|(|X| - 1) \cdot (B_{2\eta}/q)^{nk} = \varepsilon_4$ which concludes the proof. $\square$

**Remark 4.1.** For common choices of $n, m$ and prime $q$, we heuristically observe that the ideals $\langle z_1 \rangle, \dots, \langle z_m \rangle, \langle q \rangle$ are relatively prime with high probability, which means that $\mathcal{I}_z = R$ in the proof above. In this case, $N(\mathcal{I}_z) = 1$ which yields a much better bound on the probability. Since the probability sums over all the possible $\mathbf{x}'$, one would need to evaluate the proportion of $\mathbf{z}$ generated as above that verify $\mathcal{I}_z = R$. We leave it as an open problem.

For example, consider the case of cyclotomic fields. By Lemma 2.4 (or Remark 2.1 for power-of-two conductors), if $q$ splits into few factors and is large enough with respect to $\eta$ so that $S_{2\eta} \setminus \{0\} \bmod qR \subset R_q^\times$, then we have that for all $\mathbf{z} \in S_{2\eta}^m \setminus \{0\}$, $\mathcal{I}_z = R$. Indeed, for such $\mathbf{z}$, there exists $i \in [m]$ such that $z_i \in S_{2\eta} \setminus \{0\}$ and therefore $z_i \bmod qR \in R_q^\times$. This implies that $\langle z_i \rangle + \langle q \rangle = R$ and as a result $\mathcal{I}_z = R$. Hence, we can improve the bound on the probability to $\varepsilon_4 = (|X| - 1)/q^{nk}$ if we accept to enforce a specific splitting on $q$.
### 4.2.3 One-wayness of M-LWE with Small Uniform Error.
Using the results from Sections 4.2.1 and 4.2.2, we can give the main theorem of this section. Under the assumption that the M-LWE function family is pseudorandom with respect to a Gaussian error distribution, it proves that the M-LWE function family is one-way with respect to a small uniform error distribution. Recall that if a function is one-way, then it is also uninvertible. Hence, this shows that the search version M-SLWE with small uniform error is at least as hard as the decision version M-LWE with Gaussian error.

**Theorem 4.1.** Let $K$ be a number field of degree $n$, and $R$ its ring of integers. Let $d, m, k$ be positive integers such that $m > d \ge k \ge 1$. Let $q$ be an unramified prime such that $\min_{i \in [k]} N(p_i)^{\min(m-d,k)+1} \ge n^{\omega(1)}$, where the $p_i$'s are the prime ideal factors of $\langle q \rangle$. Let $\eta$ be a positive integer, and $X \subseteq S_\eta^m$. We define $\ell = m - d + k$. Assume that the function family (M-LWE($n, k, \ell, q, R^\ell$), $D_{R,\alpha}^\ell$) is $\varepsilon_1$-pseudorandom for $\alpha > 0$. Then (M-LWE($n, d, m, q, X$), $U(X)$) is $\varepsilon$-one-way for

$$ \varepsilon = \delta(m, d) + \frac{(m - \ell)(2\delta(\ell, m - d) + \varepsilon_1/(1 - \delta(\ell, k))) + \varepsilon_3 + \varepsilon_4}{1 - \delta(m, m - d)}, $$

where $\varepsilon_3, \varepsilon_4$ are defined in the statement of Lemma 4.3 and 4.4 respectively.

*Proof.* Define the function families $\mathcal{F} = \text{M-ISIS}(n, m-d, \ell, q, R^\ell) \circ \mathcal{L}(\ell, m, \alpha, X)$, and $\mathcal{G} = \text{M-ISIS}(n, m-d, m, q, X)$.

*Indistinguishability:* Using Lemma 4.1, the pseudorandomness of the M-LWE function family implies that (M-ISIS($n, m-d, \ell, q, R^\ell$), $D_{R,\alpha}^\ell$) is $\varepsilon_2$-pseudorandom with

$$ \varepsilon_2 = 2\delta(\ell, \ell - k) + \frac{\varepsilon_1}{1 - \delta(\ell, k)}. $$

Take $f_A \circ h_Y$ according to $\mathcal{F}$, and $f_{A'}$ according to $\mathcal{G}$. Then $f_A \circ h_Y$ is the linear map $x \mapsto [A^T | A^T Y]x$. Decomposing $A'^T$ into $[(A'_1)^T | (A'_2)^T]$, with $A'_1 \in R_q^{\ell \times (m-d)}$, $A'_2 \in R_q^{(m-\ell) \times (m-d)}$, we have that $f_{A'} = x \mapsto [(A'_1)^T | (A'_2)^T]x$. By the $\varepsilon_2$-pseudorandomness of M-ISIS with respect to $D_{R,\alpha}^\ell$, a hybrid argument yields that $\mathcal{F}$ and $\mathcal{G}$ are $(m - \ell)\varepsilon_2$-indistinguishable.

*Uninvertibility:* By Lemma 4.3, it holds that $(\mathcal{F}, U(X))$ is $\varepsilon_3$-uninvertible, where $\varepsilon_3$ is defined in Lemma 4.3.

*Second Preimage Resistance:* By Lemma 4.4, it holds that $(\mathcal{G}, U(X))$ is $\varepsilon_4$-second preimage resistant for

$$ \varepsilon_4 = (|X| - 1) \cdot \left( \frac{B_{2\eta}}{q} \right)^{n(m-d)}. $$

We thus have that $(\mathcal{F}, \mathcal{G}, U(X))$ is a lossy function family, depending on $\varepsilon_2, \varepsilon_3, \varepsilon_4$. Lemma 2.16 yields that $(\mathcal{G}, U(X))$ is $\varepsilon_0$-one-way with $\varepsilon_0 = (m - \ell)\varepsilon_2 + \varepsilon_3 + \varepsilon_4$. Using Lemma 4.2, it gives that (M-LWE($n, d, m, q, X$), $U(X)$) is $\varepsilon$-one-way with

$$ \varepsilon = \delta(m, d) + \frac{\varepsilon_0}{1 - \delta(m, m - d)}. $$
Combining everything, we get

$$ \varepsilon = \delta(m, d) + \frac{(m - \ell)(2\delta(\ell, m - d) + \varepsilon_1/(1 - \delta(\ell, k))) + \varepsilon_3 + \varepsilon_4}{1 - \delta(m, m - d)}, $$

which yields the claim. The condition on $q$ ensures that all the $\delta(\cdot, \cdot)$ are negligible. Indeed, as noted after Lemma 2.6, if the smallest norm $N$ of the prime ideal factors is such that $N^{a-b+1} \ge n^{\omega(1)}$ for $a \ge b$, then $\delta(a, b) \le n^{-\omega(1)}$. The condition on $q$ thus yields that $\delta(m, d)$, $\delta(m, m-d)$, $\delta(\ell, m-d)$, $\delta(\ell, k)$ are negligible. $\square$

Let us now discuss the various conditions that are needed to apply this theorem in the context of cyclotomic fields. The lower bound on $q$ comes from ensuring that $\varepsilon_4$ is negligible. Indeed, we have that $|X| = (2\eta + 1)^{nm}$, and therefore it suffices to have

$$ (2\eta + 1)^m \left( \frac{2n\eta}{q} \right)^{m-d} < 1, \qquad (6) $$

which can be written as $q > 2n\eta \cdot (2\eta + 1)^{m/(m-d)}$. Hence, for $\lambda > 0$ one can choose $q > 2^{\lambda/(m-d)} \cdot 2n\eta \cdot (2\eta + 1)^{m/(m-d)}$ which ensures $\varepsilon_4 < 2^{-\lambda n}$. Once this lower bound on $q$ is set, one can easily find the closest prime $q$ with an appropriate splitting as required by the theorem.

The expression of $\varepsilon_3$ is more involved, but the idea is the same. For it to be negligible, we need

$$ \frac{\eta^\ell}{(2\eta + 1)^m (\pi n \ell)^{1/2n}} \left( \sqrt{2\pi e} \left( 1 + C \alpha \sqrt{\frac{m-\ell}{\ell}} \left( \sqrt{\ell} + \sqrt{m-\ell} + t \right) \right) \right)^\ell < 1, \qquad (7) $$

where $t = \omega(\sqrt{\log_2 n})$. Due to the many dependencies in $m, k, d$ and $\eta$, it is harder to extract a closed-form inequality on $m$ given $k, d$ and $\eta$. Instead, we evaluate the inequality with different parameters while trying to minimize $\eta$ and maximize $m$, while ensuring $m > d \ge k \ge 1$. As we aim at proving the hardness of M-LWE with small parameters, one can evaluate Equations (6) and (7) with the goal of minimizing $\eta$, $q$ and $d$, while maximizing $m$ and making sure that $k \ge 1$ ($k \ge 2$ being preferable to rely on modules). It turns out that the condition is not met for all sets of parameters, and $\eta$ cannot be arbitrarily small for arbitrary ranks $k, d$. Nonetheless, we can find settings in which $\eta$ is a small constant, but this might require to take $d$ slightly larger. As expected, when $m - d$ grows for a fixed $d$, the error bound $\eta$ must be larger as well. Table 4.1 give two example sets of parameters that verify the conditions, along with the losses $\varepsilon_3, \varepsilon_4$, one relying on ideals ($k = 1$).

**Remark 4.2.** Note that we can provide the asymptotic behavior $\varepsilon_3 = O(\alpha \cdot m \cdot \eta \cdot t/\sqrt{\ell})^{n\ell}/|X| + 2ne^{-\pi t^2}$, but this approach makes it unclear how to choose the parameters. In particular, as we can use low ranks like $d = O(1)$, we have to make sure that $k \ge 1$ and $m \ge d + 1$, which is not always possible for low
<table><thead><tr><th>n</th><th>k</th><th>d</th><th>m</th><th>η</th><th>q</th><th>ε<sub>3</sub></th><th>ε<sub>4</sub></th></tr></thead><tbody><tr><td>256</td><td>1</td><td>11</td><td>12</td><td>1</td><td>≈ 2<sup>31</sup></td><td>≈ 2<sup>-496</sup> + 2<sup>-281</sup></td><td>2<sup>-256</sup></td></tr><tr><td>256</td><td>2</td><td>14</td><td>16</td><td>10</td><td>≈ 2<sup>48</sup></td><td>≈ 2<sup>-360</sup> + 2<sup>-281</sup></td><td>2<sup>-256</sup></td></tr></tbody></table>

**Table 4.1.** Example parameter sets reaching the conditions of Theorem 4.1. We take $t = \log_2 n$, and $\alpha \approx \log_2 n$ if $k = 1$ and $\alpha \approx 2\sqrt{k}\log_2 n$ if $k > 1$. Empirically, we have $C \approx 1/\sqrt{2\pi}$ as noticed for example in [37, Sec. 2.4]. The loss of $2^{-281}$ that dominates in the value of $\varepsilon_3$ comes from the spectral bound loss $2n \cdot e^{-\pi t^2}$. For such parameters, one can determine the appropriate splitting of $q$ for the $\delta(\cdot, \cdot)$ to be negligible. For the first set of parameters, if $q$ splits into $n/2$ factors, all the $\delta(\cdot, \cdot)$ will be less than $2^{-117}$, but if it splits into $n/4$ factors, they will be less than $2^{-242}$. For the second set of parameters, if $q$ is fully splitted, they can all be bounded by $2^{-136}$ and if $q$ splits into $n/2$ factors, they will be less than $2^{-281}$.

values of $\eta$. The asymptotic approach gives a more direct condition on $m$. Indeed, taking $\alpha = 2\sqrt{k}t$, and denoting by $C'$ the asymptotic constant, we have

$$O(s \cdot m \cdot \eta \cdot t / \sqrt{\ell})^{n\ell} / |X| \le \left( \frac{(2C'mt^2\eta \sqrt{k/\ell})^\ell}{(2\eta + 1)^m} \right)^n$$

Since $\ell > k$, we can choose the parameters to have $(2C'mt^2\eta)^\ell/(2\eta + 1)^m \le 1/2$ to have an exponentially small loss. We thus have

$$\begin{align*}
(2C'mt^2\eta)^\ell / (2\eta + 1)^m \le 1/2 \\
\Leftrightarrow (m - (d - k)) \log_2(2C'mt^2\eta) &\le m \log_2(2\eta + 1) - 1 \\
\Leftrightarrow m(\log_2(2C'mt^2\eta) - \log_2(2\eta + 1)) &\le (d - k) \log_2(2C'mt^2\eta) - 1 \\
\Leftrightarrow m &\le (d - k)(1 + \log_2(2\eta + 1) / \log_2(2C'mt^2\eta / (2\eta + 1))) \\
&\quad - 1 / \log_2(2C'mt^2\eta / (2\eta + 1)).
\end{align*}$$

This leads to a condition on $m$ which is

$$d < m \le (d - k) \left( 1 + \frac{\log_2(2\eta + 1)}{\log_2(2C' \cdot m \cdot t^2 / 3)} \right),$$

which is much similar to the condition in [38]. The main difference stems from the fact that $m$ is no longer our asymptotic parameter, which explains the presence of $t^2 = \omega(\log_2 n)$. It still remains difficult to see which parameter sets meet this condition, mostly because the constant $C'$ can be rather large while we wish $d$ and $k$ to be small constants. Regardless, if we aim at small values of $\eta$, we see that we obtain $m \le d(1+o(1))$. This bound seems true even with our non-asymptotic analysis.
## 4.3 On Hermite Normal Form M-LWE with Small Keys

We now look at the use of our result to obtain the hardness of M-LWE where both the error and secret distribution are uniform over small elements. To do so we combine Theorem 4.1 with a Hermite Normal Form transformation for M-LWE. Langlois and Stehlé [24, Lem. 4.24] proposed an immediate generalization of the reduction from LWE to its Hermite Normal Form by Applebaum et al. [5] to modules. In particular, it relies on the fact that if one has access to sufficiently many M-LWE samples ($\mathbf{a}_i, b_i$), they can find a subset of the $\mathbf{a}_i$ that form a matrix in $GL_d(R_q)$. As our proof of Section 4.2 seemingly limits the number of available samples, it is relevant for us to understand the trade-off between the quality of the reduction (in terms of loss in advantage) and the number of initial samples. More precisely, if one is limited to use $m' \ge d$ samples to construct this invertible matrix, it comes down to evaluating $\delta'(m', d)$. The proof can be found in Appendix B.3 for completeness.

**Lemma 4.5 (Adapted from [5,24]).** Let $K$ be a number field, and $R$ its ring of integers. Let $d, q, m'$ be positive integers such that $q$ is an unramified prime, and $m' \ge d \ge 1$. Let $\mathbf{s}$ be an arbitrary vector of $R_q^d$ and $\psi$ a distribution over $R$. There is an efficient transformation $T$ such that $T(A_{\mathbf{s},\psi}) = A_{\mathbf{x},\psi}$ for some $\mathbf{x}$ sampled from $\psi^d$, and $T(U(R_q^d \times R_q)) = U(R_q^d \times R_q)$. $T$ can be constructed in polynomial time using $m'$ samples from $\mathcal{D} \in \{A_{\mathbf{s},\psi}, U(R_q^d \times R_q)\}$ with probability $1 - \delta'(m', d)$.

This transformation shows a reduction from worst-case (or average-case if $\mathbf{s}$ is uniformly sampled over $R_q^d$ instead of arbitrary) search-M-LWE to search-HNF-M-LWE, but also from decision-M-LWE to decision-HNF-M-LWE. All the parameters are preserved except for the number of samples because we need $m' \ge d$ extra samples to construct the transformation, i.e., construct the invertible matrix $\bar{\mathbf{A}}$ involved in the map with the corresponding $\bar{\mathbf{b}}$. To prove the hardness of HNF-M-LWE with $m''$ samples, we thus need to assume the hardness of M-LWE with $m = m' + m''$ samples. The choice of $m'$ allows for tweaking the success probability of the reduction, but at the expense of requiring more samples. Let us now discuss the loss $\delta'(m', d)$. In the case of integers, $\mathbb{Z}_q$ is generally a field which yields a closed-form expression of this probability. Unfortunately, in the case of $R_q$, it becomes anything but trivial as explained in Appendix A. We can still obtain the following bound

$$ \delta'(m', d) \le \delta'(d, d)^{\lfloor m'/d \rfloor} = \left(1 - \prod_{\ell=0}^{d-1} \prod_{i \in [\kappa]} \left(1 - \frac{1}{N(\mathfrak{p}_i)^{d-\ell}}\right)\right)^{\lfloor m'/d \rfloor}, $$

which we briefly prove here.
Proof. For each $j \in [\lfloor m'/d \rfloor]$, we define $S_j = \{(j-1)d+1, \dots, jd\}$ which is of size $d$. We then have

$$
\begin{align*}
\delta'(m', d) &= \mathbb{P}_{(\mathbf{a}_i)_{i \in [m']}} \sim U(R_q^d)^{m'} \left[ \bigcap_{S \subseteq [m'], |S|=d} \{ (\mathbf{a}_i)_{i \in S} \text{ are not } R_q\text{-l. i.} \} \right] \\
&\le \mathbb{P}_{(\mathbf{a}_i)_{i \in [m']}} \sim U(R_q^d)^{m'} \left[ \bigcap_{j \in [\lfloor m'/d \rfloor]} \{ (\mathbf{a}_i)_{i \in S_j} \text{ are not } R_q\text{-l. i.} \} \right] \\
&= \prod_{j \in [\lfloor m'/d \rfloor]} \mathbb{P}_{(\mathbf{a}_i)_{i \in S_j}} \sim U(R_q^d)^d \{ (\mathbf{a}_i)_{i \in S_j} \text{ are not } R_q\text{-l. i.} \} \\
&= \delta'(d, d)^{\lfloor m'/d \rfloor},
\end{align*}
$$

where the first inequality is just an inclusion of events, the second equality is by independence of the $\mathbf{a}_i$'s as none of the $S_j$ overlap, and the last equality follows from the definition of $\delta'(d, d)$. $\square$

We note that $\delta'(d, d)$ highly depends on the size and splitting of $q$ as it is essentially dominated by $\frac{1}{\min_{i \in [\kappa]} N(\mathfrak{p}_i)}$. Hence, depending on the splitting of $q$, we would need to take $m' = Cd$ with $C$ sufficiently large to make $\delta'(m', d)$ negligible. Our bound is however not tight and we expect $\delta'(m', d)$ to decrease much faster when $m'$ grows. Unfortunately, we were not able to find a better bound on $\delta'(m', d)$ which would support this conjecture. We leave it as an interesting open problem.

As concrete examples, let us take the parameters of Table 4.1. If $q \approx 2^{31}$ splits into $n/4 = 64$ factors of inertia degree 4, for $d = 11$, we have $\delta'(d, d) \approx 2^{-118}$. As a result, $m' = 2d$ ensures $\delta'(m', d) \le 2^{-236}$. However, if $q$ splits into $n/2 = 128$ factors of inertia degree 2, we now have $\delta'(d, d) \approx 2^{-55}$, and we would thus need to take a larger $m'$.

We then obtain the following result by combining Theorem 4.1 with Lemma 4.5.

**Corollary 4.1.** Let $K$ be a number field of degree $n$, and $\mathbb{R}$ its ring of integers. Let $d, m, k$ be positive integers such that $m > d \ge k \ge 1$. Let $q$ be an unramified prime such that $\min_{i \in [\kappa]} N(\mathfrak{p}_i)^{\min(m-d,k)+1} \ge n^{\omega(1)}$, where the $\mathfrak{p}_i$'s are the prime ideal factors of $\langle q \rangle$. Let $m'$ be a positive integer such that $m > m' \ge d$ and $\delta'(m', d) \le n^{-\omega(1)}$. Then, let $\eta$ be a positive integer, and $X \subseteq S_\eta^m$. We define $\ell = m - d + k$. Assuming that the decision version $\mathrm{M-LWE}_{n,k,q,\ell,D_{R,\alpha}}$ is $\varepsilon_1$-hard for $\alpha > 0$, it holds that search version $\eta$-$\mathrm{SLWE}_{n,d,q,m-m',U(T_\eta)}$ is $\varepsilon'$-hard for

$$
\varepsilon' = \delta'(m', d) + \delta(m, d) + \frac{(m - \ell)(2\delta(\ell, m - d) + \varepsilon_1/(1 - \delta(\ell, k))) + \varepsilon_3 + \varepsilon_4}{1 - \delta(m, m - d)},
$$

where $\varepsilon_3, \varepsilon_4$ are defined in the statement of Lemma 4.3 and 4.4 respectively.
## 4.4 A Thought on Practical Hardness

Several cryptanalytic works target the LWE problem, with sometimes increased efficiency when the parameters are small, e.g. particularly small secret, or particularly small error. They leverage either lattice reduction [27,28], combinatorial [55,9,23] or algebraic [6,3] techniques. The latter attack by Arora and Ge specifically targets LWE with small errors. It does not depend on the underlying structure, and therefore also applies to the more general case of M-LWE. The idea is to see the (search) LWE problem as solving a noisy system of equations, and transforming it into a noiseless polynomial system (where the degree of the polynomials depend on the size of the LWE error). Then, using root finding algorithms for multivariate polynomials, one can solve the new system.

More precisely in the case of LWE with $\eta$-bounded error ($e \in \{-\eta, ..., \eta\}^m$), the Arora and Ge attack [6] solves the problem in polynomial time if $m \approx \binom{d+2\eta+1}{2\eta+1} = \Omega(d^{2\eta+1})$, where $d$ is the LWE dimension. For $\eta = 1$, the attack becomes exponential for $m = O(d)$. It has been refined in [3] to obtain subexponential attacks whenever $m = \Omega(d \log_2 \log_2 d)$ in the uncentered binary case ($\{0, 1\}$). As the attack ignores the structure, one can embed the $m$ M-LWE equations with $d$ unknowns over $R_q$ into $nm$ equations with $nd$ unknowns over $\mathbb{Z}_q$ and apply the same attack. However, we now obtain a polynomial attack only for $nm = \Omega((nd)^{2\eta+1})$ and therefore $m = \Omega(n^{2\eta}d^{2\eta+1})$. In practical schemes relying on M-LWE with small errors [10,18], the rank $d$ is a small constant and $n$ drives the security parameter. Additionally, we saw in Section 4.3 that roughly $m = m' + m''$ is enough to establish the hardness of M-LWE with small secret and error with $m''$ samples. For common parameters where $m'' = d$ or $d+1$, we thus have $m = m' + m'' = O(d) \ll n^{2\eta}d^{2\eta+1}$. This is why we think that the hardness of M-LWE with both small secret and error is yet to be determined. The gap between what we proved in this section and the applicable attacks can still be reduced in either direction: either by finding new attacks that require fewer samples, or by improving theoretical hardness results to allow for more samples.

# 5 A Quick Survey on the Hardness of M-LWE

This section aims at gathering all known results on the hardness of the M-LWE problem along with our new contributions, and comparing them whenever possible.

**General Hardness.** Although the M-LWE problem was originally introduced in [16] for power-of-two cyclotomic fields, its hardness was first studied by Lan-glois and Stehlé in [24]. They established the hardness of the standard formula-tion $\mathrm{M-LWE}_{n,d,m,q,\gamma_\alpha}$ based on the quantum hardness of $\mathrm{Mod-GIVP}_{\gamma}^{\eta_\epsilon}$ (which is a generalized version of $\mathrm{SIVP}_\gamma$), where $\alpha = \tilde{\Omega}(d\sqrt{n}/\gamma)$. Although the proof for the decision version requires $q$ to be a fully split prime in the cyclotomic ring, the authors gave a modulus switching reduction showing that the form of $q$
is not restrictive if one accepts a (moderately) increased error. This reduction
proves that if M-LWE$_{n,d,m,q,\Upsilon_\alpha}$ is hard, then so is M-LWE$_{n,d,m,p,\Upsilon'}$ for an ar-
bitrary modulus $p$. This comes at the expense of increasing the error from $\alpha$
to $\alpha' \ge \alpha \cdot \max(1, q/p) \cdot n^{3/4} \sqrt{\log_2 n}$. Then, combined with [12, Lem. 13],
one can obtain the hardness of M-LWE with error in $\mathcal{D}_{R^\vee, \alpha'q}$ for $\alpha' = \alpha\omega(\log_2 n)$
instead of $\Upsilon_\alpha$, and where $R^\vee$ is the dual of $R$. The quantum reduction from [24]
was later used in [4] to derive the hardness of M-LWR (Module Learning With
Rounding) which we do not cover in this discussion.

As discussed in [16], the M-LWE problem offers a trade-off between secu-
rity and efficiency depending on whether the parameters lean towards LWE
(degree $n$ equal to 1) or R-LWE (rank $d$ equal to 1) respectively. In particular,
establishing a hierarchy of hardness between M-LWE and the widely studied and
used R-LWE was up for debate. Albrecht and Deo [1] provided a first answer
by showing that R-LWE with modulus $q^d$ is at least as hard as M-LWE with
modulus $q$ and rank $d$. This actually comes as a byproduct of their more gen-
eral result showing a modulus-rank switching reduction from M-LWE$_{n,d,m,q,D_\alpha}$
to M-LWE$_{n,d',m,q',D_{\alpha'}}$. The moduli and ranks can be arbitrarily chosen provided
that one can efficiently describe the lattice $\Lambda = q'^{-1}\mathbf{G}^T\mathbf{R}^{d'} + \mathbf{R}^d$ for a cho-
sen $\mathbf{G} \in \mathbf{R}^{d' \times d}$. It also requires to increase the error from $\alpha$ to $\alpha' \ge \sqrt{\alpha^2 + \Delta}$,
where $\Delta$ depends on the size of the secret distribution and the quality of the
description of $\Lambda$. As a result, the reduction becomes less interesting for very
large secrets. We refer to [1,2] for the detailed expression of $\Delta$. The reduction
to R-LWE was later improved and generalized by Wang and Wang [56] to hold
over all cyclotomic fields. A revision of the work by Albrecht and Deo, which
can be found in [2], further improved this line of work with a new analysis.
Additionally, a result from Peikert and Pepin [44] tightly proves the hardness
of M-LWE over a number field $K$ of degree $n$ and with rank $d$ assuming the
hardness of R-LWE over any one of a class of number field extensions $K'/K$
with extension degree $d = [K' : K]$. Instead of showing a modulus-rank trade-off
as in [1], they provide a degree-rank trade-off, where the underlying ring struc-
ture is changed, while preserving the modulus $q$. Note that, in contrast to [1],
their reduction allows for an arbitrary large uniform secret.

**Small Distributions Hardness.** The work of this paper focuses on the hardness of M-LWE when the secret and error distributions deviate from the original formulation. The first result in this line of work was due to [24], which extended the reduction by Applebaum et al. [5] to modules. In particular, combined with their main proof of hardness, it can be used to obtain the hardness of M-LWE$_{n,d,m,q,D_{R^\vee,\alpha}}$ with secrets drawn from $\mathcal{D}_{R^\vee,\alpha}^d$. As observed in Lemma 4.5, this is at the expense of using $m' \ge d$ M-LWE samples to construct the transformation.

Section 3 provides proofs of hardness for M-LWE with small bounded secret,
in both the search (Section 3.1) and decision (Section 3.2) variants. As discussed,
they generalize the approaches by Goldwasser et al. [21] and by Brakerski et
al. [17] respectively, which are the analog results for LWE. The prior version
from [12] can be used to derive the classical hardness of M-LWE, meaning that if one has a classical solver for M-LWE, then it can also construct a classical solver for worst-case module lattice problems. This removes the need for quantum algorithms in the reduction of [24], with the caveat of introducing further restrictions on the parameters. More precisely, the result of our previously published work [12] proves the classical hardness of M-LWE. It yields a classical reduction from Mod-GapSVP$_{γ}$ in module lattices of rank $nk$ to M-LWE$_{n,d,m,p,\Psi_{\le \alpha}}$, where $d \ge k^2n/2 + \Omega(\log_2 n)$.

Another line of work studied by Brakerski and Döttling for LWE [14] and R-LWE [15] was recently extended to M-LWE by Lin et al. [26]. It looks at the hardness of the problem when the only requirement on the secret distribution is to contain a sufficient entropy. Although [15] cannot be instantiated for $\eta$-bounded secret with $\eta$ being a small constant, the result by [26] on M-LWE can with certain restrictions. In particular, the entropy condition in this specific instantiation becomes a condition on the module ranks $d$ and $k$ that is similar to ours, i.e., $d \log_2(2\eta + 1) \gtrsim k \log_2 q$. This does not come as a surprise as the proof relies more or less on the same lossy argument as ours.

Finally, prior to our work, no result was formally known about the hardness of M-LWE with unusually small uniform error. We once again stress that the rank $d$, number of samples $m$ and error bound $\eta$ must be cautiously chosen with respect to one another for Theorem 4.1 to apply. As mentioned, the algebraic attacks, e.g. [6], on this variant do not depend on the underlying structure and therefore apply for LWE as well as M-LWE. When the number of samples $m$ covered by the proof of hardness is sufficiently larger than the rank $d$, the Hermite Normal Form transform from Lemma 4.5 can be used to derive the hardness of M-LWE with uniform $\eta$-bounded secret *and* error. This regime would give strong hardness guarantees for practical schemes, provided that the number of available samples is sufficient once again.

**Summary.** We summarize the results and the achieved parameters when clear in Table 5. The achievable rank $d$ depends on the secret distribution (for [26], Sections 3.1 and 3.2) or on the error size (for Section 4).
<table><caption>**Table 5.1.** Summary of the results on the hardness of the M-LWE problem. FSP stands for Fully Splitted Prime, IP for Inert Prime, and S denotes the search version, while D denotes the decision version. By abuse of language, we call monogenic the number fields $K = \mathbb{Q}(\zeta)$ for which $R = \mathbb{Z}[\zeta]$. Note that rigorously, a monogenic number field is $K = \mathbb{Q}(\zeta)$ for which $R = \mathbb{Z}[\zeta']$ for a possibly different $\zeta'$.</caption><thead><tr><th></th><th>[24]<br>(quantum)</th><th>[12]<br>(classical)</th><th>[26]</th><th>Sec. 3.1</th><th>Sec. 3.2</th><th>Sec. 4</th></tr></thead><tbody><tr><td>Field K of degree n</td><td>Cyclo</td><td>Cyclo</td><td>All</td><td>Monogenic</td><td>Cyclo</td><td>All</td></tr><tr><td>Rank d</td><td>All</td><td>Ω(n)</td><td>(Depends)</td><td>Ω(log<sub>2</sub> n)</td><td>ω(log<sub>2</sub> n)</td><td>All<sup>1</sup></td></tr><tr><td>Modulus q</td><td>All (S)<br>FSP (D)</td><td>Prime (S)<br>FSP (D)</td><td>All (S)<br>IP (D)</td><td>Prime</td><td>Prime, number-theoretic cond.</td><td></td></tr><tr><td>Secret s</td><td>Mod q<br>Gaussian<sup>2</sup></td><td>Mod q</td><td>Entropic</td><td>η-bounded</td><td>η-bounded</td><td>Mod q<br>η-bounded<sup>2</sup></td></tr><tr><td>Error e</td><td>Gaussian</td><td>Gaussian</td><td>Gaussian</td><td>Gaussian</td><td>Gaussian</td><td>η-bounded</td></tr><tr><td>Variant</td><td>S/D</td><td>S/D</td><td>S(/D<sup>3</sup>)</td><td>S</td><td>S<sup>4</sup>/D</td><td>S</td></tr></tbody></table>

## Acknowledgments

This work was supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701), by the PEPR quantum France 2030 programme (ANR-22-PETQ-0008), and by the Danish Independent Research Council under project number 0165-00107B (C3PO). We thank our anonymous referees of Asiacrypt 2020, Indocrypt 2020, CT-RSA 2021, and the IACR Journal of Cryptology for their thorough proof reading and constructive feedback on the original papers and the present one. We thank Thomas Prest for making us aware of improved rank conditions when using of the leftover hash lemma in the Rényi divergence. We also thank Olivier Sanders for helpful discussions on linear independence probabilities.

<footnote n="1">¹ Low ranks can be achieved at the expense of a larger $\eta$. However, one can still reach $\log_2 n$ ranks (instead of $\Omega(\log_2 q) + \omega(\log_2 n)$) for constant values of $\eta$.</footnote>

<footnote n="2">² Obtained by the Hermite Normal Form transformation reduction from [24].</footnote>

<footnote n="3">³ The hardness proof for the decision version of M-LWE requires $q$ to be an inert prime. This is a very restrictive condition as certain number fields do not contain any inert primes. For example, there exist inert primes in the $\nu$-th cyclotomic field if and only if $\nu$ is 2, 4 or $2^b p^k$ for $b \in \{0, 1\}$ and $p$ an odd prime. Then, (almost) all power-of-two cyclotomic fields do not contain inert primes.</footnote>

<footnote n="4">⁴ The hardness of the search version is obtained from the decision version through a trivial reduction.</footnote>
References

[1] M. R. Albrecht and A. Deo. Large modulus ring-lwe ≥ module-lwe. In *ASI-ACRYPT (1)*, volume 10624 of *Lecture Notes in Computer Science*, pages 267–296. Springer, 2017.

[2] M. R. Albrecht and A. Deo. Large modulus ring-lwe >= module-lwe. *IACR Cryptol. ePrint Arch.*, page 612, 2017.

[3] Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. Algebraic algorithms for LWE problems. *ACM Commun. Comput. Algebra*, 49(2):62, 2015.

[4] J. Alperin-Sheriff and D. Apon. Dimension-preserving reductions from LWE to LWR. *IACR Cryptol. ePrint Arch.*, page 589, 2016.

[5] B. Applebaum, D. Cash, C. Peikert, and A. Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In *CRYPTO*, volume 5677 of *Lecture Notes in Computer Science*, pages 595–618. Springer, 2009.

[6] S. Arora and R. Ge. New algorithms for learning in presence of errors. In *ICALP (1)*, volume 6755 of *Lecture Notes in Computer Science*, pages 403–415. Springer, 2011.

[7] S. Bai, T. Lepoint, A. Roux-Langlois, A. Sakzad, D. Stehlé, and R. Steinfeld. Improved security proofs in lattice-based cryptography: Using the rényi divergence rather than the statistical distance. *J. Cryptol.*, 31(2):610–640, 2018.

[8] Iván Blanco-Chacón. On the RLWE/PLWE equivalence for cyclotomic number fields. *Appl. Algebra Eng. Commun. Comput.*, 33(1):53–71, 2022.

[9] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. *J. ACM*, 50(4):506–519, 2003.

[10] J. W. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehlé. CRYSTALS - kyber: A cca-secure module-lattice-based KEM. In *EuroS&P*, pages 353–367. IEEE, 2018.

[11] K. Boudgoust. Theoretical hardness of algebraically structured learning with errors, 2021. https://katinkabou.github.io/Documents/Thesis_Boudgoust_Final.pdf.

[12] K. Boudgoust, C. Jeudy, A. Roux-Langlois, and W. Wen. Towards classical hardness of module-lwe: The linear rank case. In *ASIACRYPT (2)*, volume 12492 of *Lecture Notes in Computer Science*, pages 289–317. Springer, 2020.

[13] K. Boudgoust, C. Jeudy, A. Roux-Langlois, and W. Wen. On the hardness of module-lwe with binary secret. In *CT-RSA*, volume 12704 of *Lecture Notes in Computer Science*, pages 503–526. Springer, 2021.

[14] Z. Brakerski and N. Döttling. Hardness of LWE on general entropic distributions. In *EUROCRYPT (2)*, volume 12106 of *Lecture Notes in Computer Science*, pages 551–575. Springer, 2020.

[15] Z. Brakerski and N. Döttling. Lossiness and entropic hardness for ring-lwe. In *TCC (1)*, volume 12550 of *Lecture Notes in Computer Science*, pages 1–27. Springer, 2020.

[16] Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In *ITCS*, pages 309–325. ACM, 2012.

[17] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehlé. Classical hardness of learning with errors. In *STOC*, pages 575–584. ACM, 2013.

[18] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé. Crystals-dilithium: A lattice-based digital signature scheme. *IACR Trans. Cryptogr. Hardw. Embed. Syst.*, 2018(1):238–268, 2018.
[19] L. Ducas and D. Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In *EUROCRYPT (1)*, volume 9056 of *Lecture Notes in Computer Science*, pages 617–640. Springer, 2015.

[20] C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In *STOC*, pages 197–206. ACM, 2008.

[21] S. Goldwasser, Y. Tauman Kalai, C. Peikert, and V. Vaikuntanathan. Robustness of the learning with errors assumption. In *ICS*, pages 230–240. Tsinghua University Press, 2010.

[22] R. Impagliazzo and D. Zuckerman. How to recycle random bits. In *FOCS*, pages 248–253. IEEE Computer Society, 1989.

[23] P. Kirchner and P.-A. Fouque. An improved BKW algorithm for LWE with applications to cryptography and lattices. In *CRYPTO (1)*, volume 9215 of *Lecture Notes in Computer Science*, pages 43–62. Springer, 2015.

[24] A. Langlois and D. Stehlé. Worst-case to average-case reductions for module lattices. *Des. Codes Cryptogr.*, 75(3):565–599, 2015.

[25] A. Langlois, D. Stehlé, and R. Steinfeld. Gghlite: More efficient multilinear maps from ideal lattices. In *EUROCRYPT*, volume 8441 of *Lecture Notes in Computer Science*, pages 239–256. Springer, 2014.

[26] H. Lin, Y. Wang, and M. Wang. Hardness of module-lwe and ring-lwe on general entropic distributions. *IACR Cryptol. ePrint Arch.*, page 1238, 2020.

[27] Richard Lindner and Chris Peikert. Better key sizes (and attacks) for lwe-based encryption. In *CT-RSA*, volume 6558 of *Lecture Notes in Computer Science*, pages 319–339. Springer, 2011.

[28] Mingjie Liu and Phong Q. Nguyen. Solving BDD by enumeration: An update. In *CT-RSA*, volume 7779 of *Lecture Notes in Computer Science*, pages 293–309. Springer, 2013.

[29] V. Lyubashevsky. Lattice signatures without trapdoors. In *EUROCRYPT*, volume 7237 of *Lecture Notes in Computer Science*, pages 738–755. Springer, 2012.

[30] V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. *J. ACM*, 60(6):43:1–43:35, 2013.

[31] V. Lyubashevsky, C. Peikert, and O. Regev. A toolkit for ring-lwe cryptography. In *EUROCRYPT*, volume 7881 of *Lecture Notes in Computer Science*, pages 35–54. Springer, 2013.

[32] V. Lyubashevsky and G. Seiler. Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs. In *EUROCRYPT (1)*, volume 10820 of *Lecture Notes in Computer Science*, pages 204–224. Springer, 2018.

[33] Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler. Shorter lattice-based zero-knowledge proofs via one-time commitments. In *Public Key Cryptography (1)*, volume 12710 of *Lecture Notes in Computer Science*, pages 215–241. Springer, 2021.

[34] D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. *Comput. Complex.*, 16(4):365–411, 2007.

[35] D. Micciancio. On the hardness of learning with errors with binary secrets. *Theory Comput.*, 14(1):1–17, 2018.

[36] D. Micciancio and P. Mol. Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In *CRYPTO*, volume 6841 of *Lecture Notes in Computer Science*, pages 465–484. Springer, 2011.

[37] D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In *EUROCRYPT*, volume 7237 of *Lecture Notes in Computer Science*, pages 700–718. Springer, 2012.
[38] D. Micciancio and C. Peikert. Hardness of SIS and LWE with small parameters. In *CRYPTO* (1), volume 8042 of *Lecture Notes in Computer Science*, pages 21–39. Springer, 2013.

[39] D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. *SIAM J. Comput.*, 37(1):267–302, 2007.

[40] NIST. Post-quantum cryptography standardization. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization.

[41] C. Peikert. Limits on the hardness of lattice problems in $lp$ norms. *Comput. Complex.*, 17(2):300–351, 2008.

[42] C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In *STOC*, pages 333–342. ACM, 2009.

[43] C. Peikert. An efficient and parallel gaussian sampler for lattices. In *CRYPTO*, volume 6223 of *Lecture Notes in Computer Science*, pages 80–97. Springer, 2010.

[44] C. Peikert and Z. Pepin. Algebraically structured lwe, revisited. In *TCC* (1), volume 11891 of *Lecture Notes in Computer Science*, pages 1–23. Springer, 2019.

[45] C. Peikert, O. Regev, and N. Stephens-Davidowitz. Pseudorandomness of ring-lwe for any ring and modulus. In *STOC*, pages 461–473. ACM, 2017.

[46] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In *STOC*, pages 84–93. ACM, 2005.

[47] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. *J. ACM*, 56(6):34:1–34:40, 2009.

[48] A. Rényi. On measures of entropy and information. In *Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. I*, pages 547–561. Univ. California Press, Berkeley, Calif., 1961.

[49] S. Rjasanow. Effective algorithms with circulant-block matrices. *Linear Algebra and its Applications*, 202:55–69, 1994.

[50] M. Rosca, D. Stehlé, and A. Wallet. On the ring-lwe and polynomial-lwe problems. In *EUROCRYPT* (1), volume 10820 of *Lecture Notes in Computer Science*, pages 146–173. Springer, 2018.

[51] D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa. Efficient public key encryption based on ideal lattices. In *ASIACRYPT*, volume 5912 of *Lecture Notes in Computer Science*, pages 617–635. Springer, 2009.

[52] Chao Sun, Mehdi Tibouchi, and Masayuki Abe. Revisiting the hardness of binary error LWE. In *ACISP*, volume 12248 of *Lecture Notes in Computer Science*, pages 425–444. Springer, 2020.

[53] T. van Erven and P. Harremoës. Rényi divergence and kullback-leibler divergence. *IEEE Trans. Inf. Theory*, 60(7):3797–3820, 2014.

[54] Roman Vershynin. *Introduction to the non-asymptotic analysis of random matrices*, page 210–268. Cambridge University Press, 2012.

[55] David A. Wagner. A generalized birthday problem. In *CRYPTO*, volume 2442 of *Lecture Notes in Computer Science*, pages 288–303. Springer, 2002.

[56] Y. Wang and M. Wang. Module-lwe versus ring-lwe, revisited. *IACR Cryptol. ePrint Arch.*, page 930, 2019. Version dated from Aug. 18th 2019.
# Appendix A Singularity of Uniform Matrices

In this section, $K$ denotes an arbitrary number field and $R$ its ring of integers. Throughout the entire section, $q$ is a prime integer that does not ramify in $R$ and that splits as $qR = \prod_{i \in [\kappa]} \mathfrak{p}_i$, where $\kappa \le n = [K : \mathbb{Q}]$. We still use $R_q$ to define $R/qR$ and we also define $\mathbb{F}_i = R/\mathfrak{p}_i$ for each $i \in [\kappa]$. We recall that for each $i \in [\kappa]$, $\mathbb{F}_i$ is a finite field of size $N(\mathfrak{p}_i)$, see e.g. [31, Sec. 2.5.3].

We prove several results on the probability that a uniformly random matrix $\mathbf{A} \in R_q^{d \times d}$ is invertible in $R_q$. For a ring $A$ and an integer $d$, we denote by $GL_d(A)$ the set of matrices of $A^{d \times d}$ that are invertible in $A$. We note that such results were provided in [56]. However, the proofs were based on a flawed argument which was that a vector of $R_q^d$ which is linearly independent (with itself) must contain a coefficient in $R_q^\times$. This is not the case as a vector of $R_q^d$ consisting only of zero divisors can still be linearly independent. We give more details in Section A.2. We also provide new corrected proofs for their results which essentially rely on analyzing each residue modulo $\mathfrak{p}_i$.

## A.1 Preliminaries

The ring $R_q$ is a finite commutative ring. As such, an element of $R_q$ is either a unit or a zero divisor. We denote the set of units by $R_q^\times$, and the set of zero divisors by $Z(R_q) = \{r \in R_q : \exists s \in R_q \setminus \{0\}, rs = 0 \mod qR\}$. By the Chinese Remainder Theorem [30, Lem. 2.12], there exists an isomorphism $\theta$ between $R_q$ and $\oplus_{i \in [\kappa]} \mathbb{F}_i$ such that for all $r \in R$, $\theta(r \mod qR) = (r \mod \mathfrak{p}_1, \dots, r \mod \mathfrak{p}_\kappa)$. Note that the direct sum $\oplus_{i \in [\kappa]} \mathbb{F}_i$ is here canonically isomorphic to the direct product, which also corresponds to the Cartesian product $\times_{i \in [\kappa]} \mathbb{F}_i$ with coordinate-wise operations. We thus identify the elements in the range of $\theta$ as vectors. Also, $R_q^\times$ is isomorphic to $\oplus_{i \in [\kappa]} \mathbb{F}_i^\times = \oplus_{i \in [\kappa]} \mathbb{F}_i \setminus \{0\}$.

In what follows, we consider vectors and matrices over $R_q$. Since $R_q$ is not a field, we cannot use regular linear algebra results. Instead we use results from module theory to obtain similar results over $R_q$. Although many of the following may be folklore for the reader who is familiar with module theory, we provide proofs for completeness. First, we give a characterization of invertible matrices in $R_q$ using the determinant.

**Lemma A.1.** Let $\mathbf{A} \in R_q^{d \times d}$. Then: $\mathbf{A} \in GL_d(R_q) \Leftrightarrow \det \mathbf{A} \in R_q^\times$.

*Proof.* Assume $\mathbf{A} \in GL_d(R_q)$. Then, there exists $\mathbf{B} \in R_q^{d \times d}$ such that $\mathbf{A}\mathbf{B} = \mathbf{B}\mathbf{A} = \mathbf{I}_d$. Then $(\det \mathbf{A})(\det \mathbf{B}) = \det \mathbf{A}\mathbf{B} = \det \mathbf{I}_d = 1$. Hence, $\det \mathbf{A} \in R_q^\times$. Reciprocally, assume that $\det \mathbf{A} \in R_q^\times$. Since $R_q$ is a commutative ring, we have

$$ \mathrm{Com}(\mathbf{A})^T \cdot \mathbf{A} = \mathbf{A} \cdot \mathrm{Com}(\mathbf{A})^T = (\det \mathbf{A})\mathbf{I}_d, $$

where $\mathrm{Com}(\mathbf{A})$ is the comatrix of $\mathbf{A}$. Since $\det \mathbf{A} \in R_q^\times$, it holds that

$$ (\det \mathbf{A})^{-1} \mathrm{Com}(\mathbf{A})^T \cdot \mathbf{A} = \mathbf{A} \cdot (\det \mathbf{A})^{-1} \mathrm{Com}(\mathbf{A})^T = \mathbf{I}_d, $$

thus proving that $\mathbf{A} \in GL_d(R_q)$. $\square$

<figure><img src="image_9.png" /></figure>
We recall that $k$ vectors $(\mathbf{a}_1, \dots, \mathbf{a}_k)$ of $R_q^d$ are $R_q$-linearly independent if and only if for all $(\lambda_1, \dots, \lambda_k) \in R_q^k$, if $\sum_{j \in [k]} \lambda_j \mathbf{a}_j = \mathbf{0} \bmod qR$, then $\lambda_j = 0 \bmod qR$ for all $j \in [k]$. We first show that $R_q$-linear independence can be analyzed from the $\mathbb{F}_i$-linear independence of the residues.

**Lemma A.2.** Let $\mathbf{a}_1, \dots, \mathbf{a}_\ell$ be vectors of $R_q^d$. Then $(\mathbf{a}_1, \dots, \mathbf{a}_\ell)$ are $R_q$-linearly independent if and only if for all $i \in [\kappa]$, $(\mathbf{a}_1 \bmod \mathfrak{p}_i, \dots, \mathbf{a}_\ell \bmod \mathfrak{p}_i)$ are $\mathbb{F}_i$-linearly independent.

*Proof.* We extend the CRT isomorphism $\theta$ to vectors coefficient-wise. For $j \in [\ell]$ and $i \in [\kappa]$, we denote $\mathbf{a}_j \bmod \mathfrak{p}_i$ by $\mathbf{a}_j^{(i)}$ for clarity.

First, assume that for all $i \in [\kappa]$, $(\mathbf{a}_1^{(i)}, \dots, \mathbf{a}_\ell^{(i)})$ are $\mathbb{F}_i$-linearly independent. Let $(\lambda_1, \dots, \lambda_\ell)$ be in $R_q^\ell$ such that $\sum_{j \in [\ell]} \lambda_j \mathbf{a}_j = \mathbf{0} \bmod qR$. By applying $\theta$, we have that for all $i \in [\kappa]$

$$ \sum_{j \in [\ell]} (\lambda_j \bmod \mathfrak{p}_i) \mathbf{a}_j^{(i)} = \mathbf{0} \bmod \mathfrak{p}_i. $$

By assumption, it gives that for all $j \in [\ell]$ and all $i \in [\kappa]$, $\lambda_j \bmod \mathfrak{p}_i = 0$. Then, for all $j \in [\ell]$, it holds

$$ \lambda_j = \theta^{-1}(\lambda_j \bmod \mathfrak{p}_1, \dots, \lambda_j \bmod \mathfrak{p}_\kappa) = \theta^{-1}(0, \dots, 0) = 0, $$

where the equalities are in $R_q$. Hence, $(\mathbf{a}_1, \dots, \mathbf{a}_\ell)$ are $R_q$-linearly independent.

Reciprocally, assume that $(\mathbf{a}_1, \dots, \mathbf{a}_\ell)$ are $R_q$-linearly independent. Let $i \in [\kappa]$ and let $(\mu_1, \dots, \mu_\ell)$ be in $\mathbb{F}_i^\ell$ such that $\sum_{j \in [\ell]} \mu_j \mathbf{a}_j^{(i)} = \mathbf{0} \bmod \mathfrak{p}_i$. For each $j \in [\ell]$, define $\lambda_j = \theta^{-1}(0, \dots, 0, \mu_j, 0, \dots, 0)$, where $\mu_j$ is at position $i$. Then,

$$ \theta \left( \sum_{j \in [\ell]} \lambda_j \mathbf{a}_j \right) = \left( \mathbf{0}, \dots, \mathbf{0}, \sum_{j \in [\ell]} \mu_j \mathbf{a}_j^{(i)}, \mathbf{0}, \dots, \mathbf{0} \right) = (\mathbf{0}, \dots, \mathbf{0}). $$

Hence, $\sum_{j \in [\ell]} \lambda_j \mathbf{a}_j = \mathbf{0} \bmod qR$ and by assumption, it holds that $\lambda_j = 0 \bmod qR$ for all $j \in [\ell]$. As a result, it gives that $\mu_j = 0 \bmod \mathfrak{p}_i$ for all $j \in [\ell]$, thus proving that $(\mathbf{a}_1^{(i)}, \dots, \mathbf{a}_\ell^{(i)})$ are $\mathbb{F}_i$-linearly independent. Being valid for all $i \in [\kappa]$, it yields the claim. $\square$

We can now prove that a square matrix is invertible if and only if its columns are $R_q$-linearly independent, as claimed in [56, Lem. 18]. The following can be used to show that if $\ell > d$, then $\ell$ vectors of $R_q^d$ cannot be $R_q$-linearly independent.

**Lemma A.3.** Let $\mathbf{A} = [\mathbf{a}_1 | \dots | \mathbf{a}_d]$ be in $R_q^{d \times d}$. It then holds that $\mathbf{A} \in GL_d(R_q)$ if and only if $(\mathbf{a}_1, \dots, \mathbf{a}_d)$ are $R_q$-linearly independent.

*Proof.* First, by contraposition, assume that $(\mathbf{a}_1, \dots, \mathbf{a}_d)$ are not $R_q$-linearly independent. Hence, there exists $(\lambda_1, \dots, \lambda_d) \in R_q^d \setminus \{\mathbf{0}\}$ such that $\sum_{j \in [d]} \lambda_j \mathbf{a}_j =$
0 mod $qR$. There exists some $j_0 \in [d]$ such that $\lambda_{j_0} \neq 0 \mod qR$. We then have

$$
\begin{align*}
\lambda_{j_0} \cdot \det \mathbf{A} &= \det ( [\mathbf{a}_1 | \dots | \mathbf{a}_{j_0-1} | \lambda_{j_0} \mathbf{a}_{j_0} | \mathbf{a}_{j_0+1} | \dots | \mathbf{a}_d] ) \\
&= \det \left( \left[ \mathbf{a}_1 | \dots | \mathbf{a}_{j_0-1} | \lambda_{j_0} \mathbf{a}_{j_0} + \sum_{j \in [d] \setminus \{j_0\}} \lambda_j \mathbf{a}_j | \mathbf{a}_{j_0+1} | \dots | \mathbf{a}_d \right] \right) \\
&= \det ( [\mathbf{a}_1 | \dots | \mathbf{a}_{j_0-1} | \mathbf{0} | \mathbf{a}_{j_0+1} | \dots | \mathbf{a}_d] ) \\
&= 0 \mod qR.
\end{align*}
$$

This proves that $\det \mathbf{A} \in Z(R_q)$ and thus $\det \mathbf{A} \notin R_q^\times$. By Lemma A.1, it holds
that $\mathbf{A} \notin GL_d(R_q)$.

Now assume that $(\mathbf{a}_1, \dots, \mathbf{a}_d)$ are $R_q$-linearly independent. Then, Lemma A.2 yields that for all $i \in [\kappa]$, $(\mathbf{a}_1 \text{ mod } \mathbf{p}_i, \dots, \mathbf{a}_d \text{ mod } \mathbf{p}_i)$ are $\mathbb{F}_i$-linearly independent. Let $i$ be in $[\kappa]$. Since $\mathbb{F}_i$ is a field and that $(\mathbf{a}_1 \text{ mod } \mathbf{p}_i, \dots, \mathbf{a}_d \text{ mod } \mathbf{p}_i)$ are $\mathbb{F}_i$-linearly independent, then the matrix $\mathbf{A} \text{ mod } \mathbf{p}_i$ is in $GL_d(\mathbb{F}_i)$. Hence $\det \mathbf{A} \neq 0 \text{ mod } \mathbf{p}_i$, which proves that $(\det \mathbf{A}) \text{ mod } \mathbf{p}_i \in \mathbb{F}_i^\times$. Being valid for all $i \in [\kappa]$, the Chinese Remainder Theorem yields $\det \mathbf{A} \in R_q^\times$. Hence, by Lemma A.1, $\mathbf{A} \in GL_d(R_q)$. $\square$

**A.2 Linear Independence in Uniform Matrices — Lemma 2.5**

As a warm-up for proving Lemma 2.5, we first analyze the probability that a random vector of $R_q^d$ is $R_q$-linearly independent. The formula given in footnote 9 of [56] provides only a lower bound. This formula relies on the flawed observation that a vector is $R_q$-linearly independent if and only if it contains a coefficient in $R_q^\times$. The argument provided for this claim is as follows. If $\mathbf{a} = [a_1 | \dots | a_d]^T \in Z(R_q)^d$, then there exist $y_1, \dots, y_d \in (R_q \setminus \{0\})^d$ such that $a_i \cdot y_i = 0 \mod qR$ for all $i \in [d]$. Then, by defining $\lambda = \prod_{i \in [d]} y_i$, we get $\lambda \mathbf{a} = \mathbf{0} \mod qR$. However, the authors claim at this point that $\lambda \neq 0 \mod qR$, which has no reason to be the case. We provide the following lemma to show the contrary, as well as a concrete counterexample that satisfies the conditions of the lemma.

**Lemma A.4.** Let $K$ be a number field, and $R$ its ring of integers. Let $q$ be a
prime integer that is not inert<fnref n="5" /> in $R$. Let $r, s$ be elements of $R$ such that $r \mod
qR \in Z(R_q)$, $s \mod qR \in Z(R_q)$ and $\langle r \rangle + \langle s \rangle = R$. Then, the vector $[r \mod
qR, s \mod qR]^T \in Z(R_q)^2$ is $R_q$-linearly independent.

*Proof.* By assumption, $r$ and $s$ are coprime and therefore there exists $u, v$ in $R$ such that $u \cdot r + v \cdot s = 1$. Hence $(u \bmod qR)(r \bmod qR) + (v \bmod qR)(s \bmod qR) = 1 \bmod qR$. Define $\mathbf{x} = [r \bmod qR, s \bmod qR]^T$. By assumption $\mathbf{x} \in Z(R_q)^2$. Let $\lambda \in R_q$ be such that $\lambda \mathbf{x} = 0 \bmod qR$. It implies that $\lambda(r \bmod qR) =$

<footnote n="5">⁵ If $q$ is inert, then $R_q$ is a field, and therefore $Z(R_q) = \{0\}$, meaning that there does not exist $r, s$ satisfying the conditions.</footnote>