# Cryptanalysis of rank-2 module-LIP in Totally Real Number Fields

Guilhem Mureau, Alice Pellet-Mary, Georgii Pliatsok, Alexandre Wallet

► To cite this version:

Guilhem Mureau, Alice Pellet-Mary, Georgii Pliatsok, Alexandre Wallet. Cryptanalysis of rank-2 module-LIP in Totally Real Number Fields. Eurocrypt 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2024, Zurich, Switzerland. pp.226-255, 10.1007/978-3-031-58754-2_9. hal-04701342

HAL Id: hal-04701342

https://hal.science/hal-04701342v1

Submitted on 18 Sep 2024

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Cryptanalysis of rank-2 module-LIP in Totally Real Number Fields

Guilhem Mureau¹, Alice Pellet-Mary¹, Heorhii Pliatsok²,³, and Alexandre Wallet³

¹ Univ Bordeaux, CNRS, Inria, Bordeaux INP, IMB, UMR 5251, Talence, France
guilhem.mureau@math.u-bordeaux.fr
alice.pellet-mary@math.u-bordeaux.fr

² Insitute of Mathematics, NAS of Ukraine
georgiipliatsok@icloud.com

³ Univ Rennes, Inria, CNRS, Irisa, UMR 6074, France
alexandreima wallet@inria.fr

**Abstract.** At Asiacrypt 2022, Ducas, Postlethwaite, Pulles, and van Woerden introduced the Lattice Isomorphism Problem for module lattices in a number field $K$ (module-LIP). In this article, we describe an algorithm solving module-LIP for modules of rank 2 in $K^2$, when $K$ is a totally real number field. Our algorithm exploits the connection between this problem, relative norm equations and the decomposition of algebraic integers as sums of two squares. For a large class of modules (including $O_K^2$), and a large class of totally real number fields (including the maximal real subfield of cyclotomic fields) it runs in classical polynomial time in the degree of the field and the residue at 1 of the Dedekind zeta function of the field (under reasonable number theoretic assumptions). We provide a proof-of-concept code running over the maximal real subfield of some cyclotomic fields. As a side contribution, we also provide some algorithmic and theoretical tools for the future study of the module-LIP problem.

**Keywords:** Module Lattices · Lattice Isomorphism Problem · Cryptanalysis.

## 1 Introduction

The Lattice Isomorphism Problem (LIP) is an algorithmic problem recently introduced in cryptography [15,2]. In its search version, LIP asks to find a linear isometry, that is, a distance-preserving linear transformation, mapping a lattice $L_1$ onto an isomorphic lattice $L_2$.<fnref n="4" /> The decisional variant asks, given two lattices $L_1$ and $L_2$, to determine whether they are isomorphic. Algorithms for solving either variant of the problems have been studied independently of cryptography first [31,21]. In cryptography, the LIP problem was initially studied

<footnote n="4">⁴ Lattices are geometric objects, so an isomorphism between lattices should respect the group structure *and* the geometry.</footnote>
as a way to cryptanalyse the GGH and NTRU signatures [34], but the new cryptographic constructions based on LIP have motivated a lot of recent crypt-analytic works [7,27,13,12,14]. A classical approach for solving the search variant is to enumerate (possibly many) short vectors in both lattices and then to re-construct linear isometries matching these short vectors by using a backtracking algorithm [31,16]. An alternative approach, which gives the best asymptotic complexity, is due to Haviv and Regev [21]: it finds all linear isometries between two isomorphic lattices in time $n^{O(n)}$, where $n$ is the dimension of the lattice. To our current understanding, it seems that LIP is at least as hard as the Shortest Vector Problem (SVP), since all known algorithms solving LIP require to solve SVP first.

An algebraic variant of LIP (named module-LIP) was introduced in 2023 in [14], and used to construct the scheme Hawk, currently in evaluation in NIST's additional call for digital post-quantum signatures.<fnref n="5" /> The security of the scheme is related to the hardness to find a given isomorphism to $O_K^2$, where $O_K$ is the ring of integers of a power-of-two cyclotomic field. More precisely, recovering such an isomorphism would provide a key-recovery attack on Hawk (up to an automorphism). Note that the converse is not known: there is for the moment no security proof reducing the module-LIP problem to the security of Hawk. The authors of [14] provided some analysis on the security of this new variant of LIP, based on the algorithms solving LIP in the unstructured case. In other words, so far, the only algorithms we know for solving the module-LIP variant from [14] consist in forgetting about the algebraic structure, treating the instance as a non-structured one. Generally, the cryptographic novelty of the problem means that there are few tools for cryptanalysts to understand it. The main goal of this work is to initiate the development of these tools, motivated by the following question:

> *Is it possible to exploit the algebraic structure of module-LIP to solve it more efficiently than LIP?*

**Contributions.** Our main contribution is an algorithm solving module-LIP when the module $M \subset K^2$ has rank-2 and when the number field $K$ is a totally real number field.<fnref n="6" /> An important family of totally real fields is $K = \mathbb{Q}(\zeta + \zeta^{-1})$, with $\zeta$ a primitive root of unity, which is a degree 2 subfield of the cyclotomic field $\mathbb{Q}(\zeta)$, called its maximal totally real subfield. The precise complexity of our algorithm is related to arithmetic properties of the module. Informally, when the “gap” between the ideal generated by the coordinates of vectors in the module and the ideal generated by the norms of these vector is small, our algorithm runs in polynomial time (in the size of the input and in some field related quantities, including the residue $\rho_K$ of the zeta function). This is the case for the important module $M = O_K^2$ for which the result is stated in Corollary 4.7.

<footnote n="5">⁵ https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures</footnote>

<footnote n="6">⁶ Our algorithm relies on arithmetic properties of the module, and does not extend to modules $M \subset K_{\mathbb{R}}^2$, where $K_{\mathbb{R}} := K \otimes_{\mathbb{Q}} \mathbb{R}$.</footnote>
The general complexity statement of the algorithm (for any totally real field $K$ and any module $M \subset K^2$) is provided in Corollary 4.8. We want to stress that this result *does not* break the Hawk signature scheme. Indeed, our algorithm only works for totally real number fields, whereas the Hawk scheme is defined over a power-of-two cyclotomic field. However, our algorithm rules out a large class of possibly interesting fields, showing that using them for instantiations could result in an insecure scheme.

We provide a proof-of-concept implementation of our algorithm using a mix of Sagemath [36] and PARI/GP [35]. The code is available at https://gitlab.inria.fr/capsule/code-for-module-lip. We were able to run our algorithm successfully on module lattices isomorphic to $O_K^2$, when $K$ is the maximal totally real subfield of a cyclotomic field up to conductor 256 (which means that the lattices involved have dimension 128) — see also Table 1.

As a side contribution, we also develop some new tools and security foundations for the future study of the module-LIP problem. We extend the definition of module-LIP from [14] to cover all modules, using the notion of pseudo-bases [10] (the definition from [14] was restricted to free modules, represented by a basis). While our formulation is slightly different from the one in [14], we still have the property that solving module-LIP for our definition leads to a key recovery attack on Hawk (up to an isomorphism). We also extend standard tools for the unstructured case to the module setting, such as a worst-case to average-case reduction<fnref n="7" /> and algorithms such as the Cholesky decomposition.

**Technical details.** A central tool for our definition of module-LIP is the notion of pseudo-Gram matrices. Modules usually do not admit bases but only pseudo-bases, as defined by Cohen in [10]. A pseudo-basis $\mathbf{B}$ of a module $M$ consists of a matrix $\mathbf{B} \in K^{\ell \times \ell}$ and a list of $\ell$ fractional ideals $I_1, \dots, I_\ell$, such that $M = \{\sum_i x_i \mathbf{b}_i | x_i \in I_i\}$, where $\mathbf{b}_i$ are the columns of $\mathbf{B}$. In a natural way, we define the pseudo-Gram matrix associated to the pseudo-basis $\mathbf{B}$ to be $\mathbf{G} = (B^*\mathbf{B}, (I_i)_{1 \le i \le \ell})$.

In the same way that a Gram matrix-based formulation is the better fit in the unstructured case, this basic ingredient leads us to a well-defined version of the module-LIP problem. Let $\mathbf{B}, \mathbf{C}$ be two pseudo-bases of a module $M$, and let $\mathbf{G}$ be the pseudo-Gram matrix of $\mathbf{C}$ (the pseudo-basis $\mathbf{B}$ is fixed, and will be a parameter of the problem). The module-LIP problem with parameter $\mathbf{B}$ (wc-smodLIP$_K^{\mathbf{B}}$) is, given as input $\mathbf{G}$, to recover a pseudo-basis $\mathbf{C}'$ of $M$ such that its Gram matrix is $\mathbf{G}$ ($\mathbf{C}$ is a solution to this problem, but it may not be unique).<fnref n="8" /> Let us explain briefly why this definition of the module-LIP problem includes the problem underlying the security of Hawk. In Hawk, the secret key is a basis $\mathbf{C}$ of $O_K^2$, and the public key contains the Gram matrix $\mathbf{G} = \mathbf{C}^*\mathbf{C}$. Since $O_K^2$ is free, no ideals are involved. The secret key $\mathbf{C}$ is then a solution of the

<footnote n="7">⁷ A structured variant of this reduction was already present in [14, Lemma 5] for cyclotomic number fields and free modules. We extend it to all number fields and modules.</footnote>

<footnote n="8">⁸ This definition is not formulated exactly in the same way as Definition 3.11 below, but both are equivalent.</footnote>
module-LIP problem with parameter $I_2$ (the trivial basis of $O_K^2$), on input $G$. It can be checked that any other solution $C'$ to this problem can be used to forge valid signatures.

The tools that we provide in Section 3 for manipulating module-LIP are generalization of the results known for non-structured lattices. This extension is easy once the formal framework is set up. For example, the worst-case to average-case reduction (Appendix A) is the adaptation to the module context of the reduction provided in [15]. The latter used a standard algorithm in lattice theory, which computes a short basis of a lattice $L$ given as input short linearly independent vectors and a (potentially large) basis of $L$. A module variant of this algorithm was provided in [18], and we used it to complete our reduction.

**Algorithm for module-LIP.** We now explain how our algorithm for module-LIP works, when $K$ is totally real. To simplify the description in this introduction, we will restrict ourselves to the case where the problem is parameterized by the module $O_K^2$ (with basis $B = I_2$), and where the input of the problem is a Gram matrix $G$ (instead of a pseudo-Gram matrix $G$). In other words, we are given as input $G \in M_2(O_K)$ are we are asked to compute $C \in GL_2(O_K)$ a basis of $O_K^2$ such that $C^*C = C^T C = G$. We are thus looking for $u, v, r, t \in O_K^2$ such that

$$ \begin{pmatrix} u & v \\ r & t \end{pmatrix} \cdot \begin{pmatrix} u & r \\ v & t \end{pmatrix} = \begin{pmatrix} u^2 + v^2 & ur + vt \\ ur + vt & r^2 + v^2 \end{pmatrix} = G. $$

The diagonal coefficients of $G$ must hence be the sum of two squares in $O_K$. Sums of two squares $x^2 + y^2 = a$ over $\mathbb{Z}$ are the topic of Fermat's two-squares theorem. Algorithms such as Cornacchias's allow to find all solutions of this equation efficiently, and the equation usually does not have too many solutions (this depends on the number of prime factors of $a$). A similar situation happens when $\mathbb{Z}$ is changed to the ring of integers $O_K$ of a totally real field $K$.

Let us explain the principles behind the algorithm solving equations of the form $x^2 + y^2 = a$ (with unknowns $x, y \in O_K$). As $K$ is totally real, it contains no square roots of $-1$. Thus there is a quadratic extension $L = K(i)$ where $i$ is such that $i^2 = -1$. To any solution $(x, y)$ of our equation corresponds the element $z := x + iy \in O_L$. By definition of $L$, the relative norm $N_{L|K}(z)$ of this element is precisely $z\bar{z} = x^2 + y^2 = a$. Hence, two-squares decompositions reduces to the computation of all solutions $z \in O_L$ of $z\bar{z} = a$.<fnref n="9" />

To solve this norm equation $N_{L|K}(z) = a$, we use the Gentry-Szydlo algorithm, as described by Lenstra and Silverberg in [24]. Given $a = z\bar{z} \in O_K$ and $I = zO_L$, the Gentry-Szydlo algorithms recovers $z$ in polynomial time. To apply it in our setting, we then need to compute the ideal $I = zO_L$ for all possible solutions $z$. To do so, we observe that $I \cdot \bar{I} = z\bar{z}O_L = aO_L$ is known. Hence, the ideals $I$ we are looking for are principal divisors of the ideal $aO_L$. It then only remains to factor the ideal $aO_L$ and test all possible divisors $I$ of it. The

<footnote n="9">⁹ The set of $z \in O_L$ with $z\bar{z} = a$ might be strictly larger than the set of solutions, since we may have $O_K + iO_K \subsetneq O_L$, but we can easily check, given a $z = x + iy$ if $(x, y)$ is a solution to our equation.</footnote>
number of such divisors is exponential in the number of prime factors of $a\mathcal{O}_L$, so our algorithm is, also, exponential in the number of prime factors of $a\mathcal{O}_L$. These two steps are handled by our provided code.

Combining everything, we obtain an algorithm which finds all the matrices $C \in M_2(\mathcal{O}_K)$ such that $C^T C = G$ (so it solves module-LIP), but whose complexity is, for the moment, exponential in the number of prime factors of the diagonal coefficients $q_1$ and $q_2$ of the Gram matrix $G$. To make this algorithm polynomial time, we re-randomize the matrix $G$ (by computing $G' = U^{-1}GU$ with $U \in \text{GL}_2(\mathcal{O}_K)$, which transforms $C$ into $C' = CU$), until its two diagonal coefficients $q_1$ and $q_2$ are prime. Under some heuristic (formalised in Assumption 1), we expect to find a good re-randomized matrix $G'$ in polynomial time polynomial in the input size and in $\rho_K$, the residue of the Dedekind zeta function of $K$ at 1.

# 2 Preliminaries

*Notations.* Vectors are by default column vectors, and are denoted by bold lower case letters (e.g., $\mathbf{v}$). Matrices are denoted by non-bold upper case letters (e.g., $B$), and pseudo-matrices by bold upper case letters (e.g., $\mathbf{B}$). For a ring $R$, we write $\text{GL}_n(R)$ the set of $n \times n$ matrices whose determinant is an invertible element of $R$. We let $\mathcal{O}_n(\mathbb{R})$ be the set of orthogonal real matrices, $\mathcal{U}_n(\mathbb{C})$ be the set of unitary complex matrices, $S_n^{>0}(\mathbb{R})$ be the set of real symmetric positive definite matrices, and $\mathcal{H}_n^{>0}(\mathbb{C})$ be the set of complex Hermitian positive definite matrices. For vectors $\mathbf{v}$ in $\mathbb{R}^n$ or in $\mathbb{C}^n$, we let $\|\mathbf{v}\|$ (resp. $\|\mathbf{v}\|_{\infty}$, $\|\mathbf{v}\|_1$) denote their $\ell_2$ (resp. $\ell_{\infty}$, $\ell_1$) norm. For a matrix $B \in \mathbb{C}^{n \times m}$ with column vectors $\mathbf{b}_1, \dots, \mathbf{b}_m$, we use the notation $\|B\| := \max_i \|\mathbf{b}_i\|$. For a field $K$ and a subset $S$ of a $K$-vector space $H$, we write $\text{Span}_K(S)$ for the $K$-vector subspace of $H$ spanned by $S$. We use log to refer to the natural logarithm (in base e).

## 2.1 Lattices

We call lattice any set of the form $L = \sum_{1 \le i \le r} \mathbf{b}_i \cdot \mathbb{Z}$, where $\mathbf{b}_1, \dots, \mathbf{b}_n \in \mathbb{R}^m$ are $\mathbb{R}$-linearly independent vectors. It is a discrete additive subgroup of $\mathbb{R}^m$. The integer $n$ is called the rank of $L$, when $n = m$ we say that the lattice has full rank. The matrix $B = (\mathbf{b}_1 | \dots | \mathbf{b}_n)$ is called a basis of $L$ and all bases of $L$ are obtained by multiplication on the right by a unimodular matrix $U \in \text{GL}_n(\mathbb{Z})$. For a given matrix $B \in \text{GL}_n(\mathbb{R})$, we write $L(B)$ the lattice spanned by $B$. The determinant (or volume) of a lattice $L$ is $\det(L) := \sqrt{\det(B^T \cdot B)}$ for any basis $B$ of $L$. For $1 \le i \le n$, the $i$-th successive minimum $\lambda_i(L)$ of the lattice $L$ is the smallest real number $r > 0$ such that the set $\{\mathbf{v} \in L \mid \|\mathbf{v}\| \le r\}$ spans a real vector space of dimension at least $i$. We define analogously the successive minima of $L$ in the $\ell_{\infty}$-norm. Minkowski's first theorem states that $\lambda_1^{(\infty)}(L) \le \det(L)^{1/n}$ and $\lambda_1(L) \le \sqrt{n} \cdot \det(L)^{1/n}$. The dual of a lattice $L$ is the lattice $L^* = \{\mathbf{x} \in \text{Span}_{\mathbb{R}}(L) \mid \langle \mathbf{x}, \mathbf{v} \rangle \in \mathbb{Z}, \forall \mathbf{v} \in L\}$.
**The lattice isomorphism problem.** Two lattices $L, L'$ (with respective bases $B, B'$) are said isomorphic if there exists an orthogonal transformation $O$ such that $L' = O \cdot L$. In terms of matrices, $L(B)$ and $L(B')$ are isomorphic if and only if there exists a unimodular transformation $U \in GL_n(\mathbb{Z})$ such that $B' = OBU$. The search version of the problem is precisely to find either such $O$ or $U$.

**Definition 2.1 (wc-sLIP<sup>B</sup>).** For a matrix $B \in GL_n(\mathbb{R})$, the worst-case search Lattice Isomorphism Problem with parameter $B$ (wc-sLIP<sup>B</sup>) is, given a basis $B' \in GL_n(\mathbb{R})$ of a lattice $L' \subset \mathbb{R}^n$ isomorphic to $L(B)$, to find $O \in O_n(\mathbb{R})$ or $U \in GL_n(\mathbb{Z})$ such that $B' = OBU$.

For convenience, we restate LIP in terms of quadratic forms. The Gram matrix associated to a basis $B \in GL_n(\mathbb{R})$ is the definite positive quadratic form $G = B^T B \in S_n^{>0}(\mathbb{R})$. Two quadratic forms $Q, Q' \in S_n^{>0}(\mathbb{R})$ are said congruent if there exists $U \in GL_n(\mathbb{Z})$ such that $Q' = U^TQU$.

**Definition 2.2 (wc-sLIP<sup>Q</sup>).** For a quadratic form $Q \in S_n^{>0}(\mathbb{R})$, the worst-case search LIP problem with parameter $Q$ (wc-sLIP<sup>Q</sup>) is, given any quadratic form $Q' \in S_n^{>0}(\mathbb{R})$ congruent to $Q$, to find a unimodular transformation $U \in GL_n(\mathbb{Z})$ such that $Q' = U^TQU$.

The two problems are polynomial-time equivalent, thanks to the Cholesky decomposition for quadratic forms.

**Discrete Gaussian distributions.** The Gaussian function over $\mathbb{R}^m$ with parameter $s \in \mathbb{R}_{>0}$ is $\rho_s(v) = \exp(-\pi \cdot \|v\|^2/s^2)$ for all $v \in \mathbb{R}^m$. For a rank-$n$ lattice $L \subset \mathbb{R}^m$, the discrete Gaussian distribution $D_{L,s}$ over $L$ with parameter $s$ (and center 0) is the probability distribution defined over $L$ by

$$ \Pr_{X \sim D_{L,s}} (X = v) = \frac{\rho_s(v)}{\rho_s(L)}, $$

for all $v \in L$, where $\rho_s(L) = \sum_{v \in L} \rho_s(v)$.

For $\varepsilon > 0$ and $L$ a rank-$n$ lattice, the smoothing parameter $\eta_\varepsilon(L)$ is the smallest real number $s > 0$ such that $\rho_{1/s}(L^* \setminus \{0\}) \le \varepsilon$. Instantiating [28, Lemma 3.3] with $\varepsilon = 1/2$, we obtain the following upper bound, for any rank-$n$ lattice $L$

$$ \eta_{1/2}(L) \le \sqrt{\frac{\log(6n)}{\pi}} \cdot \lambda_n(L). \qquad (1) $$

**Lemma 2.3 (Proof of [28, Lemma 4.4]).** Let $L$ be a rank-$n$ lattice, $\varepsilon > 0$ and $s \ge \eta_\varepsilon(L)$, then

$$ \rho_s(L) \in [1 - \varepsilon, 1 + \varepsilon] \cdot \frac{s^n}{\det(L)}. $$

One can efficiently sample discrete Gaussian distributions over lattices, provided the parameter $s$ is large enough.
**Lemma 2.4 (Weakening of [6, Lemma 2.3]).** There is a probabilistic polynomial time algorithm Discrete Gaussian (B, s) that takes as input a basis B of an n-dimensional lattice and a parameter s ≥ $\sqrt{\log(2n + 4)/\pi} \cdot \max_i ||b_i||$ (where b_i are the columns of B) and returns a sample from $D_{L,s}$.

Note that the lower bound on s, in our statement above, is slightly larger than the one provided in [6, Lemma 2.3] (it involves the euclidean norm of the column vectors of B, instead of the Gram-Schmidt orthogonalization of B), but this will be sufficient for our purposes in this article.

**Lemma 2.5 ([17, Lemma A.5]).** For any rank-n lattice L with basis B = ($b_i$)$_{1 \le i \le n}$, if $s \ge \sqrt{n} \cdot \max_i ||b_i||$, then for any $\varepsilon \in (0, 1]$ it holds that

$$ \mathrm{Pr}_{v \sim D_{L,s}} (||v|| > s\sqrt{4n + \log(1/\varepsilon)}) \le \varepsilon. $$

## 2.2 Number fields

A number field K is a finite extension of the field of rational numbers $\mathbb{Q}$. Any such K is isomorphic to $\mathbb{Q}[X]/(P)$ for an irreducible monic polynomial $P \in \mathbb{Q}[X]$. The degree of P is exactly the degree of the extension. Furthermore, any extension K of degree d comes naturally with d embeddings $K \to \mathbb{C}$, sending the class of X to a complex root of P. An embedding $\sigma: K \to \mathbb{C}$ such that $\sigma(K) \subset \mathbb{R}$ is called a real embedding. An embedding $\sigma$ which is not real is called complex. In this case, it can be composed with complex conjugation and gives another distinct complex embedding $\bar{\sigma}$. We denote by $d_1$ the number of real embeddings and $d_2$ the number of complex embeddings up to complex conjugation, so that $d = d_1 + 2d_2$. We order the embeddings $\sigma_1, \dots, \sigma_d$ such that $\sigma_i$ is a real embedding for $1 \le i \le d_1$ and $\sigma_{i+d_2} = \bar{\sigma}_i$ for $d_1 < i \le d_1 + d_2$. When $d_1 = d$ (resp. $2d_2 = d$), we say that the extension K|$\mathbb{Q}$ is totally real (resp. totally imaginary).

The space $K_{\mathbb{R}}$. The $\mathbb{R}$-algebra $K_{\mathbb{R}} := K \otimes_{\mathbb{Q}} \mathbb{R}$ is a real vector space of dimension d. If $K \sim \mathbb{Q}[X]/(P)$, then we have an identification $K_{\mathbb{R}} \sim \mathbb{R}[X]/(P)$. The embeddings of K can be uniquely extended to $K_{\mathbb{R}}$, which leads to the so-called canonical embedding $\sigma(x) = (\sigma_1(x), \dots, \sigma_d(x)) \in \mathbb{C}^d$. This map defines a ring homomorphism from $K_{\mathbb{R}}$ to $\sigma(K_{\mathbb{R}})$, which is the d-dimensional real vector space

