0 mod $qR$ and $\lambda(s \bmod qR) = 0 \bmod qR$. As a result, it holds

$$
\begin{align*}
\lambda &= \lambda \cdot ((u \bmod qR)(r \bmod qR) + (v \bmod qR)(s \bmod qR)) \bmod qR \\
&= (u \bmod qR) \cdot \lambda(r \bmod qR) + (v \bmod qR) \cdot \lambda(s \bmod qR) \\
&= 0 \bmod qR
\end{align*}
$$

It thus proves that the only common annihilator of $r \bmod qR$ and $s \bmod qR$ is 0, which in other terms means $\mathbf{x}$ is $R_q$-linearly independent. $\square$

The conditions of the previous lemma can easily be met. As a concrete ex-
ample, in the cyclotomic field of conductor $\nu = 256$, for $q = 257$, one can check
that the elements $r = \zeta + 3$ and $s = \zeta + 6$ verify the conditions of the above
lemma. Such counterexamples can easily be found by enumerating the first few
zero divisors, or by sampling a few zero divisors at random.

We then recall the following lemma which we need to prove Lemma 2.5. We
provide a proof for completeness.

**Lemma A.5.** Let $r$ be a random variable that is uniformly distributed over $R_q$. Then, the random variables $(r \bmod \mathbf{p}_i)_{i \in [\kappa]}$ are independent and uniformly distributed over their respective support $\mathbb{F}_i$.

*Proof.* Denote by $\mathbf{r} = \theta(\mathbf{r})$, which is the random vector composed of the $r$ mod $\mathbf{p}_i$. Since $\theta$ is an isomorphism, it holds that $\mathbf{r} \sim U(\oplus_{i \in [\kappa]} \mathbb{F}_i)$. Let $\mathbf{s}$ be the random vector over $\oplus_{i \in [\kappa]} \mathbb{F}_i$ such that the coordinates are independent and uniform over each $\mathbb{F}_i$ respectively. Let $\mathbf{r}' \in \oplus_{i \in [\kappa]} \mathbb{F}_i$. It holds

$$
\mathbb{P}_{\mathbf{r}}[\mathbf{r} = \mathbf{r}'] = q^{-n} = \prod_{i \in [\kappa]} N(\mathbf{p}_i)^{-1} = \prod_{i \in [\kappa]} \mathbb{P}_{\mathbf{s}_i}[s_i = r_i'] = \mathbb{P}_{\mathbf{s}}[\mathbf{s} = \mathbf{r}'].
$$

This proves that **r** and **s** are identical random vectors, which yields that the
coordinates of **r** are independent and uniform over each $\mathbb{F}_i$. $\square$

We now focus on proving Lemma 2.5, where the first part was claimed in [56, Lem. 9]. First, we note that we cannot naively use the analysis over residues to obtain a proof of [56, Lem. 19]. The latter argues that if $(\mathbf{a}_1, \dots, \mathbf{a}_\ell) \in (R_q^d)^\ell$ are $R_q$-l. i. with $\ell \le d$, then one can always extract a submatrix in $GL_\ell(R_q)$ by selecting some subset of the rows. However, this is not generally true for such matrices over $R_q$. This is due to the fact that a minimal spanning set of an $R_q$-submodule of $R_q^d$ is not necessarily a basis of said submodule. When analyzing the problem in the residues, we will obtain submatrices in $GL_\ell(\mathbb{F}_i)$. But it is not guaranteed that these submatrices correspond to the same subsets of rows, in which case we cannot re-combine the residues. We show that we do not need this fact to prove Lemma 2.5. For convenience, we now abbreviate “$R_q$-linearly independent” by “$R_q$-l. i.”.

*Proof (of Lemma 2.5).* By Lemma A.2 and A.5, we can analyze the residues and first determine $\mathbb{P}_{\mathbf{b}^{(i)} \sim U(\mathbb{F}_i^d)}[(\mathbf{a}_1 \bmod \mathbf{p}_i, \dots, \mathbf{a}_\ell \bmod \mathbf{p}_i, \mathbf{b}^{(i)})]$ are $\mathbb{F}_i$-l. i.] for each
$i \in [\kappa]$ individually. Let $i$ be in $[\kappa]$. Since $(\mathbf{a}_1, \dots, \mathbf{a}_\ell)$ are $R_q$-linearly independent, then again the residues $(\mathbf{a}_1 \bmod \mathbf{p}_i, \dots, \mathbf{a}_\ell \bmod \mathbf{p}_i)$ are $\mathbb{F}_i$-linearly independent by Lemma A.2. It yields that two linear combinations of $(\mathbf{a}_1 \bmod \mathbf{p}_i, \dots, \mathbf{a}_\ell \bmod \mathbf{p}_i)$ that are equal must have equal coefficients. Hence, there are $|\mathbb{F}_i|^{\ell}$ distinct linear combinations of the $(\mathbf{a}_1 \bmod \mathbf{p}_i, \dots, \mathbf{a}_\ell \bmod \mathbf{p}_i)$.

As a result, if we denote by $S_i$ the set of $\mathbf{b}^{(i)} \in \mathbb{F}_i^d$ that are not in the $\mathbb{F}_i$-span of $(\mathbf{a}_1 \bmod \mathbf{p}_i, \dots, \mathbf{a}_\ell \bmod \mathbf{p}_i)$, we have $|S_i| = |\mathbb{F}_i|^d - |\mathbb{F}_i|^{\ell}$. Note that when $\ell = 0$, there are $|\mathbb{F}_i|^0 = 1$ vectors in the span of $\mathbf{0}$. In this case, we obtain $|S_i| = |\mathbb{F}_i|^d - 1$ which is coherent with the previous formula. Since we work over a field $\mathbb{F}_i$, and thus a vector space, if $\mathbf{b}^{(i)}$ is in $S_i$, then $(\mathbf{a}_1 \bmod \mathbf{p}_i, \dots, \mathbf{a}_\ell \bmod \mathbf{p}_i, \mathbf{b}^{(i)})$ are $\mathbb{F}_i$-linearly independent (which is not necessarily true in a module). It then yields

$$ \begin{aligned} \mathbb{P}_{\mathbf{b}^{(i)} \sim U(\mathbb{F}_i^d)}[(\mathbf{a}_1 \bmod \mathbf{p}_i, \dots, \mathbf{a}_\ell \bmod \mathbf{p}_i, \mathbf{b}^{(i)}) \text{ are } \mathbb{F}_i\text{-l. i.}] &= \mathbb{P}_{\mathbf{b}^{(i)} \sim U(\mathbb{F}_i^d)}[\mathbf{b}^{(i)} \in S_i] \\ &= \frac{|S_i|}{|\mathbb{F}_i|^d} \\ &= 1 - \frac{1}{N(\mathbf{p}_i)^{d-\ell}}. \end{aligned} $$

By combining the residues, we obtain

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

We note that we can still prove the relaxed lower bound claimed in [56]. Since all the prime ideal factors $\mathbf{p}_i$ are above $q$, we have $N(\mathbf{p}_i) = q^{f_i} \ge q$ for some $f_i \ge 1$. It yields

$$ \prod_{i \in [\kappa]} \left(1 - \frac{1}{N(\mathbf{p}_i)^{d-\ell}}\right) \ge \left(1 - \frac{1}{q^{d-\ell}}\right)^{\kappa} \ge 1 - \frac{\kappa}{q^{d-\ell}} \ge 1 - \frac{\kappa}{q}, $$

where the second inequality holds by the Bernoulli inequality, and the last follows from the fact that $d-\ell \ge 1$. Since $\kappa$ is at most the degree $n$ of the number field $K$, we can lower bound the probability by $1 - n/q$.

Finally, let us prove the last formula. Fix $\ell \in \{1, \dots, k-1\}$. We study the following probability

$$ \mathbb{P}_{(\mathbf{a}_j)_{j \in [\ell+1]} \sim U(R_q^d)^{\ell+1}}[(\mathbf{a}_j)_{j \in [\ell+1]} \text{ are } R_q\text{-l. i.}]. $$

It can be decomposed by the total probability formula as

$$ \sum_{(\bar{\mathbf{a}}_j)_{j \in [\ell]}} \mathbb{P}_{(\mathbf{a}_j)_{j \in [\ell]} \left[ (\bar{\mathbf{a}}_j)_{j \in [\ell]} = (\bar{\mathbf{a}}_j)_{j \in [\ell]} \right]} \cdot \mathbb{P}_{\mathbf{a}_{\ell+1} \left[ ((\bar{\mathbf{a}}_j)_{j \in [\ell]}, \mathbf{a}_{\ell+1}) \text{ are } R_q\text{-l. i.} \right]}. $$

