# Antrag: Annular Ntru Trapdoor Generation

Thomas Espitau, Quyen Thi Thu Nguyen, Chao Sun, Mehdi Tibouchi,
Alexandre Wallet

► To cite this version:

Thomas Espitau, Quyen Thi Thu Nguyen, Chao Sun, Mehdi Tibouchi, Alexandre Wallet. Antrag: Annular Ntru Trapdoor Generation. ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2023, Guangzhou (Canton), China. pp.1-56. hal-04258578

HAL Id: hal-04258578

https://inria.hal.science/hal-04258578v1

Submitted on 25 Oct 2023

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
ANTRAG: Annular NTRU Trapdoor Generation
Making MITAKA As Secure As FALCON

Thomas Espitau[0000-0002-7655-9594]¹, Thi Thu Quyen Nguyen², Chao Sun[0000-0002-1461-1473]³, Mehdi Tibouchi[0000-0002-2736-2963]⁴, and Alexandre Wallet[0000-0003-0492-2435]⁵

¹ PQShield SAS, France

t.espitau@gmail.com

² IDEMIA, France & Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, France

thi-thu-quyen.nguyen@inria.fr

³ Osaka University, Japan

c-sun@ist.osaka-u.ac.jp

⁴ NTT Social Informatics Laboratories, Japan

mehdi.tibouchi@ntt.com

⁵ IRISA, Univ Rennes, Inria, Irisa, CNRS, France

alexandreima wallet@inria.fr

**Abstract.** In this paper, we introduce a novel trapdoor generation technique for Prest's hybrid sampler over NTRU lattices. Prest's sampler is used in particular in the recently proposed MITAKA signature scheme (Eurocrypt 2022), a variant of the FALCON signature scheme, one of the candidates selected by NIST for standardization. MITAKA was introduced to address FALCON's main drawback, namely the fact that the lattice Gaussian sampler used in its signature generation is highly complex, difficult to implement correctly, to parallelize or protect against side-channels, and to instantiate over rings of dimension not a power of two to reach intermediate security levels. Prest's sampler is considerably simpler and solves these various issues, but when applying the same trapdoor generation approach as FALCON, the resulting signatures have far lower security in equal dimension. The MITAKA paper showed how certain randomness-recycling techniques could be used to mitigate this security loss, but the resulting scheme is still substantially less secure by FALCON (by around 20 to 50 bits of CoreSVP security depending on the parameters), and has much slower key generation.

Our new trapdoor generation techniques solves all of those issues satisfactorily: it gives rise to a much simpler and faster key generation algorithm than MITAKA's (achieving similar speeds to FALCON), and is able to comfortably generate trapdoors reaching the same NIST security levels as FALCON as well. It can also be easily adapted to rings of intermediate dimensions, in order to support the same versatility as MITAKA in terms of parameter selection. All in all, this new technique combines all the advantages of both FALCON and MITAKA (and more) with none of the drawbacks.
# 1 Introduction

## 1.1 Hash-and-sign lattice-based signatures

From GGH to FALCON. FALCON [34] is one of the three signature schemes already selected for standardization in the NIST post-quantum competition. It represents the state of the art in hash-and-sign lattice-based signatures, one of the two main paradigms for constructing lattice-based signatures alongside Lyubashevsky's Fiat-Shamir with aborts [24, 25] (which is also represented among the final selected candidates of the NIST competition in the form of DILITHIUM [26]).

This makes FALCON the culmination of a long line of research in constructing signature schemes from lattice trapdoors. The basic idea, which dates back to the late 1990s with the GGH [22] and NTRUSign [23] signature schemes, is to use as the signing key a “good” basis (the trapdoor) of a certain lattice allowing to approximate the closest vector problem within a good factor, and as the verification key a “bad” basis which allows to test membership but not decode large errors. The signature algorithm then hashes a given message to a vector in the ambient space of the lattice, and uses the trapdoor to find a relatively close lattice point to that vector. The difference is the signature, which is verified by checking that it is small and that its difference with the hashed vector does indeed belong to the lattice.

The GGH scheme, as well as several successive variants of NTRUSign, were eventually broken by statistical attacks [21, 29, 10]: it turned out that signatures would leak partial information about the secret trapdoor, that could then be progressively recovered by an attacker. This problem was finally solved in 2008, when Gentry, Peikert and Vaikuntanathan (GPV) [20] showed how to use Gaussian sampling in the lattice in order to guarantee that signatures would reveal no information about the trapdoor.