$$ \sigma(K_{\mathbb{R}}) := \{z = (z_i)_i \in \mathbb{C}^d \mid z_1, \dots, z_{d_1} \in \mathbb{R}, \overline{z_{d_1+i}} = z_{d_1+d_2+i}, 1 \le i \le d_2\}. $$

To any $z \in K_{\mathbb{R}}$ we associate its complex conjugate $\bar{z} := \sigma^{-1}(\sigma(z)) \in K_{\mathbb{R}}$, where $\sigma(z)$ consists in taking the complex conjugation of $\sigma(z) \in \mathbb{C}^d$ coordinate-wise. We let $K_{\mathbb{R}}^+$ (resp. $K_{\mathbb{R}}^{++}$) be the subset of $K_{\mathbb{R}}$ corresponding to elements with all non-negative (resp. positive) embeddings (in particular, the complex embeddings are all real numbers). The norm map defined over $K_{\mathbb{R}}$ is $N_K(z) = \prod_i \sigma_i(z)$, and extends the well-known notion of algebraic norm for elements of K. Similarly, the trace map is $\mathrm{Tr}_K(z) = \sum_i \sigma_i(z)$. When there is no ambiguity, we drop the subscript. If $z \in K$ (resp. $\mathcal{O}_K$), then $\mathcal{N}(z), \mathrm{Tr}(z) \in \mathbb{Q}$ (resp. $\mathbb{Z}$).
Another important notion of size for $K_{\mathbb{R}}$ is the corresponding "$T_2$-norm" $\|z\|^2 := \|\sigma(z)\|^2 = \mathrm{Tr}(z\bar{z}) \in \mathbb{R}^+$.