Note that if the summands $(\bar{\mathbf{a}}_j)_j$ are not $R_q$-linearly independent, it directly gives that $((\bar{\mathbf{a}}_j)_{j \in [\ell]}, \mathbf{a}_{\ell+1})$ cannot be $R_q$-linearly independent and that the second
probability is therefore 0. Hence, we consider the sum over the $(\bar{a}_j)_j$ that are $R_q$-linearly independent. By the first formula, the second probability over $\mathbf{a}_{\ell+1}$ is given by $\prod_{i \in [\kappa]} (1 - 1/N(\mathbf{p}_i)^{d-\ell})$. As it does not depend on the summand, we have that the probability is exactly

$$ \mathbb{P}_{(\mathbf{a}_j)_{j \in [\ell]} \sim U(R_q^d)^\ell}[(\mathbf{a}_j)_{j \in [\ell]} \text{ are } R_q\text{-l. i.}] \cdot \prod_{i \in [\kappa]} \left(1 - \frac{1}{N(\mathbf{p}_i)^{d-\ell}}\right). $$

Using Equation (8) with $\ell = 0$ for initialization, induction on $\ell$ then yields

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

as desired.

□

We note that the number of columns is $k \le d$. Additionally, in $R_q$ we still have the fact that a linearly independent family of vectors of $R_q^d$ cannot contain more than $d$ vectors. As a result, when $k > d$, we have to analyze the following probability

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

As explained, even if there exists subsets $S_i \subseteq [k]$ with $|S_i| = d$ and $(\mathbf{a}_j \mod \mathbf{p}_i)_{j \in S_i}$ are $\mathbb{F}_i$-l. i., there is no guarantee that all the $S_i$ are equal.

### A.3 Singularity of Uniform Matrices – Lemma 2.6

In this section, we can show that the equality of the $S_i$ is not necessary to guarantee that the columns form a spanning set of $R_q^d$.

*Proof (of Lemma 2.6).* We prove the lower bound by inclusion of events. Let $\mathbf{A} = [\mathbf{a}_1|\dots|\mathbf{a}_m] \in R_q^{d \times m}$ be such that

$$ \forall i \in [\kappa], \exists S_i \subseteq [m], |S_i| = d \wedge (\mathbf{a}_j \mod \mathbf{p}_i)_{j \in S_i} \text{ are } \mathbb{F}_i\text{-l. i..} \quad (9) $$

We show that this guarantees that $\mathbf{A} \cdot R_q^m = R_q^d$. Consider the CRT basis $\lambda_1, \dots, \lambda_\kappa$ defined by $\lambda_i = \theta^{-1}(\mathbf{e}_i)$ where $(\mathbf{e}_1, \dots, \mathbf{e}_\kappa)$ is the canonical basis of $\oplus_{i \in [\kappa]} \mathbb{F}_i$. We index each set $S_i$ as $S_i = \{j_1^{(i)}, \dots, j_d^{(i)}\}$. We then construct the vectors $\mathbf{b}_\ell = \sum_{i \in [\kappa]} \lambda_i \mathbf{a}_{j_\ell}^{(i)}$ for all $\ell \in [d]$. We now prove that $(\mathbf{b}_\ell)_{\ell \in [d]}$ are $R_q$-linearly independent. Let $(\mu_\ell)_{\ell \in [d]} \in R_q^d$ be such that $\sum_{\ell \in [d]} \mu_\ell \mathbf{b}_\ell = \mathbf{0} \mod qR$. Let $i^* \in [\kappa]$. It holds that

$$ \mathbf{0} = \sum_{\ell \in [d]} (\mu_\ell \mod \mathbf{p}_{i^*})(\mathbf{b}_\ell \mod \mathbf{p}_{i^*}) = \sum_{\ell \in [d]} (\mu_\ell \mod \mathbf{p}_{i^*})(\mathbf{a}_{j_\ell}^{(i^*)} \mod \mathbf{p}_{i^*}), $$
where the equality is over $\mathbf{F}_{i^*}$. The last equality follows from the construction of the $\mathbf{b}_\ell$ as $\mathbf{b}_\ell \mod \mathfrak{p}_{i^*} = \sum_{i \in [\kappa]} \delta_{i, i^*}(\mathbf{a}_{j_\ell^{(i)}} \mod \mathfrak{p}_{i^*}) = \mathbf{a}_{j_\ell^{(i^*)}} \mod \mathfrak{p}_{i^*}$. By definition of $S_{i^*}$, the $(\mathbf{a}_{j_\ell^{(i^*)}} \mod \mathfrak{p}_{i^*})_{\ell \in [d]}$ are $\mathbf{F}_{i^*}$-linearly independent and therefore $\mu_\ell \mod \mathfrak{p}_{i^*} = 0$. Being true for all $i^*$, it proves by Lemma A.2 that $(\mathbf{b}_\ell)_{\ell \in [d]}$ are $R_q$-linearly independent.

We can then write $\mathbf{B} = [\mathbf{b}_1 | \dots | \mathbf{b}_d] = \mathbf{AC} \in R_q^{d \times d}$ where the matrix $\mathbf{C} \in R_q^{m \times d}$ is composed of the $\lambda_i$ at the correct positions. More precisely, the $\ell$-th column of $\mathbf{C}$ is $\sum_{i \in [\kappa]} \lambda_i \mathbf{e}_{j_\ell^{(i)}} \in R_q^m$, where the $\mathbf{e}_1, \dots, \mathbf{e}_m$ represent the canonical basis of $R_q^m$. By Lemma A.3, since the columns of $\mathbf{B}$ are $R_q$-linearly independent, then $\mathbf{B} \in GL_d(R_q)$. Hence, for all $\mathbf{y} \in R_q^d$, there exists $\mathbf{x}' \in R_q^d$ such that $\mathbf{B}\mathbf{x}' = \mathbf{y} \mod qR$. By defining $\mathbf{x} = \mathbf{C}\mathbf{x}' \in R_q^m$, we have $\mathbf{A}\mathbf{x} = \mathbf{y} \mod qR$. This proves that $\mathbf{A} \cdot R_q^m = R_q^d$.

As a result, for any matrix $\mathbf{A}$ verifying (9), it holds that $\mathbf{A} \cdot R_q^m = R_q^d$. By inclusion of events, we have

$$ \begin{aligned} & \mathbb{P}_{\mathbf{A} \sim U(R_q^{d \times m})} [\mathbf{A} \cdot R_q^m = R_q^d] \\ & \ge \mathbb{P}_{\mathbf{A} \sim U(R_q^{d \times m})} [\forall i \in [\kappa], \exists S_i \subseteq [m], |S_i| = d \wedge (\mathbf{a}_j \mod \mathfrak{p}_i)_{j \in S_i} \text{ are } \mathbf{F}_i\text{-l. i.}]. \end{aligned} $$

We now evaluate the right-hand side. By Lemma A.5, the latter probability equals

$$ \prod_{i \in \kappa} \mathbb{P}_{\mathbf{A}^{(i)} \sim U(\mathbf{F}_i^{d \times m})} [\exists S_i \subseteq [m], |S_i| = d \wedge (\mathbf{a}_j^{(i)} \mod \mathfrak{p}_i)_{j \in S_i} \text{ are } \mathbf{F}_i\text{-l. i.}] $$

Let $i \in [\kappa]$. Since $\mathbf{F}_i$ is a field, we have the following

$$ \begin{aligned} & \mathbb{P}_{\mathbf{A}^{(i)} \sim U(\mathbf{F}_i^{d \times m})} [\exists S_i \subseteq [m], |S_i| = d \wedge (\mathbf{a}_j^{(i)} \mod \mathfrak{p}_i)_{j \in S_i} \text{ are } \mathbf{F}_i\text{-l. i.}] \\ &= \mathbb{P}_{\mathbf{A}^{(i)} \sim U(\mathbf{F}_i^{d \times m})} [\text{Column-Rank}(\mathbf{A}^{(i)}) = d] \\ &= \mathbb{P}_{\mathbf{A}^{(i)} \sim U(\mathbf{F}_i^{d \times m})} [\text{Row-Rank}(\mathbf{A}^{(i)}) = d] \\ &= \mathbb{P}_{(\mathbf{a}_i')_{i \in [d]} \sim U(\mathbf{F}_i^m)^d} [(\mathbf{a}_i')_{i \in [d]} \text{ are } \mathbf{F}_i\text{-l. i.}]. \\ &= \prod_{\ell=0}^{d-1} \left( 1 - \frac{1}{N(\mathfrak{p}_i)^{m-\ell}} \right), \end{aligned} $$