GPV signatures over NTRU lattices. In order to instantiate the GPV framework efficiently in practice, one then needs lattices with compact representation and efficiently computable trapdoors, which has so far been achieved using module lattices over rings—in fact, mostly rank-2 modules over cyclotomic rings, exactly corresponding to NTRU lattices (although higher rank modules, namely ModNTRU lattices, have been shown to be usable as well in certain ranges of parameters [7]). This was first carried out by Ducas, Lyubashevsky and Prest (DLP) [9], who analyzed trapdoor generation for power-of-two cyclotomic ring NTRU lattices and constructed corresponding GPV-style signatures. DLP signatures are compact, but the signing algorithm is rather slow: quadratic in the dimension 2d of the lattice. This is because the lattice Gaussian sampling algorithm that forms the core of its signing procedure (namely Klein-GPV sampling, in essence a randomized version of Babai's nearest plane algorithm for approximate CVP) cannot directly take advantage of the algebraic structure of the
lattice, and thus operates on the full (2d) × (2d) matrix of the lattice basis as
well as its Gram–Schmidt orthogonalization.

FALCON is a direct descendant of the DLP scheme, that replaces the generic,
quadratic complexity Klein–GPV sampler in signature generation by an efficient,
quasilinear complexity lattice Gaussian sampler that does take advantage of the
ring structure. Specifically, that new algorithm is constructed by randomizing
the Fast Fourier Orthogonalization (FFO) algorithm of Ducas and Prest [12],
and operates in a tree-like fashion traversing the subfields of the power-of-two
cyclotomic field over which the NTRU lattice is defined. This makes FALCON
particularly attractive in various ways: it offers particularly compact signatures
and keys (providing the best bandwidth requirements of all signature schemes
in the NIST competition), achieves high security levels in relatively small lattice
dimensions, and has both fast signing and very efficient verification speeds.

However, the FFO-based Gaussian sampler is also the source of FALCON’s
main drawbacks: it is a really contrived algorithm that is difficult to implement
correctly, parallelize or protect against side-channels. It is also really difficult
to adapt to other rings than power-of-two cyclotomics, which drastically limits
FALCON’s versatility in terms of parameter selection: in fact, recent versions of
FALCON in the NIST competition only target either the lowest NIST security
level (using cyclotomic fields of dimension 512) or the highest (using fields of
dimension 1024) and nothing in-between.<fnref n="6" />

## 1.2 The hybrid sampler and MITAKA

*The Peikert and hybrid samplers.* After the publication of the DLP paper, Ducas and Prest explored and analyzed other approaches for lattice Gaussian sampling over NTRU lattices, as discussed in depth in Prest’s Ph.D. thesis [32], with a view towards overcoming the quadratic complexity of the naive Klein–GPV sampler. While the introduction of the FFO sampler was the final step of that exploration, they also considered two other major approaches along the way, which also achieve quasilinear complexity (see also [11]).

The first approach was not actually novel: it was the ring version of Peikert’s
lattice Gaussian sampler [30], which is the randomization of the Babai rounding
algorithm for approximate CVP, just like Klein–GPV is the randomization of
Babai’s nearest plane. For NTRU lattices, this algorithm consists of independent
one-dimensional Gaussian samplings for each vector component (hence a linear
number in total), as well as 2 × 2 matrix-vector products over the ring, amount-
ing to a constant number of ring multiplications, that are all quasilinear when
using FFT-based fast arithmetic. Thus, Peikert’s sampler for NTRU lattices is
quasilinear as required. However, Ducas and Prest analyzed the *quality* of NTRU
trapdoors (generated in the same way as DLP) with respect to Peikert’s sam-
pler, and found that it was much worse than for Klein–GPV, both concretely

<footnote n="6">⁶ The earliest version of the FALCON specification [33] also included an intermediate parameter set of dimension 768, but the corresponding algorithms were so complicated that it was eventually dropped.</footnote>
and asymptotically. In other words, for the same choice of parameters, it would
reduce security considerably to instantiate DLP with Peikert's sampler instead
of Klein-GPV (and to recover the same security, a large increase in the dimen-
sion of the underlying ring, and hence the size of keys and signatures, would be
required).

As a kind of middle ground between Peikert (fast but less secure) and Klein-GPV (secure but much slower), they introduced as a second approach the *hybrid sampler*, which uses the same structure as Klein-GPV (a randomized nearest plane algorithm) but over the larger ring instead of over $\mathbb{Z}$. In the rank-2 case of NTRU, this reduces to just two “nearest plane” iterations consisting of Gaussian sampling over the ring, which is itself carried out using Peikert’s sampler with respect to a short basis of the ring. This algorithm remains quasilinear, but achieves a significantly better quality than Peikert for DLP-style NTRU trapdoors, although not as good as Klein-GPV. Concretely, for those NTRU trapdoors over the cyclotomic ring of dimension 512 (resp. 1024), signatures instantiated with the hybrid sampler achieve a little over 80 bits (resp. 200 bits) of classical CoreSVP security, compared to over 120 bits (resp. 280 bits) for Klein-GPV.

*Pros and cons of hybrid vs. FFO.* This substantial security loss is presumably the main reason that led to the hybrid sampler being abandoned in favor of the FFO sampler (which achieves the same quality as Klein-GPV but with quasilinear complexity) in the FALCON scheme. Indeed, security aside, the hybrid sampler has a number of advantages compared to the FFO sampler of FALCON: it is considerably simpler to implement, somewhat more efficient in equal dimension, easily parallelizable and less difficult to protect against side-channels; it also has an online-offline structure that can be convenient for certain applications, and it is easier to instantiate over non power-of-two cyclotomics, making it easier to reach intermediate security levels.

For these reasons, the use of the hybrid sampler to instantiate signatures
over NTRU lattices was recently revisited by Espitau et al. as part of their
proposed scheme MITAKA [15]. One of the key contributions of that paper is
an optimization of trapdoor generation for the hybrid sampler that mitigates
the security loss by making it possible to construct better quality trapdoor in
reasonable time. Combined with the various advantages of the hybrid sampler,
this allows the authors of MITAKA to achieve a trade-off between simplicity
and security that they argue can be more attractive than FALCON. However,
despite their efforts, MITAKA remains substantially less secure than FALCON in
equal dimension (it loses over 20 bits of classical CoreSVP security over rings of
dimension 512, and over 50 bits over rings of dimension 1024), with a much slower
and more contrived key generation algorithm as well. In particular, MITAKA falls
short of NIST security level I in dimension 512 and of level V in dimension 1024,
making it less than ideal from the standpoint of parameter selection.
## 1.3 Contributions and technical overview of this paper

In this paper, we introduce a novel trapdoor generation technique for Prest's hybrid sampler that solves the issues faced by MITAKA in a natural and elegant fashion. Our technique gives rise to a much simpler and faster key generation algorithm than MITAKA's (achieving similar speeds to FALCON), and it is able to comfortably generate trapdoors reaching the same NIST security levels as FALCON. It can also be easily adapted to rings of intermediate dimensions, in order to support the same versatility as MITAKA in terms of parameter selection (just with better security). All in all, this new technique achieves in some sense the best of both worlds between FALCON and MITAKA.

NTRU trapdoors and their quality. In order to give an overview of the technical ideas involved, we need to recall a few facts about NTRU trapdoors and their quality with respect to the Klein-GPV and hybrid samplers. For simplicity, we concentrate on the special case of power-of-two cyclotomic rings $\mathcal{R} = \mathbb{Z}[x]/(x^d+1)$. Over such a ring, an NTRU lattice is simply a full-rank submodule lattice of $\mathcal{R}^2$ generated by the columns of a matrix of the form:

$$ \mathbf{B}_h = \begin{bmatrix} 1 & 0 \\ h & q \end{bmatrix} $$

for some rational prime number $q$ and some ring element $h$ coprime to $q$. Note that this can also be described as a lattice of pairs $(u, v) \in \mathcal{R}^2$ such that $uh - v = 0 \mod q$.

A trapdoor for this lattice is a relatively short basis:

$$ \mathbf{B}_{f,g} = \begin{bmatrix} f & F \\ g & G \end{bmatrix} $$

where the basis vectors $(f, g)$ and $(F, G)$ are not much larger than the normalized volume $\sqrt{\det \mathbf{B}_h} = \sqrt{q}$ of the lattice. Since those vectors belong to the lattice, we have in particular that $g/f = G/F = h \mod q$. Moreover, since the determinants are equal up to a unit of $\mathcal{R}$, we can impose without loss of generality that $fG - gF = q$.

Using the trapdoor $\mathbf{B}_{f,g}$, lattice Gaussian samplers are able to output lattice vectors following a Gaussian distribution on the lattice of standard deviation<fnref n="7" /> a small multiple $\alpha\sqrt{q}$ of the normalized volume $\sqrt{q}$. The factor $\alpha$ is the quality, and depends both on the trapdoor and on the sampler itself. The lower the quality, the better the trapdoor, and the higher the security level of the resulting signature scheme. For the Klein-GPV sampler, one can show that the quality $\alpha$ is $(1/\sqrt{q}$ times) the maximum norm of a vector in the Gram-Schmidt orthogonalization of the basis $\mathbf{B}_{f,g}$ regarded as a $(2d) \times (2d)$ matrix over $\mathbb{Z}$, whereas for the hybrid sampler, it is similar but with the Gram-Schmidt orthogonalization over $\mathcal{R}$ itself.

<footnote n="7">⁷ The actual standard deviation also includes an additional factor (the smoothing parameter of the ring) which we omit in this overview for simplicity's sake.</footnote>
Those quantities admit a simple expression in terms of the embeddings of the ring elements $f$ and $g$. Recall that the embeddings are the $d$ ring homomorphisms $\varphi_i: \mathcal{R} \to \mathbb{C}$; when elements of $\mathcal{R}$ are seen as polynomials, these embeddings are simply the evaluation morphisms $\varphi_i(u) = u(\zeta_i)$ where the $\zeta_i$'s are the $d$ primitive $2d$-th roots of unity in $\mathbb{C}$. Then, quality of the basis $\mathbf{B}_{f,g}$ with respect to the Klein-GPV sampler admits the following simple expression:

$$ (\alpha_{\text{GPV}})^2 = \max \left( \frac{1}{d} \sum_{i=1}^{d} \frac{|\varphi_i(f)|^2 + |\varphi_i(g)|^2}{q}, \frac{1}{d} \sum_{i=1}^{d} \frac{q}{|\varphi_i(f)|^2 + |\varphi_i(g)|^2} \right). $$

Similarly, the quality with respect to the hybrid sampler satisfies:

$$ (\alpha_{\text{hybrid}})^2 = \max_{1 \le i \le d} \left( \max \left( \frac{|\varphi_i(f)|^2 + |\varphi_i(g)|^2}{q}, \frac{q}{|\varphi_i(f)|^2 + |\varphi_i(g)|^2} \right) \right). $$

Note that $|\varphi_i(f)|^2 + |\varphi_i(g)|^2 = \varphi_i(ff^* + gg^*)$ where the star denotes the complex conjugation automorphism of $\mathcal{R}$ (defined by $x^* = 1/x = -x^{d-1}$). Thus, put differently, one can say that a trapdoor $\mathbf{B}_{f,g}$ achieves quality $\alpha$ or better for the Klein-GPV sampler if and only if the embeddings of $(ff^* + gg^*)/q$ and of its inverse are at most $\alpha$ on average, whereas quality $\alpha$ or better is obtained for the hybrid sampler if all of the embeddings of these values are at most $\alpha$. This shows in particular that the quality of a given trapdoor is always at least as good for Klein-GPV as it is for the hybrid sampler, which explains why it may be easier in practice to construct good quality trapdoors for the former than for the latter.

### Trapdoor generation in FALCON and MITAKA.
Now, the way trapdoors are generated in FALCON is by sampling $f$ and $g$ according to a discrete Gaussian in $\mathcal{R}$ (which can easily be done by sampling the coefficients as discrete Gaussians over $\mathbb{Z}$) so that their expected length is a bit over $\sqrt{q}$, and verifying using the condition above that the quality with respect to the Klein-GPV (or equivalently FALCON's) sampler is $\alpha_{\text{FALCON}} = 1.17$ or better, and restarting otherwise (the value 1.17 here is chosen roughly as small as possible while keeping the number of repetitions relatively small).

The approach to generate trapdoors in MITAKA is similar using the quality formula for the hybrid sampler, and a target quality of $\alpha_{\text{MITAKA}} = 2.04$ in dimension 512 (and slightly increasing as the dimension becomes larger). Doing so directly would take too many repetitions, however; therefore, the candidates for $f$ and $g$ are actually obtained by linear combinations of smaller Gaussian vectors and by applying Galois automorphisms to generate many candidate vectors $(f,g)$ from a limited number of discrete Gaussian samples. Using that approach, MITAKA achieves the stated quality with a comparable number of discrete Gaussian samples as FALCON; its key generation algorithm is much slower, however, as it has to carry out an exhaustive search on a much larger set of possible candidates.
Our ANTRAG strategy: annular NTRU trapdoor generation. In both FALCON and MITAKA, however, the overall strategy is to generate random-looking candidates (f,g) of plausible length, and repeat until the target quality is reached. In this paper, we suggest a completely different strategy that is in some sense much simpler and more natural: just pick the pair (f,g) uniformly at random in the set of vectors that satisfy the desired quality level. We propose and analyze this approach specifically for the hybrid sampler.<fnref n="8" />

Concretely, yet another way of reformulating the quality condition for the hybrid sampler is to say that the quality is $\alpha$ or better if and only if for all the embeddings $\varphi_i$, one has:

$$q/\alpha^2 \le |\varphi_i(f)|^2 + |\varphi_i(g)|^2 \le \alpha^2 q.$$

In other words, for each embedding, the pair $(|\varphi_i(f)|, |\varphi_i(g)|)$ lies in the annulus $A(\sqrt{q}/\alpha, \alpha\sqrt{q})$ bounded by the circles of radii $\sqrt{q}/\alpha$ and $\alpha\sqrt{q}$—or more precisely, in the arc $A_\alpha^+ = A^+(\sqrt{q}/\alpha, \alpha\sqrt{q})$ of that annulus located in the upper-right quadrant of the plane since those absolute values are non-negative numbers. Our approach is then to sample $f$ and $g$ by their embeddings (i.e., directly in the Fourier domain), and select those embeddings uniformly and independently at random in the desired space. Namely, we sample $d/2$ pairs $(x_i, y_i)$ in the arc of annulus $A_\alpha^+$, and set the $i$-th embedding of $f$ (resp. $g$) to a uniformly random complex number of absolute value $x_i$ (resp. of absolute value $y_i$).

An obvious issue is that the elements $f$ and $g$ constructed in this way will generally not lie in the ring itself: after mapping back to the coefficient domain by Fourier inversion, their coefficients are a priori arbitrary real numbers instead of integers. But this is easy to address: we simply round coefficient-wise to obtain an actual ring element.

A second issue is that this rounding step will not necessarily preserve the quality property we started from: the embeddings of the rounded values do not necessarily remain in the correct domain. In fact, the probability that all embeddings remain in the correct domain after rounding is very low. But there is again a simple workaround: we just carry out our original continuous sampling in the Fourier domain from a slightly smaller annulus than the target one. Instead of picking the pairs $(x_i, y_i)$ in $A_\alpha^+$ as above, we sample them uniformly in some $A^+(r, R)$ with $r$ slightly larger than $\sqrt{q}/\alpha$ and $R$ slightly smaller than $\alpha\sqrt{q}$. This considerably increases the probability that, after rounding, all of the pairs $(|\varphi_i(f)|, |\varphi_i(g)|)$ will in fact end up in $A_\alpha^+$.

And voilà: the description above is essentially a complete trapdoor generation algorithm for the hybrid sampler, that easily reaches the same NIST security

<footnote n="8">⁸ One could consider doing so for Klein-GPV as well, but this appears less relevant for two reasons. First, since 1.17 is already quite close to the theoretical optimal quality of 1, and since the number of repetitions in FALCON’s key generation is fairly modest, there is not much to gain in the Klein-GPV setting. Second, the space of key candidates has a less elegant geometric description, making it more difficult to sample uniformly in it. Extending the approach to MODFALCON [7], however, could be an interesting, albeit challenging, avenue for future research.</footnote>
<table><caption>**Table 1.** Comparison with FALCON and MITAKA for the same dimensions 512 and 1024 and the same modulus $q = 12289$ (excerpt from Table 4).</caption><thead><tr><th rowspan="2">d</th><th colspan="2">FALCON [34]</th><th colspan="2">MITAKA [15]</th><th colspan="2">This paper</th></tr><tr><th>512</th><th>1024</th><th>512</th><th>1024</th><th>512</th><th>1024</th></tr></thead><tbody><tr><td>Quality α</td><td>1.17</td><td>1.17</td><td>2.04</td><td>2.33</td><td>1.15</td><td>1.23</td></tr><tr><td>Classical sec.</td><td>123</td><td>284</td><td>102</td><td>233</td><td>124</td><td>264</td></tr><tr><td>Key size (bytes)</td><td>896</td><td>1792</td><td>896</td><td>1792</td><td>896</td><td>1792</td></tr><tr><td>Sig. size (bytes)</td><td>666</td><td>1280</td><td>713</td><td>1405</td><td>646</td><td>1260</td></tr></tbody></table>

levels as FALCON. Concretely, we target $\alpha = 1.15$ in dimension 512 (even better than FALCON's 1.17) and $\alpha = 1.23$ in dimension 1024 (which comfortably exceeds the 256 bits of classical CoreSVP security corresponding to NIST level V), and with those numbers, we achieve key generation speeds close to FALCON's, while benefiting of all the advantages of MITAKA in terms of simplicity of implementation, efficiency, parallelizability and so on as far as signing in concerned.

*Our contributions.* The main contribution of this paper is to introduce, analyze and implement the ANTRAG trapdoor generation algorithm for the hybrid sampler described above.

The analysis includes a heuristic estimate of the success probability of sampling in the required domain, as well as a discussion of possible attacks on the resulting keys (and even though our security analysis is in a very optimistic model for the attacker, we find no weakness as long as the original sampling domain $A^+(r, R)$ is not chosen to be extremely narrow), and concrete parameters to instantiate a signature scheme.

We also provide a full portable C implementation of the corresponding signature scheme [36] based on those of FALCON and MITAKA. In fact, since the C implementation of MITAKA did not include the key generation algorithm, our implementation is the first complete implementation of the corresponding paradigm. This implementation lets us compare the performance of our key generation with FALCON's, and we find that they are quite close.

Although most of the previous discussion was in the context of power-of-two cyclotomics, our approach also extends with little change to other base rings such as the cyclotomic rings with 3-smooth conductors considered in MITAKA (and we actually provide an analysis in a more general setting still). In particular, it is still possible to map candidate continuous random values generated in the Fourier domain to the ring by coefficient-wise rounding (we could consider other decoding techniques, but this one is sufficient for our purposes; it was in fact already used in the original ternary version of FALCON: see [33, Algorithm 10]). This only changes the distribution of the “rounding error” and hence the success probability slightly, but the analysis carries over easily. It follows that our approach supports the same versatility as MITAKA in terms of parameter selection.
## 2 Preliminaries

For two real numbers $0 \le r \le R$, we denote by $A(r, R)$ the annulus limited by radii $r$ and $R$, i.e. the following subset of the plane $\mathbb{R}^2$: $A(r, R) := \{(x, y) \in \mathbb{R}^2 | r^2 \le x^2 + y^2 \le R^2\}$. We also denote by $A^+(r, R)$ the arc of annulus in the upper-right quadrant of the plane, i.e., $A^+(r, R) := \{(x, y) \in A(r, R) | x, y \ge 0\}$.

When $f$ is a real-valued function over a countable set $S$, we write $f(S) = \sum_{s \in S} f(s)$ assuming that this sum is absolutely convergent. We note $\cdot$ the rounding of a real number to its closest integer. We extend this notation for the coefficient-wise rounding of polynomials. If $\mathbf{x} = (x_1, \dots, x_k)$ is a random variable, we let $\mathbb{E}[\mathbf{x}]$ the expected vector and $\text{Cov}(\mathbf{x})$ its covariance matrix. The variance of a scalar random variable $x$ is denoted by $\text{Var}[x]$.

Write $\mathbf{A}^t$ for the transpose of any matrix $\mathbf{A}$. A lattice $\mathcal{L}$ is a discrete additive subgroup in a Euclidean space. When the space is $\mathbb{R}^m$, and if it is generated by (the columns of) $\mathbf{B} \in \mathbb{R}^{m \times d}$, we also write $\mathcal{L}(\mathbf{B}) = \{\mathbf{B}x | x \in \mathbb{Z}^d\}$. If $\mathbf{B}$ has full column rank, then we call $\mathbf{B}$ a basis and $d$ the rank of $\mathcal{L}$. When the ambient space is equipped with a norm $\|\cdot\|$, the volume of $\mathcal{L}$ is $\text{vol}(\mathcal{L}) = \det(\mathbf{B}^t\mathbf{B})^{1/2} = |\det(\mathbf{B})|$ for any basis $\mathbf{B}$.

### 2.1 Cyclotomic fields

Let $m$ be a positive integer, and $d = \phi(m)$ be the degree of the $m$-th cyclotomic polynomial $\Phi_m$ ($\phi$ is the Euler totient function). Let $\zeta$ to be a $m$-th primitive root of 1. Then for a fixed $m$, $\mathcal{K} := \mathbb{Q}(\zeta)$ is the cyclotomic field associated with $\Phi_m$, and its ring of algebraic integers is $\mathcal{R} := \mathbb{Z}[\zeta]$. The field automorphism induced by $\zeta \mapsto \zeta^{-1} = \bar{\zeta}$ corresponds to the complex conjugation, and we write $f^*$ the image of $f \in \mathcal{K}$ under this automorphism. We have $\mathcal{K} \simeq \mathbb{Q}[x]/(\Phi_m(x))$ and $\mathcal{R} \simeq \mathbb{Z}[x]/(\Phi_m(x))$, and both are contained in $\mathcal{K}_{\mathbb{R}} := \mathcal{K} \otimes \mathbb{R} = \mathbb{R}[x]/(\Phi_m(x))$. Each $f = \sum_{i=0}^{d-1} f_i \zeta^i \in \mathcal{K}_{\mathbb{R}}$ can be identified with its coefficient vector $(f_0, \dots, f_{d-1}) \in \mathbb{R}^d$. The complex conjugation operation extends naturally to $\mathcal{K}_{\mathbb{R}}$, and $\mathcal{K}_{\mathbb{R}}^+$ is the subspace of elements satisfying $f^* = f$.

The cyclotomic field $\mathcal{K}$ comes with $d$ complex field embeddings $\varphi_i : \mathcal{K} \to \mathbb{C}$ that maps $f$ seen as a polynomial to its evaluations at $\zeta^k$ where $\gcd(k, m) = 1$. This defines the so-called canonical embedding $\varphi(f) := (\varphi_1(f), \dots, \varphi_d(f))$. It extends straightforwardly to $\mathcal{K}_{\mathbb{R}}$ and identifies it to the space $\mathcal{H} = \{v \in \mathbb{C}^d : v_i = \overline{v_{d/2+i}}, 1 \le i \le d/2\}$. Note that $\varphi(fg) = (\varphi_i(f)\varphi_i(g))_{0<i\le d}$. When needed, this embedding extends entry-wise to vectors or matrices over $\mathcal{K}_{\mathbb{R}}$. We let $\mathcal{K}_{\mathbb{R}}^{++}$ be the subset of $\mathcal{K}_{\mathbb{R}}^+$ which have all positive coordinates in the canonical embedding. We have a partial ordering over $\mathcal{K}_{\mathbb{R}}^+$ by $f \succ g$ if and only if $f - g \in \mathcal{K}_{\mathbb{R}}^{++}$. The algebra $\mathcal{K}_{\mathbb{R}}$ is also equipped with a norm $N_{\mathcal{K}}(x) = \prod_i \varphi_i(x)$, which extends the standard field norm.

The next technical lemma is useful in our analyses, and is obtained by elementary trigonometric identities.

**Lemma 1.** Let $\zeta = \exp(i\theta)$ with $\theta = \frac{2k\pi}{m}$ and $\gcd(k, m) = 1$ be a $m$-th primitive root of the unity, and $d = \phi(m)$. Let $S(\theta) = \sum_{j=0}^{d-1} \zeta^{2j}$. We have $S(\theta) =$
$\frac{\sin(\theta d)}{\sin \theta} e^{i\theta(d-1)}$ and

$$ \mathrm{Re} S(\theta) = \frac{1}{2} + \frac{\sin((2d-1)\theta)}{2\sin\theta} \quad \text{and} \quad \mathrm{Im} S(\theta) = \frac{\sin(d\theta)\sin((d-1)\theta)}{\sin\theta}. $$

Remark 1. If $m$ is a power of 2 then $2d = m$ so we always have $S(\theta) = 0$.

## 2.2 NTRU lattices

This work deals with free $\mathcal{R}$-modules of rank 2 in $\mathcal{K}^2$, or in other words, groups of the form $\mathcal{M} = \mathcal{R}\mathbf{x} + \mathcal{R}\mathbf{y}$ where $\mathbf{x} = (x_1, x_2)$, $\mathbf{y} = (y_1, y_2)$ span $\mathcal{K}^2$. Given $f, g \in \mathcal{R}$ such that $f$ is invertible modulo some prime $q \in \mathbb{Z}$, we let $h = f^{-1}g$ mod $q$. The NTRU module determined by $h$ is $\mathcal{L}_{\mathrm{NTRU}} = \{(u, v) \in \mathcal{R}^2 : uh - v = 0 \mod q\}$. Two bases of this free module are of particular interest:

$$ \mathbf{B}_h = \begin{bmatrix} 1 & 0 \\ h & q \end{bmatrix} \quad \text{and} \quad \mathbf{B}_{f,g} = \begin{bmatrix} f & F \\ g & G \end{bmatrix}, $$

where $F, G \in \mathcal{R}$ are such that $fG - gF = q$ and $(F, G)$ should be relatively small. This module is usually seen as a lattice of volume $q^d$ in $\mathbb{R}^{2d}$ in the coefficient embedding.

We equip the ambient space $\mathcal{K}_{\mathbb{R}}^2$ with the inner product $\langle \mathbf{x}, \mathbf{y} \rangle_{\mathcal{K}} = x_1^* y_1 + x_2^* y_2$. The well-known Gram-Schmidt orthogonalization procedure for a pair of linearly independent vectors $\mathbf{b}_1, \mathbf{b}_2 \in \mathcal{K}^2$ is defined as

$$ \tilde{\mathbf{b}}_1 := \mathbf{b}_1, \tilde{\mathbf{b}}_2 := \mathbf{b}_2 - \frac{\langle \mathbf{b}_1, \mathbf{b}_2 \rangle_{\mathcal{K}}}{\langle \mathbf{b}_1, \mathbf{b}_1 \rangle_{\mathcal{K}}} \cdot \tilde{\mathbf{b}}_1. $$

One readily checks that $\langle \tilde{\mathbf{b}}_1, \tilde{\mathbf{b}}_2 \rangle = 0$. The Gram-Schmidt matrix with columns $\tilde{\mathbf{b}}_1, \tilde{\mathbf{b}}_2$ is denoted by $\tilde{\mathbf{B}}$ and we have $\det \tilde{\mathbf{B}} = \det \mathbf{B}$. We also let $|\mathbf{B}|_{\mathcal{K}} = \max(||\varphi(\langle \tilde{\mathbf{b}}_1, \tilde{\mathbf{b}}_1 \rangle)||_{\infty}, ||\varphi(\langle \tilde{\mathbf{b}}_2, \tilde{\mathbf{b}}_2 \rangle)||_{\infty})^{1/2}$.

**Lemma 2.** Let $\mathbf{B}_{f,g}$ be a basis of an NTRU module and $\mathbf{b}_1 = (f,g)$. We have $\sqrt{q} \le |\mathbf{B}_{f,g}|_{\mathcal{K}}$ and

$$ |\mathbf{B}_{f,g}|_{\mathcal{K}}^2 = \max \left( ||\varphi(\langle \mathbf{b}_1, \mathbf{b}_1 \rangle_{\mathcal{K}})||_{\infty}, \left\| \frac{q^2}{\varphi(\langle \mathbf{b}_1, \mathbf{b}_1 \rangle_{\mathcal{K}})} \right\|_{\infty} \right). $$

## 2.3 Gaussian and chi-squared distributions

For $\mu \in \mathbb{R}$ and $\sigma > 0$ we let $\mathcal{N}(\mu, \sigma^2)$ be the normal distribution of mean $\mu$ and standard deviation $\sigma$, that is, the continuous distribution over $\mathbb{R}$ with density proportional to $\exp(-(x - \mu)^2/(2\sigma^2))$. In higher dimensions, for $\Sigma$ a positive definite matrix and a vector $\mu \in \mathbb{R}^k$, we let $\mathcal{N}(\mu, \Sigma)$ be the normal distribution of density proportional to $\exp(-\frac{1}{2}(x - \mu)^t \Sigma^{-1} (x - \mu))$.

Let $T \sim \mathcal{N}(\mu, \sigma^2 \mathbf{I}_k)$ be a $k$-dimensional spherical normal random vector. The random variable $\|T\|^2$ follows a non central chi-squared distribution of degree $k$, non-centrality $c := \|\mu\|^2$ and scaling $\sigma^2$, denoted by $\chi^2(k, \sigma^2; c)$. Its expectation, variance and cumulative distribution function are described by the following classical result.
**Lemma 3.** Let U be a random variable distributed as $\chi^2(k, \sigma^2; c)$. We have $E[U] = \sigma^2k + c$ and $\text{Var}[U] = 2\sigma^2(\sigma^2k + 2c)$. For $0 \le a < b$, we have $\mathbb{P}[a \le U \le b] = Q_{k/2}(\sqrt{c}/\sigma, \sqrt{a}/\sigma) - Q_{k/2}(\sqrt{c}/\sigma, \sqrt{b}/\sigma)$, where $Q_{k/2}$ is the Marcum Q-function of order $k/2$.

Moreover, the Marcum Q-function $Q_m$ of integer order $m$ satisfies the following inequalities.

**Lemma 4 ([35, 3]).** For integer $m$ and $u, v \ge 0$, the following inequalities hold:

$$Q_m(u, v) \ge 1 - \frac{1}{2}e^{-(u-v)^2/2} \qquad \text{if } u \ge v;$$

$$Q_m(u, v) \le e^{-(v-u)^2/2} \cdot \left( 1 + \frac{(v/u)^{m-1} - 1}{\pi \cdot (1 - u/v)} \right) \qquad \text{if } u \le v.$$

We also note that the independent sum of a $\chi^2(k, \sigma^2; c)$ variable and a $\chi^2(k', \sigma^2; c')$ variable, for the same scaling $\sigma^2$, follows a $\chi^2(k + k', \sigma^2; c + c')$ distribution.

In the general case where $T \sim \mathcal{N}(\mu, \Sigma)$, let $\lambda_i > 0$ be the eigenvalues of the positive definite symmetric matrix $\Sigma$. If $P$ is an orthogonal matrix that diagonalizes $\Sigma$, let $\nu = (\nu_1, \dots, \nu_k) := P\mu$. Then $\|T\|^2 \sim \chi^2(1, \lambda_1; \nu_1^2) + \dots + \chi^2(1, \lambda_k; \nu_k^2)$. This distribution is called the weighted sum of k independent non central chi-squared variables. There is no known closed form for its cumulative distribution function, but there exist tools to evaluate it numerically (e.g., the Python package `chi2comb`).

# 3 New trapdoor algorithms for hybrid sampling

## 3.1 Hash-then-sign over lattices in a nutshell

The rationale behind this design is that a signature corresponds to a short Gaussian vector in a lattice $\mathcal{L}_{\text{NTRU}}$ centered at the hash of a (salted) message. On the one hand, these vectors can only be generated efficiently with the knowledge of a trapdoor $\mathbf{B}_{f,g}$, that is, a basis with good quality for a given sampling method. On the other hand, verifying amounts to checking lattice membership and that the vector is indeed shorter than a threshold. For the sake of completeness, we recap this design in the form of high-level, generic algorithms `KeyGen`, `Sign`, `Verify` corresponding to the current efficient instantiations.

In Algorithm 1, the procedure `Sample` differs from FALCON to MITAKA. The former relies on the FFO sampler (a Fast-Fourier-like version of the GPV sampler [20], while the latter prefers the simpler hybrid sampler of Ducas-Prest [11]. Lattice membership is implicitly checked at the first step of Algorithm 2. We finish the section with a high-level description of `KeyGen` in Algorithm 3. Its purpose is to generate a pair $(h, \mathbf{B}_{f,g})$ where $\mathbf{B}_{f,g}$ should have a good quality with respect to the selected instantiation of `Sample`. For simplicity, we omit in its description the additional secret data related to the sampler. The procedure
Algorithm 1: Signing

Input: A message m, a trapdoor $\mathbf{B}_{f,g}$, a standard deviation parameter $\sigma$

Result: the first component $s_0$ of $s = (s_0, s_1) \in \mathbb{R}^2$ such that $c - s$ has a distribution close to $D_{\mathcal{L}_{\text{NTRU},c,\sigma}}$.

1 $r \leftarrow \{0, 1\}^{320}$

2 $c \leftarrow (0, H(m||r))$

3 $v \leftarrow \text{Sample}(\mathbf{B}_{f,g}, c, \sigma)$

4 $(s_0, s_1) \leftarrow c - v$

5 **return** $s_0$

Algorithm 2: Verification

Input: A message m, a salt $r$, $s_0 \in \mathbb{R}$, a public key $h$ and a threshold $\beta$

Result: Accept or reject

1 $s_1 \leftarrow H(m||r) + s_0h \bmod q$

2 **if** $\|(s_0, s_1)\| > \beta$ **then**

3 **|** **Reject.**

4 **end if**

5 **Accept.**

GoodPair, our focus in this work, outputs $(f,g) \in \mathbb{R}^2$ with the guarantee that the basis $\mathbf{B}_{f,g}$ output by NTRUSolve will have quality $\alpha$ or better for the choice of Sample.

## 3.2 NTRU trapdoors in FALCON and MITAKA

With respect to Prest's hybrid sampler, an NTRU trapdoor $\mathbf{B}_{f,g}$ has a quality $\alpha$ defined as

$$ \alpha = |\mathbf{B}_{f,g}|_{\mathcal{X}} / \sqrt{q}, \qquad (1) $$

where we recall that $|\mathbf{B}_{f,g}|_{\mathcal{X}}^2 = \max(\|\varphi(ff^* + gg^*)\|_{\infty}, \|\frac{q^2}{\varphi(ff^* + gg^*)}\|_{\infty})$. The quality with respect to the Klein-GPV sampler admits a similar expression.

In hash-and-sign signatures, security against forgery attacks is driven by the standard deviation of the sampler, which is essentially $\alpha\sqrt{q}$. As the smaller the value of $\alpha$, the harder forgery becomes, the goal of KeyGen in schemes such as DLP [9], FALCON [34] and MITAKA [15] is to construct in reasonable time bases $\mathbf{B}_{f,g}$ with $\alpha$ as small as possible (and in particular, smaller than a given threshold related to the acceptance radius of signature verification). In other words, the goal is to instantiate efficiently the procedure GoodPair.

An important observation regarding NTRU trapdoors is that the knowledge of the first basis vector $(f,g)$ alone is sufficient to determine the quality of the whole basis (see for example Lemma 2 for MITAKA). As a result, to test if a vector $(f,g)$ can be completed into a trapdoor $\mathbf{B}_{f,g}$ reaching the desired quality
Algorithm 3: Generic NTRU Trapdoor generator

Input: A degree $d$, a modulus $q$, a target quality $\alpha$

Result: a public key $h \in \mathbb{R}$ and the trapdoor $\mathbf{B}_{f,g}$

1. $(f, g) \leftarrow \text{GoodPair}(d, q, \alpha)$

2. $\mathbf{B}_{f,g} \leftarrow \text{NTRUSolve}(f, g, q)$

3. $h \leftarrow gf^{-1} \bmod q$

4. **return** $(h, \mathbf{B}_{f,g})$.

threshold, it is not necessary to compute the second vector $(F, G)$, which is a notoriously costly operation, even accounting for optimizations such as [31].

In DLP, FALCON and MITAKA, GoodPair is a trial-and-error routine, generating many potential candidate first vectors $(f, g)$ and testing whether they satisfy the required quality threshold. The candidates themselves are generated as discrete Gaussian vectors in $\mathbb{R}^2$ with the correct expected length. In that way, FALCON reaches quality $\alpha = 1.17$ with respect to its FFO-based sampler (that admits the same quality metric as Klein-GPV). Doing this directly for the hybrid sampler, as discussed in [32], only achieves quality $\gtrsim 3$ in dimension 512, and even larger in higher dimensions. As a result, the MITAKA paper has to introduce randomness recycling and other techniques on top of this general approach in order to increase the number of candidates and improve the achievable quality; with those improvements, MITAKA reaches $\alpha = 2.04$ in dimension 512 (which translates to 20 fewer bits of security compared to FALCON, and is thus unfortunately not sufficient to reach NIST security level I).

3.3 ANTRAG: annular NTRU trapdoor generation

The main contribution of this paper is a novel instantiation of GoodPair for the hybrid sampler, resulting in a NTRU trapdoor generation algorithm achieving much better quality than MITAKA, while reaching the same security NIST levels as FALCON.

The intuition behind our new approach stems from the following observation. For a fixed $\alpha \ge 1$, requiring a trapdoor $\mathbf{B}_{f,g}$ to satisfy $|\mathbf{B}_{f,g}|_\mathcal{X} \le \alpha\sqrt{q}$ is equivalent to enforcing that for all $1 \le i \le d$, we have

$$ \frac{q}{\alpha^2} \le |\varphi_i(f)|^2 + |\varphi_i(g)|^2 \le \alpha^2 q, \quad (2) $$

(where we recall that the $\varphi_i(f)$ are the embeddings of $f$ in $\mathbb{C}$, and similarly for $g$). Equivalently, this means that for all $i$, the pair $(|\varphi_i(f)|, |\varphi_i(g)|)$ belongs to the arc of annulus $A_\alpha^+ := A^+(\sqrt{q}/\alpha, \alpha\sqrt{q})$.

It is thus natural to try and sample $f$ and $g$ from their embeddings (i.e., in the Fourier domain), by picking the pairs $(\varphi_i(f), \varphi_i(g))$ as uniform random pairs of complex numbers such that satisfying the condition that the pair of their magnitudes belongs to $A_\alpha^+$: in other words, pick

<figure><img src="image_2.png" /><figcaption>Fig. 1. ($|z|, |w|$) is sampled uniformly in the annulus $A^+(r, R)$.</figcaption></figure>
<caption>Algorithm 4: Candidate pairs from uniform annulus sampling</caption>

Input: $0 < r < R$, the radii of $A^+(r, R)$
Result: $z, z' \in \mathbb{C}$ such that $|z|, |z'|$ is uniformly distributed in $A^+(r, R)$
1 & $u \leftarrow U([r^2, R^2])$
2 & $\rho \leftarrow \sqrt{u}$
3 & $\theta \leftarrow U([0, \pi/2])$
4 & $\left(x, y\right) \leftarrow \left(\rho \cos \theta, \rho \sin \theta\right)$ & $\ast$ $\left(x, y\right) \leftarrow U\left(A^+(r, R)\right)$ $\ast$
5 & $\omega, \omega' \leftarrow U([0, 2\pi])$
6 & $\left(z, z'\right) \leftarrow \left(x \cdot e^{i\omega}, y \cdot e^{i\omega'}\right)$
7 & **return** $\left(z, z'\right)$

$(x_i, y_i)$ uniformly at random in $A_\alpha^+$ and then sample $\varphi_i(f)$ and $\varphi_i(g)$ as uniform complex numbers of magnitudes $x_i$ and $y_i$ respectively. Note that only $d/2$ pairs are needed, as the remaining ones are determined by conjugation.

Moreover, sampling uniformly in an annulus (or, as in our case, an arc of annulus) in polar coordinates $(\rho, \theta)$ is easy: it suffices to sample the angle $\theta$ and the square $\rho^2$ of the radial coordinate uniformly in their respective ranges. This is because the area element in polar coordinates is $\rho d\rho d\theta = \frac{1}{2} d(\rho^2) d\theta$. This gives rise to Algorithm 4 for sampling the pairs of embeddings.

However, one soon realizes that the real polynomials $\tilde{f}, \tilde{g}$ corresponding to the embeddings generated by the Algorithm 4 (via the inverse Fourier transform $\varphi^{-1}$) do not always have integer coefficients, and hence do not generally correspond to ring elements. In general, they are elements of the $\mathbb{R}$-algebra $\mathcal{K}_{\mathbb{R}}$.

In order to obtain actual ring elements, a natural solution is to round those real polynomials $\tilde{f}, \tilde{g}$ coefficient-wise. This yields $f = \lfloor \tilde{f} \rfloor$ and $g = \lfloor \tilde{g} \rfloor$ in $\mathbb{R}$, which are potential candidates for a trapdoor. It turns out, however, that if one starts from $\tilde{f}, \tilde{g}$ uniform with their embeddings of magnitude in $A_\alpha^+$, the resulting rounded ring elements are very unlikely to also have their embeddings of magnitude in that arc of annulus. Thus, they do not typically give rise to a trapdoor of the desired quality. This is because rounding adds an additive term (essentially uniformly distributed in $[-1/2, 1/2)$) to each coefficient, which translates to an additive “error” on each embedding, making it unlikely that the embeddings all remain in the desired domain.

A straightforward workaround is to compensate this decoding error by sampling the embeddings of $\tilde{f}, \tilde{g}$ from a narrower annulus $A^+(r, R)$ for some radii $r, R$ such that $\sqrt{\tilde{q}}/\alpha < r < R < \alpha\sqrt{\tilde{q}}$. This yields Algorithm 5, which is our proposed ANTRAG trapdoor generation algorithm.

*Remark 2.* One could consider carrying out the decoding to the ring differently, for example by sampling discrete Gaussians $f$ and $g$ in $\mathbb{R}$ centered at $\tilde{f}$ and $\tilde{g}$ respectively. The resulting algorithm would be simpler to analyze in some
<caption>Algorithm 5: ANTRAG trapdoor generation</caption>

**Input:** The degree $d$, the modulus $q$, a target quality $\alpha$, and starting radii $r, R$ such that $\sqrt{\tilde{q}}/\alpha < r < R < \alpha\sqrt{\tilde{q}}$.
**Result:** $f, g \in \mathbb{R}^2$ such that $\frac{q}{\alpha^2} \le |\varphi_i(f)|^2 + |\varphi_i(g)|^2 \le \alpha^2 q$ for all $i$.
1 repeat
2 &nbsp;&nbsp;&nbsp;for $1 \le i \le d/2$ do
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;using Algorithm 4, sample $(z_i, w_i) \in \mathbb{C}^2$ uniformly such that $(|z_i|, |w_i|) \in A^+(r, R)$.
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end for
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{f} \leftarrow \varphi^{-1}(z_1, \dots, z_{d/2}) \in \mathcal{K}_{\mathbb{R}}$
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{g} \leftarrow \varphi^{-1}(w_1, \dots, w_{d/2}) \in \mathcal{K}_{\mathbb{R}}$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$f \leftarrow [\tilde{f}]$
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$g \leftarrow [\tilde{g}]$
9 **until** $(|\varphi_i(f)|, |\varphi_i(g)|) \in A^+(\sqrt{\tilde{q}}/\alpha, \alpha\sqrt{\tilde{q}})$ for all $i = 1, \dots, d/2$
10 **return** $(f, g)$

ways, and might be seen as better behaved in a certain sense, but it does have a major drawback: it introduces a much larger decoding error (on the order of the smoothing parameter $\eta_e(\mathbb{Z})$ of $\mathbb{Z}$ on each coefficient, instead of the standard deviation $1/\sqrt{12}$ of the uniform distribution in $[-1/2, 1/2)$, so about 4 times larger). As a result, in this work, we focus on the rounding approach.

## 3.4 On the distribution of embeddings

We have mentioned above that taking the magnitudes of the embeddings of $\tilde{f}$ and $\tilde{g}$ in $A_\alpha^+$ was very unlikely to result in $f$ and $g$ of the required quality $\alpha$ after rounding, but that the probability increased greatly when choosing $\tilde{f}$ and $\tilde{g}$ with embedding magnitudes in a narrower arc of annulus $A^+(r, R)$. We choose the bounds $r$ and $R$ as complementary convex combinations of $\alpha\sqrt{\tilde{q}}$ and $\sqrt{\tilde{q}}/\alpha$; in other words, we set:

$$r = \frac{1 - \xi}{2} \alpha \sqrt{\tilde{q}} + \frac{1 + \xi}{2} \cdot \frac{\sqrt{\tilde{q}}}{\alpha} \quad \text{and} \quad R = \frac{1 + \xi}{2} \alpha \sqrt{\tilde{q}} + \frac{1 - \xi}{2} \cdot \frac{\sqrt{\tilde{q}}}{\alpha} \quad (3)$$

for some constant $\xi \in (0, 1)$, so that $A^+(r, R)$ corresponds to the middle $\xi$-fraction of $A_\alpha^+$. We will later specifically choose $\xi = 1/3$ (i.e., $A^+(r, R)$ as the “middle third” of $A_\alpha^+$) to fix ideas, and because it yields the following expression for $r$ and $R$ with minimal coefficient height:

$$r = \left( \frac{1}{3}\alpha + \frac{2}{3} \cdot \frac{1}{\alpha} \right) \sqrt{\tilde{q}} \quad \text{and} \quad R = \left( \frac{2}{3}\alpha + \frac{1}{3} \cdot \frac{1}{\alpha} \right) \sqrt{\tilde{q}}.$$

In this section, we would like to provide a model allowing us to quantify the claim that sampling $\tilde{f}$ and $\tilde{g}$ in this $A^+(r, R)$ increases success probability. To that end, write $e = (e_f, e_g) = (f - \tilde{f}, g - \tilde{g}) \in \mathcal{K}_{\mathbb{R}}^2$ for the error term introduced
by rounding. We would like to control the distribution of the embeddings of $e_f$ and $e_g$ in order to estimate the likelihood that the condition $(|\varphi_i(f)|, |\varphi_i(g)|)$ will be satisfied for all $i$.

In the polynomial basis, we write $e_f = \sum_{j=0}^{d-1} e_f^{(j)} x^j$ and similarly for $e_g$. Heuristically, we expect the coefficients $e_f^{(j)}$ and $e_g^{(j)}$ to behave essentially like independent uniform random variables in $[-1/2, 1/2)$.<fnref n="9" /> This is well-supported by experiments (see the full version of this paper [17]).

Now consider a single embedding $\varphi_\theta$, and recall that we are interested in an a priori arbitrary cyclotomic base ring, so that $\varphi_\theta$ is defined by the evaluation at some primitive $m$-th root of unity $\zeta = e^{i\theta}$. We therefore have:

$$ \varphi_{\theta}(e_f) = x_{\theta} + iy_{\theta} \quad \text{with} \quad x_{\theta} = \sum_{j=0}^{d-1} e_f^{(j)} \cos(j\theta) \quad \text{and} \quad y_{\theta} = \sum_{j=0}^{d-1} e_f^{(j)} \sin(j\theta). $$

This expresses the real and imaginary parts $x_\theta, y_\theta$ of $\varphi_\theta(e_f)$ as the sum of $d$ independent random variables, with $d$ relatively large, so by the central limit theorem, $\varphi_\theta(e_f)$ should essentially behave<fnref n="10" /> like a normal random variable in $\mathbb{C}$, essentially determined by its expectation and covariance.

Now since $e_f^{(j)}$ has mean 0 and variance 1/12 for all $j$, we obtain that $\mathbb{E}[x_\theta] = \mathbb{E}[y_\theta] = 0$. Therefore, the pair $(x_\theta, y_\theta)$ has mean 0, and its covariance matrix is easily expressed as follows:

$$ \Sigma_{\theta} = \frac{d}{24} \mathbf{I}_2 + E(\theta) \quad \text{where} \quad E(\theta) = \frac{1}{24} \begin{bmatrix} \operatorname{Re} S(\theta) & \operatorname{Im} S(\theta) \\ \operatorname{Im} S(\theta) & -\operatorname{Re} S(\theta) \end{bmatrix}. $$

Note that $\Sigma_\theta$ has eigenvalues $\lambda_+^\theta = \frac{d+|S(\theta)|}{24}$ and $\lambda_-^\theta = \frac{d-|S(\theta)|}{24}$. We thus expect that $\varphi_\theta(e_f)$ follows the normal distribution $N(0, \Sigma_\theta)$, and the same argument applies to $\varphi_\theta(e_g)$ as well. Moreover, heuristically, those two normal distributions should be independent (this is again well-verified in practice), therefore, we can write

$$ (\varphi_{\theta}(e_f), \varphi_{\theta}(e_g)) \sim \mathcal{N}\left(0, \begin{pmatrix} \Sigma_{\theta} & 0 \\ 0 & \Sigma_{\theta} \end{pmatrix}\right) \quad (4) $$

This leads us to model the distribution of the embeddings of secret keys as follows.

**Heuristic 1.** Let $(f, g) \in \mathcal{K}^2$ a pair output by Algorithm 5, corresponding to $(\tilde{f}, \tilde{g}) \in \mathcal{K}_{\mathbb{R}}^2$ obtained from the executions of Algorithm 4. For the embedding $\varphi_\theta$ corresponding to the primitive root of unity $e^{i\theta}$, $(\varphi_\theta(f), \varphi_\theta(g))$ is distributed as

$$ (\varphi_{\theta}(f), \varphi_{\theta}(g)) \sim \mathcal{N}((\varphi_{\theta}(\tilde{f}), \varphi_{\theta}(\tilde{g})), \mathbf{I}_2 \otimes \Sigma_{\theta}). $$

Moreover, the pairs $(\varphi_\theta(f), \varphi_\theta(g))$ as $\varphi_\theta$ ranges through all the embeddings of $\mathcal{K}$ are independently distributed.

<footnote n="9">⁹ This is equivalent to saying that the distribution of $\tilde{f}$ and $\tilde{g}$ is uniform modulo $\mathcal{R}$ in $\mathcal{K}_{\mathbb{R}}$, which should indeed happen as soon as we have sufficient width (i.e., if we exceed a regularity metric analogous to the smoothing parameters for Gaussians).</footnote>

<footnote n="10">¹⁰ This can in fact be made rigorous with the Berry-Esseen theorem.</footnote>
Note that this heuristic considers the pair $(\varphi_{\theta}(f), \varphi_{\theta}(g))$, which is actually supported on dense but countable subgroup of $\mathbb{C}^2$, as following a continuous distribution. This has the merit of allowing an analysis while being an accurate representation of the situation according to our experiments.

Under this heuristic we can express the expected length of the embeddings of secret keys and related elements, which will be useful in the security analysis. The proof is provided in the full version of this paper [17].

**Proposition 1 (Heuristic).** Keeping the notation of Algorithm 5, let $(f,g)$ be a random variable following the distribution of its output. Let $\theta$ be an argument of a primitive m-th root of unity, and let $\varphi_{\theta}$ be the corresponding embedding. Then:

$$ \mathbb{E}[|\varphi_{\theta}(f)|^2 + |\varphi_{\theta}(g)|^2] = \frac{d}{6} + \frac{r^2 + R^2}{2}. $$

Let $\| \cdot \|_{\theta}$ be the norm induced by the quadratic form $\Sigma_{\theta}$. Then we also have:

$$ \mathbb{E}[|\varphi_{\theta}(f)|^4 + |\varphi_{\theta}(g)|^4] = \frac{5}{8}(R^4 + r^4) + R^2 r^2 + \frac{d}{12}(R^2 + r^2) + \frac{d^2}{36} + T(\theta), $$

$$ \text{where } T(\theta) := |S(\theta)|^2/72 + 4 \cdot \mathbb{E}[\|\varphi_{\theta}(\tilde{f})\|_{\theta}^2 + \|\varphi_{\theta}(\tilde{g})\|_{\theta}^2]. $$

# 4 Success probability and security analysis

In this section, we first concentrate on the case of a power-of-two cyclotomic base ring, in which, under Heuristic 1, all the embeddings of $f$ and $g$ are simply modeled as independent and identically distributed isotropic normal variates, which simplifies the analysis somewhat. In this context, we analyze the success probability of Algorithm 5 as well as the security of the resulting scheme, which lets us derive concrete parameters.

At the end of the section, we also briefly describe how the analysis extends to the more general setting of cyclotomic rings with conductor $m = 2^k p^l$, with further details provided in the full version of this paper [17].

## 4.1 Success probability over power-of-two cyclotomics

Suppose that $\mathcal{K}$ is a cyclotomic field of conductor a power of two, and let $(\tilde{f}, \tilde{g}) \in \mathcal{K}^2$ and $(f,g) \in \mathcal{R}^2$ be generated as in Steps 5–6 and Steps 7–8 of Algorithm 5 respectively.

We first fix one embedding $\varphi_{\theta}: \mathcal{K} \to \mathbb{C}$ of $\mathcal{K}$, and try to determine the probability with which the test of Step 10 of Algorithm 5 is satisfied with respect to that particular embedding. In other words, we want to estimate the probability that:

$$ q/\alpha^2 \le |\varphi_{\theta}(f)|^2 + |\varphi_{\theta}(g)|^2 \le \alpha^2 q. \qquad (5) $$
Now, according to Heuristic 1, the pair $(\varphi_{\theta}(f), \varphi_{\theta}(g)) \in \mathbb{C}^2$ follows a normal distribution centered at $(\varphi_{\theta}(\tilde{f}), \varphi_{\theta}(\tilde{g}))$ of scalar covariance $\frac{d}{24} \mathbf{I}_4$ (since over power-of-two cyclotomic fields, $E(\theta) = 0$ for all $\theta$). Therefore, for fixed $(\tilde{f}, \tilde{g})$ and following the definitions of Section 2.3, the squared norm:

$$ \| (\varphi_{\theta}(f), \varphi_{\theta}(g)) \|^2 = |\varphi_{\theta}(f)|^2 + |\varphi_{\theta}(g)|^2 $$

follows a non central chi-squared distribution $\chi^2(4, \sigma^2; c)$ of degree 4, non-centrality $c = |\varphi_{\theta}(\tilde{f})|^2 + |\varphi_{\theta}(\tilde{g})|^2$ and scaling $\sigma^2 = d/24$. In particular, the probability that condition (5) does not depend on the exact position of the pair $(\varphi_{\theta}(\tilde{f}), \varphi_{\theta}(\tilde{g}))$, but only on its squared norm $c$, or equivalently on:

$$ \beta := \frac{1}{\sqrt{q}} \|(\varphi_{\theta}(\tilde{f}), \varphi_{\theta}(\tilde{g}))\|. $$

We denote the probability that condition (5) is satisfied for a certain value $\beta$ by $p_{\text{succ}}(\beta)$. According to Lemma 3, the probability $p_{\text{succ}}(\beta)$ can be expressed in terms of the Marcum $Q$-function $Q_2$ as follows:

$$ p_{\text{succ}}(\beta) = Q_2(\tau\beta, \tau/\alpha) - Q_2(\tau\beta, \tau\alpha) \quad \text{where} \quad \tau = \sqrt{\frac{24q}{d}}. $$

Based on this result, we will first provide a simple but loose lower bound of the success probability of Algorithm 5, and then derive a more complicated but tight estimate that we can use for numerical estimates and parameter selection.

*Bounding the success probability below.* According to Lemma 4, the following bounds on the Marcum $Q$ function hold for any $1/\alpha \le \beta \le \alpha$:

$$ \begin{aligned} Q_2(\tau\beta, \tau/\alpha) &\ge 1 - \frac{1}{2} \exp\left(-\frac{\tau^2}{2}(\beta - 1/\alpha)^2\right) \\ Q_2(\tau\beta, \tau\alpha) &\le \left(1 + \frac{\alpha/\beta}{\pi}\right) \exp\left(-\frac{\tau^2}{2}(\alpha - \beta)^2\right) \end{aligned} $$

from which it follows that:

$$ p_{\text{succ}}(\beta) \ge 1 - \frac{1}{2}u_{\tau}(\beta - 1/\alpha) - \left(1 + \frac{\alpha/\beta}{\pi}\right)u_{\tau}(\alpha - \beta) \quad \text{where} \quad u_{\tau}(x) = \exp\left(-\frac{\tau^2}{2}x^2\right). \tag{6} $$

We write $\beta = (\alpha + 1/\alpha)/2 + t(\alpha - 1/\alpha)/2$ for some $t \in (-1, 1)$. Recall furthermore from Eq. (3) that we have set:

$$ \frac{r}{\sqrt{q}} = (\alpha + 1/\alpha)/2 - \xi(\alpha - 1/\alpha)/2 \quad \text{and} \quad \frac{R}{\sqrt{q}} = (\alpha + 1/\alpha)/2 + \xi(\alpha - 1/\alpha)/2 $$

so that $t$ actually varies in $[-\xi, \xi]$. In particular, we have:

$$ \frac{\alpha}{\beta} \le \frac{\alpha}{r} = \frac{\alpha}{\frac{1-\xi}{2}\alpha + \frac{1+\xi}{2}\frac{1}{\alpha}} = \frac{2}{1-\xi} \cdot \frac{1}{1 + \frac{1+\xi}{1-\xi}\frac{1}{\alpha^2}} \le \frac{2}{1-\xi}. $$
Thus, inequality (6) becomes:

$$p_{\text{succ}}(\beta) \geq 1 - \frac{1}{2}u_{\tau}((1-t)\delta) - \left(1 + \frac{2/\pi}{1-\xi}\right)u_{\tau}((1+t)\delta) \quad \text{for } \delta = \frac{\alpha - 1/\alpha}{2}.$$

Since $u_{\tau}$ is a decreasing function, both $u_{\tau}((1-t)\delta)$ and $u_{\tau}((1+t)\delta)$ are bounded above by $u_{\tau}((1-\xi)\delta)$, so that:

$$p_{\text{succ}}(\beta) \geq 1 - K_{\xi} u_{\tau}((1-\xi)\delta) \quad \text{with} \quad K_{\xi} = \frac{3}{2} + \frac{2/\pi}{1-\xi}$$

holds for all $\beta \in [r/\sqrt{q}, R/\sqrt{q}]$.

As a result, the overall success probability $p_{\text{succ-all}}$ for a single embedding (which is the probability that condition (5) holds when the starting embedding pair $(|\varphi_{\theta}(\tilde{f})|, |\varphi_{\theta}(\tilde{g})|)$ is sampled uniformly in $A^{+}(r, R)$ is similarly lower bounded as:

$$p_{\text{succ-all}} \geq 1 - K_{\xi} u_{\tau}((1-\xi)\delta) \quad (7)$$

and under our independence heuristic, the success probability $p_{\text{succ-all}}$ for all $d/2$ embeddings at the same time satisfies:

$$p_{\text{succ-all}} \geq \left(1 - K_{\xi} u_{\tau}((1-\xi)\delta)\right)^{d/2}.$$

To reach an overall success probability of $1/M$ (i.e., $M$ repetitions on average), it therefore suffices to have:

$$\frac{d}{2} \log \left(1 - K_{\xi} u_{\tau}((1-\xi)\delta)\right) \geq -\log M.$$

Using the usual first order approximation $\log(1-x) \approx -x$, this yields $\frac{d}{2}K_{\xi}u_{\tau}((1-\xi)\delta) \lesssim \log M$, or equivalently:

$$\frac{\alpha - 1/\alpha}{2} \geq \frac{d}{12(1 - \xi)^2 q} \log \frac{K_{\xi} d}{2 \log M}.$$

This shows that a quality $\alpha$ is achievable (with repetition rate up to $M$) as long as:

$$\alpha \geq \sqrt{A} + \sqrt{1+A} \quad \text{where} \quad A = \frac{d}{12(1-\xi)^2 q} \log \frac{K_{\xi} d}{2 \log M}. \quad (8)$$

In particular, we see that, as long as $q = \Omega(d \log d)$, quality measures $\alpha = O(1)$ are achievable with any constant repetition rate. This is similar to FALCON and unlike MITAKA [14, Appendix C] and the original approach for the Peikert and hybrid samplers [32], where $\alpha$ increases as a power function of the dimension independently of $q$.

As discussed in the previous section, we choose $\xi = 1/3$ to fix ideas, so that the starting annulus becomes the “middle third” of the target annulus (we will see below that this choice is very safe). Condition (8) above with $M = 4$ and $q = 12289$ shows that one can reach quality at least $\alpha = 1.24$ in dimension 512 and $\alpha = 1.38$ in dimension 1024 with this modulus $q$ and repetition rate up to 4. This is already much better than the quality parameters achievable by MITAKA, but since we have used loose inequalities throughout, these are actually rough lower bounds.
*More precise expression of success probability.* For concrete parameter selection, and also to test the validity of our heuristic assumptions, it is useful to write down the exact expression of success probability according to our model.

Recall that the success probability $p_{\text{succ-one}}$ for a single embedding is the probability that condition (5) holds when the starting embedding pair ($|\varphi_{\theta}(\hat{f})|, |\varphi_{\theta}(\tilde{g})|$) is sampled uniformly in $A^{+}(r, R)$. In other words, $p_{\text{succ-one}}$ is the expected value of $p_{\text{succ}}(\beta)$ for $\beta^2$ uniformly distributed in $[r^2/q, R^2/q]$. Therefore:

$$p_{\text{succ-one}} = \frac{q}{R^2 - r^2} \int_{r^2/q}^{R^2/q} p_{\text{succ}}(\sqrt{B}) dB = \frac{2q}{R^2 - r^2} \int_{r/\sqrt{q}}^{R/\sqrt{q}} p_{\text{succ}}(\beta) \beta \, d\beta.$$

Carrying out the change of variables $\beta = (\alpha+1/\alpha)/2+t(\alpha-1/\alpha)/2$ and plugging in the expression of $p_{\text{succ}}(\beta)$ in terms of $Q_2$, we finally get:

$$p_{\text{succ-one}} = \frac{1}{2\xi} \int_{-\xi}^{\xi} F(\alpha, t) \cdot \left(1 + t \frac{\alpha - \frac{1}{\alpha}}{\alpha + \frac{1}{\alpha}}\right) dt$$

where

$$F(\alpha, t) = Q_2\left(\tau\left(\frac{\alpha + \frac{1}{\alpha}}{2} + t\frac{\alpha - \frac{1}{\alpha}}{2}\right), \tau/\alpha\right) - Q_2\left(\tau\left(\frac{\alpha + \frac{1}{\alpha}}{2} + t\frac{\alpha - \frac{1}{\alpha}}{2}\right), \tau\alpha\right),$$

and $1/M = p_{\text{succ-all}} = p_{\text{succ-one}}^{d/2}$. This makes it easy to solve numerically for $\alpha$ in order to reach a certain repetition rate. Again for $q = 12289$, we find that we reach repetition rate $M = 4$ for $\alpha \approx 1.143$ in dimension $d = 512$, and for $\alpha \approx 1.229$ for $d = 1024$. For $q = 3329$, the same repetition rate is reached for $\alpha \approx 1.290$ for $d = 512$ and $\alpha \approx 1.478$ for $d = 1024$. Moreover, this allows us to confirm that our model very closely matches experiments, as demonstrated on Fig. 2.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Base 2 logarithm of the repetition rate $M$ of Algorithm 5 as a function of $\alpha$, for $d \in \{512, 1024\}$ and $q \in \{12289, 3329\}$. The continuous lines are obtained based on our model, and the triangle data points are measured by simulations (averaging 100 iterations of the algorithm for each data point).</figcaption></figure>
## 4.2 Security analysis for power-of-two cyclotomics

In order to assess the concrete security of the resulting signature scheme, we proceed using the usual cryptanalytic methodology of estimating the complexity of the best attacks against key recovery attacks on the one hand, and signature forgery on the other. In the hash-and-sign paradigm, the security of the forgery is a function of the standard deviation of the lattice Gaussian sampler used in the signature function, which itself depends on the quality $\alpha$ of the trapdoor. A first straightforward observation is that, since our work has only modified which trapdoors are used for signing, and not how they are used in signing, our modifications cannot have a negative impact on the resilience against forgery. On the contrary, we have shown how to increase the trapdoor quality, and therefore our new approach increases the security against forging attackers. As such our focus will now be the resilience to key recovery attacks.

In Section 4.2.1, we go through a short review of the general lattice reduction approach for key recovery, which is the current best attack when no additional information is provided to the attacker (seeing as combinatorial or hybrid attacks are irrelevant in our setting, with dense, non-ternary keys). Nevertheless, by changing the sampling of the good trapdoors, we might have restricted to a possibly smaller set of secret keys, or to a possibly much more geometrically constrained set of keys. Indeed, all their complex embeddings must lie in a publicly described annulus, so an adversary could use this additional information to gather more power for an attack.

In Section 4.2.2 we present a new approach exploiting this additional geometric information. It is reminiscent of the subfield attacks [1, 6], however here we stop the descent in the subfields at the totally real subfield $\mathcal{K}^+$ (the set of elements satisfying $f = f^*$). Indeed, this subfield encodes the length information of the pair $(f, g)$ in the elements $(f f^*, g g^*)$ and its collection of embeddings. In the extreme (unlikely) case where the annulus would be a circle, an adversary would know this element exactly, and could use the Gentry-Szydlo attack [21] to recover $f$ or $g$. Our situation could be summed-up as an “approximate” Gentry-Szydlo attack, where too much proximity of all the embeddings to a known circle could be exploited by an attacker through lattice reduction.

Our trapdoor generator could output keys with embeddings that would all be close to some circle, and we call these temporarily potentially weak keys. Our analysis will show that these potentially weak keys are in fact not so weak, or in other words, that we have some freedom for parametrization with respect to the available space $(\alpha - \alpha^{-1})\sqrt{q}$. This ensures a good success rate for ANTRAG. Ultimately, the attack will use lattice reduction but on a different lattice than in the direct, standard key-recovery context, and will try to recover $(f f^*, g g^*)$.

For the context of Section 4.2.2, we need the expected length of $(f, g)$ and $(f f^*, g g^*)$. These two properties are gathered in the next result. The proof, a direct application of Proposition 1, is provided in the full version of this paper [17].
**Corollary 1.** With the notation of Algorithm 5, let $(f,g)$ be a random variable following the distribution of its output. Then we have $\mathbb{E}[\|(f,g)\|^2] = \frac{d}{6} + \frac{R^2+r^2}{2}$ and $\mathbb{E}[\|(ff^*, gg^*)\|^2] = \frac{5}{8}(R^4+r^4) + R^2r^2 + \frac{d}{6}(R^2+r^2) + \frac{d^2}{36}$.

**4.2.1 Classical attack against NTRU keys.** The key recovery in this context consists in constructing the algebraic lattice over $\mathcal{R}$ spanned by the vectors $(0, q)$ and $(1, h)$ (i.e. the public basis attached to the NTRU key) and retrieving the lattice vector $\mathbf{s} = (f,g)$ among all possible lattice vectors of norm bounded by $\|\mathbf{s}\|$ (or a functionally equivalent vector, for instance $(\mu \cdot f, \mu \cdot g)$ for any unit $\mu$ of the ring of integer of the number field). From Corollary 1 we obtain $\mathbb{E}[\|\mathbf{s}\|^2] \le qA$, where $A = \frac{d}{6q} + \frac{1}{9}(\frac{5\alpha^2}{2} + \frac{5}{\alpha^2} + 4)$. Since the attack is easier when the key to recover is longer, we take the value $qA$ acting as $\mathbb{E}[\|\mathbf{s}\|^2]$. In order to avoid enumerating and testing all integer vectors in the sphere of radius $\sqrt{q}S$, which would contain a large number of vectors under the Gaussian heuristic$^{11}$, namely around $(\frac{qA}{q})^d = A^d$, we make use of the projection trick (see also [15, 18]). This technique involves reducing the public basis with some lattice reduction algorithm, and seeking for the projection of the secret key onto the lattice spanned by the few last Gram-Schmidt vectors of this reduced basis. If we find the projection of the secret key, we can retrieve the full key by using the Babai nearest plane algorithm to lift it to a lattice vector of the desired norm.

More precisely we proceed as follows. Set $\beta$ to be the block size parameter of the DBKZ algorithm [28] and start by reducing the public basis with this latter algorithm. Call $[\mathbf{b}_1, \dots, \mathbf{b}_{2d}]$ the resulting vectors. Then if we can recover the projection of the secret key onto $\mathcal{P}$, the orthogonal space to $\operatorname{span}(\mathbf{b}_1, \dots, \mathbf{b}_{2d-\beta-1})$, then we can retrieve in polynomial time the full key by Babai nearest plane algorithm to lift it to a lattice vector of the desired norm. Hence it suffices to be able find the projection of the secret key among the shortest vector of the lattice generated by the last $\beta$ vectors projected onto $\mathcal{P}$. Classically, sieving on this projected lattice will recover all vectors of norm smaller than $\sqrt{\frac{4}{3}\ell}$, where $\ell$ is the norm of the $2d-\beta$-th Gram-Schmidt vector $\tilde{\mathbf{b}}_{2d-\beta}$ of the reduced basis.

The expected length of the projection is usually estimated under the *Geo-metric Series Assumption* (GSA). Instantiated on NTRU lattices, it states that the Gram-Schmidt vectors of the basis outputted by DBKZ with block-size $\beta$ satisfy the relations (see Cor. 2. of [28]):

$$ \|\tilde{\mathbf{b}}_i\| = \delta_{\beta}^{2(d-i)+1} \sqrt{q} \quad \text{where} \quad \delta_{\beta} = \left( \frac{(\pi\beta)^{1/\beta} \cdot \beta}{2\pi e} \right)^{\frac{1}{2(\beta-1)}}. $$

<footnote>$^{11}$ The Gaussian heuristic predicts the number of vectors of length at most $\ell$ in a random lattice $\Gamma$ of volume $V$ to be a $v_{\Gamma}(\ell)/V + o(1)$ for large enough $\ell$, where $v_{\Gamma}(\ell)$ is the volume of the sphere of radius $\ell$ for the measure induced by the inner product on $\Gamma$.</footnote>
Therefore, we expect that $\ell = \delta_{\beta}^{-2(d-\beta)+1} \sqrt{q} \approx \sqrt{q} \cdot \left(\frac{\beta}{2\pi e}\right)^{1-\frac{d}{\beta-1}}$. Moreover, assuming that $\mathbf{s}$ behaves as a random vector, and using the GSA to bound the norm of the Gram-Schmidt vectors $[\tilde{\mathbf{b}}_1, \dots, \tilde{\mathbf{b}}_{2d-\beta}]$, the (squared) norm of its projection over $\mathcal{P}$ concentrates around $\frac{\beta}{2d} \cdot \mathbb{E}[\|\mathbf{s}\|^2] = \frac{Aq\beta}{2d}$. Hence, we will retrieve the projection among the sieved vectors if $\frac{Aq\beta}{2d} \le \frac{4}{3}\ell^2$, that is if the following condition is fulfilled:

$$A \le \frac{8d}{3\beta} \delta_{\beta}^{4(\beta-d)+2}. \qquad (9)$$

**Remark 3.** (On the use of GSA) In order to make a more accurate assessment of potential attacks, numerical models of the profile of the Gram-Schmidt length derived from simulations of the behavior of (D)BKZ can be utilized instead of relying solely on the Gaussian heuristic approximation (GSA). While this section focuses on using the GSA for the purpose of simplifying the formulae and presenting the information in a clear manner, it is important to note that predictive models that generate a "Z-shaped" profile are employed in the estimation scripts.

(On the size of the enumeration window) In the previous description we only considered the space $\mathcal{P}$, orthogonal to span $(b_1, \dots, b_{2d-\beta-1})$. It is natural to want to extend its dimension, and choose the optimal one. It appears that for the specific parameters of our work, this optimization would only result in a difference of less than a single bit of security. Besides, on the one hand, by using the exact block size beta we can extract the vectors we need to sieve for free from the preliminary run of DBKZ, avoiding the need for an additional sieving pass. On the other hand, using a larger dimension for the additional sieving pass adds a non-negligible cost. Note that this is a consequence of the Core-SVP methodology, which we discuss in more length in Section 4.3 which ignores the polynomial overhead cost of (D)BKZ.

### 4.2.2 Towards a subfield attack.
Given the knowledge of the relative norm $M = ff^* + gg^*$, the structure of NTRU keys allows an attacker to determine both $ff^*$ and $gg^*$. Note that $(ff^*, gg^*)$ is in the NTRU lattice of $hh^*$ over the totally real subfield $\mathcal{K}^+$, meaning that $ff^* \cdot hh^* \equiv gg^*$ (mod $q$). Thus, we deduce that $gg^* = \frac{Mhh^*}{1+hh^*}$ mod $q$ and $fg^* = \frac{Mh^*}{1+hh^*}$ mod $q$ over $\mathcal{R}$ — a step we refer to as “algebra”. As observed in [19], since $f$ and $g$ are chosen to be co-prime, the attacker can recover a $\mathbb{Z}$-basis of the principal ideal $(g)$ in addition to $gg^*$ through a greatest common divisor computation between the ideals $(fg^*)$ and $(gg^*)$. The attacker can finally retrieve $g$ modulo units through the application of either the Gentry-Szydlo algorithm for power-of-two cyclotomic number fields or its extension for arbitrary cyclotomics, as demonstrated in the attack of Espitau et al. in [13].

Now if the attacker does not know the value of $M$ exactly, but has a fairly good approximation of it, the preliminary “algebra” can be replaced by lattice
reduction. Indeed, write $ff^* + gg^* = qN + E$ for a known$^{12}$ N and a small E, so that $(ff^*, gg^*, E)$ is a rather short solution of the linear system

$$ \begin{cases} HX - Y = 0 \mod q, \\ X + Y - E = qN, \end{cases} \qquad (10) $$

where $H = hh^*$. More precisely, this value would not correspond to an element of the ring $R$, but solving such a system amounts to finding a short vector inside the coset $(0, 0, qN) + \mathcal{L}$ (considered inside the extended NTRU lattice in $(\mathcal{K}^+)^3$ corresponding to $\{(u, v, w) | uH = v \pmod q\}$). A (row) basis of the lattice $\mathcal{L}$ corresponding to (10) is given by:

$$ L = \begin{pmatrix} 1 & H & H + 1 \\ 0 & q & q \end{pmatrix}. $$

and the most efficient known algorithms to solve this problem are essentially variations of lattice reduction and decoding (see for instance [16]), and amount in estimating the hardness of retrieving a vector of a given norm inside $\mathcal{L}$. We now give the details to find lower bound on the parameters of the key generation algorithm to make such attacks infeasible.

**Distribution of the relative norm vector.** We now want to estimate the expected length of $(ff^*, gg^*, E)$. By Corollary 1, we know already $\mathbb{E}[\|ff^*, gg^*\|^2]$. To determine the remaining term $\mathbb{E}[\|E\|^2]$, we must select a convenient value for $qN$. For this, fix an embedding $\varphi_\theta$, and let $(F, G) = (\varphi_\theta(ff^*), \varphi_\theta(gg^*))$ and $(\tilde{F}, \tilde{G}) = (|\varphi_\theta(\tilde{f})|^2, |\varphi_\theta(\tilde{g})|^2)$ as in Proposition 1, so that $\mathbb{E}[F + G] = \frac{d}{6} + \frac{R^2+r^2}{2}$. Since each embedding of $ff^* + gg^*$ averages around this (public!) value, we conveniently choose it for $qN$. From $ff^* + gg^* - qN = E$ and the definition of the variance, we obtain $\mathbb{E}[\|E\|^2] = \mathrm{Var}[F + G]$. It follows that (see the full version of this paper for details [17]):

$$ \begin{aligned} \mathbb{E}[\|E\|^2] &= \mathrm{Var}\left[\frac{d}{6} + \tilde{F} + \tilde{G}\right] + \mathbb{E}\left[\frac{d}{12}\left(\frac{d}{6} + 2\tilde{F} + 2\tilde{G}\right)\right] \\ &= \frac{(R^2 - r^2)^2}{12} + \frac{d}{12}(R^2 + r^2) + \frac{d^2}{72}. \end{aligned} $$

For convenience in the next paragraphs, we write $\mathbb{E}[\|ff^*, gg^*\|^2] = 2q^2x$ and $\mathbb{E}[\|E\|^2] = q^2y$, then:

$$ x \cdot q^2 = \frac{5}{16}(R^4 + r^4) + \frac{1}{2}(R \cdot r)^2 + \frac{d}{12}(R^2 + r^2) + \frac{d^2}{72}, $$

$$ y \cdot q^2 = \frac{1}{12}(R^2 - r^2)^2 + \frac{d}{12}(R^2 + r^2) + \frac{d^2}{72}. $$

<footnote>$^{12}$ A typical “known” N would be the radius of a well-chosen circle inside the annulus. This value would not correspond to a ring element in general, but one can reduce to this case in a similar way as SIS and ISIS relate.</footnote>
Mounting the lattice attack. In order to find a short solution for the system in Equation (10), it is known that $\|ff^*\|^2$ and $\|gg^*\|^2$ approximate to $xq^2$ and $\|E\|^2$ concentrates to $yq^2$. This results in the vector $(ff^*, gg^*, E)$ being unbalanced with the first two coefficients being significantly larger than the third one. To address this issue, we can utilize a technique similar to the rescaling approach proposed in [4, 18].

It has been observed that in the estimation procedure outlined in Section 4.2.1, the ratio of the length of the secret vector to the normalized volume of the lattice is the only relevant quantity. As such, we can run the same attack under any quadratic twist of the norm of the lattice, by replacing the $l_2$ norm with any quadratic form of determinant 1, and selecting the one that minimizes the desired ratio. By following the proof technique in [18], we can restrict ourselves to quadratic forms corresponding to diagonal matrices.

Therefore, to view the corresponding lattice problem in a more suitable manner, we want to analyze it under the twisted (Euclidean) norm encoded by the Gram matrix (clearly of determinant 1) $G_\eta = \text{diag}(\eta, \eta, 1/\eta^2)$ with for $\eta = (\frac{y}{x})^{\frac{1}{3}}$. Then under this new norm $\|\cdot\|_\eta$, we find that:

$$ \mathbb{E} \left[ \|(ff^*, gg^*, E)\|_{\eta}^2 \right] = \eta \mathbb{E} \left[ \|(ff^*)^2\| \right] + \eta \mathbb{E} \left[ \|gg^*\|^2 \right] + \frac{\mathbb{E} \left[ \|E\|^2 \right]}{\eta^2} = 3q^2 (x^2 y)^{\frac{1}{3}}. $$

Under this norm the lattice $\mathcal{L}$ has $\mathcal{K}^+$-volume:

$$ \det(LG_{\eta}L^T) = \left| \begin{bmatrix} \eta H^2 + \eta + \frac{(H+1)^2}{\eta^2} & \eta H q + \frac{(H+1)q}{\eta^2} \\ \eta H q + \frac{(H+1)q}{\eta^2} & \eta q^2 + \frac{q^2}{\eta^2} \end{bmatrix} \right| = q^2 \left( \eta^2 + \frac{2}{\eta} \right), $$

giving a lattice of normalized volume being $\sqrt{q}(\eta^2 + \frac{2}{\eta})^{\frac{1}{4}}$ as of $\mathcal{K}^+$-rank 2. The attack is then similar as the one in Section 4.2.1 but where we want to recover a vector of squared norm $3q^2(x^2y)^{\frac{1}{3}}$ in a $\mathbb{Z}$-lattice<fnref n="13" /> of normalized (squared) volume $2q(\eta^2 + \frac{1}{\eta})^{\frac{1}{2}}$ of rank $2^{\frac{d}{2}} = d$, yielding a condition of the form:

$$ \frac{\beta}{d} 3q^2 (x^2 y)^{\frac{1}{3}} \le 2q \left( \eta^2 + \frac{2}{\eta} \right)^{\frac{1}{2}} \delta_{\beta}^{2(2\beta-d+1)} \quad (11) $$

simplifying into:

$$ q \le \frac{2d}{3\beta} \sqrt{\frac{y+2x}{x^2 y}} \delta_{\beta}^{2(2\beta-d+1)}. $$

### 4.2.3 Further optimizations.
Beyond the projection trick and the rescaling, we can apply a final standard optimization to this lattice reduction part as there is an unbalance between the size of the secret vector we want to recover and the normalized volume of the lattice. Instead of working with the full lattice coming from the descent of $\mathcal{L}$ over $\mathbb{Z}$, we can instead consider the lattice spanned by a

<footnote n="13">¹³ The factor 2 accounting here for the normalized discriminant of the totally real subfield.</footnote>
subset of the vectors of the public basis and perform the decoding within this sublattice. The only interesting subset seems to consist in forgetting the $k \le \frac{d}{2}$ first vectors (dropping the so-called q-vectors would not be beneficial as it would actually sparsify the lattice, making the attack worst). Doing so, the rank is of course reduced by $k$, at the cost of working with a lattice with covolume proportionally $q^{\frac{k}{2(d-k)}}$ bigger. The condition of (11) updates into<fnref n="14" />:

$$ \frac{\beta(d-k)}{(d-k)d} 3q^2 (x^2 y)^{\frac{1}{3}} \le 2q^{\frac{n}{2n-2k}} \left( \eta^2 + \frac{2}{\eta} \right)^{\frac{1}{2}} \delta_{\beta}^{2(2\beta-d+k+1)}, $$

for all $k \in \{0, \dots, \frac{d}{2}\}$, which in turn simplifies to:

$$ q \le \min_{0 \le k \le \frac{n}{2}} \left( \frac{2d}{3\beta} \sqrt{\frac{y+2x}{x^2 y}} \delta_{\beta}^{2(2\beta-d+1)} \right)^{\frac{2n-2k}{n-2k}}. \quad (12) $$

The right-hand-side term increases as $y$ becomes smaller making the attack easier and easier, recovering the intuition presented that knowing exactly the value of $f f^* + g g^*$) leads to a complete key recovery in polynomial time. However, because of the rounding to the ring of integer this term cannot be 0: it converges to a term which is greater than $\frac{d^2}{72} + \frac{dq}{6}$. Thus, the condition is never satisfied for cryptographically relevant parameters.

**Remark 4 (On other subfield type attacks and related).** We can also approach the problem as solving a noisy-ring SIS instance (namely $(1+H)F = N+E$ (mod $q$)) or as solving a NTRU instance with a hint, in the spirit of [8]). In both cases, we are in fine decoding a lattice point at distance $\|E\|$ inside a lattice of normalized volume comparable to $q$. Up to some minor unessential constants, all three approaches give comparable results.

It is tempting to go further and try projection to other subfields, but the ratio secret size to normalized volume is increasing, worsening the attack. It indicates that we shall only focus on the plain NTRU and on the totally real subfield.

## 4.3 Practical security assessment

This analysis translates into concrete bit-security estimates following the methodology of NEWHOPE [2] (so-called “core-SVP methodology”). In this model [5], the bit complexity of lattice sieving (which is asymptotically the best SVP oracle) is taken as $\lfloor 0.292\beta \rfloor$ in the classical setting and $\lfloor 0.259\beta \rfloor$ in the quantum setting in dimension $\beta$. Using the analysis presented, we can tailor the radius $\alpha$ of the final annulus to match the desired security level (NIST-I and NIST-V). The size of the signature is then derived similarly as in [18].

<footnote n="14">¹⁴ This assumes the coefficients of $s$ are balanced, which is a reasonable assumption after the rescaling by $\eta$.</footnote>
4.4 Extension to more general cyclotomic rings

As discussed at the beginning of this section, the analysis so far has concentrated
on base fields $\mathcal{K}$ that are cyclotomic with power-of-two conductor for the sake of
simplicity, but it extends with relatively few changes to a more general setting.
Specifically, in the full version of this paper [17], we show that both the success
probability estimates and the security analysis carry over to cyclotomic conduc-
tors of the form $m = 2^\ell p^k$ for some odd prime $p$. This setting encompasses in
particular the case of 3-smooth conductors $m = 2^\ell 3^k$ for which parameters are
proposed in the MITAKA paper [15] (and for which we also propose parameters
below), and provides plenty of leeway to reach essentially any desired security
level.<fnref n="15" />

While the analysis in this more general setting closely mimics the one pre-
sented so far, we briefly highlight the ways in which it does differ. The key change
is that, for these conductors, the covariance matrix in Heuristic 1 is no longer
scalar, making the estimation of the meaningful quantities more subtle. We give
a high-level description of the situation here, referring to the full version of this
paper [17] for details.

First, for the success probability of Algorithm 5, the conditional distribution
of the embeddings of (f, g) becomes the sum of two non-central $\chi^2$ distributions
with different scaling parameters, each corresponding to the eigenvalues $\lambda_+^\theta, \lambda_-^\theta$
of $\Sigma_\theta$. This complicates the analysis somewhat, but counterparts to the results
of Section 4.1 can still be obtained, either through numerical computations or
by upper and lower bounding $\Sigma_\theta$ by scalar matrices independent of $\theta$.

Second, regarding the security analysis with respect to key recovery attacks,
the length of the secret keys is also impacted by the additional error term $T(\theta)$
in Proposition 1. Qualitatively speaking, the behavior in the case $m = 2^\ell p^k$ is
however quite close to the power-of-two case, since for most embeddings, $|S(\theta)| =$
$|\frac{\sin(d\theta)}{\sin\theta}|$ is small compared to $d$: only a handful of embeddings have a phase $\theta$
close to a multiple of $\pi$. We use the worst of these embeddings to bound from
above the magnitude of $T(\theta)$, and find that even this pessimistic estimate only
has negligible impact on the security level. Lastly, while we could rely on the
identity $d\|x\|^2 = \|\varphi(x)\|^2$ in the power-of-two case, this is not true anymore for
general conductors; we rely on upper bounds instead. Nevertheless, the geometry
of the power basis for 3-smooth conductors remains quite good, acting at worst
as an additional $\sqrt{2}$ factor.

<footnote n="15">¹⁵ One could in principle generalize the analysis even further (e.g., to arbitrary cyclo-
tomic conductors), but this would introduce additional technicalities (such as the
need to replace the power basis by the so-called powerful basis in order to obtain a
well-behaved matrix for the canonical embedding), and would really be of theoretical
interest at best.</footnote>
# 5 ANTRAG in practice

## 5.1 Optimization and parameter selection

In [18] new techniques to compress lattice-based hash-then-sign schemes were presented. Theoretically, they can all be applied to ANTRAG's signatures as well. One of these technique is a fine-tuned encoding approach for discrete Gaussian vectors, and is oblivious to the actual structure of the secret keys — we thus consider it done by default when estimating the bit size of signatures. The two other techniques are choosing a smaller modulus $q$ than the popular choice $q = 12289$ on the one hand, and elliptical sampling on the other hand. They have more impact on the key generation step, and although they were shown somewhat equivalent when applied to scheme such as FALCON or MITAKA, the situation is different for ANTRAG.

We first discuss smaller moduli. From our analysis in Section 3 and Section 4, the annulus where candidate pairs are sampled becomes relatively smaller as $q$ decreases, which noticeably impacts the success probability of Algorithm 5. To keep a small rejection rate in practice, we are led to decrease the quality of the key pairs, or in other words, to use a larger parameter $\alpha$. Fortunately, it was pointed out in [18] that there is a range for such smaller $q$ where, at fixed dimension, the key recovery becomes harder. This actually means that reducing $q$ and increasing $\alpha$ does not necessarily translate to a substantially lower security level. We note however that $q$ cannot be chosen arbitrarily small, as attacks exist for very small $q$.

The situation for elliptical sampling is less attractive for the following reason. Candidates should now be sampled in well-chosen elliptic annuli rather than circular ones. We can easily sample continuously uniformly in such annuli, but when carrying out the decoding back to the ring (e.g., by coefficient-wise rounding), we still incur an error term on embeddings that behaves like an isotropic normal distribution of standard deviation $\Omega(\sqrt{q})$. After the addition of the error term, embeddings sampled more towards the direction of the major axis of the ellipse are more likely than in a spherical case to end up in the target elliptical annulus, but embeddings sampled in the direction of the minor axis have much lower probability of success, and this has a much greater effect on overall success probability, constraining the choice of the quality parameter $\alpha$. In the end, we find that rather than using elliptical sampling in our setting with a certain skewing factor $\gamma$, it is essentially just as effective to reduce the modulus $q$ by the same factor $\gamma$ instead (which additionally has the advantage of reducing public key size). As a result, we omit the detailed analysis of this less attractive approach.

We present our parameter selection in Table 2 for power-of-two cyclotomics, and Table 3 for the 3-smooth case. For all parameter sets, we set the quality $\alpha$ with two decimal places in such a way as to reach a repetition rate $M$ of around 3 to 4. For the moduli, we give both the choices of $q$ found in the literature as well as smaller candidates that also have close to optimal splitting in the ambient ring, should one wish to rely on NTT multiplication to slightly speed up verification.
<table><caption>**Table 2.** Practical parameter selection, power-of-two case</caption><thead><tr><th rowspan="2">d</th><th colspan="2">q = 12289</th><th colspan="2">q = 3329</th></tr><tr><th>512</th><th>1024</th><th>512</th><th>1024</th></tr></thead><tbody><tr><td>Quality α</td><td>1.15</td><td>1.23</td><td>1.23</td><td>1.48</td></tr><tr><td>Repetition rate M</td><td>3</td><td>4</td><td>4</td><td>4</td></tr><tr><td>Bit security (C/Q)</td><td>124/113</td><td>264/240</td><td>121/110</td><td>265/240</td></tr><tr><td>Verification key size (bytes)</td><td>896</td><td>1792</td><td>768</td><td>1536</td></tr><tr><td>Signature size (bytes)</td><td>646</td><td>1260</td><td>591</td><td>1176</td></tr></tbody></table>

<caption>**Table 3.** Practical parameter selection for ANTRAG, 3-smooth conductor case.</caption>

(a) Modulus $q = 12289$

<table><thead><tr><th>d</th><th>648</th><th>768</th><th>864</th><th>972</th></tr></thead><tbody><tr><td>Quality α</td><td>1.17</td><td>1.19</td><td>1.21</td><td>1.22</td></tr><tr><td>Repetition rate M</td><td>4</td><td>3</td><td>3</td><td>4</td></tr><tr><td>Bit security (C/Q)</td><td>166/151</td><td>196/178</td><td>222/201</td><td>251/227</td></tr><tr><td>Verification key size (bytes)</td><td>1134</td><td>1344</td><td>1512</td><td>1701</td></tr><tr><td>Signature size (bytes)</td><td>808</td><td>952</td><td>1069</td><td>1200</td></tr></tbody></table>

(b) Various moduli. For $d = 768, 864, 972$, the right column shows moduli of [15].

<table><thead><tr><th rowspan="2">Modulus q</th><th colspan="2">d = 648</th><th colspan="2">d = 768</th><th colspan="2">d = 864</th><th colspan="2">d = 972</th></tr><tr><th>3889</th><th>9721</th><th>3329</th><th>18433</th><th>3727</th><th>10369</th><th>4373</th><th>17497</th></tr></thead><tbody><tr><td>Quality α</td><td>1.32</td><td>1.19</td><td>1.39</td><td>1.16</td><td>1.40</td><td>1.23</td><td>1.40</td><td>1.18</td></tr><tr><td>Expected repetitions</td><td>4</td><td>4</td><td>4</td><td>3</td><td>4</td><td>3</td><td>4</td><td>4</td></tr><tr><td>Bit security (C/Q)</td><td>159/144</td><td>164/149</td><td>192/174</td><td>195/177</td><td>220/200</td><td>222/201</td><td>254/230</td><td>250/227</td></tr><tr><td>Verification key size (bytes)</td><td>972</td><td>1134</td><td>1152</td><td>1440</td><td>1296</td><td>1512</td><td>1580</td><td>1823</td></tr><tr><td>Signature size (bytes)</td><td>747</td><td>796</td><td>883</td><td>977</td><td>1000</td><td>1058</td><td>1133</td><td>1225</td></tr></tbody></table>

## 5.2 Implementation results

We have implemented our trapdoor generation algorithm ANTRAG as well as the resulting complete signature scheme in portable C based on the source codes of FALCON and MITAKA. The code is publicly available on GitHub [36].

Since the signature scheme arising from ANTRAG is essentially identical to MITAKA for signing and verification, we largely reuse the code of MITAKA for those parts. Key generation consists of the original algorithm presented in this paper to generate the first basis vector $(f, g)$, along with code to solve the NTRU equation in order to deduce $(F, G)$, for which we basically reuse the code of FALCON, which follows the techniques presented in [31]. The Fast Fourier transform and the resulting code for ring arithmetic are similarly borrowed from FALCON.

We note that, since the C code of MITAKA itself did not include a key generation algorithm (only precomputed fixed keys obtained using separate Python scripts), our implementation constitutes, to the best of our knowledge, the first full C implementation of a hybrid sampler-based signature.

In view of the simplicity of our trapdoor generation, the code is fairly straightforward. In particular, since the floating point uniform distributions we generate
<table><caption>**Table 4.** Performance comparison with FALCON and MITAKA.</caption><thead><tr><th></th><th colspan="2">FALCON [34]</th><th colspan="2">MITAKA [15]</th><th colspan="2">This paper</th></tr><tr><th><i>d</i></th><th>512</th><th>1024</th><th>512</th><th>1024</th><th>512</th><th>1024</th></tr></thead><tbody><tr><td>Quality α</td><td>1.17</td><td>1.17</td><td>2.04</td><td>2.33</td><td>1.15</td><td>1.23</td></tr><tr><td>Classical sec.</td><td>123</td><td>284</td><td>102</td><td>233</td><td>124</td><td>264</td></tr><tr><td>Key size (bytes)</td><td>896</td><td>1792</td><td>896</td><td>1792</td><td>896</td><td>1792</td></tr><tr><td>Sig. size (bytes)</td><td>666</td><td>1280</td><td>713</td><td>1405</td><td>646</td><td>1260</td></tr><tr><td><i>keygen</i> speed (Mcycles)</td><td>—</td><td>—</td><td>—</td><td>—</td><td>9.5</td><td>33.2</td></tr><tr><td><i>keygen</i> speed (ms)</td><td>4.2</td><td>12.4</td><td>1657<sup>*</sup></td><td>6214<sup>*</sup></td><td>3.5</td><td>12.3</td></tr><tr><td><i>sign</i> speed (kcycles)</td><td>—</td><td>—</td><td>299</td><td>584</td><td>298</td><td>586</td></tr><tr><td><i>sign</i> speed (μs)</td><td>184</td><td>371</td><td>111</td><td>217</td><td>111</td><td>218</td></tr><tr><td><i>verif</i> speed (kcycles)</td><td>—</td><td>—</td><td>20</td><td>41</td><td>20</td><td>40</td></tr><tr><td><i>verif</i> speed (μs)</td><td>18</td><td>36</td><td>8</td><td>16</td><td>8</td><td>15</td></tr></tbody></table>

for the absolute values of the embeddings are bounded away from zero, there is no subtlety related to precision loss for values close to zero (this is unlike the Box-Muller algorithm used in signing, for which we reuse MITAKA's code that behaves properly in that respect). The only trick worth mentioning is a check in the generation of $(f,g)$ which rejects early the pairs such that the cyclotomic integer prime above 2 divides both $f$ and $g$ (this is a necessary condition for the later computation of $F$ and $G$ to succeed, so it saves some time to test it early).

As explained above, dimension 512 and 1024 are supported, and our GoodPair algorithm naturally extends to other conductors such as the 3-smooth cyclotomics considered in MITAKA to reach intermediate dimensions, as well as the signing and verification procedure. However, suitably optimized FFT code is needed for those intermediate rings, and more importantly, the NTRUSolve code of [31] needs to be adapted as well, in the spirit of, e.g., [27]. Neither of those steps are difficult in principle, but they represent a significant engineering effort left as future work.

A performance comparison with FALCON and MITAKA is provided in Table 4, using the same modulus $q = 12289$ for consistency. Compilation is carried out with gcc 13.2.1 with -O3 -march=native optimizations enabled. Timings are collected on a single core of an AMD Ryzen 7 PRO 6860Z @ 2.7 GHz laptop with hyperthreading and frequency scaling disabled. Cycle counts are not provided for FALCON, since the FALCON benchmarking tool only measures clock time.

As noted previously, the MITAKA C implementation does not include a key generation procedure. For reference, we provide the timings for the numpy-based SageMath implementation of the MITAKA key generation procedure instead, not including the cost of NTRUSolve, so that only the highly optimized GoodPair code is accounted for. As expected from the fact that MITAKA needs to explore

<footnote>* Timings for the optimized SageMath implementation (excluding NTRUSolve), since no C implementation exists.</footnote>
a search space of millions of key candidates, the timings are orders of magnitude worse than FALCON and ANTRAG.

The running time of our key generation is close to that of FALCON. Signing speeds are basically identical to MITAKA since we mostly reuse that code (up to very minor optimizations). Verification is consistent across all three schemes.

## Acknowledgments

We are indebted to Léo Ducas for the idea of the attack considered in Section 4.2.2, and for invaluable comments and discussions. We thank anonymous reviewers for numerous comments and suggestions for improvement.

Chao Sun was supported by the project "Research and development on IoT malware removal / make it non-functional technologies for effective use of the radio spectrum" among "Research and Development for Expansion of Radio Wave Resources (JPJ000254)", which was supported by the Ministry of Internal Affairs and Communications, Japan. Thi Thu Quyen Nguyen and Alexandre Wallet were supported by PEPR quantique France 2030 programme (ANR-22-PETQ-0008) and by the ANR ASTRID project AMIRAL (ANR-21-ASTR-0016).

## References

1. Albrecht, M.R., Bai, S., Ducas, L.: A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 153-178. Springer, Heidelberg (Aug 2016).

2. Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - A new hope. In: Holz, T., Savage, S. (eds.) USENIX Security 2016. pp. 327-343. USENIX Association (Aug 2016)

3. Annamalai, A., Tellambura, C.: Cauchy-Schwarz bound on the generalized Marcum-Q function with applications. Wireless Communications and Mobile Computing 1(2), 243-253 (2001)

4. Bai, S., Galbraith, S.D.: Lattice decoding attacks on binary LWE. In: Susilo, W., Mu, Y. (eds.) ACISP 14. LNCS, vol. 8544, pp. 322-337. Springer, Heidelberg (Jul 2014).

5. Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 27th SODA. pp. 10-24. ACM-SIAM (Jan 2016).

6. Cheon, J.H., Jeong, J., Lee, C.: An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero. LMS Journal of Computation and Mathematics 19, 255-266 (2016)

7. Chuengsatiansup, C., Prest, T., Stehlé, D., Wallet, A., Xagawa, K.: ModFalcon: Compact signatures based on module-NTRU lattices. In: Sun, H.M., Shieh, S.P., Gu, G., Ateniese, G. (eds.) ASIACCS 20. pp. 853-866. ACM Press (Oct 2020).

8. Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: Attacks and concrete security estimation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 329-358. Springer, Heidelberg (Aug 2020).
9. Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 22–41. Springer, Heidelberg (Dec 2014).

10. Ducas, L., Nguyen, P.Q.: Learning a zonotope and more: Cryptanalysis of NTRUSign countermeasures. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 433–450. Springer, Heidelberg (Dec 2012).

11. Ducas, L., Prest, T.: A hybrid Gaussian sampler for lattices over rings. Cryptology ePrint Archive, Report 2015/660 (2015), https://eprint.iacr.org/2015/660

12. Ducas, L., Prest, T.: Fast Fourier orthogonalization. In: Abramov, S.A., Zima, E.V., Gao, X. (eds.) ISSAC 2016. pp. 191–198. ACM (2016)

13. Espitau, T., Fouque, P.A., Gérard, B., Tibouchi, M.: Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017. pp. 1857–1874. ACM Press (Oct / Nov 2017).

14. Espitau, T., Fouque, P.A., Gérard, F., Rossi, M., Takahashi, A., Tibouchi, M., Wallet, A., Yu, Y.: Mitaka: a simpler, parallelizable, maskable variant of falcon. Cryptology ePrint Archive, Report 2021/1486 (2021), https://eprint.iacr.org/2021/1486

15. Espitau, T., Fouque, P.A., Gérard, F., Rossi, M., Takahashi, A., Tibouchi, M., Wallet, A., Yu, Y.: Mitaka: A simpler, parallelizable, maskable variant of falcon. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. LNCS, vol. 13277, pp. 222–253. Springer, Heidelberg (May / Jun 2022).

16. Espitau, T., Kirchner, P.: The nearest-colattice algorithm. Cryptology ePrint Archive, Report 2020/694 (2020), https://eprint.iacr.org/2020/694

17. Espitau, T., Nguyen, T.T.Q., Sun, C., Tibouchi, M., Wallet, A.: Antrag: Annular NTRU trapdoor generation. Cryptology ePrint Archive, Paper 2023/1335 (2023), https://eprint.iacr.org/2023/1335, https://eprint.iacr.org/2023/1335

18. Espitau, T., Tibouchi, M., Wallet, A., Yu, Y.: Shorter hash-and-sign lattice-based signatures. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part II. LNCS, vol. 13508, pp. 245–275. Springer, Heidelberg (Aug 2022).

19. Fouque, P.A., Kirchner, P., Tibouchi, M., Wallet, A., Yu, Y.: Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part III. LNCS, vol. 12107, pp. 34–63. Springer, Heidelberg (May 2020).

20. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC. pp. 197–206. ACM Press (May 2008).

21. Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (Apr / May 2002).

22. Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO'97. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (Aug 1997).

23. Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSIGN: Digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (Apr 2003).

24. Lyubashevsky, V.: Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (Dec 2009).
25. Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (Apr 2012).

26. Lyubashevsky, V., Ducas, L., Kiltz, E., Lepoint, T., Schwabe, P., Seiler, G., Stehlé, D., Bai, S.: CRYSTALS-DILITHIUM. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

27. Lyubashevsky, V., Seiler, G.: NTTRU: Truly fast NTRU using NTT. IACR TCHES 2019(3), 180–201 (2019). https://tches.iacr.org/index.php/TCHES/article/view/8293

28. Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 820–849. Springer, Heidelberg (May 2016).

29. Nguyen, P.Q., Regev, O.: Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 271–288. Springer, Heidelberg (May / Jun 2006).

30. Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (Aug 2010).

31. Pornin, T., Prest, T.: More efficient algorithms for the NTRU key generation using the field norm. In: Lin, D., Sako, K. (eds.) PKC 2019, Part II. LNCS, vol. 11443, pp. 504–533. Springer, Heidelberg (Apr 2019).

32. Prest, T.: Gaussian Sampling in Lattice-Based Cryptography. Ph.D. thesis, École Normale Supérieure, Paris, France (2015)

33. Prest, T., Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: FALCON. Tech. rep., National Institute of Standards and Technology (2017), available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions

34. Prest, T., Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: FALCON. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

35. Simon, M., Alouini, M.S.: Exponential-type bounds on the generalized Marcum Q-function with application to error probability analysis over fading channels. IEEE Trans. Commun. 48(3), 359–366 (2000)

36. Tibouchi, M.: Companion implementation of this paper. GitHub repository mti/antrag (2023), https://github.com/mti/antrag