We extend the canonical embedding to vectors of $K_{\mathbb{R}}^k$ and matrices in $K_{\mathbb{R}}^{k \times k'}$ by applying it coordinate-wise. We say that $r$ vectors $b_1, \cdots, b_r$ in $K_{\mathbb{R}}^k$ are $(K_{\mathbb{R}})$-linearly independent if there exists no non-zero $r$-tuple $x = (x_1, \cdots, x_r) \in K_{\mathbb{R}}^r \setminus \{0\}$ such that $\sum_i x_i b_i = 0$. Note that, since $K_{\mathbb{R}}$ is not a field, this notion can be interesting even for $r = 1$ vector: a vector $b \in K_{\mathbb{R}}^k$ is linearly independent if and only if $\sigma_i(b) \neq 0$ for all embeddings $\sigma_i$. For a matrix $B \in K_{\mathbb{R}}^{k \times k'}$, we let $B^* = \bar{B}^T$; this covers vectors $(k$ or $k'$ is 1). We let $\mathcal{U}_k(K_{\mathbb{R}})$ denote the group of unitary matrices of $K_{\mathbb{R}}$, that is the matrices $B \in \mathrm{GL}_k(K_{\mathbb{R}})$ such that $B^* \cdot B = I_k$. Thanks to the injectivity of the canonical embedding, it holds that $B$ is in $\mathcal{U}_k(K_{\mathbb{R}})$ if and only if $\sigma_i(B) \in \mathcal{U}_k(\mathbb{C})$ for all embeddings $\sigma_i$. For $v = (v_i)_i$ and $w = (w_i)_i \in K_{\mathbb{R}}^k$ (for some $k \ge 1$), we define

$$ \langle v, w \rangle_{K_{\mathbb{R}}} := v^* w = \sum_i \bar{v_i} \cdot w_i \in K_{\mathbb{R}}. $$

This extends the $T_2$-norm to $K_{\mathbb{R}}^k$ as $\|v\|^2 := \mathrm{Tr}(v, v)_{K_{\mathbb{R}}} = \sum_i \mathrm{Tr}(v_i \bar{v_i}) = \|\sigma(v)\|^2$.

**Ring of integers.** We denote by $\mathcal{O}_K$ the ring of integers of a number field $K$. The ring $\mathcal{O}_K$ is a free $\mathbb{Z}$-module of rank $d$. The discriminant of $K$ is defined by $(\mathrm{det}(\sigma_i(e_j))_{i,j})^2 \in \mathbb{Z}$, where $(e_i)_{1 \le i \le d}$ is any $\mathbb{Z}$-basis of $\mathcal{O}_K$ (this does not depend on the choice of the basis). Its absolute value is denoted $\Delta_K$. There exists some absolute constant $c$ such that $\Delta_K \ge c^d$ for all number fields $K$. In particular, we always have $d = \mathrm{poly}(\log \Delta_K)$.

A special case that will be of interest for us in Section 4.3 is when $K$ is totally real and $L = K[X]/(X^2+1)$. In this case, we have $\Delta_L | 4^d \Delta_K^2$. This can be obtained using the formula $\Delta_L = \mathcal{N}_K(\Delta_{L|K}) \cdot \Delta_K^{[L:K]}$ and the fact that $\Delta_{L|K}$ divides $\mathrm{disc}(X^2+1) \cdot \mathcal{O}_K = 4 \cdot \mathcal{O}_K$ (see [33, III, §4, Proposition 8] and [33, III, §2, Corollary to Proposition 5] with lattices $X = \mathcal{O}_L$ and $X' = \mathcal{O}_K[i]$). In particular for these extensions we always have $\log \Delta_L = \mathrm{poly}(\log \Delta_K)$. Moreover, we also know how to compute $\mathcal{O}_L$ efficiently from $\mathcal{O}_K$, as stated in the following lemma.

**Lemma 2.6 (Specialization of [9, Theorem 1.2]).** Let $K$ be a totally real number field and $L := K[X]/(X^2+1)$. There exists a polynomial time algorithm $\mathcal{A}$ that, given as input a $\mathbb{Z}$-basis $B_K$ of $\mathcal{O}_K$, computes a $\mathbb{Z}$-basis $B_L$ of $\mathcal{O}_L$.

*Proof.* We apply Buchmann-Lenstra algorithm to the order $\mathcal{O} = \mathcal{O}_K[X]/(X^2+1)$ of $L$, with basis $B = B_0 \cup X \cdot B_0$. One can prove that in our situation, the index $[\mathcal{O}_L : \mathcal{O}]$ is a power of two so it is enough to make it 2-maximal, i.e., we can take $m = 2$ in input of the algorithm. $\square$

**Residue.** We write $\rho_K$ the residue of the zeta function of $K$ at $s = 1$. This is a positive number, which is always $\le \mathcal{O}(\log \Delta_K)^d$ [25, Theorem 1]. In some number fields, such as when $K$ is a cyclotomic fields, we have better bounds, and we know that $\rho_K = \mathrm{poly}(d)$ [5, Theorem A.5]. Unfortunately, we are not
aware of a proven polynomial bound for the maximal totally real subfield of a
cyclotomic field (for these fields, the best bound we found was $\rho_K = O(1.31^d)$
[37, Lemma 11.5]). However, in practice, in all our experiments with maximal
totally real subfield of a cyclotomic field, we observed that the residue $\rho_K$ was
quite small.

**Ideals.** An integral ideal **a** is an additive subgroup of $O_K$ such that $x \cdot **a** \subset **a**$ for all $x \in O_K$. Equivalently, it is an $O_K$-module contained in $O_K$.<fnref n="10" /> An ideal generated by a single element $a$ is called principal, and is denoted by $aO_K$. A fractional ideal $I$ of $K$ is any additive subgroup of $K$ of the form $x \cdot **a**$ where $x \in K \setminus \{0\}$ and **a** $\subset O_K$ is an integral ideal. We use fraktur lower-case letters for integral ideals (e.g., **a**, **b**) and upper-case letters for fractional ideals (e.g., $I$, $J$). The product of two fractional ideals $I$ and $J$ is the smallest ideal containing all products $xy$ for $x \in I$ and $y \in J$, denoted by $IJ$. This operation turns the set of non-zero fractional ideals into a multiplicative group. Given two fractional ideals $I$ and $J$, we have that $I \subseteq J$ if and only if there exists an integral ideal **a** such that $I = J \cdot **a**$. When this is the case, we say that $J$ divides $I$, and we may write $J|I$. An integral ideal **p** is prime when $\mathfrak{p} \neq \{0\}$ and $ab \in \mathfrak{p}$ implies $a \in \mathfrak{p}$ or $b \in \mathfrak{p}$ — such ideals are maximal in $O_K$. We have unique factorization of integral ideals into prime ideals (up to permutation of the factors).

The algebraic norm of an integral ideal is $\mathcal{N}(\mathfrak{a}) = |O_K/\mathfrak{a}|$. It is multiplicative, extends to fractional ideals as $\mathcal{N}(I) = \mathcal{N}(dI)/\mathcal{N}(d)$ for any $d$ such that $dI$ is integral. If $I = aO_K$ is principal, then $\mathcal{N}(I) = |\mathcal{N}(a)|$.

**Modules.** In this article, an (*O*<sub>*K*</sub>-)module *M* will refer to a subset of *K*<sub>*R*</sub><sup>*l*</sup> of the form **b**<sub>1</sub>*I*<sub>1</sub> + ... + **b**<sub>*r*</sub>*I*<sub>*r*</sub>, where the *I*<sub>*i*</sub> are non-zero fractional ideals of *K* and (**b**<sub>1</sub>, ..., **b**<sub>*r*</sub>) are *K*<sub>*R*</sub>-linearly independent vectors of *K*<sub>*R*</sub><sup>*l*</sup>, for some *l* > 0. The integer *r* is called the rank of the module. When *r* = *l*, we say that the module has full rank. When *M* ⊂ (*O*<sub>*K*</sub>)<sup>*l*</sup> (resp. *M* ⊂ *K*<sup>*l*</sup>), we say *M* is an integer module (resp. a rational module). We say that **B** = (*B*, {*I*<sub>*i*</sub>}<sub>1≤*i*≤*r*</sub>) is a pseudo-basis for *M*, where *B* ∈ *K*<sub>*R*</sub><sup>*l*×*r*</sup> is the matrix whose columns are the **b**'<sub>*i*</sub>s. Two pseudo-bases **B** = (*B*, {*I*<sub>*i*</sub>}<sub>1≤*i*≤*r*</sub>) and **B**' = (*B*', {*J*<sub>*i*</sub>}<sub>1≤*i*≤*r*</sub>) represent the same module if and only if there exists *U* = (*u*<sub>*i*,*j*</sub>)<sub>1≤*i*,*j*≤*r*</sub> ∈ <sup>GL</sup><sub>*r*</sub>(*K*) such that **B**' = *BU* and *u*<sub>*i*,*j*</sub> ∈ *I*<sub>*i*</sub>*J*<sub>*j*</sub><sup>-1</sup>, *v*<sub>*i*,*j*</sub> ∈ *J*<sub>*i*</sub>*I*<sub>*j*</sub><sup>-1</sup>, where *V* = (*v*<sub>*i*,*j*</sub>)<sub>1≤*i*,*j*≤*l*</sub> = *U*<sup>-1</sup>.<sup>11</sup> Given a module *M* and a non-zero fractional ideal *J*, we define *J* · *M* to be the smallest module containing all α · **v** for α ∈ *J* and **v** ∈ *M*. If **B** = (*B*, {*I*<sub>*i*</sub>}<sub>1≤*i*≤*r*</sub>) is a pseudo-basis of *M*, then **B**' = (*B*, {*J* · *I*<sub>*i*</sub>}<sub>1≤*i*≤*r*</sub>) is a pseudo-basis of *J* · *M*.

If $M \subset K_{\mathbb{R}}^l$ is a module of rank $r$, then the set $\sigma(M) := \{\sigma(\mathbf{v}) \mid \mathbf{v} \in M\}$ is a module lattice, that is, a lattice of rank $dr$ in the real space $\sigma(K_{\mathbb{R}})^l$ equipped with the (extended) $T_2$-norm. Since we always use the canonical embedding to view modules as lattices in this work, we will simplify notations and write $\lambda_i(M)$ and $\det(M)$ instead of $\lambda_i(\sigma(M))$ and $\det(\sigma(M))$.

<footnote n="10">¹⁰ Note that $\mathcal{O}_K$ is a Dedekind ring. In particular, it is Noetherian, so all ideals are finitely generated as $\mathcal{O}_K$-module.</footnote>

<footnote n="11">¹¹ When $M \subset K^l$ is a rational module, these are the conditions for $U$ to be a pseudo-base change matrix, see [10].</footnote>
A special case of module lattices is when $M = I$ is a non-zero fractional ideal of $K$. In this case, we know that $\det(I) = \sqrt{\Delta_K} \cdot \mathcal{N}(I)$ (see e.g., [30, Chapter I. Proposition 5.2]). We also know that the successive minima of $\sigma(I)$ cannot be very unbalanced. More precisely, we have

$$ \lambda_d(I) \le \Delta_K^{1/d} \cdot \lambda_1(I) \le \sqrt{d} \cdot \Delta_K^{3/(2d)} \cdot \mathcal{N}(I)^{1/d}. \quad (2) $$

The second inequality follows from Minkowski's first theorem, and the equality $\det(I) = \Delta_K^{1/2} \cdot \mathcal{N}(I)$. This first inequality can be obtained by choosing $x \in I$ reaching $\lambda_1(I)$ (i.e., such that $\|\sigma(x)\| = \lambda_1(I)$) and $\{\alpha_1, \dots, \alpha_d\}$ linearly independent elements of $\mathcal{O}_K$ reaching the successive minima in infinity norm (i.e., such that $\|\sigma(\alpha_i)\|_{\infty} = \lambda_i^{(\infty)}(\mathcal{O}_K)$). Then $\{\alpha_1 x, \dots, \alpha_d x\}$ are $\mathbb{Z}$-linearly independent elements of $I$ thus $\lambda_d(I) \le \max_i ||\sigma(\alpha_i x)|| \le ||\sigma(x)|| \cdot \lambda_d^{\infty}(\mathcal{O}_K)$. The desired upper bound is then obtained by the fact that $\lambda_d^{(\infty)}(\mathcal{O}_K) \le \Delta_K^{1/d}$ (see [3] for the asymptotic result and [5, Theorem A.4] for the upper bound with an explicit constant).

In the general case, the volume of a module $M$ of rank $r$ with pseudo-basis $(B, (I_i)_i)$ is $\det(M)^2 = \Delta_K^r \cdot \det(B^*B) \cdot \prod_{i=1}^r \mathcal{N}(I_i)^2$.

**CM extensions.** A CM (complex multiplication) extension is any quadratic extension $L|K$ of number fields such that $K$ is totally real and $L$ is totally imaginary. In the rest of this article, we will always use the convention that the degree of $K$ is $d$, and the degree of $L$ is $2d$. A typical example to keep in mind is when $L$ is a cyclotomic field and $K$ is its maximal totally real subfield.

Any CM extension $L|K$ is Galois, and so $L$ has two field automorphisms fixing $K$ point-wise, namely the identity and another automorphism which we will call $\tau$. The automorphism $\tau$ somehow plays the role of a complex conjugation on $L$, as can be seen in the following lemma.

**Lemma 2.7.** Let $L|K$ be a CM extension of number fields and $\sigma_i$ be an embedding of $L$ in $\mathbb{C}$. Then $\sigma_i(\tau(x)) = \bar{\sigma}_i(x)$ for all $x \in L$.

*Proof.* First, observe that the composition map $\sigma_i \circ \tau$ is an embedding of $L$. Moreover, since $\tau$ is the identity on $K$, then it must be that $\sigma_i \circ \tau = \sigma_i$ on $K$, which restricts it to be either $\sigma_i$ or $\bar{\sigma}_i$. Finally, $\tau$ is not the identity on $L$, and $\sigma_i$ is injective, hence we cannot have $\sigma_i \circ \tau = \sigma_i$ and we conclude that $\sigma_i \circ \tau = \bar{\sigma}_i$ as desired. $\square$

For an element $x \in L$, the relative norm of $x$ is defined as $N_{L|K}(x) := x \cdot \tau(x)$, which is an element of $K$ (since it is fixed by $\tau$). We also define similarly the relative norm of a fractional ideal $I$ of $L$: $N_{L|K}(I) := I \cdot \tau(I) \cap K$, where $\tau(I) := \{\tau(x) | x \in I\}$ is also a fractional ideal of $L$. Finally, if $I = x\mathcal{O}_L$ is a principal ideal, then it holds that $N_{L|K}(I) = N_{L|K}(x) \cdot \mathcal{O}_K$.

*Splitting of prime ideals in CM extensions.* Let $p$ be a prime ideal in $\mathcal{O}_K$. Then, $p\mathcal{O}_L$ is an integral ideal of $\mathcal{O}_L$ and one of the three situations holds for its
factorization into prime ideals (see e.g., [30, Chap 2. Proposition 8.2])

$$ \mathfrak{p}\mathcal{O}_L = \begin{cases} \mathfrak{q} & \text{with } \mathfrak{q} \text{ prime and } \mathcal{N}_{L|K}(\mathfrak{q}) = \mathfrak{p}^2 \text{ (inert case),} \\ \mathfrak{q}_1\mathfrak{q}_2 & \text{with } \mathfrak{q}_1 \neq \mathfrak{q}_2 \text{ prime and } \mathcal{N}_{L|K}(\mathfrak{q}_i) = \mathfrak{p} \text{ (split case),} \\ \mathfrak{q}^2 & \text{with } \mathfrak{q} \text{ prime and } \mathcal{N}_{L|K}(\mathfrak{q}) = \mathfrak{p} \text{ (ramified case).} \end{cases} \quad (3) $$

This implies in particular the following result.

**Lemma 2.8.** Let $\mathfrak{q}$ be a prime ideal of $\mathcal{O}_L$ and $\mathfrak{p}$ be a prime ideal of $\mathcal{O}_K$. If $\mathfrak{p}$ divides $\mathcal{N}_{L|K}(\mathfrak{q})$, then $\mathfrak{q}$ divides $\mathfrak{p}\mathcal{O}_L$.

*Proof.* Since $\mathfrak{q}$ is prime, then $\mathfrak{a} = \mathfrak{q} \cap \mathcal{O}_K$ is a prime ideal of $\mathcal{O}_K$. Moreover, $\mathfrak{a}\mathcal{O}_L \subseteq \mathfrak{q}$, i.e., $\mathfrak{q}$ divides $\mathfrak{a}\mathcal{O}_L$. Equation (3) gives us all the possibilities for the factorization of $\mathfrak{a}\mathcal{O}_L$ into prime ideals, from which we conclude that $\mathcal{N}_{L|K}(\mathfrak{q}) = \mathfrak{a}$ or $\mathcal{N}_{L|K}(\mathfrak{q}) = \mathfrak{a}^2$. This implies that $\mathfrak{p} = \mathfrak{a}$, and concludes the proof. $\square$

## 2.3 Algorithmic considerations

This section collects various computational results. In this article, we assume a model of computation where computers have access to infinite precision real numbers. Most of the time, we will work with elements of $K$ which we can represent with rational numbers, and for which we define a notion of size. When we need to work with complex numbers, we assume that we have enough precision so that all computations are correct.

*Representation of ideals and modules.* We assume in this article that we are always given an LLL reduced basis $\alpha_1, \dots, \alpha_d$ of $\mathcal{O}_K$, i.e., such that $(\sigma(\alpha_i))_i$ is an LLL-reduced basis of $\mathcal{O}_K$. Elements in $K$ (resp. $K_\mathbb{R}$) are represented by their coordinates in the basis $(\alpha_1, \dots, \alpha_d)$, which is a vector in $\mathbb{Q}^d$ (resp $\mathbb{R}^d$). For $x \in K$ represented by the vector $(x_1, \dots, x_d) \in \mathbb{Q}^d$, we define size($x$) := $\sum_i$ size($x_i$), where the size of a rational number $a/b$ with $a$ and $b$ coprime is $\lceil \log_2 |a| \rceil + \lceil \log_2 |b| \rceil$. Since $(\alpha_i)_i$ is LLL-reduced for the canonical embedding, [18, Lemma 2] states that if $x = \sum_i x_i \alpha_i \in K$, then $\max_i |x_i| \le 2^{3d/2} \cdot \|\sigma(x)\|$. This implies in particular that for any integral $x \in \mathcal{O}_K$, size($x$) = poly($d$, $\|\sigma(x)\|$). Inversely, we have $\|\sigma(x)\| \le \sum_i |x_i| \cdot \|\sigma(\alpha_i)\| \le d^{3/2} \cdot 2^d \cdot \Delta_K^{1/d} \cdot \max_i |x_i|$ (where we used the fact that $\lambda_d(\mathcal{O}_K) \le \sqrt{d} \cdot \Delta_K^{1/d}$). This implies that for any rational $x \in K$, we have $\|\sigma(x)\| \le \text{poly}(\log \Delta_K, \text{size}(x))$.

A fractional ideal $I$ is represented by a $\mathbb{Z}$-basis $(y_1, \dots, y_d)$ of the ideal, such that $(\sigma(y_i))_i$ is an LLL-reduced basis of $\sigma(I)$. In particular, we have

$$ \|\sigma(y_i)\| \le 2^d \cdot \lambda_d(I) \le \sqrt{d} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \mathcal{N}(I)^{1/d}, \quad (4) $$

where we used Inequality (2). We define size($I$) := $\sum_i$ size($y_i$). If $\mathfrak{a}$ is an integral ideal, then (4) shows that size($\mathfrak{a}$) = poly(log $\Delta_K$, log $\mathcal{N}(\mathfrak{a})$). By default, in the rest of this article, whenever an algorithm takes as input, manipulates, or returns an ideal, we implicitly assume that the ideal is represented as described above.
For vectors and matrices with coefficients in $K$, we define their size as the sum of the size of their coordinates. Modules in $K^\ell$ are represented by a pseudo-basis $B = (B, (I_i))$, where $B$ is a matrix with coefficients in $K$ and the $I_i$'s are fractional ideals, represented by LLL-reduced bases as discussed above. We define $\text{size}(B) := \text{size}(B) + \sum_i \text{size}(I_i)$.

*Basic algorithms for number fields.* If $x, y \in K$, then $\text{size}(x \cdot y) \le \text{poly}(\text{size}(x), \text{size}(y), \log(\Delta_K))$, where we used the relations between $\text{size}(x)$ and $\|\sigma(x)\|$ mentioned above, and the fact that $\|\sigma(x \cdot y)\| \le \|\sigma(x)\| \cdot \|\sigma(y)\|$. Such a product can be computed in time $\text{poly}(\text{size}(x), \text{size}(y), \log(\Delta_K))$.

With the representation of ideals as described above, one can multiply two ideals $I$ and $J$ in time $\text{poly}(\text{size}(I), \text{size}(J), \log \Delta_K)$. Indeed, if $(x_i)_i$ is an LLL reduced basis of $I$ and $(y_i)_i$ is an LLL reduced basis of $J$, then $(x_i \cdot y_i)_{i,j}$ is a generating set of $I \cdot J$, and one can run the LLL algorithm on this generating set to extract an LLL-reduced basis from it.

**Lemma 2.9.** Let $B = (B, \{I_i\}_i)$ be a pseudo-basis of a rank $r$ module $M$ in $K^\ell$. Then one can compute in polynomial time a basis $C \in \mathbb{C}^{d\ell \times dr}$ of $\sigma(M)$ such that the column vectors $c_i$ of $C$ satisfy

$$ \|c_i\| \le \sqrt{d} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1 \le j \le r} \left( \|\sigma(\mathbf{b}_j)\| \cdot \mathcal{N}(I_j)^{1/d} \right), $$

where $\mathbf{b}_j$ is the $j$-th column of $B$.

*Proof.* Let $(\alpha_i^{(j)})_i$ be the LLL reduced basis representing the ideal $I_j$ for all $1 \le j \le r$ and $\mathbf{b}_i$ be the columns of the matrix $B$. The basis $C$ of $\sigma(M)$ is composed of the vectors $c_{d(j-1)+i} := \sigma(\alpha_i^j \cdot \mathbf{b}_j)$, for $1 \le j \le r$ and $1 \le i \le d$. These vectors can be computed in polynomial time from $B$ and the $\alpha_i^{(j)}$'s. The upper bound on their size follows from the upper bound $\|\sigma(\alpha_i^{(j)})\| \le \sqrt{d} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \mathcal{N}(I_j)^{1/d}$ (see Equation (4)). $\square$

The computation of roots of unity is handled by the following lemma.

**Lemma 2.10 (Factoring polynomials over a number field [1]).** There is a polynomial time algorithm that given a number field $K$ and a polynomial $P \in K[X]$, factorizes $P$ in $K$.

**Corollary 2.11 (Computing roots of unity in a number field).** Let $K$ be a degree $d$ number field. Then, $K$ has at most $2d^2$ roots of unity and there is a polynomial time algorithm that given a basis of $\mathcal{O}_K$, computes the roots of unity in $K$.

*Proof.* Let $K$ be a number field of degree $K$. By Dirichlet's unit theorem, we know that the group $\mathbb{U}_K$ of roots of unity in $K$ is finite and cyclic. Let $\zeta$ be a generator of this group, and $m$ be its order. Since $K$ contains $\mathbb{Q}(\zeta)$, and $\mathbb{Q}(\zeta)$ has degree $\varphi(m)$, it should be that $\varphi(m) \le d$. Also, we remark that for all $n \ge 2$, it holds that $\varphi(n) \ge \sqrt{n/2}$ (this is obtained by observing that $p-1 \ge \sqrt{p}$
for all prime $p \ge 3$ and $p-1 \ge \sqrt{p}/\sqrt{2}$ for $p=2$, and using the fact that
$\varphi(\prod_i p_i^{e_i}) = \prod_i (p_i-1) p_i^{e_i-1}$. Hence, the number $m$ of roots of unity in $K$
satisfies $m \le 2\varphi(m)^2 \le 2d^2$. Then to compute $U_K$, it is enough to factor the
polynomials $X^k-1$ over $K$, for $1 \le k \le 2d^2$. This can be done in polynomial
time using the algorithm from Lemma 2.10.

We note that the knowledge of a basis of $\mathcal{O}_K$ is used here because we said
that elements of $K$ are represented as rational linear combination of a given basis
of $\mathcal{O}_K$. If one chooses a different representation for elements of $K$ (for example,
polynomials in $\mathbb{Q}[X]/P(X)$ with $P$ a defining polynomial of $K$), the knowledge
of this basis of $\mathcal{O}_K$ might not be needed. $\square$

**Factoring ideals.** Given a prime integer $p \in \mathbb{Z}$, we can compute all prime ideals of $\mathcal{O}_K$ above $p$. This can be done using Buchmann-Lenstra's algorithm [8], whose detailed analysis can be found in Cohen's book [11, Section 6.2.5].

**Lemma 2.12 ([11, Section 6.2.5]).** There exists a polynomial time algorithm that takes as input any prime integer $p \in \mathbb{Z}$ and a basis of the ring of integers $\mathcal{O}_K$ of a number field $K$, and computes all the prime ideals of $\mathcal{O}_K$ dividing $p \cdot \mathcal{O}_K$.

As a corollary of this lemma, we have the following two algorithms, to test primality of ideals, and factor them.

**Corollary 2.13.** There is a polynomial time algorithm *PrimalityTest*($\mathfrak{a}$) that takes as input any integral ideal $\mathfrak{a}$ and decides whether $\mathfrak{a}$ is a prime ideal or not.

There is a polynomial time algorithm *FactorIdeal*($\mathfrak{a}$) that takes as input an integral ideal $\mathfrak{a}$ and the factorization of $\mathcal{N}(\mathfrak{a}) \in \mathbb{Z}$, and returns the factorisation of $\mathfrak{a}$ into prime ideals.

*Proof.* To verify whether $\mathfrak{a}$ is a prime ideal or not, we first compute its algebraic norm $\mathcal{N}(\mathfrak{a})$ and check if it a prime power. This can be done by computing roots $\mathcal{N}(\mathfrak{a})^{1/e}$ (for $1 \le e \le \log |\mathcal{N}(\mathfrak{a})|$) with good enough precision and see if the result is a prime integer. If we do have $\mathcal{N}(\mathfrak{a}) = p^e$ for some prime $p$ and $e \ge 1$, then using the previous lemma we compute the prime ideals $p \cdot \mathcal{O}_K$. For each of them, we test for equality with $\mathfrak{a}$.

To factorize an integral ideal $\mathfrak{a}$, the first step is to factor its algebraic norm
$\mathcal{N}(\mathfrak{a}) = \prod_{1 \le i \le r} p_i^{e_i}$, which is done in time $T_{\text{factor}}(\mathcal{N}(\mathfrak{a}))$. For each prime factor $p_i$
we compute the splitting of $p_i \cdot \mathcal{O}_K$ with the preceding lemma. There are at most
$d = [K : \mathbb{Q}]$ prime ideals above each $p_i$ and for each of them, say $\mathfrak{p}_{i,j}$ (a prime
ideal of $\mathcal{O}_K$ above $p_i$) we test if $\mathfrak{p}_{i,j}$ divides $\mathfrak{a}$. If it does, we check if powers $\mathfrak{p}_{i,j}^e$
of this prime factor still divide $\mathfrak{a}$ (see that the largest $e$ such $\mathfrak{p}_{i,j}^e | \mathfrak{a}$ is smaller than $e_i$).
All together, the number of divisions is at most $r \cdot d \cdot \max_i \{e_i\} = \text{poly}(\log |\mathcal{N}(\mathfrak{a})|)$.

$\square$

Let us write $T_{\text{factor}}(N)$ is the time needed to factor an integer $N \in \mathbb{Z}_{>0}$.
Then Algorithm **FactorIdeal** can be used to factor an integral ideal **a** in time
$\text{poly}(\text{size}({\mathfrak{a}})) + T_{\text{factor}}(\mathcal{N}({\mathfrak{a}}))$.
Norm equations in CM fields. Let us first consider a simple case of norm equa-
tion, which will be useful later on.

**Lemma 2.14.** Let $L|K$ be a CM extension of number fields with $K$ of degree $d$. The units $u \in O_L^\times$ that satisfy $N_{L|K}(u) = 1$ are exactly the roots of unity in $L$.

Proof. Let $u \in O_L^\times$ be a unit such that $N_{L|K}(u) = u\tau(u) = 1$. Because $u$ is an algebraic integer, its minimal polynomial $\mu_u$ over $\mathbb{Q}$ has coefficients in $\mathbb{Z}$. By Lemma 2.7, we have $|\sigma_i(u)|^2 = \sigma_i(u \cdot \tau(u)) = 1$ for all $2d$ complex embeddings $\sigma_i$ of $L$. Since the $\sigma_i(u)$'s are exactly the complex roots of $\mu_u$ (appearing possibly multiply times), this implies that all the roots of $\mu_u$ over $\mathbb{C}$ have modulus 1. A theorem of Kronecker$^{12}$ implies $u$ and its conjugates are roots of unity. $\square$

The Gentry-Szydlo algorithm [20] was originally presented in a cyclotomic
field $K$ and allows one to recover in polynomial-time an element $x \in K$, given
as input a basis of the ideal $xO_K$ and the element $x\bar{x}$.<fnref n="13" /> A generalization of
this algorithm to CM-fields (and more generally CM-orders) was proposed by
Lenstra and Silverberg in [24].

**Theorem 2.15 (Specialization of [24, Theorem 1.3])**. There exists a deter-
ministic polynomial time algorithm *GentrySzydlo* such that the following holds.
Let $L|K$ be a CM extension of number fields, $w \in L$ and $I$ be a fractional
ideal of $L$. Given as input a basis of $O_L$, the ideal $I$ and the element $w$, algo-
rithm *GentrySzydlo* decides whether there exists $v \in O_L$ such that $I = v \cdot O_L$
and $v\bar{v} = w$, and if so computes such an element $v$.

We note that Theorem 1.3 from [24] is stated for an arbitrary CM order $A$. We specialized the statement to $A = O_L$, which is a CM order (see Example 3.7 (i) from [24]). With this specialization, the $\mathbb{Q}$-algebra $A_{\mathbb{Q}}$ (using the notations from [24]) is the field $L$, and the set $(A_{\mathbb{Q}}^+)^{\gg 0}$ is the set $L \cap L_{\mathbb{R}}^{++}$. In the original statement from [24], the element $w$ is taken in this set $(A_{\mathbb{Q}}^+)^{\gg 0}$. We note that in our case, if $w \in L$ does not have all its embeddings real and positive, then we know that there is no solution to the equation $v\bar{v} = w$, and so this case is easily discarded. For this reason, we did not restrict the statement to specific elements $w$. Similarly, we did not impose in the statement that the ideal $I$ satisfies $I\bar{I} = wO_L$, because this condition can be tested in polynomial time, and the two equations $I = v \cdot O_L$ and $v\bar{v} = w$ can be satisfied only if $I\bar{I} = (v\bar{v})O_L = wO_L$.

With this theorem, one obtains the following algorithm (Algorithm 2.1),
which solves norm equations in CM extensions. This is a generalization to any
CM field extensions of an algorithm by Howgrave-Graham and Szydlo [22] which
solves relative norm equations in some cyclotomic number fields (over their to-
tally real subfields). Note that the algorithm by Howgrave-Graham and Szydlo

<footnote n="12">12 Let $P \in \mathbb{Z}[X]$ be a monic polynomial such that $P(0) \neq 0$. If all the complex roots of $P$ have modulus less or equal to 1, then these are roots of unity.</footnote>

<footnote n="13">¹³ The element $x$ is recovered up to a root of unity.</footnote>
was published in 2004, before the generalization of the Gentry-Szydło algorithm to all CM orders by Lenstra and Silverberg. This explains why Howgrave-Graham and Szydło only mention cyclotomic fields in [22], but the generalization to all CM fields is immediate once we have the generalization of the Gentry-Szydło algorithm for such fields. A result similar to Theorem 2.16 below and its proof are provided in [23, Theorem 14]. Since the latter article does not seem to be published, we provide a proof for completeness.

<caption>**Algorithm 2.1** Solve relative norm equations (NormEquation)</caption>

**Input:** A basis of $\mathcal{O}_K$ and $\mathcal{O}_L$, an element $q \in \mathcal{O}_K$, the prime factorization of $|\mathcal{N}_K(q)|$.
**Output:** All elements $z \in \mathcal{O}_L$ such that $\mathcal{N}_{L|K}(z) = q$.
1: Compute the roots of unity $U_L$ in $L$, using Corollary 2.11.
2: Factor $q \cdot \mathcal{O}_K = \prod_{i=1}^r \mathfrak{p}_i^{\alpha_i}$, using Corollary 2.13.
3: $\mathfrak{J}_0 \leftarrow \{q \subset \mathcal{O}_L \text{ prime ideal } | \exists i \in \{1, \dots, r\}, q | \mathfrak{p}_i \mathcal{O}_L\}$
4: $\mathfrak{J} \leftarrow \{\mathfrak{a} = \mathfrak{q}_1 \dots \mathfrak{q}_s \mid s > 0, \mathfrak{q}_i \in \mathfrak{J}_0, \mathcal{N}_{L|K}(\mathfrak{a}) = q \cdot \mathcal{O}_K\}$
5: $S \leftarrow \{\}$
6: **for** $\mathfrak{a} \in \mathfrak{J}$ **do**
7:     $z_\mathfrak{a} \leftarrow \text{GentrySzydło}(\mathcal{O}_L, \mathfrak{a}, q)$ (see Theorem 2.15)
8:     **if** GentrySzydło did not fail **then**
9:     $S \leftarrow S \cup \{\zeta \cdot z_\mathfrak{a} \mid \zeta \in U_L\}$
10:    **end if**
11: **end for**
12: **return** $S$

**Theorem 2.16.** Let $L|K$ be a CM extension of number fields and $q \in \mathcal{O}_K$. Given as input a basis of $\mathcal{O}_K$, a basis of $\mathcal{O}_L$, the element $q \in \mathcal{O}_K$, and the factorization of $|\mathcal{N}_K(q)|$ over $\mathbb{Z}$, Algorithm 2.1 (NormEquation) computes the list of all elements $z \in \mathcal{O}_L$ such that $\mathcal{N}_{L|K}(z) = q$. Moreover, the algorithm runs in time poly($\log \Delta_L$, $\log |\mathcal{N}_K(q)|$) $\cdot (1 + \log |\mathcal{N}_K(q)|)^r$, where $r$ is the number of distinct prime factors of the ideal $q \cdot \mathcal{O}_K$.

Note that the size of the output of the algorithm, and so in particular the number of solutions to the equation $\mathcal{N}_{L|K}(z) = q$, is bounded by the running time of the algorithm.

**Proof. Correctness.** Let us first show that the set $\mathfrak{J}$ from Step 4 contains all integral ideals of $\mathcal{O}_L$ with relative norm $q \cdot \mathcal{O}_K$. To do so, consider an integral ideal $\mathfrak{b} \subset \mathcal{O}_L$ with relative norm $q \cdot \mathcal{O}_K$ and write down its factorization $\mathfrak{b} = \prod_{j=1}^s \mathfrak{q}_j^{\beta_j}$ in $\mathcal{O}_L$. Since the relative norm is multiplicative, we have $\prod_{j=1}^s \mathcal{N}_{L|K}(\mathfrak{q}_j)^{\beta_j} = q \cdot \mathcal{O}_K = \prod_{i=1}^r \mathfrak{p}_i^{\alpha_i}$ (using the notations from Step 1). By uniqueness of the factorization into prime ideals, we deduce that for any $j \in \{1, \dots, s\}$, there exists $i_j \in \{1, \dots, r\}$ such that $\mathfrak{p}_{i_j}$ divides $\mathcal{N}_{L|K}(\mathfrak{q}_j)$. By Lemma 2.8, this implies that $\mathfrak{q}_j | \mathfrak{p}_{i_j}$. This means that $\mathfrak{b}$ has all its prime factors in $\mathfrak{J}_0$, and so $\mathfrak{b}$ is in $\mathfrak{J}$ (by definition of $\mathfrak{J}$), as desired. In particular, for any $z \in \mathcal{O}_L$ such that $z\bar{z} = q$, the corresponding principal ideal $z\mathcal{O}_L$ is in $\mathfrak{J}$.
In Step 7, the Gentry-Szydło algorithm outputs, when it exists, a generator of $\mathfrak{a}$ with relative norm $q$ for an ideal $\mathfrak{a} \in \mathfrak{J}$ (it always succeeds when a solution exists). Let us fix a principal ideal $\mathfrak{a}$ that has a generator $z_{\mathfrak{a}}$ of relative norm $q$. Let $z'_{\mathfrak{a}}$ be another generator with the same relative norm, so there is a unit $u$ such that $z_{\mathfrak{a}} = uz'_{\mathfrak{a}}$. But then we have $N_{L|K}(u) = q/q = 1$. By Lemma 2.14, we conclude that $u \in \mathbb{U}_L$ is a root of unity. Conversely, for any root of unity $\zeta \in \mathbb{U}_L$, one can check that $z_{\mathfrak{a}} \cdot \zeta$ is a generator of $\mathfrak{a}$ with relative norm $q$. We then conclude that the generators of $\mathfrak{a}$ whose relative norm is $q$ are exactly the elements $\{\zeta \cdot z_{\mathfrak{a}} | \zeta \in \mathbb{U}_L\}$. This concludes the correctness of the algorithm.

*Complexity.* The roots of unity $\mathbb{U}_L$ can be computed in polynomial time thanks to Corollary 2.11. Recall that the factorization of $N_K(q)$ is known. For Step 2 of the Algorithm, one can use FactorIdeal from Corollary 2.13 to factor the ideal $qO_K$ in polynomial time, thanks to the knowledge of the factorization of $N_K(q)$. In Step 3, computing all the prime ideals dividing $\mathfrak{p}_iO_L$ for a fixed prime ideal $\mathfrak{p}_i$ can be done in time polynomial in $\log N(\mathfrak{p}_i)$ and $\log \Delta_L$ thanks to Lemma 2.12. Note that each prime factor $\mathfrak{p}_i$ of $qO_K$ has its algebraic norm bounded by $|N_K(q)|$. Moreover, there are at most $\log_2|N_K(q)|$ distinct prime ideals $\mathfrak{p}_i$ dividing $qO_K$. Hence, in Step 3, the set $\mathfrak{J}_0$ can be computed in time poly($\log \Delta_L, \log |N_K(q)|$).

Recall that, above each prime ideal $\mathfrak{p}$ of $O_K$ are at most two prime ideals of $O_L$. More precisely, for each $\mathfrak{p}_i$ appearing in the prime decomposition of $q \cdot O_K$, either $\mathfrak{p}_iO_L$ is inert (and thus stays prime), splits into $\mathfrak{q}_i$ and $\tau(\mathfrak{q}_i)$ or ramifies as $\mathfrak{q}_i^2$. The respective relative norm ideals are then $N_{L|K}(\mathfrak{p}_iO_L) = \mathfrak{p}_i^2$, $N_{L|K}(\mathfrak{q}_i) = N_{L|K}(\tau(\mathfrak{q}_i)) = \mathfrak{p}_i$ or $N_{L|K}(\mathfrak{q}_i) = \mathfrak{p}_i$. To build the set $\mathfrak{J}$ from the set of prime ideals $\mathfrak{q}_{i,j}$, we proceed as follows. Let $\mathfrak{p}_i$ be a prime factor of $q \cdot O_K$. Any ideal $\mathfrak{a} \in \mathfrak{J}$ is divisible by a prime ideal above $\mathfrak{p}_i$ (recall the correctness part of the proof). From the condition on the norm of $\mathfrak{a}$ and the computation of the $N_{L|K}(\mathfrak{q}_{i,j})$, we can enumerate all the possibilities for the prime factors of $\mathfrak{a}$.

Keeping the notation of the algorithm, if $\mathfrak{p}_iO_L$ is inert, then $\alpha_i$ is an even number and $\mathfrak{a}$ must be divisible by $\mathfrak{q}_{i,0}^{\alpha_i/2}$. If $\mathfrak{p}_iO_L$ ramifies as $\mathfrak{q}_i^2$, then $\mathfrak{a}$ must be divisible by $\mathfrak{q}_i^{\alpha_i}$. Lastly, if $\mathfrak{p}_iO_L$ splits as $\mathfrak{q}_i$ and $\tau(\mathfrak{q}_i)$, then there exists $0 \le a \le \alpha_i$ such that $\mathfrak{q}_i^a \tau(\mathfrak{q}_i)^{\alpha_i-a}$ divides $\mathfrak{a}$. This number is bounded by $(\log_2|N_K(q)|+1)^r$ so we get at most $(\log_2|N_K(q)|+1)^r$ different ways to choose the prime factors of $\mathfrak{a}$. This is a bound for the cardinal of $\mathfrak{J}$, and one can construct the set $\mathfrak{J}$ (by following the procedure described above) in time poly($\log \Delta_L, \log |N_K(q)|) \cdot |\mathfrak{J}|$.

The last part of the algorithm consists in repeating $|\mathfrak{J}|$ times Steps 7 to 10. These steps can be performed in time poly($\log \Delta_L, \log |N_K(q)|$) (using Theorem 2.15). The upper bound on the size of $\mathfrak{J}$ gives us the desired upper bound on the running time, which concludes the proof. $\square$

## 3 Module-LIP for all modules

In this section, we extend the definition of the module-LIP problem from [14] to any (not necessarily free) module. We also provide some tools which are the analogue in the module settings of standard results in the unstructured case (such
as Cholesky decomposition). We believe that these basic tools may be useful for further study of the module-LIP problem. Finally, at the end of the section, we compare our new definition of module-LIP with the one from [14], and we explain why breaking the module-LIP problem that we define in Definition 3.11 allows to break the Hawk scheme.

**3.1 Pseudo-Gram matrices**

By applying the canonical embedding coordinate-wise to vectors and matrices, many well-known matrix decompositions and operations also extends *mutatis mutandis* to matrices over $K_\mathbb{R}$ — another expression of the algebraic structure. This happens since field embeddings preserve linear (and even polynomial) combinations, and we will follow this intuition in this section.

**Definition 3.1.** A matrix $G \in M_\ell(K_\mathbb{R})$ is said to be Hermitian definite positive$^{14}$ if it satisfies $G^* = G$ and $x^*Gx \in K_\mathbb{R}^{++}$ for any linearly independent vector $x \in K_\mathbb{R}^\ell$ (i.e., such that $\sigma_i(x) \neq 0$ for all embeddings $\sigma_i$, see preliminaries). The set of Hermitian definite positive forms is denoted $\mathcal{H}_\ell^{>0}(K_\mathbb{R})$, and $\mathcal{H}_\ell^{>0}(K)$ when restricted to matrices with entry in $K$.

*Basic properties.* Below we give some standard results on Hermitian definite positive matrices in $K_\mathbb{R}$. The key ingredient is to observe that a matrix $G$ is in $\mathcal{H}_\ell^{>0}(K_\mathbb{R})$ if and only if for all embeddings $\sigma_i$, the complex matrix $\sigma_i(G)$ is in $\mathcal{H}_\ell^{>0}(\mathbb{C}) = \{A \in M_\ell(\mathbb{C}) | A^* = A, x^*Ax > 0, \forall x \in \mathbb{C}^\ell \setminus \{0\}\}$. One can then apply the known results over complex Hermitian definite positive matrices and lift them to $\mathcal{H}_\ell^{>0}(K_\mathbb{R})$.

**Lemma 3.2.** A matrix $G \in M_\ell(K_\mathbb{R})$ is in $\mathcal{H}_\ell^{>0}(K_\mathbb{R})$ if and only if $\sigma_i(G) \in \mathcal{H}_\ell^{>0}(\mathbb{C})$ for all embeddings $\sigma_i$ of $K$.

*Proof.* Let $G \in M_\ell(K_\mathbb{R})$. First of all, observe that from the definition of the complex conjugation over $K_\mathbb{R}$, we have that $G^* = G$ if and only if $\sigma_i(G)^* = \sigma_i(G)$ for all embeddings, i.e., $\sigma_i(G)$ is Hermitian (or symmetric if $\sigma_i$ is real).

Recall also that $\sigma$ induces a bijection from $K_\mathbb{R}$ to the set $\{z = (z_i)_i \in \mathbb{C}^d | z_1, \dots, z_{d_1} \in \mathbb{R}, \bar{z}_{d_1+i} = z_{d_1+d_2+i}, 1 \le i \le d_2\}$. Hence, it holds that $x^*Gx \in K_\mathbb{R}^{++}$ for all linearly independent vector $x \in K_\mathbb{R}^\ell$ if and only if $y_i^*\sigma_i(G)y_i > 0$ for all $y_i \in \mathbb{R}^\ell \setminus \{0\}$ ($1 \le i \le d_1$) and $y_i \in \mathbb{C}^\ell \setminus \{0\}$ ($d_1 < i \le d_1 + d_2$). In other words, $G \in \mathcal{H}_\ell^{>0}(K_\mathbb{R})$ if and only if $\sigma_i(G) \in S_\ell^{>0}(\mathbb{R})$ for $1 \le i \le d_1$ and $\sigma_i(G) \in \mathcal{H}_\ell^{>0}(\mathbb{C})$ for all $d_1 < i \le d_1 + d_2$. We conclude using the fact that $S_\ell^{>0}(\mathbb{R}) = \mathcal{H}_\ell^{>0}(\mathbb{C}) \cap M_\ell(\mathbb{R})$. $\square$

**Proposition 3.3.** Let $B \in \text{GL}_\ell(K_\mathbb{R})$, then $B^*B \in \mathcal{H}_\ell^{>0}(K_\mathbb{R})$.

*Proof.* Note that since $B \in \text{GL}_\ell(K_\mathbb{R})$, then $\sigma_i(B) \in \text{GL}_\ell(\mathbb{C})$ for all complex embedding $\sigma_i$. Then, $\sigma_i(B^* \cdot B) = \sigma_i(B)^* \cdot \sigma_i(B) \in \mathcal{H}_\ell^{>0}(\mathbb{C})$ and we conclude using Lemma 3.2. $\square$

<footnote n="14">¹⁴ In prior literature, this is sometimes called *Humbert forms*.</footnote>
**Proposition 3.4 (Cholesky factorization).** Let $G \in \mathcal{H}_{\ell}^{>0}(K_{\mathbb{R}})$, then there exists a unique lower triangular matrix $L \in \text{GL}_{\ell}(K_{\mathbb{R}})$ with diagonal coefficients in $K_{\mathbb{R}}^{++}$ such that $G = LL^*$. Moreover, this matrix $L$ can be computed from $G$ in polynomial time.

*Proof.* By Cholesky factorization over $\mathcal{H}_{\ell}^{>0}(\mathbb{C})$, we know that for every $i \in \{1, \dots, d_1 + d_2\}$ there exists a unique lower triangular matrices $L_i$ in $M_{\ell}(\mathbb{C})$ with real positive diagonal coefficients such that $\sigma_i(G) = L_i \cdot L_i^*$ (we even have $L_i \in M_{\ell}(\mathbb{R})$ for $1 \le i \le d_1$). By bijectivity of the canonical embedding, there exists then a unique matrix $L \in M_{\ell}(K_{\mathbb{R}})$ such that $\sigma_i(L) = L_i$ for all $1 \le i \le d_1 + d_2$, and this matrix has its diagonal coefficients in $K_{\mathbb{R}}^{++}$ since all the $L_i$ have real positive diagonal coefficients. This proves the existence of $L$. Unicity is obtained by observing that if $L$ is as in the theorem statement, then $\sigma_i(L) \cdot \sigma_i(L)^*$ is a Cholesky decomposition of $\sigma_i(G)$, and so $\sigma_i(L) = L_i$ by unicity of Cholesky decomposition over $\mathcal{H}_{\ell}^{>0}(\mathbb{C})$.

To compute the matrix $L$, a possibility is to compute $\sigma_i(G)$ for all $1 \le i \le d_1+d_2$, then compute the Cholesky decomposition of $\sigma_i(G) \in \mathcal{H}_{\ell}^{>0}(\mathbb{C})$ to obtain $L_i$, and finally reconstruct $L \in M_{\ell}(K_{\mathbb{R}})$ such that $\sigma_i(L) = L_i$. Computing $\sigma$ can be done by evaluating polynomials, and computing $\sigma^{-1}$ (to recover $L$ from the $L_i$'s) can be done by polynomial interpolation. Both steps can be done in polynomial time. Cholesky decomposition over $\mathcal{H}_{\ell}^{>0}(\mathbb{C})$ can also be performed in polynomial time, hence the full procedure is polynomial. $\square$

**Proposition 3.5.** Let $B$ and $C \in \text{GL}_{\ell}(K_{\mathbb{R}})$ be such that $B^*B = C^*C$. Then there exists $O \in \mathcal{U}_{\ell}(K_{\mathbb{R}})$ such that $B = O \cdot C$.

*Proof.* The equality $B^*B = C^*C$ can be rearranged as $(BC^{-1})^* \cdot (BC^{-1}) = I_{\ell}$ (note that $C$ is invertible), which exactly means that $BC^{-1} \in \mathcal{U}_{\ell}(K_{\mathbb{R}})$. $\square$

**Pseudo-Gram matrices.** We define an analog of quadratic forms and Gram matrices for module lattices, namely the pseudo-Gram matrices.

**Definition 3.6.** Let $B = (B, (I_i)_i)$ be a pseudo-basis of a rank-$\ell$ module $M$ in $K_{\mathbb{R}}^k$. The pseudo-Gram matrix associated to $B$ is $G := (G, (I_i)_i)$, where $G = B^*B \in \mathcal{H}_{\ell}^{>0}(K_{\mathbb{R}})$.

Using the Cholesky decomposition that we reviewed above, one can see that for any Hermitian positive definite matrix $G \in \mathcal{H}_{\ell}^{>0}(K_{\mathbb{R}})$ and any non-zero fractional ideals $I_1, \dots, I_{\ell}$, there always exists a pseudo-basis $B = (B, (I_i)_i)$ whose pseudo-Gram matrix is $G = (G, (I_i)_i)$. Note however that Cholesky only guarantees the existence of such pseudo-basis in $K_{\mathbb{R}}$ (the matrix $B$ is in $M_{\ell}(K_{\mathbb{R}})$). Even when $G \in M_{\ell}(K)$, there may not exist a pseudo-basis in $K$ (with $B \in M_{\ell}(K)$) whose pseudo-Gram matrix is $G$.

**Definition 3.7.** Let $G = (G, (I_i)_{1 \le i \le \ell})$ and $G' = (G', (J_i)_{1 \le i \le \ell})$ be two pseudo-Gram matrices (with $G$ and $G'$ in $\mathcal{H}_{\ell}^{>0}(K_{\mathbb{R}})$). They are said congruent if there exists $U = (u_{i,j})_{1 \le i,j \le \ell} \in \text{GL}_{\ell}(K)$ such that $G' = U^*G U$ and $u_{i,j} \in I_i J_j^{-1}$, $v_{i,j} \in$
$J_i I_j^{-1}$, where $V = (v_{i,j})_{1\le i,j\le \ell} := U^{-1}$. Such $U$ is called a congruence matrix between $G$ and $G'$. This defines an equivalence relation $\sim$ on the set of pseudo-Gram matrices.<fnref n="15" /> The class of $G$ is denoted by $[G]$.

**Sampling (implicit) Gaussian vectors.** As in the case of standard (non-structured) lattices, it is possible to sample vectors from a discrete Gaussian distribution in an implicit module $M$ given as input a pseudo-Gram matrix $G$ of this module.

**Lemma 3.8.** There is a probabilistic polynomial time algorithm GaussianGram such that the following holds. Let $\mathbf{B} = (B, (I_i)_{1\le i\le \ell})$ be a pseudo-basis of a rank-$\ell$ module $M$ in $K_\mathbb{R}^\ell$, and $\mathbf{G} = (G, (I_i)_{1\le i\le \ell})$ be the pseudo-Gram matrix of $\mathbf{B}$. Let $s > 0$ be a real number satisfying

$$s \ge \sqrt{\frac{d \cdot \log(2d\ell + 4)}{\pi}} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1 \le j \le r} (\|\sigma(g_{j,j})^{1/2}\| \cdot \mathcal{N}(I_j)^{1/d}),$$

where $G = (g_{i,j})_{1\le i,j\le \ell}$ and the square-root is applied coordinate-wise to $\sigma(g_{j,j}) \in \mathbb{C}^d$. On input $\mathbf{G}$ and $s$, GaussianGram($\mathbf{G}$, $s$) outputs $\mathbf{z} \in I_1 \times \cdots \times I_\ell$ such that $\mathbf{v} := B \cdot \mathbf{z}$ follows a discrete Gaussian distribution of parameter $s$ in $M$ (i.e., $\sigma(\mathbf{v}) \sim D_{\sigma(M),s}$).

**Proof.** The algorithm GaussianGram first computes a pseudo-basis $\mathbf{C} = (C, (I_i)_i)$ such that $C^*\mathbf{C} = \mathbf{G}$, using Cholesky decomposition. According to Proposition 3.4, this can be done in polynomial time. The pseudo-basis $\mathbf{C}$ generates a rank-$\ell$ module $M' \subset K_\mathbb{R}^\ell$, and from Proposition 3.5, since $\mathbf{C}$ and $\mathbf{B}$ have the same pseudo-Gram matrix $\mathbf{G}$, we know that there exists $O \in \mathcal{U}_\ell(K_\mathbb{R})$ such that $C = O \cdot \mathbf{B}$.

From $\mathbf{C}$, the algorithm then computes a basis $D \in \mathbb{C}^{d\ell \times d\ell}$ of the lattice $\sigma(M')$. This can be done in polynomial time from Lemma 2.9, and the same lemma also tells us that the column vectors $\mathbf{d}_i$ of $D$ have Euclidean norm upper bounded by

$$\|\mathbf{d}_i\| \le \sqrt{d} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1 \le j \le r} (\|\sigma(\mathbf{c}_j)\| \cdot \mathcal{N}(I_j)^{1/d}),$$

where $\mathbf{c}_j$ are the column vectors of $\mathbf{C}$. Observe that, since $G = C^*C$, then $g_{i,j} = \langle c_i, c_j \rangle_{K_\mathbb{R}}$ (where $G = (g_{i,j})_{1\le i,j\le \ell}$). Hence, the quantity $\max_j \|\sigma(\mathbf{b}_j)\|$ in the bound above can be replaced by $\max_j \|\sigma(g_{j,j})^{1/2}\|$, where the square-root is applied coordinate-wise to $\sigma(g_{j,j}) \in \mathbb{C}^d$.

Finally, the algorithm uses the basis $D$ to sample $\mathbf{x} \in \sigma(M')$, following the discrete Gaussian distribution $D_{\sigma(M'),s}$. This is doable in polynomial time, using Lemma 2.4 and the fact that $s \ge \sqrt{\log(2d\ell + 4)/\pi} \cdot \max_i \|\mathbf{d}_i\|$.

<footnote n="15">¹⁵ For the transitivity; let $\mathbf{G} = (G, (I_i)_{1\le i\le \ell})$, $\mathbf{G}' = (G', (J_i)_{1\le i\le \ell})$, $\mathbf{G}'' = (G'', (I_i)_{1\le i\le \ell})$ and $U$ (resp. $U'$) a congruence matrix between $\mathbf{G}$ and $\mathbf{G}'$ (resp. between $\mathbf{G}'$ and $\mathbf{G}''$), then $U'' := U \cdot U'$ satisfies $G'' = U''^* \cdot G \cdot U''$ and has coefficients $U''_{i,j} = \sum_{k=1}^\ell u_{i,k} \cdot u'_{k,j}$. All terms of the sum are in $I_i J_j^{-1}$ by definition. The same observation for $(U'')^{-1}$ finally gives $\mathbf{G} \sim \mathbf{G}'$.</footnote>
The algorithm then reconstructs $\mathbf{w} \in M'$ such that $\sigma(\mathbf{w}) = \mathbf{x}$. This can again be done in polynomial time. The vector $\mathbf{w} \in M'$ is distributed according to a discrete Gaussian distribution over $M'$ of parameter $s$. Let $\mathbf{z}$ be the coordinates of $\mathbf{w}$ in the pseudo-basis $C$. Since $\mathbf{w}$ is in $M'$, then $\mathbf{z}$ must be in $I_1 \times \cdots \times I_\ell$. This vector $\mathbf{z}$ is then output by the algorithm.

We have seen so far that the algorithm runs in polynomial time, and outputs a vector $\mathbf{z} \in I_1 \times \cdots \times I_\ell$ such that $\mathbf{w} = C \cdot \mathbf{z}$ follows a discrete Gaussian distribution in $M'$ of parameter $s$. To conclude, remember that $B = O \cdot C$ and that $O \in \mathcal{U}_\ell(K_\mathbb{R})$ preserves the euclidean norm (i.e., for any $\mathbf{y} \in K_\mathbb{R}^\ell$, we have $\|\sigma(y)\| = \|\sigma(O \cdot y)\|$. Hence the vector $\mathbf{v} = B \cdot \mathbf{z} = O \cdot \mathbf{w}$ follows a Gaussian distribution of parameter $s$ in $M$. $\square$

## 3.2 Module-LIP

We are now ready to define the module-LIP problem for any number field $K$ and any module $M$. Using the formalism of pseudo-bases and pseudo-Gram matrices, the situations for module lattices and non-structured lattices become quite similar. Consequently, the definitions in this subsection will be very reminiscent of the ones from preliminaries. We start by introducing the notion of isomorphism for module lattices.

**Definition 3.9.** Let $M, M' \subset K_\mathbb{R}^\ell$ be two modules of rank $\ell$. We say that $M, M'$ are isomorphic as module lattices if there exists a unitary transformation $O \in \mathcal{U}_\ell(K_\mathbb{R})$ such that $M' = O \cdot M$.

Note that if $M$ and $M'$ are isomorphic as module lattices, then the lattices $\sigma(M)$ and $\sigma(M')$ are isomorphic for the standard (non-structured) definition of lattice isomorphism. In the case of module lattice isomorphism, we restrict ourselves to specific lattices (the ones of the form $\sigma(M)$ for $M$ a module) and specific orthogonal transformations (they should be $K$-linear on the modules).

Isomorphism of module lattices can be restated in terms of pseudo-bases or pseudo-Gram matrices.

**Lemma 3.10.** Let $M, M' \subset K_\mathbb{R}^\ell$ be two modules of rank $\ell$ with respective pseudo-bases $\mathbf{B} = (B, (I_i)_{1\le i\le \ell})$ and $\mathbf{B}' = (B', (J_i)_{1\le i\le \ell})$. Let $\mathbf{G}$ (resp. $\mathbf{G}'$) be the pseudo-Gram matrix associated to $\mathbf{B}$ (resp $\mathbf{B}'$). Then, the three following assertions are equivalent

(1) $M$ and $M'$ are isomorphic as module lattices;

(2) there exists $O \in \mathcal{U}_\ell(K_\mathbb{R})$ and $U \in \text{GL}_\ell(K)$ with $u_{i,j} \in I_i J_j^{-1}$ and $v_{i,j} \in J_i I_j^{-1}$ (where $U = (u_{i,j})_{1\le i,j\le \ell}$ and $U^{-1} = (v_{i,j})_{1\le i,j\le \ell}$) such that $B' = OBU$;

(3) $\mathbf{G}$ and $\mathbf{G}'$ are congruent (see Definition 3.7).

*Proof.* We prove that (1) $\Rightarrow$ (2) $\Rightarrow$ (3) $\Rightarrow$ (1). Assume that $M$ and $M'$ are isomorphic as module lattices. By definition, there exists $O \in \mathcal{U}_\ell(K_\mathbb{R})$ such that $M' = O \cdot M$. A pseudo-basis of $OM$ is given by $(OB, (I_i)_i)$. Since $\mathbf{B}'$ is also a pseudo-basis of $O \cdot M$, there must exist a matrix $U \in \text{GL}_\ell(K)$ such that $u_{i,j} \in I_i J_j^{-1}$ and $v_{i,j} \in J_i I_j^{-1}$ and $B' = (OB)U$, as desired.
Let us now assume that $B' = OBU$. Then $G' = U^*GU$ and this means that $G$ and $G'$ are congruent.

Finally, let us assume that $G$ and $G'$ are congruent. By definition, there exists $U \in \text{GL}_\ell(K)$ (with $u_{i,j} \in I_i J_i^{-1}$ and $v_{i,j} \in J_i I_j^{-1}$) such that $G' = U^*GU$. Let us consider $C = (BU, (J_i)_i)$. Thanks to the condition on $U$, we know that $C$ and $B$ are both pseudo-bases of the same module $M$. Moreover, the pseudo-Gram matrix of $C$ is exactly $G'$. Using Proposition 3.5, we conclude that there exists $O \in \mathcal{U}_\ell(K_\mathbb{R})$ such that $B' = OBU$, i.e., $M' = O \cdot M$. $\square$

Let us now define the module Lattice Isomorphism Problem (module-LIP), in its worst-case variant. As in the unstructured case, we could define two variants, one using the formalism of pseudo-bases and another one using the formalism of pseudo-Gram matrices. Instead, we decided to introduce only one variant, which uses both pseudo-bases and pseudo-Gram matrices. More precisely, we define a collection of problems parametrized by the field $K$ and a pseudo-basis $B$ of a module $M$, and whose input is a pseudo-Gram matrix $G'$ (of a different pseudo-basis $B'$ of $M$). This variant is tailored to fit our attack in the next section, but we also believe that it makes sense for itself. Indeed, so far, the instantiations of LIP and module-LIP in cryptography have been parameterized by very specific (module) lattices, for which a good (pseudo-)basis was known (e.g., in Hawk, the module lattice is $\mathcal{O}_K^2$).$^{16}$ On the other hand, the algorithm then usually manipulates only (pseudo-)Gram matrices, and so an attacker would get as input such a (pseudo-)Gram matrix and not a (pseudo-)basis of an isomorphic (module) lattice.

**Definition 3.11 (wc-smodLIP<sub>K</sub><sup>B</sup>)**. For $B$ a pseudo-basis of a module-lattice $M \subset K_\mathbb{R}^\ell$ with associated pseudo-Gram matrix $G$, the worst-case search module-Lattice Isomorphism Problem with parameter $K$ and $B$ denoted by wc-smodLIP<sub>K</sub><sup>B</sup> is, given as input any pseudo-Gram matrix $G' \sim G$ (see Definition 3.7), to find a congruence matrix between $G$ and $G'$.

When we say that the problem is parameterized by $K$ and $B$, we mean that this is a collection of algorithmic problems, one for each choice of $(K, B)$. $^{17}$ In particular, the number field $K$ and pseudo-basis $B$ are known to an adversary.

A definition of module-LIP was also provided in [14, Definition 7], which differs slightly from ours. There are three main differences between the two definitions: [14, Definition 7] defines module-LIP for free modules $M$ (with $B = (B, (O_K)_{1\le i\le 2})$ a basis of the module), over a CM number field, and restricts $G'$ to be the Gram-matrix of a basis $B' = (B', (O_K)_{1\le i\le 2})$ of $M$, and such that the

<footnote>$^{16}$ By good, we mean here a (pseudo)-basis with rational coefficients. This will be needed for our attack, and we do not know how to recover it efficiently from the (pseudo-)Gram matrix since Cholesky decomposition only provides a basis with co-efficients in $\mathbb{R}$ (or $K_\mathbb{R}$).</footnote>

<footnote>$^{17}$ The same terminology is used for, e.g., the LWE problem. We usually say that $n, m, q$ are parameters of the problem, which means that for each choice of $(n, m, q)$, we have a different algorithmic problem.</footnote>
determinant of $\mathcal{B}'$ is the same as the one of $\mathcal{B}$. On the other hand, Definition 3.11 above holds for any module $M$ (and any pseudo-basis $\mathcal{B}$), any number field, and the input $\mathcal{G}'$ of the problem is the Gram-matrix of any pseudo-basis $\mathcal{B}'$ of $M$. Note that even if one takes $K$ a CM field, and $\mathcal{B}$ a basis of a free module $M$, then our problem wc-smodLIP$_K^B$ from Definition 3.11 is still not exactly the same as the problem defined in [14, Definition 7]. Indeed, in our definition, the input of the problem can be any Gram-matrix $\mathcal{G}'$ congruent to $\mathcal{G}$, whereas in [14, Definition 7] the input is restricted to specific congruent Gram-matrices $\mathcal{G}'$.

**Hawk and module-LIP.** In the case of Hawk [14], the authors consider a power-of-two cyclotomic field $K$ and the free rank-2 module-lattice $M = \mathcal{O}_K^2$. The secret key consists in a short basis $U$ of $M$ and the public key is the Gram matrix $\mathcal{G}' = U^*U \in \mathcal{H}_2^{\otimes 0}(K)^{18}$. With the formalism we introduced in the previous paragraph, $U$ is a congruence matrix between $I_2 = (I_2^*I_2, (\mathcal{O}_K)_{1\le i\le 2})$ and $\mathcal{G}' = (\mathcal{G}', (\mathcal{O}_K)_{1\le i\le 2})$. We now recall how (uncompressed) Hawk proceeds (Section 3.1, [14]).

Given a message $m$ to sign, first hash $m$ together with a salt $r$ to a point $h \in \{0, 1\}^{2d}$, which is interpreted as an element of $\mathcal{O}_K^2$ thanks to the following bijective map, called coefficient embedding $K \to \mathbb{Q}^d; (\sum_i a_i X^i) \mapsto (a_0, \dots, a_{d-1})^T$. Then, a vector $x \in \mathcal{O}_K^2 + \frac{1}{2}U \cdot h$ close to $0$ is sampled using Gaussian samples in $\mathbb{Z}$ and $\frac{1}{2}\mathbb{Z}$ (the identification between $\mathcal{O}_K^2$ and $\mathbb{Z}^{2d}$ being possible via coefficient embedding). Finally, the signer computes $s := \frac{1}{2}h - U^{-1} \cdot x$. The (uncompressed) signature consists of the pair $\mathbf{sig} = (r, s)$.

A verifier receiving $\mathbf{sig}$ computes the hash $h$ and checks if $\|\frac{1}{2}h - s\|_{\mathcal{G}'}$ is smaller than a fixed security parameter (here, $\|z\|_{\mathcal{G}'} := \|z^*G'z\|$ for any $z \in K^2$). It also checks that $s \in \mathcal{O}_K^2$. If both tests succeed, it accepts the signature. Using the fact that $\|\frac{1}{2}h - s\|_{\mathcal{G}'} = \|U \cdot (\frac{1}{2}h - s)\| = \|x\|$, one can check that the first verification test must be satisfied when the signature is honestly generated. For the second one, writing $x = y + \frac{1}{2}U \cdot h$ with $y \in \mathcal{O}_K^2$, one can see that $s = U^{-1}y$. The fact that $s \in \mathcal{O}_K^2$ follows from the fact that $U \in \text{GL}_2(\mathcal{O}_K)$ (since $U$ is a basis of $\mathcal{O}_K^2$).

**Lemma 3.12.** With the notations of the previous paragraph, finding any congruence matrix $V$ between $I_2$ and the public key $\mathcal{G}'$ allows to forge signatures in Hawk. In other words, if one can solve the wc-smodLIP$_K^{I_2}$ problem, then one can forge signatures in Hawk, given only the public key.

*Proof.* By definition, a congruence matrix $V$ between $\mathcal{G}$ and $\mathcal{G}'$ satisfies $V \in \text{GL}_2(\mathcal{O}_K)$ and $\mathcal{G}' = V^*V$. We show that any such matrix can be used to produce valid signatures : let $(r, s)$ be a signature produced by Hawk with input basis $V$. Then $x = y + \frac{1}{2}V \cdot h$ is small, with $y \in \mathcal{O}_K^2$, and $s = \frac{1}{2}h - V^{-1}x = V^{-1}y$. Since $V \in \text{GL}_2(\mathcal{O}_K)$, the vector $s$ is in $\mathcal{O}_K^2$ as desired. Moreover, $\|\frac{1}{2}h - s\|_{\mathcal{G}'} = \|V \cdot (\frac{1}{2}h - s)\| = \|x\|$, since $\mathcal{G}' = V^*V$, which means that the latter norm is small the pair $(r, s)$ is then accepted by the verifier. $\square$

<footnote n="18">18 Here $M$ is a free module so it has a basis (equivalently, the coefficient ideals are equal to $\mathcal{O}_K$) so the authors use bases (resp. Gram-matrices) instead of pseudo-bases (resp. pseudo-Gram matrices).</footnote>
The previous lemma underlines that, to forge signatures in Hawk it is enough
to recover any congruence matrix $V$ and not specifically the secret key $U$. There-
fore, the problem of signature forgery in Hawk reduces to solving wc-smodLIP<sub>$K$</sub><sup>$V_2$</sup>,
as defined in Definition 3.11.

4 An algorithm for module-LIP in rank 2 over totally
real fields

We now present our main algorithm, which solves wc-smodLIP<sub>K</sub><sup>B</sup> for totally real
fields K and when the module generated by the pseudo-basis **B** lives in K<sup>2</sup>
(see Algorithm 4.2 when the module is in O<sub>K</sub><sup>2</sup> and Algorithm 4.3 for the general
case). At a high level, it is based on the observation that, when the module is
in O<sub>K</sub><sup>2</sup>, a diagonal element q in the pseudo-Gram matrix **G** = **B**<sup>*</sup>**B** = **B**<sup>T</sup>**B**
can be written as q = x<sup>2</sup> + y<sup>2</sup> with x, y ∈ O<sub>K</sub>, that is, a sum of two squares.
Already when K = Q, a common way to find such sums is to go through a
quadratic imaginary extension L := K(i), where i is a root of X<sup>2</sup> + 1 over K.
Indeed, all solutions to a 2-square decompositions are also solutions of a relative
norm equation q = N<sub>L|K</sub>(a) = a<sup>*</sup>a, which we can solve algorithmically thanks
to Lenstra-Silverberg's algorithm. Our algorithm will thus use the procedure
NormEquation (from preliminaries) to solve the latter, then restrict to solutions
of the former in another algorithm named TwoSquares. From these solutions, we
will be able to build the set of all congruence matrices to solve wc-smodLIP<sub>K</sub><sup>B</sup>,
when the module generated by **B** is in O<sub>K</sub><sup>2</sup>. For rational modules in K<sup>2</sup>, we then
simply multiply by a common denominator, to reduce to the situation where the
module is in O<sub>K</sub><sup>2</sup>.

An apparently unavoidable component of NormEquation is the factorization
of the ideal $q \cdot O_K$, so there is no hope to obtain a classical polynomial-time
algorithm this way. Therefore, we use a re-randomization procedure to generate
random vectors $z = (z_1, z_2)$ until $z^*Gz$ generates a prime ideal (for the rest
of this paragraph, we say that $z$ is a “good vector” when this is the case). Pri-
mality testing can be done in polynomial time for ideals as well, and if we let
$B \cdot (z_1, z_2)^T = (x, y)^T$, then $z^*Gz = x^2 + y^2$ is again a sum of two squares. This
allows us to avoid the potentially costly factorization. With two linearly inde-
pendent good vectors, we can then use a two-square decomposition algorithm
together with some linear algebra to solve the module-LIP instance. Estimating
the probability of finding a good vector relies on a heuristic assumption, sup-
ported by standard (but non-trivial) number-theoretic arguments: the discussion
and justifications are the topic of Section 4.2.

4.1 Gram ideal

In order to describe our results in this section for all modules of rank 2 in $K^2$, we
introduce the Gram ideal and the relative Gram ideal of a module $M \subset K^\ell$ of
rank $\ell$. From now on, we will consider the arithmetic properties of the coefficients
of vectors in $M$, and hence restrict ourselves to modules in $K^\ell$ (as opposed to
$K_\mathbb{R}^\ell$ which we considered so far).
**Definition 4.1.** Let $K$ be a totally real number field and $M \subset K^\ell$ be a module of rank $\ell$. Let $\mathbf{B} = ((B_{i,j})_{i,j}, (J_i)_i)$ be a pseudo-basis of $M$ and $\mathbf{G} = ((G_{i,j})_{i,j}, (J_i)_i)$ be the associated pseudo-Gram matrix. We define the following fractional ideals

$$ \mathcal{G}(M) := \sum_{1 \le i \le l} G_{i,i} \cdot J_i^2 + \sum_{1 \le i < j \le l} 2 \cdot G_{i,j} \cdot J_i \cdot J_j $$

$$ \mathcal{C}(M) := \sum_{1 \le i,j \le l} B_{i,j} \cdot J_j \quad ; \quad \mathcal{R}\mathcal{G}(M) := \mathcal{G}(M)/\mathcal{C}(M)^2. $$

We call $\mathcal{G}(M)$ the Gram ideal and $\mathcal{R}\mathcal{G}(M)$ the relative Gram ideal of $M$.

The first two ideals correspond respectively to the ideal generated by the (squared) norm of vectors of $M$, and the ideal generated by the coordinates of the vectors of $M$. We show below that these ideals indeed depend only on the module lattice $M$ and not on the pseudo-basis $\mathbf{B}$.

**Lemma 4.2.** Let $K$ be totally real and $M \subset K^\ell$ be a module of rank $\ell$. Let $\mathbf{B}$ be a pseudo-basis of $M$ with associated pseudo-Gram matrix $\mathbf{G}$. Then $\mathcal{G}(M)$ is the smallest ideal (for inclusion) containing the set $\{\langle \mathbf{v}, \mathbf{v} \rangle_{K_R} | \mathbf{v} \in M\}$, and $\mathcal{C}(M)$ is the smallest ideal containing the set $\{v_j | \mathbf{v} = (v_i)_i \in M, 1 \le j \le \ell\}$. In particular, they do not depend on the choice of the pseudo-basis $\mathbf{B}$ of $M$.

*Proof.* Any module vector can be uniquely written as $\mathbf{v} = \sum_{i=1}^l x_i \cdot \mathbf{b}_i$, where $\mathbf{b}_i$ is the $i$-th vector column of $\mathbf{B}$, and $x_i \in J_i$ (with $\mathbf{B} = (B, (J_i)_i)$). Then, $\langle \mathbf{v}, \mathbf{v} \rangle_{K_R} = \sum_{1 \le i \le \ell} x_i^2 G_{i,i} + 2 \sum_{1 \le i < j \le \ell} x_i x_j G_{i,j} \in \mathcal{G}(M)$, where $G = (G_{i,j})_{i,j}$. Note that here, we used the fact that $K$ is totally real, and so $\bar{v}_i = v_i$ for all $i$'s. Conversely, any (fractional) ideal $I$ containing the square euclidean norm of the vectors of $M$ must contain $\langle x\mathbf{b}_i, x\mathbf{b}_i \rangle_{K_R} = x^2 \cdot G_{i,i}$ for all $x \in J_i$ and all $1 \le i \le \ell$. Since the ideal generated by $\{x^2 | x \in J_i\}$ is precisely $J_i^2$, we conclude that $G_{i,i} \cdot J_i^2$ is included in $I$.<fnref n="19" /> Using the polarization formula and since $I$ is stable by addition, we see that it contains $\|x_i \mathbf{b}_i + x_j \mathbf{b}_j\|^2 - \|x_i \mathbf{b}_i\|^2 - \|x_j \mathbf{b}_j\|^2 = 2G_{i,j} \cdot x_i \cdot x_j$, for all $1 \le i < j \le \ell$ and all $x_i \in J_i$ and $x_2 \in J_2$. Hence, $I$ contains $2G_{i,j}J_i \cdot J_j$ for all $i$ and $j$'s. The assertion on $\mathcal{C}(M)$ follows from its definition. $\square$

**Corollary 4.3.** The relative Gram ideal $\mathcal{R}\mathcal{G}(M)$ is integral, and do not depend on the choice of the pseudo-basis $\mathbf{B}$ of $M$.

*Proof.* The fact that $\mathcal{R}\mathcal{G}(M)$ does not depend on the choice of $\mathbf{B}$ follows from its definition, and the fact that neither $\mathcal{G}(M)$ nor $\mathcal{C}(M)$ depend on $\mathbf{B}$. To see that the ideal is integral, we show that $\mathcal{G}(M) \subseteq \mathcal{C}(M)^2$ (which implies that $\mathcal{G}(M)/\mathcal{C}(M)^2 \subseteq \mathcal{O}_K$). Let $\mathbf{v} = (v_i)_i \in M$. From Lemma 4.2, we know that $\langle \mathbf{v}, \mathbf{v} \rangle_{K_R} = \sum_i v_i^2 \in \mathcal{C}(M)^2$. Since $\mathcal{G}(M)$ is generated by the $\langle \mathbf{v}, \mathbf{v} \rangle_{K_R}$ for $\mathbf{v} \in M$ (see again Lemma 4.2), we conclude that $\mathcal{G}(M) \subseteq \mathcal{C}(M)^2$ as desired. $\square$

<footnote n="19">¹⁹ To prove that the ideal generated by $\{x^2 | x \in J_i\}$ is equal to $J_i^2$, let $a, b \in J_i$ be such that $J_i = a\mathcal{O}_K + b\mathcal{O}_K$. Then $a\mathcal{O}_K = J_i \cdot \mathfrak{a}$ and $b\mathcal{O}_K = J_i \cdot \mathfrak{b}$ with $\mathfrak{a}$ and $\mathfrak{b}$ integral coprime ideals. The ideal containing all squares $x^2$ for $x \in J_i$ must in particular contain $(a^2 + b^2) \cdot \mathcal{O}_K = J_i^2 \cdot (\mathfrak{a}^2 + \mathfrak{b}^2) = J_i^2$. The other inclusion is immediate.</footnote>
The Gram ideal and relative Gram ideal of a module $M$ can be computed in polynomial time from any pseudo-basis $\mathbf{B}$ of $M$ (directly from Definition 4.1). A simple but important case is when $M = \mathcal{O}_K^\ell$, e.g, in Hawk. In this case, we have $\mathcal{G}(M) = \mathcal{C}(M) = \mathcal{RG}(M) = \mathcal{O}_K$. In the following we prove that the relative Gram ideal is invariant when scaling the module (by a scalar, or even a fractional ideal).

**Lemma 4.4.** Let $K$ be totally real, $M \subset K^\ell$ be a module of rank $\ell$, and $J$ be a fractional ideal. Then,

$$ (1) \quad \mathcal{G}(J \cdot M) = J^2 \cdot \mathcal{G}(M). $$

$$ (2) \quad \mathcal{C}(J \cdot M) = J \cdot \mathcal{C}(M). $$

$$ (3) \quad \mathcal{RG}(J \cdot M) = \mathcal{RG}(M). $$

$$ (4) \quad \mathcal{C}(M)^{-1} \cdot M \subset \mathcal{O}_K^\ell \text{ is an integer module lattice not contained in } \mathfrak{p}^\ell \text{ for any prime ideal } \mathfrak{p}. $$

We will later use Lemma 4.4 to scale our input module $M$, in order to make it integer, but as small as possible (with respect to its determinant) among all the scaled variants of $M$ included in $\mathcal{O}_K^\ell$.

*Proof.* (1) – (3) Let $\mathbf{B} = (B, (I_i)_{1 \le i \le \ell})$ be a pseudo-basis of $M$ with pseudo-Gram matrix $\mathbf{G}$. Recall from preliminaries that $J \cdot M$ has pseudo-basis $(B, (J \cdot I_i)_{1 \le i \le \ell})$ so the Gram ideal associated is by definition

$$ \begin{aligned} \mathcal{G}(J \cdot M) &= \sum_{1 \le i \le \ell} G_{i,i} \cdot (J \cdot I_i)^2 + 2 \sum_{1 \le i < j \le \ell} G_{i,j} \cdot (J \cdot I_i) \cdot (J \cdot I_j) \\ &= J^2 \cdot \mathcal{G}(M). \end{aligned} $$

Similarly, $\mathcal{C}(J \cdot M) = J \cdot \mathcal{C}(M)$ thus $\mathcal{RG}(J \cdot M) = \mathcal{RG}(M)$ holds.

(4) $M' = \mathcal{C}(M)^{-1} \cdot M$ is such that $\mathcal{C}(M') = \mathcal{O}_K$ (using (2)) so any lattice vector $v \in M'$ has its coordinates in $\mathcal{O}_K$ thus $M' \subset (\mathcal{O}_K)^\ell$. If $M'$ were contained in some $\mathfrak{p}^\ell$ then the ideal spanned by the coordinates of $M'$ would be contained in $\mathfrak{p}$, i.e, we would have $\mathcal{O}_K = \mathcal{C}(M') \subseteq \mathfrak{p}$ (using Lemma 4.2), which is impossible. $\square$

## 4.2 The assumption

In this section, we formalize the assumption that will be used by our algorithm in Section 4.3. This assumption essentially states that, when sampling a random vector $\mathbf{u}$ in an integer rank-2 module $M \subseteq \mathcal{O}_K^2$, the probability that the ideal $\langle \mathbf{u}, \mathbf{u} \rangle_{K_\mathbb{R}} \cdot \mathcal{O}_K$ is prime is not too small. Of course, we need to exclude the cases where this assumption is obviously false, for instance if $M = 2\mathcal{O}_K^2$, then $\langle \mathbf{u}, \mathbf{u} \rangle_{K_\mathbb{R}}$ will always be divisible by 4. More generally, we need to exclude the cases where the Gram ideal $\mathcal{G}(M)$ is not $\mathcal{O}_K$. We provide in Appendix B both theoretical and experimental justifications in favor of our assumption.

**Assumption 1.** There exists some absolute polynomial $P$ (with non-negative coefficients) such that the following holds. Let $K$ be a totally real number field
of degree $d$, $M \subseteq \mathcal{O}_K^2$ be a module of rank 2, and $s > 0$ be a real number such that $s \ge \eta_{1/2}(M)$. Let $I = \mathcal{G}(M)$ be the Gram ideal of the module $M$. Let $(z_1, z_2)^T \leftarrow D_{M,s}$ and $q = z_1^2 + z_2^2$. Then

$$ \Pr(q \cdot I^{-1} \text{ is prime}) \ge \frac{1}{\rho_K \cdot \log(s/\mathcal{N}(I)^{1/d}) \cdot P(d)}, $$

where $\rho_K$ is the residue of the Dedekind zeta function of $K$ at $1$.

Note that the ideal $q \cdot I^{-1}$ in our assumption is always an integral ideal. Indeed, thanks to Lemma 4.2, we know that the ideal $I$ contains all square norms of vectors of $M$, hence it contains in particular $\langle z, z \rangle_{K_R} = q$ (where $z = (z_1, z_2)^T$), which implies $qI^{-1} \subseteq II^{-1} = \mathcal{O}_K$.

## 4.3 The algorithm

Before describing the algorithm for module-LIP, let us start with an algorithm, called TwoSquares, which solves sum of two squares equations in $\mathcal{O}_K$ for a totally real number field $K$ (i.e., equations of the form $x^2+y^2=q$ where $q \in \mathcal{O}_K$ is given and $x, y \in \mathcal{O}_K$ are the unknown). Algorithm TwoSquares works by reformulating this as a relative norm equation in some well chosen CM extension $L$ of $K$, and then applying Algorithm NormEquation from preliminaries (Algorithm 2.1).

**Algorithm 4.1 Finding sums of two squares in totally real fields (TwoSquares)**

**Input:** A basis $B_K$ of $\mathcal{O}_K$, an element $q \in \mathcal{O}_K$, the factorization of $|\mathcal{N}_K(q)|$.

**Output:** All elements $(x, y) \in \mathcal{O}_K^2$ such that $q = x^2 + y^2$.

1: Define $L \leftarrow K[X]/(X^2+1)$.

2: Compute $B_L \leftarrow$ a basis of $\mathcal{O}_L$, using Lemma 2.6.

3: $S \leftarrow \text{NormEquation}(B_K, B_L, q)$, the factorization of $|\mathcal{N}_K(q)|$.

4: Cast elements of $S$ from $L$ into $K^2$ (via the map $a+bX \in L \mapsto (a,b) \in K^2$)

5: **return** $S \cap \mathcal{O}_K^2$

**Lemma 4.5.** Let $K$ be a totally real number field and $q \in \mathcal{O}_K$. Given as input a basis of $\mathcal{O}_K$, the element $q \in \mathcal{O}_K$ and the factorization of $|\mathcal{N}_K(q)|$, Algorithm 4.1 (TwoSquares) computes all $(x, y) \in \mathcal{O}_K^2$ such that $q = x^2 + y^2$. Moreover, the algorithm runs in time poly $(\log \Delta_K, (\log |\mathcal{N}_K(q)|)^r)$, where $r$ is the number of distinct prime factors of the ideal $q \cdot \mathcal{O}_K$.

*Proof. Correctness.* The field $L = K[X]/(X^2+1)$ is a totally imaginary quadratic extension of $K$, and so $L|K$ is a CM extension as desired. Moreover, the non-trivial automorphism $\tau$ of $L$ fixing $K$ is the map sending $X$ to $-X$. Hence, for any element $z = a + bX \in L$, we have that $\mathcal{N}_{L|K}(z) = z \cdot \tau(z) = a^2 + b^2$. To any solution $(x, y)$ of the sum of two squares equation $x^2 + y^2 = q$, we can then associate a solution $z = x + y \cdot X \in \mathcal{O}_L$ to the relative norm equation
$\mathcal{N}_{L|K}(z) = q$. By correctness of the NormEquation algorithm (see Theorem 2.16), the set $S$ contains all solutions to this relative norm equation. Note that not all of them provide a solution to the sum of two squares equations, since some $z = x+y \cdot X \in S$ may have $x$ or $y$ not belonging to $\mathcal{O}_K$ (the set $\{a+bX | a, b \in \mathcal{O}_K\}$ is included in $\mathcal{O}_L$, but the inclusion may be strict). This is why we intersect the set $S$ with the set $\{a+bX | a, b \in \mathcal{O}_K\}$.

*Complexity.* A basis of $\mathcal{O}_L$ can be computed in polynomial time from a basis of $\mathcal{O}_K$, using Lemma 2.6, which proves that Step 2 can be run in polynomial time. For Step 3, we know from Theorem 2.16 that it can be run in time poly($\log \Delta_L$, $(\log |\mathcal{N}_K(q)|)$) $\cdot (1 + \log |\mathcal{N}_K(q)|)^r = \text{poly}(\log \Delta_L, (\log |\mathcal{N}_K(q)|)^r)$. Recall from the preliminaries that $\log \Delta_L = \text{poly}(\log \Delta_K)$, hence the previous quantity is also poly $(\log \Delta_K, (\log |\mathcal{N}_K(q)|)^r)$. Finally, testing whether an element $x+y \cdot X$ in $S$ satisfies $(x, y) \in \mathcal{O}_K^2$ can be done in polynomial time using the basis $B_K$. $\square$

We now describe our main algorithm, which solves wc-smodLIP<sub>K</sub><sup>B</sup> when K is a totally real number field and **B** is a pseudo-basis of a rank-2 module in $\mathcal{O}_K^2$. The general case follows as a by-product in Algorithm 4.3, thanks to the coordinate ideal $\mathcal{C}(M)$. Once a preliminary factorization of $\mathcal{G}(M)$ is done, the algorithm tries to find two “nice” vectors for the input instance $\mathbf{G}' = (\mathcal{G}', (I'_1, I'_2))$. By nice, we mean that we sample random vectors until we obtain somewhat short and linearly independent $\mathbf{v}, \mathbf{v}'$, such that both $\mathbf{v} = \mathbf{v}^*\mathcal{G}'\mathbf{v}$ and $\mathbf{v}' = \mathbf{v}'^*\mathcal{G}'\mathbf{v}$ generate a prime multiple of $\mathcal{G}(M)$ (recall that $\mathbf{q}, \mathbf{q}' \in \mathcal{G}(M)$, so the ideals they generate have to be a multiple of $\mathcal{G}(M)$). As mentioned in the beginning of this section, we will call the TwoSquares algorithm for $\mathbf{q}, \mathbf{q}'$, which requires to know the factorization of $\mathcal{N}_K(q)$ and $\mathcal{N}_K(q')$. Computing these factorizations can be done efficiently once we know the factorization of $\mathcal{N}(\mathcal{G}(M))$, since we ensured that $\mathbf{q}/\mathcal{G}(M)$ and $\mathbf{q}'/\mathcal{G}(M)$ are prime ideals. Pairing these two-square decompositions gives as many linear equations as there are entries in **B**: some of them must lead to congruence matrices (others may be non-integral). We actually prove that we find them all this way.