where the last inequality is the special case of Lemma 2.5 over the residue field $\mathbf{F}_i$. Combining it all yields

$$ \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). $$

□
# Appendix B Missing Proofs

## B.1 Missing Proofs of Section 2

### Lemma 2.1.

*Proof.* The lower bound is due to the fact that every non-zero element $x$ of $R$ has algebraic norm $N(x) \ge 1$, which implies that $\|\sigma(x)\|_{\infty} \ge 1$. Let $x$ be in $S_{\eta}$, and $i \in [n]$. Then, it holds that

$$ \begin{aligned} |\sigma_i(x)| &\le \sum_{j=0}^{n-1} |\tau_j(x)\sigma_i(\zeta)^j| = \sum_{j=0}^{n-1} |\tau_j(x)||\alpha_i|^j \\ &\le \|\tau(x)\|_1 \|\mathbf{V}\|_{\max} \le n\eta \|\mathbf{V}\|_{\max}. \end{aligned} $$

Taking the maximum over all $i \in [n]$ and $x \in S_{\eta}$ yields $B_{\eta} \le n\eta \|\mathbf{V}\|_{\max}$. In the case of cyclotomic fields, the $\alpha_i$ are roots of unity and therefore, all the entries of $\mathbf{V}$ have magnitude 1. Hence $\|\mathbf{V}\|_{\max} = 1$ which yields $B_{\eta} \le n\eta$ in this case. □

### Lemma 2.2.

*Proof.* Let $f = x^n + \sum_{k=0}^{n-1} f_k x^k$ denote the minimal polynomial of $\zeta$, and $K = \mathbb{Q}(\zeta)$. Let $\mathbf{C}$ denote the companion matrix of $f$, as in the lemma statement. It is well known that the characteristic (and minimal) polynomial of the companion matrix of $f$ is $f$ itself. This entails that $\mathbf{C}$ has the roots of $f$ for eigenvalues, which we denote by $\alpha_1, \dots, \alpha_n$. Recall that the field embeddings are such that $\sigma_i(\zeta) = \alpha_i$ for all $i \in [n]$. Since the roots of $f$ are distinct, it means that $\mathbf{C}$ is diagonalizable. More precisely, it holds that $\mathbf{C} = \mathbf{V}^{-1}\mathrm{diag}(\alpha_1, \dots, \alpha_n)\mathbf{V} = \mathbf{V}^{-1}\mathrm{diag}(\sigma(\zeta))\mathbf{V}$. Now let $x$ be in $K$. We have

$$ \forall y \in K, \tau(xy) = \mathbf{V}^{-1}\sigma(xy) = \mathbf{V}^{-1}\mathrm{diag}(\sigma(x))\sigma(y) = \mathbf{V}^{-1}\mathrm{diag}(\sigma(x))\mathbf{V}\tau(y), $$

thus proving that $M_{\tau}(x) = \mathbf{V}^{-1}\mathrm{diag}(\sigma(x))\mathbf{V}$. We can then rewrite this expression in terms of the $\tau_k$ and $\mathbf{C}$ as follows.

$$ \begin{aligned} \mathbf{V}^{-1}\mathrm{diag}(\sigma(x))\mathbf{V} &= \mathbf{V}^{-1}\mathrm{diag}\left(\sigma_1\left(\sum_{k=0}^{n-1}\tau_k(x)\zeta^k\right), \dots, \sigma_n\left(\sum_{k=0}^{n-1}\tau_k(x)\zeta^k\right)\right)\mathbf{V} \\ &= \sum_{k=0}^{n-1}\tau_k(x)\mathbf{V}^{-1}\mathrm{diag}(\sigma_1(\zeta)^k, \dots, \sigma_n(\zeta)^k)\mathbf{V} \\ &= \sum_{k=0}^{n-1}\tau_k(x)\mathbf{V}^{-1}\mathrm{diag}(\sigma(\zeta))^k\mathbf{V} \\ &= \sum_{k=0}^{n-1}\tau_k(x)\mathbf{C}^k, \end{aligned} $$

concluding the proof. □
**Lemma 2.3.**

*Proof.* For $(i, j)$ in $[d] \times [m]$, we define the polynomial function $a_{ij}(\cdot) : t \mapsto \sum_{k=0}^{n-1} \tau_k(a_{ij})t^k$. The way $a_{ij} \in K$ is defined, we have $a_{ij} = a_{ij}(\zeta)$. Lemma 2.2 gives $M_{\tau}(a_{ij}) = \sum_{k=0}^{n-1} \tau_k(a_{ij})C^k = a_{ij}(C)$. Finally, for $k \in [n]$, if $\alpha_k$ denotes $\sigma_k(\zeta)$, it holds that $a_{ij}(\alpha_k) = \sigma_k(a_{ij})$. We then define the function over complex matrices by $\mathbf{A}(t) = [a_{ij}(t)]_{(i,j)}$ for all $t$. By the prior observations, we get that $\mathbf{A} = \mathbf{A}(\zeta)$, $M_{\tau}(\mathbf{A}) = \mathbf{A}(C)$, and $\mathbf{A}(\alpha_k) = \sigma_k(\mathbf{A})$.

Consider $\mathbf{B}(t) = \mathbf{A}(t)^{\dagger}\mathbf{A}(t)$. The same reasoning holds for $\mathbf{A}(t)\mathbf{A}(t)^{\dagger}$. First, notice that $\mathbf{C}$ is diagonalizable with eigenvalues $\alpha_1, \dots, \alpha_n$, as its minimal polynomial is the minimal polynomial of $\zeta$. [49] then states that $\mathbf{B}(\mathbf{C})$ is diagonalizable if and only if the $n$ matrices $\mathbf{B}(\alpha_k)$ are diagonalizable, in which case the spectrum (set of eigenvalues) of $\mathbf{B}(\mathbf{C})$ is the union of the spectra of the $\mathbf{B}(\alpha_k)$. By construction, for every $k$ in $[n]$, $\mathbf{B}(\alpha_k)$ is Hermitian and therefore diagonalizable. Since the eigenvalues of $\mathbf{B}(\alpha_k)$ (resp. $\mathbf{B}(\mathbf{C})$) are the square singular values of $\mathbf{A}(\alpha_k)$ (resp. $\mathbf{A}(\mathbf{C})$), we directly get that

$$S(\mathbf{A}(\mathbf{C})) = \bigcup_{k \in [n]} S(\mathbf{A}(\alpha_k)),$$

which proves the first equality.

For the third equality, recall that $M_{\sigma_H}(\mathbf{A}) = (\mathbf{I}_d \otimes \mathbf{U}_H^{\dagger})M_{\sigma}(\mathbf{A})(\mathbf{I}_m \otimes \mathbf{U}_H)$. Since $\mathbf{U}_H$ is unitary, we have $S(M_{\sigma_H}(\mathbf{A})) = S(M_{\sigma}(\mathbf{A}))$. We now prove the second equality. Recall that $M_{\sigma}(\mathbf{A})$ is the block matrix of size $nd \times nm$ whose block $(i, j) \in [d] \times [m]$ is diag($\sigma(a_{ij})$). The matrix can therefore be seen as a $d \times m$ matrix with blocks of size $n \times n$. The idea is now to permute the rows and columns of $M_{\sigma}(\mathbf{A})$ to end up with a matrix of size $n \times n$ with blocks of size $d \times m$ only on the diagonal. For that, we define the following permutation $\pi_k$ of $[nk]$ for any positive integer $k$. For all $i \in [nk]$, write $i - 1 = k_1^{(i)} + nk_2^{(i)}$, with $k_1^{(i)} \in \{0, \dots, n-1\}$ and $k_2^{(i)} \in \{0, \dots, k-1\}$. Then, define $\pi_k(i) = 1 + k_2^{(i)} + k \cdot k_1^{(i)}$. This is a well-defined permutation based on the uniqueness of the Euclidean division. We can then define the associated permutation matrix $\mathbf{P}_{\pi_k} = [\delta_{i,\pi_k(j)}]_{(i,j) \in [nk]^2} \in \mathbb{R}^{nk \times nk}$. Then, by defining $\mathbf{P}_{\pi_d}$ and $\mathbf{P}_{\pi_m}$ as described, it holds that

$$\mathbf{P}_{\pi_d} M_{\sigma}(\mathbf{A}) \mathbf{P}_{\pi_m}^T = \begin{bmatrix} \sigma_1(\mathbf{A}) & & & \\ & \ddots & & \\ & & \sigma_n(\mathbf{A}) & \end{bmatrix}.$$