**Theorem 4.6 (Assumption 1).** Let $K$ be a totally real number field and $M \subset \mathcal{O}_K^2$ an integer module lattice of rank 2 with pseudo-basis $\mathbf{B} = (B, I_1, I_2)$ and associated pseudo-Gram matrix $\mathbf{G}$. Algorithm 4.2 takes as input a basis of $\mathcal{O}_K$, the pseudo-matrix $\mathbf{B}$ and $\mathbf{G}' = (\mathcal{G}', I'_1, I'_2)$ an instance of wc-smodLIP<sub>K</sub><sup>B</sup> and finds all congruence matrices between $\mathbf{G}$ and $\mathbf{G}'$. Under Assumption 1, the algorithm runs in expected polynomial time in the size of its input and in

$$ (\text{poly}(\rho_K, \log \Delta_K, \text{size}(\mathbf{G}')))^r + T_{\text{factor}}(\mathcal{N}(\mathcal{G}(M))), $$

where $\rho_K$ is the residue of the Dedekind zeta function of $K$ at 1, and $r$ is the number of distinct prime ideals dividing the Gram ideal $\mathcal{G}(M)$.

At Step 13, we actually do not need to factorize again, since standard primality tests will give us both the prime and its valuation. Note that Algorithm 4.2 solves wc-smodLIP<sub>K</sub><sup>B</sup> on input $\mathbf{G}'$, but it does even more than this, since it finds
**Algorithm 4.2 Finding all congruence matrices for integer rank-2 modules.**

**Input:** A basis $B_K$ of $O_K$, a pseudo-basis $B = (B, (I_1, I_2))$ of $M \subseteq O_K^2$ with pseudo-Gram matrix $G$, and $G' = (G', (I'_1, I'_2)) \sim G$ an instance of wc-smodLIP$^B_K$.

**Output:** All congruence matrices between $G$ and $G'$.

1: $I \leftarrow \mathcal{G}(M)$; $\alpha = \rho_K \cdot P(d)$ (with $P(d)$ from Assumption 1)

2: Factor $\mathcal{N}(I) = \prod_j q_j^{f_j}$.

*Generating two “nice” instances of TwoSquares*

3: $q \leftarrow 0$; $(u, v) \leftarrow (0, 0)$; $s \leftarrow 4^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1 \le j \le 2} (\|\sigma(g_{j,j})^{1/2}\| \cdot \mathcal{N}(I_j^{1/d}))$ (where $G' = (g'_{i,j})_{1 \le i,j \le 2}$)

4: **while** $\sqrt{\|\sigma(q)\|_1} > s \cdot \sqrt{8d + \log(4\alpha \log(s))}$ or $q \cdot I^{-1}$ is not a prime ideal do

5: $I'_1 \times I'_2 \ni (u, v)^T \leftarrow \text{GaussianGram}(G', s)$.

6: $q \leftarrow (u, v) \cdot G' \cdot (u, v)^T$.

7: **end while**

8: $q' \leftarrow 0$; $(u', v') \leftarrow (0, 0)$; $s' = 144 \cdot d \cdot \Delta_K^{1/d} \cdot \max(\alpha^2, 1) \cdot s^4$.

9: **while** $(u', v') \in \text{Span}_K((u, v))$ or $\sqrt{\|\sigma(q)\|_1} > s' \cdot \sqrt{8d + \log(4\alpha \log(s'))}$ or $q' I^{-1}$ is not a prime ideal do

10: $I'_1 \times I'_2 \ni (u', v')^T \leftarrow \text{GaussianGram}(G', s')$.

11: $q' \leftarrow (u', v') \cdot G' \cdot (u', v')^T$.

12: **end while**

*Solving the two instances of TwoSquares*

13: Factor $\mathcal{N}(qI^{-1}) = p^e$ and $\mathcal{N}(q' I^{-1}) = (p')^f$