Since $\mathbf{P}_{\pi_d}, \mathbf{P}_{\pi_m}$ are permutation matrices, they are also unitary and therefore $S(M_{\sigma}(\mathbf{A})) = S(\mathbf{P}_{\pi_d} M_{\sigma}(\mathbf{A}) \mathbf{P}_{\pi_m}^T)$. As $\mathbf{P}_{\pi_d} M_{\sigma}(\mathbf{A}) \mathbf{P}_{\pi_m}^T$ is block-diagonal, it directly holds that $S(\mathbf{P}_{\pi_d} M_{\sigma}(\mathbf{A}) \mathbf{P}_{\pi_m}^T) = \bigcup_{k \in [n]} S(\sigma_k(\mathbf{A}))$, thus proving the second equality.

Finally, by taking the maximum of the sets involved in the first equality, we obtain $\|M_{\tau}(\mathbf{A})\|_2 = \max_{k \in [n]} \|\sigma_k(\mathbf{A})\|_2$ as claimed. $\square$
**Lemma 2.8.** We begin with stating some lemmas that we need for the proof. The first two bound the Rényi divergence and statistical distance, respectively, if the second distribution is the uniform distribution over the support of the first.

**Lemma B.1.** Let P be a probability distribution and Q be the uniform distribution over its support Supp(P). It holds