14: $S_1 \leftarrow \text{TwoSquares}(B_K, q, p^e \cdot \prod_j q_j^{f_j})$; $S_2 \leftarrow \text{TwoSquares}(B_K, q', (p')^f \cdot \prod_j q_j^{f_j})$

*Recovering the congruence matrices from the solutions to TwoSquares*

15: $S \leftarrow \emptyset$.

16: **for** $((t_1, t_2), (t'_1, t'_2)) \in S_1 \times S_2$ **do**

17: $D \leftarrow \begin{pmatrix} t_1 & t'_1 \\ t_2 & t'_2 \end{pmatrix} \cdot \begin{pmatrix} u & u' \\ v & v' \end{pmatrix}^{-1}$

18: $V \leftarrow B^{-1} \cdot D$

19: **if** $V$ is a congruence matrix between $G$ and $G'$ **then**

20: $S \leftarrow S \cup \{V\}$.

21: **end if**

22: **end for**

23: **return** $S$.
all congruence matrices between $G$ and $G'$, when $wc-smodLIP_K^B$ only asks to find one such congruence matrix.

*Proof. Correctness.* First, note that thanks to the if condition in Steps 19 of the algorithm, all matrices $V$ that are output by our algorithm are indeed congruence matrices between $G$ and $G'$.

Conversely, let us fix $U \in \text{GL}_2(K_\mathbb{R})$ a congruence matrix between $G$ and $G'$ and show that $U \in S$ at the end of the algorithm. Let $C = B \cdot U$. By definition of congruence matrices, we know that $C = (C, I'_1, I'_2)$ is another pseudo-basis of the module $M$. Moreover, we also know that $U^*GU = G' = C^*C$. This means that $G'$ is the pseudo-Gram matrix of the pseudo-basis $C$ of $M$.

Let us define $z = (z_1, z_2)^T := C \cdot (u, v)^T$ (where $u$ and $v$ are as in the algorithm, after exiting the while loop in Step 7). Since $s$ satisfies the constraints from Lemma 3.8 (see the discussion below for the choice of $s$), the algorithm **GaussianGram** is correct, and so we have $u \in I'_1$ and $v \in I'_2$. This implies that $z \in M$. Moreover, we have that $q := (u, v) \cdot G' \cdot (u, v)^T = z^*z = z_1^2 + z_2^2$. Since $M \subset \text{O}_K^2$, the pair $(z_1, z_2)$ thus gives a sum of two squares for $q$. By Lemma 4.5, **TwoSquares** finds them all so the pair $(z_1, z_2)$ must belong to the set $S_1$ computed in Step 14. A similar argument works for $z' = (z'_1, z'_2)^T = C \cdot (u', v')^T$ and $S_2$.

From this, we know that during the for loop of Step 16, there must be one iteration where $(t_1, t_2) = (z_1, z_2)$ and $(t'_1, t'_2) = (z'_1, z'_2)$. When this is the case, then the matrix $D$ computed in Step 17 must be equal to $C$. Note that this computation makes sense since $(u, v)$ and $(u', v')$ are linearly independent. This finally implies that the corresponding matrix $V$ from Step 18 is equal to $U$, and so $U \in S$ at the end of the algorithm. Overall, this proves that, if the algorithm terminates, then $S$ contains all the congruence matrices between $G$ and $G'$.

*Complexity.* We have seen that the Gram ideal $\mathcal{G}(M)$ can be computed in polynomial time from the knowledge of $G'$. At Step 2, the norm of the Gram ideal is factored, which takes time $T_{factor}(\mathcal{N}(\mathcal{G}(M)))$ (note that since $M \subseteq \text{O}_K^2$, its Gram ideal $\mathcal{G}(M)$ is integral, and so $\mathcal{N}(\mathcal{G}(M)) \in \mathbb{Z}$).

We discuss the choice of the parameters $s$ and $s'$ for the sampling algorithm. To work under our Assumption 1, they must be chosen above the smoothing parameter $\eta_{1/2}(\sigma(M))$ of the module lattice $\sigma(M)$. Equation (1) tells us that it is enough to take $s$ larger than $\sqrt{\log(12d)/\pi} \cdot \lambda_{2d}(\sigma(M))$. Now, we know from Lemma 2.9 that there exists a basis of $\sigma(M)$ whose vectors are all smaller than $\sqrt{d} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1 \le j \le 2} (\|\sigma(g'_{j,j})\|^{1/2} \|\mathcal{N}(I'_j)^{1/d}\))$, so this must be an upper bound on $\lambda_{2d}(\sigma(M))$. Since $2^d \ge \sqrt{d \log(12d)/\pi}$ for all $d \ge 1$, we conclude that $s' \ge s \ge \eta_{1/2}(\sigma(M))$ as needed to apply Assumption 1 and Lemma 3.8.

As a consequence, Lemma 3.8 ensures that steps 5 and 10 run in polynomial time. Moreover, by correctness of the **GaussianGram** algorithm, we know that $\sigma(z) \sim D_{\sigma(M),s}$ and $\sigma(z') \sim D_{\sigma(M),s'}$, where $z = C \cdot (u, v)^T$ and $z' = C \cdot (u', v')$, as before.

Now we estimate the number of trials before satisfying the conditions on Step 4. By Lemma 2.5 applied to $\varepsilon = (4\alpha \log s)^{-1}$, we have $\|\sigma(z)\| > s \cdot \sqrt{8d + \log(4\alpha \log(s))}$ with probability at most $\varepsilon$. Recall that $q = z_1^2 + z_2^2$, so
we have that $\|\sigma(q)\|_1 = \|\sigma(z)\|^2$. This implies that the first condition in the while loop is satisfied with probability $\ge 1 - \varepsilon$. For the second condition in the while loop, we have seen that Assumption 1 applies, so $qI^{-1}$ is prime with probability at least $(\alpha \log(s/\mathcal{N}(I)^{1/d}))^{-1} \ge (\alpha \log s)^{-1}$ (recall that $\alpha = \rho_K \cdot P(d)$ and that $M \subseteq \mathcal{O}_K^2$ so that $\mathcal{N}(I) := \mathcal{N}(\mathcal{G}(M)) \ge 1$).

Overall, the probability to exit the first while loop in Step 4 is larger than $(\alpha \log s)^{-1} - \varepsilon \ge (2\alpha \log s)^{-1}$, using the definition of $\varepsilon$.<fnref n="20" /> The expected number of iterations of the while loop is then $\le 2\alpha \log s = \text{poly}(\log \Delta_K, \rho_K, \text{size}(\mathcal{G}'))$.

To conclude on this first while loop, note that all the operations performed during one iteration of the while loop (including the two tests in Step 4) can be performed in time $\text{poly}(\log \Delta_K, \rho_K, \text{size}(\mathcal{G}'))$ (for the test that $qI^{-1}$ is prime, we use Corollary 2.13, and we apply it only when the first test passes, which ensures that $\mathcal{N}(qI^{-1}) \le \mathcal{N}_K(q) \le \|\sigma(q)\|_1^d$ is not too big).

The reasoning for the second while loop is similar, except that we now also want that $(u', v')$ be non-colinear with $(u, v)$. This is equivalent to asking that $z'$ is not colinear to $z$. In other words, we want $z'$ to avoid the rank-1 submodule $N := M \cap \text{Span}_K(z)$. Again, Lemma 3.8 tells us that $z' \sim D_{M,s'}$, hence we want to upper bound

$$ \Pr_{y \sim \mathcal{D}_{M,s'}} (y \in N) = \frac{\rho_{s'}(N)}{\rho_{s'}(M)}. $$

To estimate $\rho_{s'}(N)$ and $\rho_{s'}(M)$ we would like to apply Lemma 2.3 (with $\varepsilon = 1/2$). We have already seen that $s \ge \eta_{1/2}(M)$ and by definition $s' \ge s$, so this handles the denominator. Since $N$ has rank 1, observe that $\lambda_d(N) \le \lambda_d^{(\infty)}(\mathcal{O}_K) \cdot \lambda_1(N) \le \Delta_K^{1/d} \cdot \|z\|$. Using the upper bound on $\|z\| = \sqrt{\|q\|_1}$ and Equation (1), one can check that $s' \ge \eta_{1/2}(N)$ as desired. We can then apply Lemma 2.3 and use the fact that $\det(N) \ge 1$ since $N \subset \mathcal{O}_K^2$ to obtain

$$ \begin{aligned} \Pr_{y \sim \mathcal{D}_{M,s'}} (y \in N) &\le 3/2 \cdot \frac{\det(M)}{(s')^{2d}} \cdot 2 \cdot \frac{(s')^d}{\det(N)} \le \frac{3 \det(M)}{(s')^d} \\ &\le \frac{(s')^{d/2}}{4\alpha \cdot (s')^d} \le \frac{1}{4\alpha \cdot (\sqrt{s'})^d} \le \frac{1}{4\alpha \log(s')}, \end{aligned} $$

where the last inequality follows from the fact that $s' \ge 1$ (so that $(\sqrt{s'})^d \ge \log(s')$) and on the second line we used the fact that $\sqrt{s'} \ge (12\alpha \det(M))^{1/d}$ by choice of $s'$. Indeed, replacing $s'$ by its value, the latter inequality is equivalent to having $12 \cdot \sqrt{d} \cdot \Delta_K^{1/2d} \cdot \max(\alpha, 1) \cdot s^2 \ge (12\alpha \det(M))^{1/d}$ which is implied by $s^2 \ge (\det(M))^{1/d}$. We know that $\det(M) \le \lambda_{2d}(M)^{2d}$ (this holds in any lattice), so it is sufficient to prove that $s \ge \lambda_{2d}(M)$, which we have already proved since this was required for the Gaussian sampling algorithm GaussianGram (see Lemma 3.8).

Similarly to the first while loop, we have that, under Assumption 1, the probability that $q'I^{-1}$ is prime is $\ge (\alpha \log(s'))^{-1}$. The probability that $\sqrt{\|q\|_1} =$

<footnote n="20">²⁰ Here we also use the general fact that for two events A and B, we can upper bound $\Pr(A \cap B) = \Pr(A) - \Pr(A \cap \neg B) \ge \Pr(A) - \Pr(\neg B)$.</footnote>
‖z'‖ is larger than the bound in the condition is ≤ (4α log(s'))⁻¹ (the argument is again similar to the first loop). Combining everything, the probability to exit the second while loop is at least

$$ \frac{1}{\alpha \log(s')} - \frac{1}{4\alpha \log(s')} - \frac{1}{4\alpha \log(s')} = \frac{1}{2\alpha \log(s')} $$

We conclude that the expected number of iterations of the second while loop is poly(log Δ<sub>K</sub>, ρ<sub>K</sub>, size(G')). Similarly to the first while loop, all the operations performed during one execution of the while loop can be done in time poly(log Δ<sub>K</sub>, ρ<sub>K</sub>, size(G')).

Step 13 can be done in polynomial time since N(qI⁻¹) and N(q'I⁻¹) are prime powers. The two calls to the TwoSquares algorithm in Step 14 can be performed in time poly (log Δ<sub>K</sub>, (log |N<sub>K</sub>(q)|)<sup>r+1</sup>) = poly(log Δ<sub>K</sub>, ρ<sub>K</sub>, size(G'))<sup>r</sup>. Here we used the fact that qO<sub>K</sub> and q'O<sub>K</sub> have at most r + 1 distinct prime factors since I = G(M) has r distinct prime factors and qI⁻¹ and q'I⁻¹ are prime ideals. We also used the fact that log |N<sub>K</sub>(q)| and log |N<sub>K</sub>(q')| are poly(log Δ<sub>K</sub>, ρ<sub>K</sub>, size(G')), thanks to the conditions on ‖σ(q)‖₁ and ‖σ(q')‖₁ in the while loops.

Finally, let us consider the final for loop from Step 16. Each step in this loop can be done in polynomial time. For the number of iterations of the loop, the proof of Theorem 2.16 gives |S<sub>1</sub>| ≤ d²(log(|N<sub>K</sub>(q)| + 1)<sup>r+1</sup> and the same holds for |S<sub>2</sub>|. Hence, the number of iterations of the loop is upper bounded by poly(log Δ<sub>K</sub>, ρ<sub>K</sub>, size(G'))<sup>r</sup>. This concludes the analysis of the running time of the algorithm. □

Before extending the previous result to modules in K<sup>2</sup>, we focus a little bit on the particular case when M = O<sub>K</sub><sup>2</sup> and K is the maximal totally real subfield of a cyclotomic field L = Q(ζ<sub>m</sub>). In this case, the Gram ideal is simply O<sub>K</sub>, leading to a polynomial complexity in d (the degree of K), the residue ρ<sub>K</sub> and the size of the input.

**Corollary 4.7 (Assumption 1).** Let K be the maximal totally real subfield of a cyclotomic field, and define I<sub>2</sub> = (I<sub>2</sub>, (O<sub>K</sub>)<sub>1≤i≤2</sub>) (this is a pseudo-basis of the rank-2 module O<sub>K</sub><sup>2</sup>). Under Assumption 1, there exists a probabilistic algorithm solving wc-smodLIP<sub>K</sub><sup>I<sub>2</sub></sup> in expected polynomial time in the degree d of K, the residue ρ<sub>K</sub>, and in the size of the input.

*Proof.* Since M = O<sub>K</sub><sup>2</sup>, the Gram ideal is trivial thus with the notation of Theorem 4.6, r = 1, and Algorithm 4.2 solves wc-smodLIP<sub>K</sub><sup>I<sub>2</sub></sup> in expected polynomial time in ρ<sub>K</sub>, log Δ<sub>K</sub> and the size of the inputs. Also, notice that the discriminant of K can be computed ([38, Proposition 3.1]) and verifies log Δ<sub>K</sub> = poly(d). □

**Corollary 4.8 (Assumption 1).** Let K be a totally real number field and M ⊂ K<sup>2</sup> a module lattice of rank 2 with pseudo-basis B = (B, I<sub>1</sub>, I<sub>2</sub>) and associated pseudo-Gram matrix G. There exists a probabilistic algorithm (Algorithm 4.3) that takes as input a basis of O<sub>K</sub>, the pseudo-basis B, and G' = (G', I'<sub>1</sub>, I'<sub>2</sub>) an
**Algorithm 4.3 Finding all congruence matrices for rank-2 modules.**

**Input:** A basis of $\mathcal{O}_K^2$, a pseudo-basis $\mathbf{B} = (B, (I_1, I_2))$ of $M \subset K^2$, with pseudo-Gram matrix $\mathbf{G}$, and $\mathbf{G}' = (G, (I'_1, I'_2)) \sim \mathbf{G}$ an instance of wc-smodLIP$^{\mathbf{B}}$.

**Output:** All congruence matrices between $\mathbf{G}$ and $\mathbf{G}'$.

1: $J \leftarrow \mathcal{C}(M)^{-1}$

2: $\mathbf{B}_J \leftarrow (B, \{J \cdot I_i\}_{i=1,2})$; $\mathbf{G}_J \leftarrow (G, \{J \cdot I_i\}_{i=1,2})$; $\mathbf{G}'_J \leftarrow (G', \{J \cdot I'_i\}_{i=1,2})$

3: $S \leftarrow$ Run Algorithm 4.2 with $\mathbf{B}_J, \mathbf{G}_J$ and $\mathbf{G}'_J$

4: **return** $S$.

instance of wc-smodLIP$^{\mathbf{B}}$ and finds all congruence matrices between $\mathbf{G}$ and $\mathbf{G}'$. Under Assumption 1, the algorithm runs in expected time polynomial in its input size and in

$$ \left( \text{poly}(\rho_K, \log \Delta_K, \text{size}(\mathbf{G}')) \right)^r + T_{\text{factor}}(\mathcal{N}(\mathcal{RG}(M))), $$

where r is the number of distinct prime ideals dividing the relative Gram ideal $\mathcal{RG}(M)$.

**Proof. Correctness.** By Lemma 4.4 (4), $M' = \mathcal{C}(M)^{-1} \cdot M$ is an integer module lattice not contained in $\mathfrak{p}^2$ for any prime ideal $\mathfrak{p} \subset \mathcal{O}_K$. Using (3) we get $\mathcal{RG}(M) = \mathcal{RG}(M') = \mathcal{G}(M')$ (since $\mathcal{C}(M') = \mathcal{O}_K$). The last thing to observe is that scaling the module doesn't change the set of solutions to modLIP. This is because a congruence matrix $U$ between $\mathbf{G}_J := (G, J \cdot I_1, J \cdot I_2)$ and $\mathbf{G}'_J := (G', J \cdot I'_1, J \cdot I'_2)$ satisfies $\mathbf{G}' = U^*\mathbf{G}U$ and $u_{i,j} \in (J \cdot I_i) \cdot (J \cdot I'_j)^{-1} = I_i(I'_j)^{-1}$, so it is also a congruence matrix between $\mathbf{G}$ and $\mathbf{G}'$.

**Complexity.** The relative Gram ideal can be computed in polynomial time in the size of $\mathbf{B}$ and $\mathbf{G}'_J$ has size poly($\text{size}(\mathbf{G}')$, size($J$)) = poly($\text{size}(\mathbf{G}')$), thus the complexity follows from Theorem 4.6. $\square$

# 5 Implementation of the algorithm

We have implemented a proof-of-concept of our algorithm mixing Sagemath and PARI/GP, for the totally real (maximal) subfield $K$ of cyclotomic fields $L = \mathbb{Q}(\zeta_m)$. The current version of the code only works for fields with conductor $m = 4k$: this ensures that $L$ contains a primitive 4-th root of unity (equivalently $L = K[X]/(X^2 + 1)$), which simplifies the code and covers the cryptographic relevant case where $m = 2^t$. This also allows us to use our implementation of the Gentry-Szydlo algorithm as in this case, $K[X]/(X^2 + 1) = L$ is a cyclotomic field. For other conductors or more general CM-extensions, a previous version of the code worked on toy-sized examples as a proof-of-concept, but we did not push more in this direction.

Our approach follows the structure of Algorithm 4.2. We give more details in Appendix C, and refer to our code in our public repository. Nonetheless, we briefly report some experimental results and observations. In our experiments,
we selected instances $(Q, B)$, with $B$ a basis of $\mathcal{O}_K^2$ and $Q = B^T \cdot B$, where $B$ had a quite short column (to emulate the situation in Hawk) but usually the second column would be much bigger. Our values of choice for $m$ included the power-of-two case but also various other of the form $4k$ (see Table 1) below). In the table, we also display the quantity $2d$, which is the dimension over $\mathbb{Z}$ of the module lattices involved in the problem (recall that they are rank-2 modules over $K$, and that $d = \deg(K)$). For a larger experiment, using PARI/GP 2.16 and its LLL relying on the “Flatter” algorithm [32], we could also solve the congruence problem for $m = 512$ (lattices of dimension $2d = 256$) in about 29 hours, essentially all spent in the two call to Gentry-Szydlo algorithm.

<table><caption>**Table 1.** Times in seconds for attacks over various maximal totally real subfields $K$ of cyclotomic fields with conductors $m = 4k$, averaged over 5 instances. The degree $d$ of $K$ is $\varphi(m)/2$, and the lattices involved have dimension $2d$. The upper table are powers-of-two. Experiments performed on a MacBook Pro (Apple M2), with Sagemath 10.2 and Pari/GP 2.15.5.</caption><thead><tr><th>(m, 2d)</th><th>(64, 32)</th><th>(128, 64)</th><th>(256, 128)</th></tr></thead><tbody><tr><th>Time</th><td>2</td><td>25</td><td>850</td></tr><tr><th>(m, 2d)</th><td>(124, 60)</td><td>(204, 64)</td><td>(228, 72)</td><td>(276, 88)</td><td>(260, 96)</td><td>(232, 112)</td><td>(340, 128)</td><td>(296, 144)</td></tr><tr><th>Time (s)</th><td>33</td><td>53</td><td>74</td><td>195</td><td>434</td><td>652</td><td>2980</td><td>4205</td></tr></tbody></table>

**Acknowledgments.** We are grateful to Aurel Page and Bill Allombert for their help with the implementation of the Gentry-Szydlo algorithm, Sébastien Labbé, Xavier Caruso and Vincent Delecroix for organizing the Sage Days 125, where a significant part of the implementation took place. Thanks to Paul Kirchner and Thomas Espitau for their preliminary implementation of Gentry-Szydlo that helped for proof-of-concepts. Finally we thank Koen de Boer and Wessel van Woerden for enlightening discussions.

Guilhem Mureau and Alice Pellet-Mary were supported by the CHARM ANR-NSF grant (ANR-21-CE94-0003). All the authors were supported by the PEPR quantique France 2030 programme (ANR-22-PETQ-0008). Alice Pellet-Mary was supported by the TOTORO ANR (ANR-23-CE48-0002).

## References

1. Belabas, K., van Hoeij, M., Klüners, J., Steel, A.: Factoring polynomials over global fields. Journal de théorie des nombres de Bordeaux 21(1), 15–39 (2009)

2. Bennett, H., Ganju, A., Peetathawatchai, P., Stephens-Davidowitz, N.: Just how hard are rotations of $\mathbb{Z}^n$? algorithms and cryptography with the simplest lattice. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 252–281. Springer (2023)
3. Bhargava, M., Shankar, A., Taniguchi, T., Thorne, F., Tsimerman, J., Zhao, Y.: Bounds on 2-torsion in class groups of number fields and integral points on elliptic curves. Journal of the American Mathematical Society 33(4), 1087–1099 (2020)

4. Biasse, J.F., Espitau, T., Fouque, P.A., Gélin, A., Kirchner, P.: Computing generator in cyclotomic integer rings: A subfield algorithm for the principal ideal problem in and application to the cryptanalysis of a fhe scheme. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 60–88. Springer (2017)

5. Boer, K.d.: Random walks on Arakelov class groups. Ph.D. thesis, Leiden University (2022)

6. Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing. pp. 575–584 (2013)

7. Bruin, P.J., Ducas, L., Gibbons, S.: Genus distribution of random q-ary lattices. Cryptology ePrint Archive (2022)

8. Buchmann, J.A., Lenstra, H.W.: Computing maximal orders and factoring over $\mathbb{Z}_p$. Preprint (1994)

9. Buchmann, J.A., Lenstra, H.W.: Approximatting rings of integers in number fields. Journal de théorie des nombres de Bordeaux 6(2), 221–260 (1994)

10. Cohen, H.: Advanced topics in computational number theory, vol. 193. Springer Science & Business Media (2012)

11. Cohen, H.: A course in computational algebraic number theory, vol. 138. Springer Science & Business Media (2013)

12. Ducas, L.: Provable lattice reduction of $\mathbb{Z}^n$ with blocksize n/2. Cryptology ePrint Archive (2023)

13. Ducas, L., Gibbons, S.: Hull attacks on the lattice isomorphism problem. In: IACR International Conference on Public-Key Cryptography. pp. 177–204. Springer (2023)

14. Ducas, L., Postlethwaite, E.W., Pulles, L.N., Woerden, W.v.: Hawk: Module lip makes lattice signatures fast, compact and simple. In: Advances in Cryptology–ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5–9, 2022, Proceedings, Part IV. pp. 65–94. Springer (2023)

15. Ducas, L., van Woerden, W.: On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In: Advances in Cryptology–EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30–June 3, 2022, Proceedings, Part III. pp. 643–673. Springer (2022)

16. Dutour Sikirić, M., Haensch, A., Voight, J., van Woerden, W.P.: A canonical form for positive definite matrices. Open Book Series 4(1), 179–195 (2020)

17. Felderhoff, J., Pellet-Mary, A., Stehlé, D., Wesolowski, B.: Ideal-svp is hard for small-norm uniform prime ideals. In: Theory of Cryptography Conference. pp. 63–92. Springer (2023)

18. Fieker, C., Stehlé, D.: Short bases of lattices over number fields. In: International Algorithmic Number Theory Symposium – ANTS. pp. 157–173. Springer (2010)

19. Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32. pp. 1–17. Springer (2013)

20. Gentry, C., Szydlo, M.: Cryptanalysis of the revised ntru signature scheme. In: Advances in Cryptology–EUROCRYPT 2002. pp. 299–320. Springer (2002)
21. Haviv, I., Regev, O.: On the lattice isomorphism problem. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. pp. 391–404. SIAM (2014)

22. Howgrave-Graham, N., Szydlo, M.: A method to solve cyclotomic norm equations. In: International Algorithmic Number Theory Symposium. pp. 272–279. Springer (2004)

23. Kirchner, P.: Algorithms on ideal over complex multiplication order. arXiv preprint arXiv:1602.09037 (2016)

24. Lenstra Jr, H.W., Silverberg, A.: Testing isomorphism of lattices over cm-orders. SIAM Journal on Computing 48(4), 1300–1334 (2019)

25. Louboutin, S.: Explicit bounds for residues of dedekind zeta functions, values of l-functions at s= 1, and relative class numbers. Journal of Number Theory 85(2), 263–282 (2000)

26. Marcus, D.A., Sacco, E.: Number fields, vol. 1995. Springer (1977)

27. Mehta, S.K., Rajasree, M.S.: On the bases of z n lattice. In: 2022 24th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC). pp. 100–107. IEEE (2022)

28. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM Journal on Computing 37(1), 267–302 (2007)

29. Narkiewicz, W.: Elementary and analytic theory of algebraic numbers, vol. 57. Springer (1974)

30. Neukirch, J.: Algebraic number theory, vol. 322. Springer Science & Business Media (2013)

31. Plesken, W., Souvignier, B.: Computing isometries of lattices. Journal of Symbolic Computation 24(3-4), 327–334 (1997)

32. Ryan, K., Heninger, N.: Fast practical lattice reduction through iterated compression. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023 - Proceedings, Part III. Lecture Notes in Computer Science, vol. 14083, pp. 3–36. Springer (2023)

33. Serre, J.P.: Local fields, vol. 67. Springer Science & Business Media (2013)

34. Szydlo, M.: Hypercubic lattice reduction and analysis of ggh and ntru signatures. In: Advances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 Proceedings 22. pp. 433–448. Springer (2003)

35. The PARI Group, Univ. Bordeaux: pari/GP version 2.16.2 (2024), available from http://pari.math.u-bordeaux.fr/

36. The Sage Developers: SageMath, the Sage Mathematics Software System (Version 10.3.0) (2024), https://www.sagemath.org

37. Washington, L.C.: Introduction to cyclotomic fields, vol. 83. Springer Science & Business Media (1997)

38. Yamagata, K., Yamagishi, M.: On the ring of integers of real cyclotomic fields (2016)
A Worst-case to average-case reduction for module-LIP

In [14] is given an average-case version of a module-LIP problem in which the instances of the problem are sampled following a certain distribution. This is used to generate secret keys (i.e. congruence matrices) and the security of the signature scheme Hawk thus lies on the average-case version of this problem (see [14, Algorithm 1 and Algorithm 6]). To ensure security, a worst-case to average-case reduction is proved ([14, Lemma 5]).

This appendix contains somehow a generalization of the result mentioned above.<fnref n="21" /> To do so, we provide a polynomial time algorithm (Algorithm A.1) which, given as inputs a pseudo-matrix B (with associated pseudo-Gram matrix G) and a parameter s > 0, samples congruent forms G' ~ G, together with a congruence matrix between them. An average-case version of module-LIP follows naturally and we prove a worst-case to average-case reduction. That means that solving module-LIP with an instance generated from this distribution is as hard as solving module-LIP for any instance, up to some polynomial-time operations.

Sampling module vectors.  From **G** we can define a distribution $\mathcal{D}_{G,s}$ (with pa-
rameter $s > 0$) on $I_1 \times \cdots \times I_\ell$ as usual (Definition A.1). Fixing $\mathbb{Z}$-bases of the
coefficient ideals, we can use Minkowski embedding to associate a positive defi-
nite quadratic form $\psi(\mathbf{G}) \in S_{d\ell}^0(\mathbb{R})$ (Definition A.2). In this paragraph we prove
that $\mathcal{D}_{G,s}$ and the distribution on $I_1 \times \cdots \times I_\ell$ obtained by sampling the coordi-
nates (in $\mathbb{Z}^{d\ell}$) with DiscreteGaussian($\psi(\mathbf{G})$, $s$) coincide (Lemma A.4). This is
a more detailed proof of the fact that the outputs to GaussianGram introduced
in Lemma 3.8 follow a Gaussian distribution.

**Definition A.1.** The distribution $\mathcal{D}_{G,s}$ on $I_1 \times \cdots \times I_\ell$ with parameter $s > 0$ is defined by

$$
\mathbb{P}(X = x) := \frac{\exp(-\pi \|x\|_G^2 / s^2)}{\sum_{y \in I_1 \times \cdots \times I_\ell} \exp(-\pi \|y\|_G^2 / s^2)},
$$

$$
\text{where } x \in I_1 \times \dots \times I_\ell \text{ and } \|y\|_G^2 := \mathrm{Tr}(y^* G y) \ge 0, \text{ for any } y \in I_1 \times \dots \times I_\ell.
$$

**Definition A.2.** For any $g \in K$ and ordered set $\alpha = \{\alpha_1, \dots, \alpha_d\} \subset K$ we put

$$
\psi_{\alpha}(g) := \left( \mathrm{Tr} \left( \bar{\alpha}_{i} \cdot g \cdot \alpha_{j} \right) \right)_{1 \le i, j \le d} \in \mathcal{M}_{d}(\mathbb{R}).
$$

<footnote n="21">²¹ Module-LIP as defined in [14] asks for a congruence matrix with determinant one, this is not a condition we kept in our definition of module-LIP. Also, the distribution used in [14] for key generation is different from the one we will present so the average-case problems are not the same.</footnote>
Now writing $G = (g_{i,j})_{1\le i,j\le \ell}$ and given $\mathbb{Z}$-bases $\alpha^{(j)} = \{\alpha_1^{(j)}, \dots, \alpha_d^{(j)}\}$ of $I_j$ for every $j \in \{1, \dots, \ell\}$, we define

$$ \psi(\mathbf{G}) := \left( \begin{array}{ccc} \begin{bmatrix} \psi_{\alpha^{(1)}}(g_{1,1}) \\ \vdots \\ \psi_{\alpha^{(1)}}(g_{\ell,1}) \end{bmatrix} & \cdots & \begin{bmatrix} \psi_{\alpha^{(\ell)}}(g_{1,\ell}) \\ \vdots \\ \psi_{\alpha^{(\ell)}}(g_{\ell,\ell}) \end{bmatrix} \\ \hline \\ \begin{bmatrix} \psi_{\alpha^{(1)}}(g_{1,1}) \\ \vdots \\ \psi_{\alpha^{(1)}}(g_{\ell,1}) \end{bmatrix} & \cdots & \begin{bmatrix} \psi_{\alpha^{(\ell)}}(g_{1,\ell}) \\ \vdots \\ \psi_{\alpha^{(\ell)}}(g_{\ell,\ell}) \end{bmatrix} \end{array} \right) \in S_{d\ell}(\mathbb{R}). $$

Note that this depends on the choice of a $\mathbb{Z}$-basis for each coefficient ideals. When the notation $\psi(\mathbf{G})$ is used, we mean that LLL-reduced $\mathbb{Z}$-bases of the coefficient ideals are fixed. Now we prove that this is indeed the matrix of a positive definite quadratic form. For a matrix $B = (\mathbf{b}_1 | \dots | \mathbf{b}_\ell) \in \mathcal{M}_\ell(K_\mathbb{R})$ and ideals $I_1, \dots, I_\ell$ with respective $\mathbb{Z}$-bases $\alpha^{(1)}, \dots, \alpha^{(\ell)}$, we define $\tilde{B} \in \mathcal{M}_{d\ell}(\mathbb{R})$ whose columns are given by $\tilde{b}_{j(d-1)+i} = \sigma(\alpha_i^{(j)} \cdot \mathbf{b}_j) \in \mathbb{R}^{d\ell}$, for $1 \le j \le \ell$ and $1 \le i \le d$.

**Lemma A.3.** Given $B = (\mathbf{b}_1 | \dots | \mathbf{b}_\ell) \in \text{GL}_\ell(K_\mathbb{R})$ such that $G = B^* \cdot B$, we have

$$ \psi(\mathbf{G}) = \tilde{B}^T \cdot \tilde{B}, $$

In particular $\psi(\mathbf{G})$ is symmetric, positive and definite.

*Proof.* Let us write $G = (g_{i,j})_{1\le i,j\le \ell}$ and let $1 \le s, t \le d\ell$. There are unique $1 \le i_s, i_t \le d$ and $1 \le j_s, j_t \le \ell$ such that $s = j_s(d-1)+i_s$ and $t = j_t(d-1)+i_t$. Then the coefficient $(s, t)$ on the right hand side is

$$ \begin{aligned} \langle \tilde{b}_s, \tilde{b}_t \rangle_{\mathbb{C}^{d\ell}} &= \langle \sigma(\alpha_{i_s}^{(j_s)} \cdot \mathbf{b}_{j_s}), \sigma(\alpha_{i_t}^{(j_t)} \cdot \mathbf{b}_{j_t}) \rangle_{\mathbb{C}^{d\ell}} \\ &= \operatorname{Tr}(\alpha_{i_s}^{(j_s)} \cdot \mathbf{b}_{j_s}^* \cdot \mathbf{b}_{j_t} \cdot \alpha_{i_t}^{(j_t)}) \\ &= \operatorname{Tr}(\alpha_{i_s}^{(j_s)} \cdot g_{j_s, j_t} \cdot \alpha_{i_t}^{(j_t)}), \end{aligned} $$

which is by definition the coefficient $(s, t)$ of $\psi(\mathbf{G})$.

**Lemma A.4.** Let $\alpha^{(j)} = \{\alpha_1^{(j)}, \dots, \alpha_d^{(j)}\}$ be a $\mathbb{Z}$-basis of $I_j$ and $x := (x_1, \dots, x_\ell) \in I_1 \times \dots \times I_\ell$. For every $1 \le j \le \ell$ we put $(z_i^{(j)})_i$ the coefficients of $x_j$ in the $\mathbb{Z}$-basis of $I_j$ i.e., $x_j = \sum_{i=1}^d z_i^{(j)} \alpha_i^{(j)}$ and $z = (z_i^{(j)})_{i,j} \in \mathbb{Z}^{d\ell}$. Then for any $s > 0$,

$$ \mathbb{P}(X = x) = \mathbb{P}(Z = z). \\ X \sim \mathcal{D}_{I_1 \times \dots \times I_\ell, s} \qquad Z \sim \mathcal{D}_{\psi(\mathbf{G}), s} $$

*Proof.* Let $s > 0$. It is enough to prove that

$$ \exp(-\pi \|x\|_G^2 / s^2) = \rho_{\psi(\mathbf{G}), s}(z) = \exp(-\pi (z^T \psi(\mathbf{G}) z) / s^2). $$
Let $B = (b_1|...|b_\ell) \in \text{GL}_\ell(K_\mathbb{R})$ such that $G = B^*B$, then by the previous lemma $z^T\psi(\mathbf{G})z = (\tilde{B}z)^T \cdot (\tilde{B}z)$ and by definition of $\tilde{B}$,

$$ 
\begin{aligned}
\tilde{B} \cdot z &= \sum_{j=1}^{d} \sum_{i=1}^{\ell} \tilde{b}_{j(d-1)+i} \cdot z_i^{(j)} \\
&= \sigma\left(\sum_{j=1}^{\ell} b_j \sum_{i=1}^{d} \alpha_i^{(j)} \cdot z_i^{(j)}\right) \\
&= \sigma\left(\sum_{j=1}^{\ell} b_j \cdot x_j\right) \\
&= \sigma(B \cdot x).
\end{aligned}
$$

Therefore we obtain as expected,

$$ 
\begin{aligned}
z^T \psi(\mathbf{G}) z &= \langle \tilde{B}z, \tilde{B}z \rangle_{\mathbb{C}^{d\ell}} \\
&= \text{Tr}((Bx)^*(Bx)) \\
&= \text{Tr}(x^*Gx) \\
&= \|x\|_G^2.
\end{aligned}
$$

*Sampling congruent forms.* Let us fix a pseudo-Gram matrix $\mathbf{G}$ associated to the pseudo-basis $\mathbf{B}$ of a module lattice $M$. Using the algorithm GaussianGram of Lemma 3.8 with input $\mathbf{G}$ and parameter $s > 0$ we can sample in the product $I_1 \times \cdots \times I_\ell$ (recall that the coefficient ideals are represented by fixed $\mathbb{Z}$-bases). Following the idea developed in [18, Fig. 2] we sample enough vectors (enough to get a rank $\ell$ matrix) and apply the CHNF algorithm to extract another pseudo-basis of $M$ together with the pseudo-bases change $U$. Then from $\mathbf{G}$ and $U$ we can build a congruent pseudo-Gram matrix $\mathbf{G}' \sim \mathbf{G}$.

**Lemma A.5.** For any pseudo-matrix $\mathbf{B} = (B, (I_j)_{1\le j \le \ell})$ with $B \in \text{GL}_\ell(K)$ and associated pseudo-Gram matrix $\mathbf{G} = ((g_{i,j})_{1\le i,j \le \ell}, (I_j)_{1\le j \le \ell}))$, and parameter

$$ s \ge \sqrt{\frac{d \cdot \log(2d\ell + 4)}{\pi}} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1 \le j \le \ell} \left( \|\sigma(g_{j,j})^{1/2}\| \cdot \mathcal{N}(I_j)^{1/d} \right), $$

Algorithm A.1 returns a pseudo-Gram matrix $\mathbf{G}' = (G', (J_j)_{1\le j \le \ell})$ congruent to $\mathbf{G} := (B^*B, (I_j)_{1\le j \le \ell})$ together with a congruence matrix $U$ between $\mathbf{G}$ and $\mathbf{G}'$. Is it a probabilistic algorithm which runs in expected time poly($d, \ell, \log s$).

Moreover, the result depends only on the equivalence class of the input, in the sense that for any congruent pseudo-Gram matrix $\mathbf{H} = (W^*GW, (H_i)_{1\le i \le \ell})$, running steps 9-11 with $\mathbf{H}$ and $W^{-1}Y$ instead of $\mathbf{G}$ and $Y$ gives the same output. This defines a Gaussian distribution on $[\mathbf{G}]$ with parameter $s$, denoted $\mathcal{D}_s([\mathbf{G}])$.
**Algorithm A.1** Sample congruent pseudo-Gram matrix.

**Input:** A pseudo-Gram matrix $G = (G, (I_i)_{1\le i\le l})$ coming from a known pseudo-basis of $M$, and a parameter $s \ge \sqrt{\frac{d \cdot \log(2d\ell+4)}{\pi}} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1\le j\le l} (\|\sigma(g_{j,j})^{1/2}\| \cdot N(I_j)^{1/d})$.

**Output:** A pseudo-Gram matrix $G' = (G', (J_i)_{1\le i\le l})$ equivalent to $G$ together with a congruence matrix $U$ between $G$ and $G'$.

1: $C \leftarrow 1 - (1 + e^{-\pi})^{-1}$ and $m \leftarrow \lfloor \frac{2\ell}{C} \rfloor$

2: **for** $1 \le i \le m$ **do**

3: $I_1 \times \cdots \times I_\ell \ni y_i \leftarrow \text{GaussianGram}(G, s)$

4: **end for**

5: $Y \leftarrow (y_1 | \dots | y_m) \in \mathcal{M}_{\ell \times m}(K)$

6: **if** $Y$ has rank $< \ell$ **then**

7: Restart

8: **end if**

9: $(H, (J_i^{-1})_{1\le i\le \ell}, U_0) \leftarrow \text{CHNF}(Y^T, (I_i^{-1})_{1\le i\le \ell})$, [10, Algorithm 1.4.7].

10: $U \leftarrow U_0^{-T}$

11: **return** $G' = (U^*GU, (J_i)_{1\le i\le l}), U)$

*Proof. Correctness.* At step 9, properties of the CHNF give $Y^T U_0 = H$ and $u_{i,j}^0 \in I_i^{-1} J_j$ (where $U_0 = (u_{i,j}^0)_{1\le i,j\le \ell}$), $v_{i,j}^0 \in J_i^{-1} I_j$ (where $U_0^{-1} = (v_{i,j}^0)_{1\le i,j\le \ell}$). Thus at step 10, the matrix $U = U_0^{-T}$ has coefficient $(i, j)$ in $I_i J_j^{-1}$ and it is a congruence matrix between $G$ and $G'$ (with notations of step 11). Thus the algorithm ensures a pseudo-Gram matrix $G' \sim G$ together with the congruence matrix.

*Complexity.* Sampling from GaussianGram (thanks to Lemma 3.8) and the CHNF Algorithm [10, Algorithm 1.4.7] run in polynomial time in $d$, $\ell$ and $\log s$. We need to estimate the probability of failure at step 6. Let $T$ be the random variable counting the number of iteration before founding a set of full rank vectors. By Lemma 5.1 of [21] (and because $s \ge \max_{1\le j\le \ell} \|\sigma(g_{j,j})^{1/2}\| \ge \lambda_{d\ell}(\sigma(M)))$, for any $i \in \{1, \dots, d\ell - 1\}$ and set of vectors $\{y_1, \dots, y_i\}$ sampled from GaussianGram($G$, $s$), the probability that $y \leftarrow GaussianGram(G, s)$ does not belong to the span of $y_1, \dots, y_i$ is greater than $C := 1 - (1 + e^{-\pi})^{-1}$. Let $m = \lfloor \frac{2\ell}{C} \rfloor$ and $X_1, \dots, X_m$ be Bernoulli variables with success parameter $C$, and $S_m = X_1 + \dots + X_m$. Then, the probability $p_{\text{fail}}$ of not finding $\ell$ linearly independent vectors within $m$ sampled vectors is upper bounded by the probability $\mathbb{P}(S_m \le \ell - 1)$, where $S_m$ follows a binomial distribution with parameters $m$ and $C$ i.e.,

$$p_{\text{fail}} \le \mathbb{P}(S_m \le \ell - 1).$$
Using Hoeffding's inequality,

$$
\begin{align*}
p_{\text{fail}} &\le \mathbb{P}\left(\frac{S_m}{m} - C \le \frac{\ell-1}{m} - C\right) \\
&\le \exp\left(-2m\left(C - \frac{\ell-1}{m}\right)^2\right) \\
&\le \exp(-mC) \\
&\le \exp(-2\ell) \\
&\le e^{-2}.
\end{align*}
$$

Therefore,

$$
\mathbb{E}[T] \leq \frac{1}{1 - p_{\text{fail}}} < 2.
$$