$$RD_2(P||Q) = |\text{Supp}(P)| \cdot \mathbb{P}[P = P'],$$

where $P \sim P'$ are independent and identically distributed.

*Proof.* By the definition of the Rényi divergence, it yields

$$RD_2(P||Q) = \sum_{x \in \text{Supp}(P)} \frac{P(x)^2}{Q(x)} = |\text{Supp}(P)| \cdot \sum_{x \in \text{Supp}(P)} P(x)^2 \\ = |\text{Supp}(P)| \cdot \mathbb{P}[P = P'].$$

□

The following result has been attributed to Rackoff by Impagliazzo and Zuckerman [22].

**Lemma B.2 ([22, Claim 2][34, Lem. 4.3]).** Let P be a probability distribution and Q be the uniform distribution over its support Supp(P). It holds

$$\Delta(P, Q) \le \frac{1}{2} \sqrt{|\text{Supp}(P)| \cdot \mathbb{P}[P = P'] - 1},$$

where $P \sim P'$ are independent and identically distributed.

We also adapt [34, Lem. 4.4] from vectors to matrices over a finite ring.

**Lemma B.3.** Let A be a finite ring and k, d be positive integers. Further, take an arbitrary vector $\mathbf{z} = (z_j)_{j \in [d]} \in A^d$. If $\mathbf{C} \sim U(A^{k \times d})$, then $\mathbf{C}\mathbf{z}$ is uniformly distributed over the module $\langle z_1, \dots, z_d \rangle^k$. In particular, the probability that $\mathbf{C}\mathbf{z} = \mathbf{0}$ is exactly $\frac{1}{|\langle z_1, \dots, z_d \rangle|^k}$.

*Proof.* Let $\mathbf{z} \in A^d$. For $\mathbf{b} \in A^k$ we define $T_{\mathbf{b}} = \{\mathbf{C} \in A^{k \times d} : \mathbf{C}\mathbf{z} = \mathbf{b}\}$. Notice that the probability that $\mathbf{C}\mathbf{z} = \mathbf{b}$ over the uniform random choice of $\mathbf{C}$ is exactly $\frac{|T_{\mathbf{b}}|}{|A|^{k \times d}}$. If $\mathbf{b} \notin \langle z_1, \dots, z_d \rangle^k$, then $T_{\mathbf{b}} = \emptyset$ and hence $\mathbb{P}_{\mathbf{C} \sim U(A^{k \times d})}[\mathbf{C}\mathbf{z} = \mathbf{b}] = 0$. We now show that all $\mathbf{b} \in \langle z_1, \dots, z_d \rangle^k$ have the same probability. Let $\mathbf{b}$ be an arbitrary element of $\langle z_1, \dots, z_d \rangle^k$, i.e., it can be represented as $\mathbf{C}\mathbf{z} = \mathbf{b}$ for some fixed $\mathbf{C} \in A^{k \times d}$. It follows that $\mathbf{C}' \in T_{\mathbf{b}}$ if and only if $\mathbf{C}' - \mathbf{C} \in T_0$. Further, the mapping $\mathbf{C}' \mapsto \mathbf{C}' - \mathbf{C}$ is a bijection between $T_{\mathbf{b}}$ and $T_0$, which implies that $|T_{\mathbf{b}}| = |T_0|$. This shows that all $\mathbf{b} \in \langle z_1, \dots, z_d \rangle^k$ have the same probability, completing the proof. □
Proof (of Lemma 2.8). Let $P$ be the distribution that samples $\mathbf{C} \leftarrow U(R_q^{k \times d})$ and $\mathbf{z} \leftarrow U(S_\eta^d)$ and outputs $(\mathbf{C}, \mathbf{C}\mathbf{z}) \in R_q^{k \times d} \times R_q^k$. Let $Q$ be the uniform distribution over the support of $P$, i.e., it samples $\mathbf{C} \leftarrow U(R_q^{k \times d})$ and $\mathbf{s} \leftarrow U(R_q^k)$, and outputs $(\mathbf{C}, \mathbf{s}) \in R_q^{k \times d} \times R_q^k$. Note that $|\text{Supp}(P)| = q^{nk(d+1)}$.

In the following we bound the collision probability of $P$ and then we simply apply Lemma B.1 and B.2 (with the finite ring $R_q$) to conclude the proof.

For $\mathbf{C}, \mathbf{C}' \sim U(R_q^{k \times d})$ and $\mathbf{z}, \mathbf{z}' \sim U(S_\eta^d)$ it yields

$$ \begin{aligned} \mathbb{P}[\mathbf{C} = \mathbf{C}' \wedge \mathbf{C}\mathbf{z} = \mathbf{C}'\mathbf{z}'] &= \mathbb{P}[\mathbf{C} = \mathbf{C}'] \cdot \mathbb{P}[\mathbf{C}\mathbf{z} = \mathbf{C}'\mathbf{z}' | \mathbf{C} = \mathbf{C}'] \\ &= \frac{1}{|R_q|^{k \cdot d}} \cdot \mathbb{P}[\mathbf{C}(\mathbf{z} - \mathbf{z}') = \mathbf{0}]. \end{aligned} $$

By Lemma B.3 over the random choice of $\mathbf{C}$ and the size of the finite ring $R_q$, we can further transform this equation to

$$ \begin{aligned} \frac{1}{q^{nk \cdot d}} \cdot \mathbb{P}[\mathbf{C}(\mathbf{z} - \mathbf{z}') = \mathbf{0}] &= \frac{1}{q^{nkd}} \cdot \sum_{I \in \mathcal{I}} \frac{\mathbb{P}[\langle z_1 - z'_1, \dots, z_d - z'_d \rangle^k = I^k]}{|I|^k} \\ &\le \frac{1}{q^{nkd}} \cdot \sum_{I \in \mathcal{I}} \frac{\mathbb{P}[\langle z_1 - z'_1, \dots, z_d - z'_d \rangle^k \subseteq I^k]}{|I|^k} \\ &= \frac{1}{q^{(nk) \cdot (d+1)}} \cdot \sum_{I \in \mathcal{I}} \frac{q^{nk}}{|I|^k} \cdot \prod_{j \in [d]} \mathbb{P}[(z_j - z'_j) \in I], \end{aligned} $$

where $\mathcal{I}$ denotes the set of all ideals in $R_q$ and we conditioned on the ideal $\langle z_1 - z'_1, \dots, z_k - z'_k \rangle$.

We now specify $\mathcal{I}$. For $K = \mathbb{Q}(\zeta)$, let $f$ be the minimal polynomial of $\zeta$ and let $f = \prod_{i \in [\kappa]} f_i$ be its factorization in irreducible polynomials in $\mathbb{Z}_q[x]$. As $\mathbb{Z}_q$ is a field, $\mathbb{Z}_q[x]$ is a principal ideal domain. The ideal correspondence theorem in commutative algebra states that every ideal in $R_q$ corresponds to an ideal in $\mathbb{Z}_q[x]$ containing $\langle f \rangle$. As each ideal in $\mathbb{Z}_q[x]$ itself is principal, thus of the form $\langle g \rangle$ for a polynomial $g \in \mathbb{Z}[x]$, this is equivalent to $g$ dividing $f$. Hence, we know that the ideals of $R_q$ are given by $\mathcal{I} = \{\langle f_G \rangle : G \subseteq \{1, \dots, \kappa\}\}$, where we define $f_G = \prod_{i \in G} f_i$. By convention, we say that the empty set $\emptyset$ defines the constant polynomial $f_\emptyset = 1$. For any $f_G$, it holds that

$$ \begin{aligned} \mathbb{P}[(z_j - z'_j) \in \langle f_G \rangle] &= \mathbb{P}[z_j = z'_j \bmod f_G] \\ &\le \max_{\tilde{z}} \mathbb{P}[z_j \bmod f_G = \tilde{z}] \le \frac{1}{(2\eta + 1)^{\deg(f_G)}}, \end{aligned} $$

where the maximum is taken over all $\tilde{z} \in R$ with $\deg(\tilde{z}) < \deg(f_G)$. As explained in [34], the last inequality follows from the fact that for any fixed value of the $n - \deg(f_G)$ highest degree coefficients of $z$, the map $z \mapsto z \bmod f_G$ is a bijection
between sets of size $(2\eta + 1)^{\deg(f_G)}$. We then get

$$ \frac{q^{nk}}{|\langle f_G \rangle|^k} \prod_{j \in [d]} \mathbb{P}[(z_j - z'_j) \in \langle f_G \rangle] \le \frac{q^{nk}}{(q^{n-\deg(f_G)})^k} \left( \frac{1}{(2\eta + 1)^{\deg(f_G)}} \right)^d \\ = \left( \frac{q^k}{(2\eta + 1)^d} \right)^{\deg(f_G)}. $$

Adding up over all ideals we can deduce

$$ \sum_{\langle f_G \rangle \in \mathcal{I}} \frac{q^{nk}}{|\langle f_G \rangle|^k} \cdot \prod_{j \in [d]} \mathbb{P}[(z_j - z'_j) \in \langle f_G \rangle] \le \sum_{G \subseteq \{1, \dots, \kappa\}} \left( \frac{q^k}{(2\eta + 1)^d} \right)^{\deg(f_G)} \\ = \prod_{i \in [\kappa]} \left( 1 + \left( \frac{q^k}{(2\eta + 1)^d} \right)^{\deg(f_i)} \right) \\ \le \prod_{i \in [\kappa]} \left( 1 + \frac{q^k}{(2\eta + 1)^d} \right)^{\deg(f_i)} \\ = \left( 1 + \frac{q^k}{(2\eta + 1)^d} \right)^n. $$

Putting everything together, it holds

$$ \mathbb{P}[P = P'] \le \left(1 + \frac{q^k}{(2\eta + 1)^d}\right)^n q^{-nk(d+1)}, $$

where $P \sim P'$ are independent and identically distributed. Using Lemma B.1 and B.2 together with $|\text{Supp}(P)| = q^{nk(d+1)}$ completes the proof. $\square$

**Lemma 2.13.**

*Proof.* First, we derive the Gaussian tail bound for a single element $a$. Notice that $\|M_{\sigma_H}(a)\|_2 = \|M_\sigma(a)\|_2 = \|\text{diag}(\sigma(a))\|_2 = \|\sigma(a)\|_\infty$. Let $a \in \mathcal{I}$ be sampled from $D_{\mathcal{I},\alpha}$. Then $\sigma_H(a)$ is distributed according to $D_{\Lambda,\alpha}$ where $\Lambda = \sigma_H(\mathcal{I})$. So $\|\sigma(a)\|_\infty = \|\mathbf{U}_H \sigma_H(a)\|_\infty \le \|\sigma_H(a)\|_\infty$. We briefly explain the last inequality. For clarity, we define $\mathbf{a} = \sigma_H(a)$. By decomposing $\mathbf{a} = [\mathbf{a}_1^T | \mathbf{a}_2^T | \tilde{\mathbf{a}}_2^T]^T$, with $\mathbf{a}_1 \in \mathbb{R}^{t_1}$ and $\mathbf{a}_2, \tilde{\mathbf{a}}_2 \in \mathbb{R}^{t_2}$, a standard calculation gives

$$ \mathbf{U}_H \mathbf{a} = \frac{1}{\sqrt{2}} \begin{bmatrix} \sqrt{2}\mathbf{a}_1 \\ \mathbf{a}_2 - i\tilde{\mathbf{a}}_2 \\ \mathbf{a}_2 + i\tilde{\mathbf{a}}_2 \end{bmatrix}. $$

Thus, $\|\mathbf{U}_H \mathbf{a}\|_\infty = \max\{\|\mathbf{a}_1\|_\infty, \|\mathbf{a}_2 + i\tilde{\mathbf{a}}_2\|_\infty/\sqrt{2}\}$. Yet $\|\mathbf{a}_1\|_\infty \le \|\mathbf{a}\|_\infty$, and for all $k \in [t_2]$, $|a_{2,k} + i\tilde{a}_{2,k}|/\sqrt{2} = \sqrt{a_{2,k}^2 + \tilde{a}_{2,k}^2}/\sqrt{2} \le \|\mathbf{a}\|_\infty$. Hence $\|\mathbf{U}_H \mathbf{a}\|_\infty \le
$\|\mathbf{a}\|_{\infty}$. By the second part of [41, Cor. 5.3] for $m = 1$, $z = 1$ and $c = 0$, it holds that for all $t \ge 0$

$$ \mathbb{P}_{a \sim \mathcal{D}_{\Lambda, \alpha}} [\|\mathbf{a}\|_{\infty} \ge \alpha t] \le 2n \cdot e^{-\pi t^2}. $$

Note that in the case where $c = 0$, the restriction of $\alpha \ge \eta_{\varepsilon}(\Lambda)$ for some $\varepsilon \le 1/(2m + 1)$ is not necessary, and the calculation of the bound on the probability saves a factor of $e$ for that reason. With the observation that $\|\sigma(a)\|_{\infty} \le \|\sigma_H(a)\|_{\infty}$ it holds

$$ \mathbb{P}_{a \sim \mathcal{D}_{\mathcal{I}, \alpha}} [\|\sigma(a)\|_{\infty} \le \alpha t] \ge \mathbb{P}_{a \sim \mathcal{D}_{\mathcal{I}, \alpha}} [\|\sigma_H(a)\|_{\infty} \le \alpha t] \ge 1 - 2n \cdot e^{-\pi t^2}. $$

Now let $\mathbf{N}$ be sampled from $\mathcal{D}_{\mathcal{I}, \alpha}^{m \times d}$. Fix any vector $\mathbf{x} = [\mathbf{x}_1^T, \dots, \mathbf{x}_d^T]^T \in \mathbb{C}^{nd}$, where each $\mathbf{x}_i \in \mathbb{C}^n$. It holds that $\|M_{\sigma}(\mathbf{N})\mathbf{x}\|_2^2 = \sum_{i \in [m]} \|\sum_{j \in [d]} M_{\sigma}(n_{i,j})\mathbf{x}_j\|_2^2$. Yet, for each $i \in [m]$, we have

$$ \left\| \sum_{j \in [d]} M_{\sigma}(n_{i,j}) \mathbf{x}_j \right\|_2 \le \sum_{j \in [d]} \| M_{\sigma}(n_{i,j}) \|_2 \| \mathbf{x}_j \|_2 \le \sqrt{\sum_{j \in [d]} \| M_{\sigma}(n_{i,j}) \|_2^2} \sqrt{\sum_{j \in [d]} \| \mathbf{x}_j \|_2^2} \\ = \sqrt{\sum_{j \in [d]} \| M_{\sigma}(n_{i,j}) \|_2^2 \| \mathbf{x}_j \|_2}. $$

Using the tail bound that we previously derived, a union bound on $(i, j) \in [m] \times [d]$ yields the claim. $\square$

**Lemma 2.14.**

*Proof.* We simply use the definition of the multiplication matrix which yields that $\sigma_H(\mathbf{y}) = M_{\sigma_H}(\mathbf{U})\sigma_H(\mathbf{e})$. Then, since $\sigma_H(\mathbf{e})$ is distributed according to $D_{\sqrt{\mathbf{s}}}$, a standard fact on multi-dimensional Gaussian distributions gives that $\sigma_H(\mathbf{y})$ is Gaussian with covariance matrix $M_{\sigma_H}(\mathbf{U})\mathbf{S}M_{\sigma_H}(\mathbf{U})^T = \mathbf{\Sigma}$. We note that it still applies in the degenerate case. In particular, the result still holds when $\mathbf{S}, \mathbf{U}$ are not full-rank, and also when $m > d$ which automatically results in $\mathbf{\Sigma}$ being singular. $\square$

**Lemma 2.15.** We need a result on the sum of independent Gaussian distributions. We therefore extend a result on the sum of a continuous Gaussian and a discrete one to more general Gaussian distributions. In particular, the lemma works for two elliptical Gaussians, which we use in the proof of Lemma 2.15.

**Lemma B.4 (Adapted from [24, Lem. 2.8] & [47, Claim 3.9]).** Let $\Lambda$ be an $n$-dimensional lattice, $\mathbf{a} \in \mathbb{R}^n$, $\mathbf{R}, \mathbf{S}$ two positive definite matrices of $\mathbb{R}^{n \times n}$, and $\mathbf{T} = \mathbf{R} + \mathbf{S}$. We define $\mathbf{U} = (\mathbf{R}^{-1} + \mathbf{S}^{-1})^{-1}$, and assume that $\rho_{\sqrt{\mathbf{U}}^{-1}}(\Lambda^*) \le 1 + \varepsilon$ for some $\varepsilon \in (0, 1/2)$. Consider the distribution $Y$ on $\mathbb{R}^n$ obtained by adding a discrete sample from $\mathcal{D}_{\Lambda+a, \sqrt{\mathbf{R}}}$ and a continuous sample from $D_{\sqrt{\mathbf{s}}}$.
Proof (of Lemma B.4). The density function Y is given by

$$
\begin{align*}
Y(\mathbf{x}) &= \sum_{\mathbf{y} \in \Lambda + \mathbf{a}} D_{\Lambda + \mathbf{a}, \sqrt{\mathbf{R}}} (\mathbf{y}) D_{\sqrt{\mathbf{S}}} (\mathbf{x} - \mathbf{y}) \\
&= \frac{1}{\rho_{-\mathbf{a}, \sqrt{\mathbf{R}}} (\mathbf{A}) \sqrt{\det \mathbf{S}}} \sum_{\mathbf{y} \in \Lambda + \mathbf{a}} \rho_{\sqrt{\mathbf{R}}} (\mathbf{y}) \rho_{\sqrt{\mathbf{S}}} (\mathbf{x} - \mathbf{y}) \\
&= \frac{1}{\rho_{-\mathbf{a}, \sqrt{\mathbf{R}}} (\mathbf{A}) \sqrt{\det \mathbf{S}}} \sum_{\mathbf{y} \in \Lambda + \mathbf{a}} \rho_{\sqrt{\mathbf{T}}} (\mathbf{x}) \rho_{\mathbf{R}\mathbf{T}^{-1}\mathbf{x}, \sqrt{\mathbf{U}} (\mathbf{y})} \quad [43, \text{Fact 2.1}]. \\
&= \frac{\rho_{\sqrt{\mathbf{T}}} (\mathbf{x})}{\sqrt{\det \mathbf{T}}} \cdot \frac{\sqrt{\det \mathbf{T}} \rho_{\mathbf{R}\mathbf{T}^{-1}\mathbf{x}, \sqrt{\mathbf{U}}} (\mathbf{A})}{\sqrt{\det \mathbf{S}} \rho_{-\mathbf{a}, \sqrt{\mathbf{R}}} (\mathbf{A})} \\
&= D_{\sqrt{\mathbf{T}}} (\mathbf{x}) \cdot \frac{(\sqrt{\det \mathbf{R}} \sqrt{\det \mathbf{S}} / \sqrt{\det \mathbf{T}})^{-1} \widehat{\rho_{\mathbf{x}', \sqrt{\mathbf{U}}}} (\mathbf{A}^*)}{(\sqrt{\det \mathbf{R}})^{-1} \widehat{\rho_{-\mathbf{a}, \sqrt{\mathbf{R}}}} (\mathbf{A}^*)},
\end{align*}
$$

where $\mathbf{x}' = \mathbf{R}\mathbf{T}^{-1}\mathbf{x}$, and $\hat{f}$ denotes the Fourier transform of $f$. First notice that $(\det \mathbf{R} \cdot \det \mathbf{S}) / \det \mathbf{T} = 1 / \det (\mathbf{R}^{-1}\mathbf{T}\mathbf{S}^{-1}) = 1 / \det \mathbf{U}^{-1}$. Moreover, recalling that $\widehat{\rho_{c, \sqrt{\Sigma}}}(\mathbf{w}) = \sqrt{\det \Sigma}e^{-2i\pi\langle \mathbf{c}, \mathbf{w} \rangle} \rho_{\sqrt{\Sigma}^{-1}}(\mathbf{w})$, we get

$$
|1 - (\sqrt{\det \mathbf{U}})^{-1} \widehat{\rho_{\mathbf{x}', \sqrt{\mathbf{U}}}}(\mathbf{A}^*)| \le \rho_{\sqrt{\mathbf{U}}^{-1}}(\mathbf{A}^* \setminus \{0\}) \le \varepsilon.
$$

For the denominator, we first notice that for two positive semi-definite matrices $\mathbf{A}$ and $\mathbf{B}$, if $\mathbf{A} - \mathbf{B}$ is positive semi-definite, then $\rho_{\sqrt{\mathbf{A}}}(\mathbf{w}) \ge \rho_{\sqrt{\mathbf{B}}}(\mathbf{w})$ for all $\mathbf{w} \in \mathbb{R}^n$. Since $\mathbf{U}^{-1} - \mathbf{R}^{-1} = \mathbf{S}^{-1}$ is positive semi-definite, it yields $\rho_{\sqrt{\mathbf{R}}^{-1}}(\mathbf{A}^* \setminus \{0\}) \le \rho_{\sqrt{\mathbf{U}}^{-1}}(\mathbf{A}^* \setminus \{0\}) \le \varepsilon$. Therefore, using the same method as above, we get

$$
|1 - (\sqrt{\det \mathbf{R}})^{-1} \widehat{\rho_{-\mathbf{a}, \sqrt{\mathbf{R}}}}(\mathbf{A}^*)| \le \rho_{\sqrt{\mathbf{R}}^{-1}}(\mathbf{A}^* \setminus \{0\}) \le \varepsilon.
$$

which leads to

$$
\frac{(\sqrt{\det \mathbf{R}} \sqrt{\det \mathbf{S}} / \sqrt{\det \mathbf{T}})^{-1} \widehat{\rho_{\mathbf{x}', \sqrt{\mathbf{U}}}}(\mathbf{A}^*)}{(\sqrt{\det \mathbf{R}})^{-1} \widehat{\rho_{-\mathbf{a}, \sqrt{\mathbf{R}}}}(\mathbf{A}^*)} \in \left[ \frac{1-\varepsilon}{1+\varepsilon}, \frac{1+\varepsilon}{1-\varepsilon} \right] \subseteq [1-2\varepsilon, 1+4\varepsilon],
$$

assuming that $\varepsilon < 1/2$. We thus end up with $|Y(\mathbf{x}) - D_{\sqrt{\mathbf{T}}} (\mathbf{x})| \le 4\varepsilon D_{\sqrt{\mathbf{T}}} (\mathbf{x})$. Integration and factor 1/2 of the statistical distance yield the lemma. $\square$

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].

**Lemma B.5 ([24, Lem. 2.13]).** Let $\mathbf{r} \in (\mathbb{R}^+)^n \cap H$, $\mathbf{z} \in K^d$ fixed and $\mathbf{e} \in K_{\mathbb{R}}^d$ sampled from $D_{\sqrt{\Sigma}}$, where $\sqrt{\Sigma} = [\delta_{i,j}\mathrm{diag}(\mathbf{r})]_{i,j \in [d]} \in \mathbb{R}^{nd \times nd}$. Then $\langle \mathbf{z}, \mathbf{e} \rangle = \sum_{i \in [d]} z_i e_i$ is distributed according to $D_{\mathbf{r}'}$ with $r'_{j} = r_j \sqrt{\sum_{i \in [d]} |\sigma_j(z_i)|^2}$.
Proof (of Lemma 2.15). Consider $\mathbf{h} \in (K_{\mathbb{R}})^d$ distributed according to $D_{\mathbf{r}',...,\mathbf{r}'}$, where $\mathbf{r}'$ is given by $r'_j = \gamma/\sqrt{\sum_{i \in [d]} |\sigma_j(z_i)|^2}$ for $j \in [n]$. Then by Lemma B.5, $\langle \mathbf{z}, \mathbf{h} \rangle$ is distributed as $D_{\gamma}$ and therefore $\Delta(\langle \mathbf{z}, \mathbf{v} \rangle + e, D_{\mathbf{r}}) = \Delta(\langle \mathbf{z}, \mathbf{v} + \mathbf{h} \rangle, D_{\mathbf{r}})$. Now, we denote $\mathbf{t}$ such that $t_j = \sqrt{\beta^2 + (r'_j)^2}$ for $j \in [n]$. Note that by assumption

$$ \min_{j \in [n]} \beta r'_j / t_j = (1/\beta^2 + \max_{j \in [n]} \sum_{i \in [d]} |\sigma_j(z_i)|^2 / \gamma^2)^{-1/2} \\ = (1/\beta^2 + \|\mathbf{z}\|_{2,\infty}^2 / \gamma^2)^{-1/2} \ge \eta_{\varepsilon}(M). $$

Lemma B.4 therefore applies and yields that $\mathbf{v} + \mathbf{h}$ is distributed as $D_{\mathbf{t},...,\mathbf{t}}$, within statistical distance at most $2\varepsilon$. By applying once more Lemma B.5 and noticing that the statistical distance does not increase when applying a function (here the inner product with $\mathbf{z}$), then we get that $\langle \mathbf{z}, \mathbf{v} + \mathbf{h} \rangle$ is distributed as $D_{\mathbf{r}}$ within statistical distance at most $2\varepsilon$, where $r_j = t_j \sqrt{\sum_{i \in [d]} |\sigma_j(z_i)|^2} = \sqrt{\beta^2 \sum_{i \in [d]} |\sigma_j(z_i)|^2 + \gamma^2}$ for $j \in [n]$. $\square$

## B.2 Missing Proofs of Section 3

### Lemma 3.4.

*Proof.* Let $\mathcal{O}$ be an oracle for ext-M-LWE$^{\ell}_{n,k,m,q,\psi,\mathcal{Z}}$. For each $i \in \{0, ..., \ell\}$, we denote by $\mathcal{H}_i$ the hybrid distribution defined as

$$ (\mathbf{A}, [\mathbf{b}_1, ..., \mathbf{b}_i, \mathbf{u}_{i+1}, ..., \mathbf{u}_{\ell}], [\langle \mathbf{e}_j, \mathbf{z} \rangle]_{j \in [\ell]}), $$

where $\mathbf{A} \sim U(R_q^{m \times k})$, the $\mathbf{u}_j$ are independent and identically distributed (i.i.d.) from $U((q^{-1}R/R)^m)$, the $\mathbf{e}_j$ are i.i.d. from $\psi^m$, and $\mathbf{b}_j = q^{-1}\mathbf{A}\mathbf{s}_j + \mathbf{e}_j \mod R$ for $\mathbf{s}_j$ i.i.d. from $U(R_q^k)$ for every $j \in [\ell]$. By definition, we have $\mathrm{Adv}[\mathcal{O}] = |\mathbb{P}[\mathcal{O}(\mathcal{H}_\ell) = 1] - \mathbb{P}[\mathcal{O}(\mathcal{H}_0) = 1]|$. The reduction $\mathcal{A}$ works as follows.

1. Sample $\mathbf{z} \leftarrow U(\mathcal{Z})$ and get $(\mathbf{A}, \mathbf{b}, \langle \mathbf{e}, \mathbf{z} \rangle)$ as input of ext-M-LWE$^{1}_{n,k,m,q,\psi,\mathcal{Z}}$.

2. Sample $i^* \leftarrow U([\ell])$.

3. Sample $\mathbf{s}_1, ..., \mathbf{s}_{i^*-1} \leftarrow U(R_q^k)$, $\mathbf{e}_1, ..., \mathbf{e}_{i^*-1}, \mathbf{e}_{i^*+1}, ..., \mathbf{e}_\ell \leftarrow \psi^m$ and finally $\mathbf{u}_{i^*+1}, ..., \mathbf{u}_\ell \leftarrow U((q^{-1}R/R)^m)$.

4. Compute $\mathbf{b}_j = q^{-1}\mathbf{A}\mathbf{s}_j + \mathbf{e}_j \mod R$ for all $j \in [i^* - 1]$.

5. Define the hybrid matrix $\mathbf{B} = [\mathbf{b}_1, ..., \mathbf{b}_{i^*-1}, \mathbf{b}, \mathbf{u}_{i^*+1}, ..., \mathbf{u}_\ell]$, and the error matrix $\mathbf{E} = [\mathbf{e}_1, ..., \mathbf{e}_{i^*-1}, \mathbf{e}, \mathbf{e}_{i^*+1}, ..., \mathbf{e}_\ell]$. Then call the oracle $\mathcal{O}$ on input $(\mathbf{A}, \mathbf{B}, \mathbf{E}^T\mathbf{z})$, and return the same output as $\mathcal{O}$.

If $\mathbf{b}$ is uniform, then the distribution in 5. is exactly $\mathcal{H}_{i^*-1}$ whereas if $\mathbf{b}$ is M-LWE, then the distribution is $\mathcal{H}_{i^*}$. By a standard hybrid argument, the oracle can distinguish between the two for some $i^*$ if it can distinguish between $\mathcal{H}_0$ and $\mathcal{H}_\ell$. So the output is correct over the randomness of $i^*$. Since $i^*$ is uniformly chosen
we have

$$
\begin{align*}
\mathrm{Adv}[\mathcal{A}] &= |\mathbb{P}[\mathcal{A}(\mathbf{b} \text{ M-LWE}) = 1] - \mathbb{P}[\mathcal{A}(\mathbf{b} \text{ uniform}) = 1]| \\
&= \left| \sum_{i^* \in [\ell]} \frac{1}{\ell} \mathbb{P}[\mathcal{A}(\mathcal{H}_{i^*}) = 1] - \sum_{i^* \in [\ell]} \frac{1}{\ell} \mathbb{P}[\mathcal{A}(\mathcal{H}_{i^*-1}) = 1] \right| \\
&= \frac{1}{\ell} \mathrm{Adv}[\mathcal{O}].
\end{align*}
$$

□

B.3 Missing Proofs of Section 4

Lemma 4.1.

Proof. We start by describing the transformation $T$ of [36] to move from M-LWE to M-ISIS. Given $(\mathbf{A}, \mathbf{b}) \in R_q^{m \times d} \times R^m$, where $\mathbf{A}$ is uniformly sampled, $T$ first checks if the rows of $\mathbf{A}$ generate $R_q^d$. If not, $T$ returns $\perp$. By the quantity defined in Section 2.1, $T$ aborts at this step with probability $\delta(m, d)$ (which can be upper bound from Lemma 2.6). We now condition on $\mathbf{A}$ being non-singular. From $\mathbf{A}$, $T$ computes $\mathbf{B} \in R_q^{m \times (m-d)}$ whose columns generate the set of vectors $\mathbf{x} \in R_q^m$ that verify $\mathbf{A}^T\mathbf{x} = \mathbf{0} \bmod qR$. $T$ samples $\mathbf{U} \in R_q^{(m-d) \times (m-d)}$ uniformly at random such that $\mathbf{U}$ is invertible in $R_q$, and define $\mathbf{B}' = \mathbf{B}\mathbf{U}$. As $\mathbf{A}$ is uniform in the set of non-singular matrices, $\mathbf{B}'$ is uniform in the set of matrices whose rows generate $R_q^{m-d}$. Again, by definition of $\delta(\cdot, \cdot)$, we get $\Delta(\mathbf{B}', U(R_q^{m \times (m-d)})) \le \delta(m, m-d)$. Finally, $T$ computes $\mathbf{c} = \mathbf{B}'^T\mathbf{b} \bmod qR$, and returns $(\mathbf{B}', \mathbf{c})$.

Assume that there exists an adversary $\mathcal{A}$ that attacks the $\varepsilon'$-uninvertibility of M-ISIS. We construct $\mathcal{B}$ that breaks the $\varepsilon$-uninvertibility of M-LWE by calling $\mathcal{A}$ on the sampled transformed by $T$. Consider $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e} \bmod qR)$, with $(\mathbf{s}, \mathbf{e}) \leftarrow U(R_q^d) \times \mathcal{X}$. We denote $E$ the event $\{\mathcal{B}(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e} + qR) = (\mathbf{s}, \mathbf{e})\}$. Then

$$
\begin{align*}
\mathbb{P}[E] &= \mathbb{P}[\mathbf{A} \text{ non-singular}] \mathbb{P}[E | \mathbf{A} \text{ non-singular}] + \mathbb{P}[\mathbf{A} \text{ singular}] \underbrace{\mathbb{P}[E | \mathbf{A} \text{ singular}]}_{0 \text{ (abort)}} \\
&= (1 - \delta(m, d)) \mathbb{P}[\mathcal{A}(\mathbf{B}', \mathbf{c}) = \mathbf{e} | \mathbf{A} \text{ non-singular}] \\
&> (1 - \delta(m, d)) \cdot (\varepsilon' - \delta(m, m-d)) \\
&= \varepsilon.
\end{align*}
$$

Indeed, by the transformation, we have

$$
\begin{align*}
(\mathbf{B}')^T \mathbf{b} \bmod qR &= (\mathbf{B}')^T \mathbf{A}\mathbf{s} + (\mathbf{B}')^T \mathbf{e} \bmod qR \\
&= (\mathbf{A}^T \mathbf{B}' \bmod qR)^T \mathbf{s} + (\mathbf{B}')^T \mathbf{e} \bmod qR \\
&= (\mathbf{B}')^T \mathbf{e} \bmod qR.
\end{align*}
$$
Then, $\mathcal{B}$ uses linear algebra to recover $\mathbf{s}$ from $\mathbf{b} - \mathbf{e}$. The proof for one-wayness is the same where $E = \{g_A(\mathcal{B}(\mathbf{A}, \mathbf{As} + \mathbf{e} \mod qR)) = \mathbf{As} + \mathbf{e} \mod qR\}$ (recalling that $g_A(\mathbf{s}, \mathbf{e}) = \mathbf{As} + \mathbf{e} \mod qR$). For the pseudorandomness, we define $E = \{\mathcal{B}(\mathbf{A}, \mathbf{b} \text{ uniform}) = 1\}$, $E' = \{\mathcal{B}(\mathbf{A}, \mathbf{b} = \mathbf{As} + \mathbf{e} \mod qR) = 1\}$, and $F$ the event $\{\mathbf{A} \text{ non singular}\}$. It then holds that

$$ \begin{aligned} & |\mathbb{P}[E] - \mathbb{P}[E'|\mathbf{A}|\mathbf{s} \text{ non-singular}]| \\ & = \mathbb{P}[\mathbf{A} \text{ non-singular}] \cdot |\mathbb{P}[E|\mathbf{A} \text{ non-singular}] - \mathbb{P}[E'|\mathbf{A} \text{ non singular}]| \\ & = (1 - \delta(m, d)) |\mathbb{P}[\mathcal{A}(\mathbf{B}', \mathbf{c} \text{ uniform}) = 1|F] - \mathbb{P}[\mathcal{A}(\mathbf{B}', (\mathbf{B}')^T \mathbf{e} \mod qR) = 1|F]| \\ & > (1 - \delta(m, d)) \cdot (\varepsilon' - 2\delta(m, m - d)) \\ & = \varepsilon, \end{aligned} $$

concluding the proof.

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

**Lemma 4.2.**

*Proof.* The transformation $T$ now works as follows. Given $(\mathbf{B}, \mathbf{c}) \in R_q^{m \times (m-d)} \times R^{m-d}$ with $\mathbf{B}$ uniformly distributed, $T$ checks whether the rows of $\mathbf{B}$ generate $R_q^{m-d}$. If not, it aborts, and that with probability $\delta(m, m - d)$. Conditioning on $\mathbf{B}$ being non-singular, $T$ computes $\mathbf{A} \in R_q^{m \times d}$ that generate $\{\mathbf{x} \in R_q^m: \mathbf{B}^T \mathbf{x} = \mathbf{0} \mod qR\}$. The transformation then randomizes $\mathbf{A}$ by a random matrix $\mathbf{U} \in R_q^{d \times d}$ that is invertible in $R_q$ to obtain $\mathbf{A}' = \mathbf{AU}$. Similarly as in the previous proof, $\Delta(\mathbf{A}', U(R_q^{m \times d})) \le \delta(m, d)$. Then, $T$ finds a vector $\mathbf{b}$ such that $\mathbf{B}^T \mathbf{b} = \mathbf{c} \mod qR$, and returns $(\mathbf{A}', \mathbf{b})$. Note that if $\mathbf{c} = \mathbf{B}^T \mathbf{e} \mod qR$ for some $\mathbf{e} \leftarrow \mathcal{X}$, then $\mathbf{b} - \mathbf{e}$ is in the span of the columns of $\mathbf{A}'$ and therefore, there exists $\mathbf{s} \in R_q^d$ such that $\mathbf{b} - \mathbf{e} = \mathbf{A}' \mathbf{s} \mod qR$. If $\mathbf{c}$ is uniform, we can argue that $\mathbf{b}$ is also uniform. Using the same calculations as before, we get that

$$ \mathrm{Adv}[\mathcal{B}] > (1 - \delta(m, m - d)) \cdot (\varepsilon' - \delta(m, d)) = \varepsilon, $$

where $\mathrm{Adv}[\mathcal{B}]$ denotes the probability of breaking uninvertibility or one-wayness, or the absolute difference of probability in the case of pseudorandomness. $\square$

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

**Lemma 4.5.**

*Proof.* Consider the distribution $\mathcal{D}$ supported over $R_q^d \times R_q$ that is either $A_{s,\psi}$ or $U(R_q^d \times R_q)$.

*Construction:* Sample independently $((\mathbf{a}_i, b_i))_{i \in [m']}$ from $\mathcal{D}$. In both cases, the first component is uniformly distributed over $R_q^d$. If there is no subset $S \subseteq [m']$ of size $d$ such that the $(\mathbf{a}_i)_{i \in S}$ are $R_q$-linearly independent, the reduction aborts. By the quantity defined in Section 2.1, this happens with probability $\delta'(m', d)$. So now, we assume that there exists a set $S \subseteq [m']$ of size $d$ such that the $(\mathbf{a}_i)_{i \in S}$ are $R_q$-linearly independent. Consider the matrix $\bar{\mathbf{A}} \in R_q^{d \times d}$ whose rows are the $(\mathbf{a}_i^T)_{i \in S}$, and $\bar{\mathbf{b}} \in R_q^d$ whose coefficients are the $(b_i)_{i \in S}$. By construction, $\bar{\mathbf{A}}$ is invertible in $R_q^{d \times d}$. Additionally, if $\mathcal{D} = A_{s,\psi}$, then $\bar{\mathbf{b}} = \bar{\mathbf{A}}\mathbf{s} + \mathbf{x} \mod qR^\vee$ for $\mathbf{x}$
sampled from $\psi^d$. On the other hand, if $\mathcal{D} = U(R_q^d \times R_q)$, then $\bar{b}$ is uniform over $R_q^d$.

**Reduction:** The transformation $T$ works as follows. Given $(\mathbf{a}, b)$ sampled from $\mathcal{D}$ as input:

- Compute $\mathbf{a}' = -(\bar{\mathbf{A}})^{-T} \cdot \mathbf{a} \bmod qR$;

- Compute $b' = b + \langle \mathbf{a}', \bar{\mathbf{b}} \rangle \bmod qR$;

- Output $(\mathbf{a}', b')$.

First, we verify that $(\mathbf{a}', b')$ indeed belongs to $R_q^d \times R_q$. Since $\bar{\mathbf{A}}$ is invertible modulo $qR$, then $-(\bar{\mathbf{A}})^{-T}$ is in $R_q^{d \times d}$. Therefore, $\mathbf{a}'$ is also in $R_q^d$. Additionally, as $\bar{\mathbf{b}} \in R_q^d$, $\langle \mathbf{a}', \bar{\mathbf{b}} \rangle$ is in $R$. It thus holds that $b'$ is in $R_q$.

As $-(\bar{\mathbf{A}})^{-T}$ is invertible modulo $qR$, and $\mathbf{a}$ is uniform in $R_q^d$, then $\mathbf{a}'$ is also uniform in $R_q^d$. Now, we look at the distribution of $b'$ in both cases. First, assume that $\mathcal{D} = A_{\mathbf{s},\psi}$. Then $b = \langle \mathbf{a}, \mathbf{s} \rangle + e \bmod qR$ for some $e \leftarrow \psi$, and $\bar{\mathbf{b}} = \bar{\mathbf{A}}\mathbf{s} + \mathbf{x} \bmod qR$. It holds that

$$ 
\begin{aligned}
b' &= \langle \mathbf{a}, \mathbf{s} \rangle + e + \langle \mathbf{a}', \bar{\mathbf{A}}\mathbf{s} + \mathbf{x} \rangle \bmod qR \\
&= \langle \mathbf{a} + \bar{\mathbf{A}}^T \mathbf{a}', \mathbf{s} \rangle + \langle \mathbf{a}', \mathbf{x} \rangle + e \bmod qR \\
&= \langle \mathbf{a}', \mathbf{x} \rangle + e \bmod qR.
\end{aligned}
$$

So $(\mathbf{a}', b')$ is indeed distributed according to $A_{\mathbf{x},\psi}$ for $\mathbf{x} \leftarrow \psi^d$ as desired. Now assume that $\mathcal{D} = U(R_q^d \times R_q)$. Then $b$ is uniform over $R_q$ and $\bar{\mathbf{b}}$ is uniform over $R_q^d$. So $b'$ is clearly uniform over $R_q$ as well, proving that $(\mathbf{a}', b')$ is uniformly distributed over $R_q^d \times R_q$ as desired. $\square$