Independance from G. Finally we prove that the result depends only on the
equivalence class of G. Let (W*GW, (I'_i)_{1≤i≤ℓ}) be equivalent to G, where W =
(w_{i,j})_{1≤i,j≤ℓ} ∈ GL_ℓ(K). Denote by (H', (J'_i^{-1})_{1≤i≤ℓ}, U'_0) the CHNF Algorithm
of [10] applied to the pseudo-matrix (Y^T W^{-T}, (I'_i^{-1})_{1≤i≤ℓ}) and U' = U'_0^{-T}. By
unicity of the CHNF (there is a unique pseudo-matrix in CHNF in the orbit of
G for the multiplication equivalence relation), we obtain

$$
(U')^{-1}W^{-1}Y = U_0'^T W^{-1}Y = (Y^T W^{-T} U_0')^T = H' = H = (Y^T U_0)^T = U^{-1}Y,
$$
so $(U')^{-1}W^{-1} = U^{-1}$ and $U' = W^{-1}U$. Then,

$$
(U')^* W^* G W U' = U^* W^{-*} W^* G W W^{-1} U = U^* G U.
$$

Also, the unicity of the CHNF implies $J'_i = J_i$ for all $1 \le i \le \ell$ so the pseudo-
Gram matrix returned is the same and this concludes the proof. □

*Average-case problem.* Now that we have an efficient algorithm to generate in-
stances of module-LIP, it leads us to an average-case version of the problem.

**Definition A.6 (ac-smodLIP<sub>K</sub><sup>B,s</sup> ).** For *B* a pseudo-basis of a module lattice *M* ⊂ *K*<sup>*ℓ*</sup> with associated pseudo-Gram matrix *G*, the average-case search module-Lattice Isomorphism Problem with parameter *K*, *B* and *s* denoted by ac-smodLIP<sub>*K*</sub><sup>B,s</sup> is, given as input any pseudo-Gram matrix *G'* ~ *G* sampled from Algorithm A.1 with parameters *G* and *s* > 0, to find a congruence matrix between *G* and *G'*.

The following results states that an oracle solving ac-smodLIP<sub>K</sub><sup>B,s</sup> also solves
wc-smodLIP<sub>K</sub><sup>B</sup>, up to a call to Algorithm A.1.

**Proposition A.7 (ac-smodLIP<sub>K</sub><sup>B,s</sup> ≥ wc-smodLIP<sub>K</sub><sup>B</sup> ).** Given an oracle that solves ac-smodLIP<sub>K</sub><sup>B,s</sup> in time τ with probability p > 0, one can solve wc-smodLIP<sub>K</sub><sup>B</sup> in time τ + poly(d, ℓ, log s) and probability p, where

$$
s \ge \sqrt{\frac{d \cdot \log(2d\ell + 4)}{\pi}} \cdot 2^d \cdot \Delta_K^{3/(2d)} \cdot \max_{1 \le j \le \ell} \left( \|\sigma(g_{j,j})^{1/2}\| \cdot \mathcal{N}(I_j)^{1/d} \right).
$$
Proof. Let $G' = (G', (J_i)_i)$ be any pseudo-Gram matrix equivalent to $G$. First, we sample $G'' = (G', (H_i)_i)$ equivalent to $G$ together with $U'' = (u''_{i,j})$ such that $G'' = U''*GU''$ and $u''_{i,j} \in I_i H_j^{-1}$. This is done in time poly($d, \ell, \log s$). Now we can apply our oracle to solve an average-case LIP instance ; we find $U' = (u'_{i,j})$ with inverse $V' = (v'_{i,j})$ such that $G'' = U'*G'U'$ and $u'_{i,j} \in J_i H_j^{-1}$, $v'_{i,j} \in H_i J_j^{-1}$. Let $U = U''U'^{-1} =: (u_{i,j}) \in GL_{\ell}(K)$, then $G' = U'*GU$ and

$$ \forall (i,j) \in \{1, \dots, \ell\}^2, \quad u_{i,j} = \sum_{k=1}^{\ell} \underbrace{u''_{i,k} \cdot v'_{k,j}}_{\in (I_i H_k^{-1}) (H_k J_j^{-1})} \in I_i J_j^{-1}, $$

so $U$ is a solution to the worst-case problem i.e. a congruence matrix between $G$ and $G'$. $\square$

## B Justifications for Assumption 1

In this appendix, we provide theoretical and experimental evidences in favor of Assumption 1.

**Theoretical justification.** First, recall that by Lemma 4.2, the ideal $I$ is generated by the elements of the form $z_1^2 + z_2^2$ for $(z_1, z_2)^T \in M$. Hence, there exists no prime ideal $p$ such that $p$ divides $(z_1^2+z_2^2)I^{-1}$ for all $(z_1, z_2)^T$ in $M$. This does not mean that all integral ideals $a$ are realisable as $(z_1^2 + z_2^2)I^{-1}$, but at least, these ideals should be co-prime when $(z_1, z_2)^T$ ranges over $M$. In terms of support, there is then some hope that some prime ideals can be realisable as $(z_1^2 + z_2^2)I^{-1}$. Note also that we chose $s \ge \eta_{1/2}(M)$ to ensure that the Gaussian distribution does not always fall in a sublattice of $\sigma(M)$ of smaller dimension.

With these precautions taken, we assume that the ideal $qI^{-1}$ behaves like a “random” ideal of $O_K$, with the condition that its class in the class-group should be the same as the one of $I^{-1}$. We now argue that if one picks a random integral ideal $a$ in a fixed class of the class group, then the probability that $a$ is prime is roughly $(\rho_K \cdot \log N(a))^{-1}$. While founded on non-trivial results in number theory, the next arguments are somewhat standard.

Let $C$ be a fixed class of the class group. We will write $i_C(X)$ the number of integral ideals in the class $C$ of norm bounded by $X$ and $p_C(X)$ the number of prime ideals in the class $C$ of norm bounded by $X$. The next results give asymptotic bounds (when $K$ is fixed and $X$ tends to infinity) on the quantities $i_C(X)$ and $p_C(X)$, from which we will derive the (asymptotic) density of prime ideals in a given class $C$.

First, it is known that $p_C(X) \sim X/(h_K \cdot \log X)$ when $X$ tends to infinity (and $K$ is fixed). A reference for this claim can be found in [29, Se. 7.2, Cor. 4], when instantiated with $I = O_K^{.22}$.

<footnote>$^{22}$ In this case, the quantities $H_I^*(K)$ and $h_I^*(K)$ from the statement are simply the class group $Cl(K)$ and the class number $h_K$ of $K$ (the notations $H_I^*(K)$ and $h_I^*(K)$ are defined in Section 3.2 of [29]).</footnote>
For the quantity $i_C(X)$, Theorems 39 and 40 from [26] and the class number formula provide the estimates $i_C(X) \sim \rho_K \cdot X/h_K$. Combining these two estimates, we obtain that the probability that a uniform ideal of norm $\le X$ in a given class $C$ is a prime ideal is asymptotically equivalent to $(\rho_K \cdot \log X)^{-1}$.

All these computations give us an expected behaviour, when the bound $X$ tends to infinity and $K$ is fixed. In our case, we would like to consider ideals of potentially small algebraic norms, and we are not even sure that our distribution produces ideals uniformly distributed in a given class below a bound $X$. Hence, our main assumption is to suppose that even though we do not satisfy all the requirements needed, the previous asymptotic bound still holds somehow in our case (up to a potential polynomial loss). In other words, we assume that the probability that $qI^{-1}$ is prime is roughly $(\rho_K \cdot \log \mathcal{N}(qI^{-1}) \cdot \text{poly}(d))^{-1}$.

Finally, we upper bound the quantity $\mathcal{N}(q)$ by $\|\sigma(q)\|^d \le (s\sqrt{d})^d$, which holds except with negligible probability using Gaussian tails bounds (see Lemma 2.5). Note also that the quantity appearing in the assumption is $\log(s/\mathcal{N}(I)^{1/d})$ and not $\log(s^d/\mathcal{N}(I))$, because we moved the factor $d$ in the polynomial $P(d)$.

*Experimental justification.* We verified experimentally our assumption on number fields $K$ that are the maximal real subfields of cyclotomic fields. The code for the experiments is available in our public repository (in the folder `experiments_for_assumption`). With these experiments, we tried to assess two claims:

- that the ideal $qI^{-1}$ is prime with probability roughly $(\rho_K \cdot \log \mathcal{N}(qI^{-1}))^{-1}$,

- and that the quantity $(\rho_K \cdot \log(s/\mathcal{N}(I)^{1/d}) \cdot \text{Pr}(q \cdot I^{-1} \text{ is prime}))^{-1}$ grows at most polynomially with $d$ (it is supposed to be upper bounded by the polynomial $P(d)$ if our assumption holds).

In order to test these two claims, we performed multiple tests with different number fields, different modules for a given number field, and many random $q$ for each module. More formally, we tested all $K$ that are the maximal real subfield of a cyclotomic field of conductor $\le 160$ (those have degree $d$ at most 78). We then tested some more maximal real subfields of cyclotomic fields (but not all of them), up to degrees $d = 125$.

In each of these number fields $K$, if the degree $d$ of $K$ was $\le 45$, we generated 10 random free modules $M$ of rank 2 (even 20 modules if $d \le 21$). We did not impose any restriction on the Gram ideal $\mathcal{G}(M)$ of the module. Most of them were equal to $\mathcal{O}_K$, but some of them were non-trivial. When $d$ was larger than 45, we did not consider 10 random modules, but only 1 module per field, namely the module $\mathcal{O}_K^2$. We also added this specific module to the 10 and 20 modules already generated for the small dimensional number fields.

For each number field and each module $M$ generated, we then sampled between 1000 and 5000 Gaussian vectors $(z_1, z_2)^T \in M$ and computed the empirical probability $P_{\text{empirical}}$ that $qI^{-1}$ be a prime ideal ($K$ and $M$ are fixed here, and the empirical probability is computed only over the random choice of $q$). We also computed the expected probability $P_{\text{expected}}$ to find a prime ideal. To do so, for each random $q$ generated, we computed $1/(\rho_K \log \mathcal{N}(q/I))$, and we took the average of this quantity over all $q$'s (for a fixed module).
In Figure 1, we plotted the ratios $P_{\text{empirical}}/P_{\text{expected}}$ for all number fields, and all modules, as a function of the degree $d$ of $K$. The red crosses represent the modules $O_K^2$ and the blue dots are the random modules (only for small degrees). One can check that this ratio is always between [0.4, 2.2], hence, the quantity $P_{\text{expected}}$ seems to approximate relatively well the empirical probability $P_{\text{empirical}}$. One can also check on the small dimensional fields that the module $O_K^2$ does not seem to have a behaviour significantly different from the random modules. The slightly larger deviation observed in the blue dots for number fields of degree between 21 and 45 might be explained by the fact that those empirical probabilities were obtained using only 1000 random $q$, whereas the blue dots for $d \le 21$ and the red crosses use at least 2000 random $q$'s.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Ratios $P_{\text{empirical}}/P_{\text{expected}}$ as a function of $d$ for various fields $K$ and various modules $M$. The red crosses correspond to $M = O_K^2$ and the blue dots correspond to a random free module $M$</figcaption></figure>

In Figure 2, we plotted the quantity $Q := (P_{\text{empirical}} \cdot \rho_K \cdot \log(\tilde{s}))^{-1}$ as a function of $d$. Here, $\tilde{s} = \max(e, s/\mathcal{N}(I)^{1/d})$, where the max is here to ensure that $\log \tilde{s} \ge 1$ is not too small (this can happen in small dimensional examples and caused some weird results, which disappear when the dimension increases). Recall that this quantity is supposed to be upper bounded by $P(d)$ for some polynomial $P$ (if our assumption holds). The result on the figure seem consistent
with this assumption (the polynomial $P(d)$ even seems linear in $d$). Once again, there is one blue point per random module and one red cross per $O_K^2$ module. Overall, our experimental results seem consistent with Assumption 1.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** The quantity $Q$ as a function of $d$ for various fields $K$ and various modules $M$. The red crosses correspond to $M = O_K^2$ and the blue dots correspond to a random free module $M$</figcaption></figure>

## C Details about the implementation

This section contains more technical details about our implementation of the attack, and some explanation for the choices we made there. Our code is available in our public repository (in the folder attack), and a high-level description of the implementation (with timings) is provided in Section 5.

**On the Gentry-Szydlo's algorithm.** The Gentry-Szydlo algorithm (in its initial form, over cyclotomic fields [20]) is a relatively complicated to implement algorithm. The main idea of the algorithm is to notice that if $P$ is a prime number that splits completely in the cyclotomic field $L$, then $O_L/(PO_L) \cong (\mathbb{F}_P)^{\deg(L)}$, and so, by Fermat's theorem, any $x \in O_L$ coprime to $P$ satisfies
$x^{P-1} = 1 \bmod P$. Assume now that $J$ is a principal ideal generated by some element $g \in O_L$, then $J^{P-1}$ is still principal, generated by $g^{P-1}$. If one is able to recover a small multiple $a \cdot g^{P-1}$ of this generator, then reducing it modulo $P$ reveals $a \bmod P$. Now, if $P$ is large enough compared to $a$, this allows to recover $a$ exactly, and then recover $g^{P-1}$ from $a \cdot g^{P-1}$. Finally, computing a root of $g^{P-1}$ in $L$ enables to recover $g$ (up to roots of unity). This high-level description of the algorithm does not actually work, since it would require $P$ to be exponentially large, causing the size of the elements to explode. A nice explanation of how to handle this issue can be found in [19, Section 7.3].

The Gentry-Szydlo algorithm is not natively implemented in Sagemath. We found a previous implementation of the algorithm in Pari/GP, done by de Vilmarest and Kirchner<sup>23</sup> and used in the article [4]. Unfortunately, we failed to use this implementation of the Gentry-Szydlo algorithm for our attack. More precisely, we managed to use the implementation of de Vilmarest and Kirchner on some instances, but the algorithm failed on some other instances without us understanding why (we guess that this was due to a bad choice of parameters at the beginning of the algorithm).

We decided to re-implement the Gentry-Szydlo algorithm in Sagemath for our attack. We did not target efficiency, but mainly stability of the algorithm. We followed the description of the algorithm provided in [19, Section 7.3], and used built-in Sage functions for manipulating ideals and number fields. The main bottleneck of the algorithm in large dimension are the (multiple) calls to an LLL algorithm in ideal lattices. We run the LLL algorithm on the Gram matrix of the ideals, and do so by calling Sage's function LLL_Gram, which itself calls the qflllgram function of Pari/GP. This function has recently been improved in Pari/GP, using the "Flatter" framework [32], but this optimization is not yet available when Pari/GP is called through Sage. In order to improve the running time of the Gentry-Szydlo algorithm, we enabled the user to specify a path to a recent installation of Pari/GP (with a fast qflllgram implementation), and use it instead of Sage's default LLL_Gram function. With this optimization, the cost of LLL is still dominating the running time of the algorithm, but it can be decreased by a factor 2 is large dimensions ($\gtrsim 200$).

**On the NormEquation algorithm.** We now explain NormEquation for our relevant fields, that is, $L = \mathbb{Q}(\zeta_m)$ is a cyclotomic field with $m = 4k$, and $K$ is its maximal totally real subfield. If $\tau$ is the non-trivial automorphism of $L|K$, we write $\tau(a) = a^*$. Note that if $a$ is a solution of $q = a^*a$, then $\rho \cdot a$ is also a solution for all roots of unity $\rho \in L$. On input an arbitrary principal ideal $qO_K$, we factor it as a product of prime ideals in $O_K$, which are then separated in inerts, ramified and splits parts in $O_L$. The separation can be done e.g. by checking how the polynomial $X^2 + 1$ factors in finite fields. For simplicity, we

<footnote n="23"><sup>23</sup> available at https://alexgelin.fr/doc/GenRec.tar.gz.</footnote>
will consider unramified primes in this section, so that

$$q\mathcal{O}_K = \prod_{\text{inert}} \mathfrak{p}^e \cdot \prod_{\text{split}} q^f.$$

If $q = a^*a$, we observe that primes above the inerts dividing $q\mathcal{O}_K$ must have an even valuation since they must appear both as divisors of $a\mathcal{O}_L$ and $a^*\mathcal{O}_L$. We can early-abort if this is not the case since there would be no solution. Now let us write

$$q\mathcal{O}_L = I^2 \cdot \prod_{\mathfrak{Q} \cap \mathcal{O}_K \text{ split}} (\mathfrak{Q}\mathfrak{Q}^*)^f,$$

where $I = \prod_{\mathfrak{Q} \cap \mathcal{O}_K \text{ inert}} \mathfrak{P}^e$ is the product of all primes above the inerts of $p\mathcal{O}_K$. We then need to find principal ideals among all possible products $I \cdot \prod_{\mathfrak{Q} \cap \mathcal{O}_K \text{ split}} \mathfrak{Q}^\alpha \cdot (\mathfrak{Q}^*)^{f-\alpha}$ as their generators are candidates for solutions of the equation $q = a^*a$. Having computed all the products, we have in fact $\mathbb{Z}$-bases for all the ideals to be tested, as well as the relative norm $q$ of its potential generators: this is where using Gentry-Szydlo algorithm makes this step polynomial time. As mentioned above, we provide an implementation of this algorithm on our repository that works well for small dimensions ($\phi(m) \le 100$) and reasonably well up to $m \le 300$.

**On the TwoSquares algorithm.** We now assume that NormEquation finds all solutions for the equation $q = a^*a$. The TwoSquares algorithm takes in input the set of all solutions to a relative norm equation $q = a^*a$ from $L = K(i)$ to $K$, and find those corresponding to $a = u + iv$ with $u, v \in \mathcal{O}_K$. The next lemma characterizes these particular solutions. Recall that $\text{Tr}_{L|K}(x) = x + x^*$ is the relative trace map, and that it sends $\mathcal{O}_L$ into $\mathcal{O}_K$.

**Lemma C.1.** We have $\mathcal{O}_K + i\mathcal{O}_K = \{x \in \mathcal{O}_L : \text{Tr}_{L|K}(x) \in 2\mathcal{O}_K\}$.

*Proof.* On the one hand, if $x = a+ib$ with $a, b \in K$, then $\text{Tr}_{L|K}(x) = 2a$. On the other hand, we have the identity $2x = \text{Tr}_{L|K}(x) + i\text{Tr}_{L|K}(-ix)$. Then if $x \in \mathcal{O}_L$ is such that $\text{Tr}_{L|K}(x) \in 2\mathcal{O}_K$, then $\text{Tr}_{L|K}(-ix) \in 2\mathcal{O}_L \cap i\mathcal{O}_K$, which gives the result. $\square$

Then, let $b$ be any solution of the relative norm equation. Using the above lemma, when the relative trace is in $2\mathcal{O}_K$ we directly compute $u = (1/2) \cdot \text{Tr}_{L|K}(b), v = (1/2) \cdot \text{Tr}_{L|K}(-ib) \in \mathcal{O}_K$ such that $(u+iv)(u-iv) = u^2 + v^2 = q$. We implement this with a simple parity check of the coefficients for a given basis of $\mathcal{O}_K$, and this allows to filter out sums-of-two-squares. In e.g. sagemath where the ring $\mathcal{O}_K$ can be instantiated, this can also be done in a black-box by testing membership.

**On the CongruenceSolver algorithm.** To test our complete attack, we provide an algorithm to generate bases of $\mathcal{O}_K^2$ and their associated quadratic form $Q$ of determinant 1. The idea behind the algorithm is a basis completion algorithm: take any vector $u \in \mathcal{O}_K^2$, find a $v \in \mathcal{O}_K^2$ such that $\det(u, v) = 1$. One can also
check [10, Alg. 1.3.16] for the basis completion step, which we have borrowed in our implementation. We also do not aim for efficiency, and thus do not try to exploit any tower structure of the totally real subfield. However, if we stop at finding a v as described in the given reference, it will likely have large coefficients and so we also do a step of algebraic “size-reduction” using a basis of $O_K$ to express our elements. For the NTRU enthousiasts out there, this is a similar procedure as in Hawk [14] and other NTRU key-generation algorithms, except that the ambient field is different so the operations are less efficient. In particular, there are less standard choices for the basis that is used to represent $O_K$. Let $K = \mathbb{Q}(\theta)$, so that $1, \theta, \dots, \theta^{d-1}$ is a $\mathbb{Z}$-basis of $O_K$. Experimentally, we observed that although easy to use, this tended to not be the best basis from a geometric point of view; in other words, the coefficients tended to be much larger with this basis than the other one we describe below.

**Lemma C.2.** Let $\tau_0 = 1$, $\tau_1 = \theta$ and for $2 \le i \le d-1$, $\tau_i = \zeta_m^i + \zeta_m^{-i}$. Then $(\tau_i)_{0 \le i \le d-1}$ is a $\mathbb{Z}$-basis of $O_K$.

*Proof.* This is observed by expanding each $\theta^i$, and noting that $\tau_i \in K$. Let us write $\zeta = \zeta_m$ to lighten the notation. For an even exponent, we readily compute

$$ \begin{aligned} \theta^{2i} &= \zeta^{2i} + \zeta^{-2i} + \sum_{j=1}^{2i-1} \binom{2i}{j} \zeta^{2i-j} \zeta^{-j} \\ &= \tau_{2i} + \sum_{j=1}^{i-1} \binom{2i}{j} (\zeta^{2(i-j)} + \zeta^{-2(i-j)}) + \binom{2i}{i} \\ &= \tau_{2i} + \sum_{j=1}^{i} \binom{2i}{j} \tau_{2(i-j)}, \end{aligned} $$

and a similar expression is derived analogously for the odd case. This shows that the matrix to express the $\theta^i$'s from the $\tau_i$'s is triangular with 1 on the diagonal, and has integer entries. In other words, it is unimodular and thus $(\tau_i)_i$ is a basis of $O_K$. $\square$

To see that the geometry is better, one can look at the matrix $G = [\mathrm{Tr}_{K|\mathbb{Q}}(\tau_i \tau_j)]_{i,j}$, and notice that it is indeed quite sparser and has much smaller entries as when the degree of $K$ grows. This comes from the vanishing of many sums of roots of unity. For the best case where $m$ is a power of two, we can even show that $G$ is diagonal with small entries. For completeness we gather this in the lemma below.

**Lemma C.3.** If $m = 2^\ell$, we have $G = \mathrm{Diag}(d, 2d, \dots, 2d) \in \mathbb{Z}^{d \times d}$.

As a direct application, we find that $2\Delta_K = \sqrt{\Delta_L}$ for these conductors.

*Proof.* The upper left coefficient is seen as $\mathrm{Tr}_{K|\mathbb{Q}}(1) = d$. Let $\epsilon_{ij} = \tau_i \tau_j$ for $0 \le i, j \le d-1$. We have that $\epsilon_{ij} = \zeta^{i+j} + \zeta^{-(i+j)} + \zeta^{i-j} + \zeta^{-(i-j)}$. The chain rule for relative traces is $\mathrm{Tr}_{L|\mathbb{Q}} = \mathrm{Tr}_{K|\mathbb{Q}} \circ \mathrm{Tr}_{L|K}$, from which we see $\mathrm{Tr}_{K|\mathbb{Q}}(\epsilon_{ij}) =$
$\mathrm{Tr}_{L|\mathbb{Q}}(\zeta^{i+j}) + \mathrm{Tr}_{L|\mathbb{Q}}(\zeta^{i-j})$. By symmetry of $G$ we can restrict to $j \le i$. When $i = j$ we have $\zeta^{i-j} = 1$ and then $\mathrm{Tr}_{L|\mathbb{Q}}(1) = 2d$. Recall that the Galois group acts on $\zeta$ by exponentiation to an integer in $(\mathbb{Z}/m\mathbb{Z})^\times$, which in this case means exponentiation to an odd power. For the other term, for all $k$ not multiple of $d$, we thus have

$$ \mathrm{Tr}_{L|\mathbb{Q}}(\zeta^k) = \sum_{i=0}^{d-1} \zeta^{k(2i+1)} = \zeta^k \sum_{i=0}^{d-1} \zeta^{2i} = \zeta^k \cdot \frac{\zeta^m - 1}{\zeta - 1} = 0, $$

first by definition of the absolute trace, then using the geometric sum and the fact that $\zeta$ is a primitive $m$-th root of 1. This gives the result. $\square$

For these conductors, the Gram matrix of the power basis is much worse. To compare, the bottom right coefficient in the Gram matrix of the power basis, for example, can be calculated from the lemma and properties of the trace to be $\binom{2(d-1)}{d-1} \cdot d$. The general case is more tedious as one needs to take into account the possible values of the trace at exponents that are not coprime to the conductor.

**On the FindPrimeNorm algorithm.** Moving onto the attack, we need to find sums-of-two squares that are also prime in $K$ from the knowledge of $Q$. We implemented an implicit Gaussian sampler to do so, outputting vectors $z = (u, v) \in \mathcal{O}_K^2$ while keeping the coefficients of the found $q = x^2 + y^2 = z^t Q z$ as small as possible. Indeed, in previous versions our more naive approach resulted in substantially larger $q$'s, which incurred a non-negligible cost on computations. To check for primality of the ideal $q\mathcal{O}_K$, our first approach was a to rely on a (probabilistic) prime-power testing implemented in sage, giving us $(p, e)$ such that $N(q) = p^e$. Then we would factor the defining polynomial of $K$ over $\mathbb{F}_p$ to find the possible two-element representation of $q\mathcal{O}_K$ among the factors. Experimentally, it was almost always the case that $e = 1$, or equivalently, that $p$ totally splits in $K$. Therefore in our current version we directly aim at finding a element $q$ of prime norm, which also makes the next step cheaper. This is of course a trade-off on the amount of repetitions, but experimentally, the benefit on the following computations was significant and we therefore kept this alternative strategy in our published code.

**Finalizing the attack.** Once a prime $q$ is found in $K$, we need to find its factors in $L$, and we want to avoid to re-factor (or deduce the primality of) the absolute norm by using black-box functions. As $L|K$ is quadratic we know that either $q\mathcal{O}_K$ splits totally, is inert, or ramifies. By construction, we have $q = x^2 + y^2 = (x + iy)(x - iy)$ so in fact, $q$ must always split.

This is similar to the situation over $\mathbb{Z}$, where primes that are sums of two squares must satisfy $p \equiv 1 \pmod{4}$, which equivalently means that they split in the ring $\mathbb{Z}[i]$. Moreover, the two factors must be conjugate by the involution, so if we know the generator $g$ for one, we have the other. This means that we only need to do one call to the Gentry-Szydlo algorithm by prime that we find at this step,
making it a total of two to get to the last phase. We still need to feed input to Gentry-Szydlo. We can use the polynomial $X^2 - \theta X + 1$ defining the extension $L|K$; as we know it will have two factors modulo $p$, we just need to compute a square root of $\Delta_{L|K} = \theta^2 - 4$ modulo $p$ to then deduce the linear factors. Note that $p$ could be large if we did not control its size previously.

In the end we obtain two linearly independent vectors $z_1 = (u_1, v_1)$ and $z_2 = (u_2, v_2)$ which are also sums of two squares in $O_K^2$, and for which we have all the possible sums. Following Step 17 to 20 in our algorithm, we then build all possible matrices corresponding to pairs of solutions, then check if they indeed give a congruence matrix (this amounts to check if the entries have a denominator). As we know already the determinant of the potential congruence matrices, we can filter out the matrices that would not fit and only do linear algebra with the ones we need. Additionally, we know that the group of $O_K$-isometries acts on the set of solutions. This group has 4 elements (identity, negation, permutation of the two basis vectors and the composition of these two), which is also what we expect as a number of final solutions. Once one is found, we could obtain the other by using this action. In our published code, we did not implement this idea, and merely enumerated all (filtered) matrices until exhaustion. Overall, we could successfully recover the congruence class of Hawk-type Gram matrices<sup>24</sup> for different conductors in about 1100s for conductors as large as 256 (or a bit larger, when not a power of 2). Up to conductors about 50, the algorithm performs well and the attack takes mere seconds. For $m$ from 50 to about 200, the attack is slower, with the two Gentry-Szydlo steps clearly dominating the running time. Notably, the attack never fails in the sense that we always find back the basis $B$ such that $B^T B = Q$.

<footnote n="24"><sup>24</sup> Hermitian forms corresponding to a (secret) basis of the free module $O_K^2$.</footnote>