# HAETAE: Shorter Lattice-Based Fiat-Shamir Signatures

Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, Markus Krausz, Georg Land, Marc Möller, Damien Stehlé, Minjune Yi

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

## To cite this version:

Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, et al.: HAETAE: Shorter Lattice-Based Fiat-Shamir Signatures. Conference on Cryptographic Hardware and Embedded Systems - CHES2024, Sep 2024, Halifax, Canada. pp.25-75, 10.46586/tches.v2024.i3.25-75. hal-04909666

HAL Id: hal-04909666

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

Submitted on 24 Jan 2025

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

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

<figure><img src="image_2.png" /></figure>
# HAETAE: Shorter Lattice-Based Fiat-Shamir Signatures

Jung Hee Cheon<sup>1,2</sup>, Hyeongmin Choe<sup>1</sup>, Julien Devevey<sup>3</sup>, Tim Güneysu<sup>4,5</sup>, Dongyeon Hong<sup>6</sup>, Markus Krausz<sup>4</sup>, Georg Land<sup>4</sup>, Marc Möller<sup>4</sup>, Damien Stehlé<sup>7</sup> and MinJune Yi<sup>1</sup>

<sup>1</sup> Seoul National University, Seoul, Republic of Korea

jhcheon@snu.ac.kr, sixtail528@snu.ac.kr, yiminjune@snu.ac.kr

<sup>2</sup> CryptoLab Inc., Seoul, Republic of Korea

<sup>3</sup> ANSSI, Paris, France julien.devevey@ens-lyon.fr

<sup>4</sup> Ruhr University Bochum, Bochum, Germany firstname.lastname@rub.de, mail@georg.land

<sup>5</sup> DFKI, Bremen, Germany

<sup>6</sup> The Affiliated Institute of ETRI, Daejeon, Republic of Korea jjoker041@gmail.com

<sup>7</sup> CryptoLab Inc., Lyon, France damien.stehle@cryptolab.co.kr

**Abstract.** We present HAETAE (Hyperball bimodAl modulE rejecTion signAture schemE), a new lattice-based signature scheme. Like the NIST-selected Dilithium signature scheme, HAETAE is based on the Fiat-Shamir with Aborts paradigm, but our design choices target an improved complexity/compactness compromise that is highly relevant for many space-limited application scenarios. We primarily focus on reducing signature and verification key sizes so that signatures fit into one TCP or UDP datagram while preserving a high level of security against a variety of attacks. As a result, our scheme has signature and verification key sizes up to 39% and 25% smaller, respectively, compared than Dilithium. We provide a portable, constant-time reference implementation together with an optimized implementation using AVX2 instructions and an implementation with reduced stack size for the Cortex-M4. Moreover, we describe how to efficiently protect HAETAE against implementation attacks such as side-channel analysis, making it an attractive candidate for use in IoT and other embedded systems.

**Keywords:** Signature, Fiat-Shamir, Lattice-based Cryptography, Bimodal Distribution

## 1 Introduction

The rise of quantum computing has brought up – among others – the necessity of new, post-quantum digital signature schemes. In the standardization process of post-quantum cryptography by the American National Institute of Standards and Technology (NIST), the lattice-based schemes Falcon [FHK<sup>+</sup>18] and Dilithium [DKL<sup>+</sup>18] have already been announced as future standards, and another 40 new candidates are on-ramp for an additional process. The critical challenge in developing lattice-based digital signatures lies in finding a balance between security and practicality: while developing secure schemes against a wide range of attacks is essential, it is also vital to ensure they are practical for real-world applications. This challenge becomes even more critical with the increasing

This work is submitted to 'Korean Post-Quantum Cryptography Competition' (www.kpqc.or.kr) and 'NIST Post-Quantum Cryptography Standardization of Additional Digital Signature Schemes.'
<table><caption>**Table 1:** NIST security level, signature size, verification key size, and implementation security, with respect to constant-time and masking of selected signature schemes</caption><thead><tr><th>Scheme</th><th>Lvl.</th><th>Sig.</th><th>vk</th><th>Const.-time.</th><th>Maskable</th></tr></thead><tbody><tr><td>Falcon-512</td><td>1</td><td>666B</td><td>897B</td><td>✓ [Por19]</td><td>✗ [Pre23]</td></tr><tr><td>Dilithium-2</td><td>2</td><td>2,420B</td><td>1,312B</td><td>✓ [DKL<sup>+18</sup>]</td><td>✓ [MGTF19]</td></tr><tr><td>HAETAE-120</td><td>2</td><td>1,474B</td><td>992B</td><td>✓</td><td>✓</td></tr></tbody></table>

prevalence of embedded devices and the Internet of Things (IoT). Both technologies have become ubiquitous, from home appliances to medical devices connected to the internet.

In particular, this leads to two practical requirements:

1. The verification key and signature sizes must be as small as possible since both are frequently transmitted. Specifically, it is helpful if the signature is small enough to be sent in only one UDP or TCP datagram, as this minimizes the need for packet fragmentation. The importance of the signature and verification key sizes for communication protocols has been highlighted already in multiple evaluations [Wes21, PST20, GS23]. Paquin et al. [PST20] observe for TLS, that fragmentation over many packets has a significant performance impact for network links with non-ideal packet loss rates. Benchmarking DNSSEC [GS23] revealed, that the smaller signatures of Falcon lead to faster resolution times in comparison to Dilithium in most scenarios, although the signature computation and verification is much faster with Dilithium compared to Falcon.

2. The secret-dependent operations such as key generation and message signing must be easy to protect against implementation attacks. This is essential in embedded use cases like the IoT, where attackers have physical access and can measure power consumption or electromagnetic emanation [KA21], additionally to the timing behaviour [Sch00], which is also exploitable from remote.

In this context, Falcon fulfills the first requirement very well, but efforts for making it to satisfy the second requirement, namely Mitaka [EFG<sup>+22</sup>], were recently broken [Pre23]. Dilithium, on the other hand, focuses on being easy to implement and protecting against side-channel attacks. However, this comes at the sacrifice of larger signatures and verification keys, which, for example, do not allow a signature to fit in one UDP datagram. We summarize this discussion in Table 1 and compare the two with HAETAE.

**Contribution.** We present HAETAE<fnref n="1" />, a lattice-based digital signature scheme that improves over Dilithium by up to 39% smaller signature and key sizes. Moreover, this improvement is not expected to come at a significant increase in the cost to protect the scheme against physical attacks. Namely, the most significant difference (w.r.t. masking in comparison to Dilithium) is the usage of fix-point arithmetic which is similar to masking integers. Its quantum security is based on the hardness of the module versions of the lattice problems LWE and SIS [BGV12, LS15], in the Quantum Random Oracle Model (QROM). The scheme design follows the “Fiat-Shamir with Aborts” paradigm [Lyu09, Lyu12], which relies on rejection sampling: rejection sampling is used to transform a signature trial whose distribution depends on sensitive information, into a signature whose distribution can be publicly simulated.

HAETAE is in part inspired from Dilithium, a post-quantum “Fiat-Shamir with Aborts” signature scheme, notably concerning the use of the module LWE and SIS assumptions. HAETAE differs from Dilithium in two major aspects: (i) we use a bimodal distribution for the rejection sampling, like in the BLISS signature scheme [DDL13], instead of a

<footnote n="1">¹The haetae is a mythical Korean lion-like creature with the innate ability to distinguish right from wrong.</footnote>
“unimodal” distribution like Dilithium, (ii) we sample from and reject to hyperball uniform distributions, instead of discrete hypercube uniform distributions. The design departs from BLISS, as HAETAE relies on module lattice problems while BLISS relies either on assumptions on unstructured lattices or the NTRU assumption [HPS98]: this leads us to introduce a new key generation algorithm. A further difference is that BLISS, which can be seen as Dilithium with bimodal rejection from Gaussians, involves discrete Gaussian distributions whereas HAETAE considers hyperball uniform distributions as suggested in [DFPS22]. We recall from [DFPS22] that, with a rejection rate constraint, the choice of bimodal rejection sampling from the hyperballs results in the optimal signature sizes among the possible variants of Dilithium. This choice also allows for simple rejection sampling without transcendental function computation on the secret key and approximations for tail-cutting, while retaining the signature compactness.

HAETAE benefits from several novel improvements in the key generation algorithm. We introduce a new rejection procedure in the key generation algorithm to minimize the magnitude of the secret key when multiplied by the challenge. This facilitates rejection sampling in the signing algorithm and leads to smaller signatures. The key generation rejection is also designed to be efficient and simple to implement. It significantly improves over a procedure with a similar objective in the key generation of BLISS. Furthermore, we introduce to the bimodal setting a verification key truncation with the same objective as Dilithium’s. A direct adaptation would lead to large bounds for the verification algorithm and degraded security. Instead, we compensate for the verification key truncation by correcting the signing key accordingly. It increases the magnitude of the signing key, but by a much smaller amount than the naive approach.

For the signing algorithm, we adapt Dilithium’s signature compression so that it is compatible with our module lattices key generation algorithm, by taking into account the residues modulo 2. The main novelty in the signing algorithm is a detailed description of a fixed-point arithmetic algorithm for sampling uniformly in a discrete hyperball, which was left open in [DFPS22]. The discretization leads to numerical errors on the uniform distribution: we bound them and bound their effect on the scheme security. High precision is required during signing; however, by applying the entropy encoding technique from [ETWY22] to hyperball uniform distributions, the output signature of the signing algorithm becomes as compact as its entropy, which is much smaller than Dilithium.

We present in Table 2 a brief comparison between the main divergence points of Dilithium, HAETAE and BLISS. Most importantly, the choice of bimodal hyperballs in HAETAE does not need to compute a secret-dependent transcendental function during signature rejection, just like Dilithium, contrary to BLISS.

<table><caption>**Table 2:** Comparison between Dilithium, HAETAE and an hypothetical update of BLISS, obtained by interpolating our approach and BLISS’s approach of rejection sampling via bimodal Gaussians. Completely updating BLISS is out of the scope of this paper and left as future work. “Maybe” means that masking is doable using generic techniques, but optimized gadgets are not yet available.</caption><thead><tr><th></th><th>Dilithium</th><th>HAETAE</th><th>Updated BLISS</th></tr></thead><tbody><tr><td>Rejection Step</td><td>Deterministic</td><td>Deterministic</td><td>Probabilistic</td></tr><tr><td>Arithmetic</td><td>Integers</td><td>Fix-point</td><td>Fix-point</td></tr><tr><td>Maskable</td><td>Yes</td><td>Maybe</td><td>Maybe</td></tr><tr><td>Sizes</td><td>Long</td><td>Short</td><td>Similar to HAETAE</td></tr><tr><td>Additional primitives to implement w.r.t. Dilithium</td><td>N/A</td><td>○ Hyperball sampler<br>○ CRT for mod2q</td><td>○ Gaussian sampler<br>○ CRT for mod2q<br>○ Secure rejection step</td></tr></tbody></table>

**Implementation and Performance.** We propose three parameter sets with NIST
<table><caption>**Table 3:** Relative comparison between HAETAE, Dilithium, and Falcon. The security levels are given in the parameter sets instead of their name. The percentages are the ratio of their sizes and the execution times. The execution time is measured as the median cycle counts among 1000 executions, obtained on one core of an Intel Core i7-10700k, with TurboBoost and hyperthreading disabled.</caption><thead><tr><th>Parameter set</th><th>Sig. size</th><th>vk size</th><th>KeyGen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>HAETAE-2 / Dilithium-2</td><td>61%</td><td>76%</td><td>409%</td><td>507%</td><td>100%</td></tr><tr><td>HAETAE-3 / Dilithium-3</td><td>71%</td><td>75%</td><td>376%</td><td>444%</td><td>113%</td></tr><tr><td>HAETAE-5 / Dilithium-5</td><td>64%</td><td>80%</td><td>328%</td><td>454%</td><td>91%</td></tr><tr><td>HAETAE-2 / Falcon-1</td><td>221%</td><td>111%</td><td>3%</td><td>35%</td><td>365%</td></tr><tr><td>HAETAE-5 / Falcon-5</td><td>230%</td><td>116%</td><td>2%</td><td>30%</td><td>399%</td></tr></tbody></table>

security levels 2, 3 and 5. Each parameter set of HAETAE has 20-25% smaller verification key size and 29-39% shorter signatures than its counterpart in Dilithium. Based on our portable and constant-time reference implementation of HAETAE, the verification process is as fast as Dilithium's, while the resulting key generation and signing algorithm are up to five times slower than Dilithium's. Up to 80% of the signing time is consumed by the hyperball sampling. Thus, any improvement to this sampling would contribute greatly to the efficiency of HAETAE, an independent speedup to further optimizations. Nonetheless, our benchmarks indicated signing with HAETAE is still around three times faster than with Falcon (portable Falcon with emulated floating-point operations). We summarize the comparison results in Table 3.

We provide a detailed, implementation-oriented specification using Chinese Remainder Theorem (CRT) and Number-Theoretic Transform (NTT), which enables efficient implementation of HAETAE (Section 5). We additionally developed an optimized version using AVX2 instructions (Section 6), and an implementation for the Cortex-M4 (Section 7), where we explore stack reduction techniques.

Moreover, we observe that masking HAETAE against physical attacks is only slightly more complex than masking Dilithium, based on the similarity of the scheme design and the use of fixed-point arithmetic. One of the conceptual differences between HAETAE and Falcon (and their variants) regarding physical attacks is that HAETAE only needs Gaussian samples for secret-independent centers and standard deviations.

Finally, we note that like other Fiat-Shamir signatures, such as Schnorr signatures [Sch90], the randomized signing of HAETAE can take advantage of pre-computations. By sampling from the hyperball and pre-computing the message-independent components offline, the online signing phase of HAETAE is cut by factor five.

Our code is publicly available.

**Related Work.** An alternative approach to avoid leakage during the rejection step in Fiat-Shamir signatures based on lattices is to remove it altogether. A first approach is to flood what depends on the signature key in signatures by a much larger quantity. As shown in [ASY22], relying on the Rényi divergence for the security analysis allows to limit the amount of flooding. A concrete instantiation was recently proposed in [dPEK$^+$]. This however results in signature sizes that are much higher than ours. A second approach was recently given in [DPS23], which uses Gaussian convolutions to obtain signatures that can be simulated, without flooding nor rejection sampling. However, signing is more complex as it relies on sampling from large-dimensional integer Gaussian distribution with non-diagonal covariance matrices. Also, the signature sizes provided in [DPS23] are worse than ours for the smallest parameter set, and only marginally smaller for larger parameter sets. An extensive comparison of the recent lattice signatures can be found in Appendix A.
# 2 Preliminaries

Before introducing specific results adapted to the setting in HAETAE in Section 3 and the HAETAE scheme itself in Section 4, we start by defining notations used throughout this paper and recapitulate relevant fundamental works.

## 2.1 Notations

Matrices are denoted in bold font and upper case letters (e.g., $\mathbf{A}$), while vectors are denoted in bold font and lowercase letters (e.g., $\mathbf{y}$ or $\mathbf{z}_1$). The $i$-th component of a vector is denoted with subscript $i$ (e.g., $y_i$ for the $i$-th component of $\mathbf{y}$).

Every vector is a column vector. We denote concatenation between vectors by putting the rows below as $(\mathbf{u}, \mathbf{v})$ and the columns on the right as $(\mathbf{u}|\mathbf{v})$. We naturally extend the latter notation to concatenations between matrices and vectors (e.g., $(\mathbf{A}|\mathbf{b})$ or $(\mathbf{A}|\mathbf{B}))$.

We let $\lfloor y \rfloor$ be a rounding of $y \in \mathbb{R}$ to the nearest integer. We naturally extend the rounding notation to vectors and polynomials by applying it component-wise.

We let $\mathcal{R} = \mathbb{Z}[x]/(x^n + 1)$ be a polynomial ring where $n$ is a power of 2 integer and for any positive integer $q$ the quotient ring $\mathcal{R}_q = \mathbb{Z}[x]/(q, x^n + 1) = \mathbb{Z}_q[x]/(x^n + 1)$. We abuse notations and identify $\mathcal{R}_2$ with the set of elements in $\mathcal{R}$ with binary coefficients. We also let $\mathcal{R}_{\mathbb{R}} = \mathbb{R}[x]/(x^n + 1)$ be a polynomial ring over real numbers. For an integer $\eta$, we let $S_\eta$ denote the set of polynomials of degree less than $n$ with coefficients in $[-\eta, \eta] \cap \mathbb{Z}$. Given $\mathbf{y} = (\sum_{0 \le i < n} y_i x^i, \dots, \sum_{0 \le i < n} y_{nk-n+i} x^i)^\top \in \mathcal{R}^k$ (or $\mathcal{R}_{\mathbb{R}}^k$), we define its $\ell_2$-norm as the $\ell_2$-norm of the corresponding “flattened” vector $\|\mathbf{y}\|_2 = \|(y_0, \dots, y_{nk-1})^\top\|_2$.

Let $\mathcal{B}_{\mathcal{R},m}(r, \mathbf{c}) = \{\mathbf{x} \in \mathcal{R}_{\mathbb{R}}^m \| \mathbf{x} - \mathbf{c}\|_2 \le r\}$ denote the continuous hyperball with center $\mathbf{c} \in \mathcal{R}^m$ and radius $r > 0$ in dimension $m > 0$. When $\mathbf{c} = \mathbf{0}$, we omit it. Let $\mathcal{B}_{(1/N)\mathcal{R},m}(r, \mathbf{c}) = (1/N)\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r, \mathbf{c})$ denote the discretized hyperball with radius $r > 0$ and center $\mathbf{c} \in \mathcal{R}^m$ in dimension $m > 0$ with respect to a positive integer $N$. When $\mathbf{c} = \mathbf{0}$, we omit it. Given a measurable set $X \subseteq \mathcal{R}^m$ of finite volume, we let $U(X)$ denote the continuous uniform distribution over $X$. It admits $\mathbf{x} \mapsto \chi_X(\mathbf{x})/\mathrm{Vol}(X)$ as a probability density, where $\chi_X$ is the indicator function of $X$ and $\mathrm{Vol}(X)$ is the volume of the set $X$. For the normal distribution over $\mathbb{R}$ centered at $\mu$ with standard deviation $\sigma$, we use the notation $\mathcal{N}(\mu, \sigma)$.

For a positive integer $\alpha$, we define $r \bmod \alpha$ as the unique integer $r'$ in the range $[-\alpha/2, \alpha/2)$ satisfying the relation $r = r' \bmod \alpha$. We also define $r \bmod^+ \alpha$ as the unique integer $r'$ in the range $[0, \alpha)$ that satisfies $r = r' \bmod \alpha$. We denote the least significant bit of an integer $r$ with LSB($r$). We naturally extend this to integer polynomials and vectors of integer polynomials, by applying it component-wise.

For a sequence of real numbers $a_0, \dots, a_n$, we denote the $i$-th maximum as $\max_j^{i\text{-th}} a_j$.

## 2.2 Signatures

We briefly recall the formalism of digital signatures.

**Definition 1 (Digital Signature).** A signature scheme is a tuple of PPT algorithms (KeyGen, Sign, Verify) with the following specifications:

* KeyGen : $1^\lambda \to (\mathrm{vk}, \mathrm{sk})$ outputs a verification key $\mathrm{vk}$ and a signing key $\mathrm{sk}$;

* Sign : $(\mathrm{sk}, \mu) \to \sigma$ takes as inputs a signing key $\mathrm{sk}$ and a message $\mu$ and outputs a signature $\sigma$;

* Verify : $(\mathrm{vk}, \mu, \sigma) \to b \in \{0, 1\}$ is a deterministic algorithm that takes as inputs a verification key $\mathrm{vk}$, a message $\mu$, and a signature $\sigma$ and outputs a bit $b \in \{0, 1\}$.
Let $\gamma > 0$. We say that it is $\gamma$-correct if for any pair $(vk, sk)$ in the range of KeyGen and $\mu$,

$$ \Pr[\text{Verify}(vk, \mu, \text{Sign}(sk, \mu)) = 1] \geq \gamma, $$

where the probability is taken over the random coins of the signing algorithm. We say that it is correct in the (Q)ROM if the above holds when the probability is also taken over the randomness of the random oracle modeling the hash function used in the scheme.

We also give two security notions, namely the existential unforgeability under chosen message attacks, and under no-message attacks.

**Definition 2 (Security).** Let $T, \delta \geq 0$. A signature scheme sig = (KeyGen, Sign, Verify) is said to be (T, δ)-UF-CMA secure in the QROM if for any quantum adversary A with runtime $\leq T$ given (classical) access to the signing oracle and (quantum) access to a random oracle H, it holds that

$$ \Pr_{(vk,sk)}[\text{Verify}(vk, \mu^*, \sigma^*) = 1 | (\mu^*, \sigma^*) \leftarrow \mathcal{A}^{H,\text{Sign}}(vk)] \leq \delta, $$

where the randomness is taken over the random coins of A and $(vk, sk) \leftarrow \text{KeyGen}(1^\lambda)$. The adversary should also not have issued a sign query for $\mu^*$. The above probability of forging a signature is called the advantage of A and denoted by $\text{Adv}_{\text{sig}}^{\text{UF-CMA}}(A)$. If A does not output anything, then it automatically fails.

Existential unforgeability against no-message attack, denoted by UF-NMA is defined similarly except that the adversary is not allowed to query any signature per message. Strong existential unforgeability, denoted by sUF-CMA, allows an adversary to query signatures for its target message, as long as it does not output a queried signature.

## 2.3 Lattice Assumptions

We first recall the well-known lattice assumptions MLWE and MSIS on algebraic lattices.

**Definition 3 (Decision-MLWE$_{n,q,k,l,\eta}$).** For positive integers $q, k, l, \eta$ and the dimension $n$ of $\mathcal{R}$, we say that the advantage of an adversary $\mathcal{A}_1$ solving the decision-MLWE$_{n,q,k,l,\eta}$ problem is

$$ \text{Adv}_{n,q,k,l,\eta}^{\text{MLWE}}(\mathcal{A}_1) = \left| \Pr[b=1 | \mathbf{A} \leftarrow \mathcal{R}_q^{k \times l}; \mathbf{b} \leftarrow \mathcal{R}_q^k; b \leftarrow \mathcal{A}_1(\mathbf{A}, \mathbf{b})] - \Pr[b=1 | \mathbf{A} \leftarrow \mathcal{R}_q^{k \times l}; (\mathbf{s}_1, \mathbf{s}_2) \leftarrow \mathcal{S}_\eta^l \times \mathcal{S}_\eta^k; b \leftarrow \mathcal{A}_1(\mathbf{A}, \mathbf{A}\mathbf{s}_1 + \mathbf{s}_2)] \right| $$

**Definition 4 (Search-MSIS$_{n,q,k,l,\beta}$).** For positive integers $q, k, l$, a positive real number $\beta$ and the dimension $n$ of $\mathcal{R}$, we say that the advantage of an adversary $\mathcal{A}_2$ solving the search-MSIS$_{n,q,k,l,\beta}$ problem is

$$ \text{Adv}_{n,q,k,l,\beta}^{\text{MSIS}}(\mathcal{A}_2) = \Pr \left[ \begin{array}{l} 0 < \|\mathbf{y}\|_2 < \beta \land \\ (\mathbf{A} | \mathbf{I} \mathbf{d}_k) \cdot \mathbf{y} = 0 \mod q \end{array} \middle| \mathbf{A} \leftarrow \mathcal{R}_q^{k \times l}; \mathbf{y} \in \mathcal{R}_q^{k+l} \leftarrow \mathcal{A}_2(\mathbf{A}) \right]. $$

Moreover, we finally introduce a variant of the SelfTargetMSIS problem introduced in Dilithium [DKL+18], which corresponds to our setting.

**Definition 5 (BimodalSelfTargetMSIS$_{H,n,q,k,l,\beta}$).** Let $H: \{0,1\}^* \times \mathcal{M} \to \mathcal{R}_2$ be a cryptographic hash function, where $\mathcal{M} \subseteq \{0,1\}^*$ is a message space. Let $q, k, l > 0$, $\beta \geq 0$ and the dimension $n$ of $\mathcal{R}$. An adversary $\mathcal{A}_3$ solving the search-BimodalSelfTargetMSIS$_{H,n,q,k,l,\beta}$
problem with respect to $\mathbf{j} \in \mathcal{R}_2^k \setminus \{0\}$ has an advantage of

$$ \mathrm{Adv}_{H,n,q,k,l,\beta}^{\mathrm{BimodalSelfTargetMSIS}}(\mathcal{A}_3) = \mathrm{Pr} \left[ \begin{array}{l} 0 < \|\mathbf{y}\|_2 < \beta \wedge \\ H(\mathbf{A}\mathbf{y} - q\mathbf{c}\mathbf{j} \bmod 2q, \mu) = c \\ (\mathbf{A}_0|\mathbf{b}) \leftarrow \mathcal{R}_q^{k \times l}; \\ \mathbf{A} = (2\mathbf{b} + q\mathbf{j} | 2\mathbf{A}_0 | 2\mathbf{I}\mathbf{d}_k) \bmod 2q; \\ (\mathbf{y}, c, \mu) \in \mathcal{R}_q^{k+l} \times \mathcal{R}_2 \times \mathcal{M} \leftarrow \mathcal{A}_3^{|H(\cdot)|}(\mathbf{A}) \end{array} \right]. $$

In the ROM (resp. QROM), the adversary is given classical (resp. quantum) access to $H$.

The following classical reduction from MSIS to BimodalSelfTargetMSIS is very similar to the reduction from MSIS to SelfTargetMSIS introduced in [DKL+18] and is similarly non-tight. As this latter reduction, it cannot be straightforwardly extended to a reduction in the QROM, since it relies on the forking lemma.

**Theorem 1 (Classical Reduction from MSIS to BimodalSelfTargetMSIS).** Let $q > 0$ be an odd modulus, $H: \{0, 1\}^* \times \mathcal{M} \to \mathcal{R}_2$ be a cryptographic hash function modeled as a random oracle and that every polynomial-time classical algorithm has a negligible advantage against $\mathrm{MSIS}_{n,q,k,l,\beta}$. Then every polynomial-time classical algorithm has negligible advantage against $\mathrm{BimodalSelfTargetMSIS}_{n,q,k,l,\beta/2}$.

*Proof sketch.* Consider a BimodalSelfTargetMSIS$_{n,q,k,l,\beta/2}$ classical algorithm $\mathcal{A}$ that is polynomial-time and has classical access to $H$. If $\mathcal{A}^{H(\cdot)}(\mathbf{A})$ makes $Q$ hash queries $H(\mathbf{w}_i, \mu_i)$ for $i = 1, \dots, Q$ and outputs a solution $(\mathbf{y}, c, \mu_j)$ for some $j \in [Q]$, then we can construct an adversary $\mathcal{A}'$ for $\mathrm{MSIS}_{n,q,k,l,\beta}$ as follows.

The adversary $\mathcal{A}'$ can first rewind $\mathcal{A}$ to the point at which the $j$-th query was made and reprogram the hash as $H(\mathbf{w}_j, \mu_j) = c'(\neq c)$. Then, with probability approximately $1/Q$, algorithm $\mathcal{A}$ will produce another solution $(\mathbf{y}', c', \mu_j)$. We then have

$$ \left\{ \begin{array}{l} \mathbf{A}\mathbf{y} - q\mathbf{c}\mathbf{j} = \mathbf{z}_j = \mathbf{A}\mathbf{y}' - q\mathbf{c}'\mathbf{j} \bmod 2q, \\ \|\mathbf{y}\|_2, \|\mathbf{y}'\|_2 < \beta/2. \end{array} \right. $$

As $q$ is odd, we have $\mathbf{A}(\mathbf{y} - \mathbf{y}') = (c - c')\mathbf{j} \bmod 2$. The fact that $c' \neq c$ implies that the latter is non-zero modulo 2, and hence so is $\mathbf{y} - \mathbf{y}'$ over the integers. As it also satisfies $(\mathbf{b}|\mathbf{A}_0|\mathbf{I}\mathbf{d}_k) \cdot (\mathbf{y} - \mathbf{y}') = 0 \bmod q$ and $\|\mathbf{y} - \mathbf{y}'\| < \beta$, it provides a $\mathrm{MSIS}_{n,q,k,l,\beta}$ solution for the matrix $(\mathbf{b}|\mathbf{A}_0|\mathbf{I}\mathbf{d}_k)$, where the submatrix $(-\mathbf{b}|\mathbf{A}_0) \in \mathcal{R}_q^{k \times l}$ is uniform. $\square$

## 2.4 Sampling from the Continuous Hyperball-uniform

In order to sample in practice from hyperball uniform, we rely on the following result.

<figure><img src="image_3.png" /><figcaption>**Figure 1:** Hyperball uniform sampling</figcaption></figure>

**Lemma 1** ([VGS17]). The distribution of the output of the algorithm in Figure 1 is $U(\mathcal{B}_{\mathcal{R},k}(r))$.
Sampling from continuous hyperball-uniform can be done using the algorithm in Figure 1 due to Lemma 1. However, to allow side-channel secure implementations of HAETAE, we sample from discrete hyperball-uniform. We delay to Section 3.2 the analysis of a discretized version which turns discrete Gaussian samples to discrete hyperball-uniform distribution.

## 2.5 Signature Encoding via Range Asymmetric Numeral System

A HAETAE signature is essentially a vector $z$, that is compressed into $z_2$ with smaller dimension and a hint $h$, that are then encoded. While Huffman coding would be applied on each coordinate at a time, an arithmetic coding encodes the entire vector coordinates in a single number. In contrast to Huffman coding, arithmetic coding gets close to entropy also for alphabets, where the probabilities of the symbols are not powers of two. We recall a recent type of entropy coding, named range Asymmetric Numeral systems (rANS) [Dud14], that encodes the state in a natural number and thus allows faster implementations. The rANS encoding technique was recently used in [ETWY22] and we adapt it to hyperball uniform distributions. As a stream variant, rANS can be implemented with finite precision integer arithmetic by using renormalization.

**Definition 6** (Range Asymmetric Numeral System (rANS) Coding). Let $t > 0$ and $S \subseteq [0, 2^t - 1]$. Let $g: [0, 2^t - 1] \to \mathbb{Z} \cap (0, 2^t]$ such that $\sum_{x \in S} g(x) \le 2^t$ and $g(x) = 0$ for all $x \notin S$. We define the following:

* CDF: $S \to \mathbb{Z}$, defined as $\text{CDF}(s) = \sum_{y=0}^{s-1} g(y)$.

* symbol: $\mathbb{Z} \to S$, where symbol($y$) is defined as $s \in S$ satisfying $\text{CDF}(s) \le y < \text{CDF}(s+1)$.

* $C: \mathbb{Z} \times S \to \mathbb{Z}$, defined as

$$C(x, s) = \left\lfloor \frac{x}{g(s)} \right\rfloor \cdot 2^t + (x \bmod^+ g(s)) + \text{CDF}(s).$$

Then, we define the rANS encoding/decoding for the set $S$ and frequency $g/2^t$ as in Figure 2.

Encode((s₁, ..., sₘ) ∈ S<sup>m</sup>):

1: $x_0 = 0$

2: for $i = 0, ..., m-1$ do

3: $x_{i+1} = C(x_i, s_{i+1})$

4: return $x_m$

Decode($x \in \mathbb{Z}$):

1: $y_0 = x$

2: $i = 0$

3: while $y_i > 0$ do

4: $s'_{i+1} = \text{symbol}(y_i \bmod^+ 2^t)$

5: $y_{i+1} = \lfloor y_i/2^t \rfloor \cdot g(s'_{i+1}) + (y_i \bmod^+ 2^t) - \text{CDF}(s'_{i+1})$

6: $i++$

7: $m = i - 1$

8: return $(s'_m, ..., s'_1) \in S^m$

<caption>**Figure 2:** rANS encoding and decoding procedures</caption>
**Lemma 2** (Adapted from [Dud14]). The rANS coding is correct, and the size of the rANS code is asymptotically equal to Shannon entropy of the symbols. That is, for any choice of $\mathbf{s} = (s_1, \cdots, s_m) \in S^m$, $\text{Decode}(\text{Encode}(\mathbf{s})) = \mathbf{s}$. Moreover, for any positive $x$ and any probability distribution $p$ over $S$, it holds that

$$ \sum_{s \in S} p(s) \log_2(C(x, s)) \le \log_2(x) + \sum_{s \in S} p(s) \log_2 \left( \frac{g(s)}{2^t} \right) + \frac{2^t}{x}. $$

Finally, the cost in bitlength of encoding the first symbol is $\le t$, i.e., for any $s \in S$, we have $\log_2(C(0, s)) \le t$.

We determine the frequency of the symbols experimentally, by executing the signature computation and collecting several million samples. Finally, we apply some rounding strategy in order to heuristically minimize the empirical entropy $\sum_{s \in S} p(s) \log(g(s)/2^n)$.

# 3 HAETAE-specific Results

While our scheme is reminiscent of Dilithium, the bimodal setting hinders the use of some of its base components. In this section, we describe parts that are specifically adapted to HAETAE. First, the key generation algorithm departs from known key generation algorithms for BLISS, as we work in the module setting. Second, we study the precision needed when discretizing the hyperball sampler from Section 2.4 to enable fixed-point arithmetic. Then, we explain how challenges are computed in HAETAE. Next, we describe the rejection sampling procedure and estimate its expected number of iterations depending on the fixed-point arithmetic precision. Finally, we explain how to split the coordinates of a signature vector into high and low bits, allowing for signature compression via low bits drop. This order is consistent with the order in which those results are used during signing.

## 3.1 Key Generation

When using bimodal rejection sampling, the verification step relies on a specific key pair $(\mathbf{A}, \mathbf{s}) \in \mathcal{R}_p^{k \times (k+\ell)} \times \mathcal{R}_p^{k+\ell}$ such that the bimodal centers $(-1)^b \mathbf{A} \mathbf{s}$ mod $p$ ($b=0,1$) are the same, regardless of the bit $b$. To generate such a pair, following [DDLL13], we choose $p=2q$ and aim at $\mathbf{A} \mathbf{s} = q \mathbf{j}$ mod $2q$ for $\mathbf{j} = (1, 0, \dots, 0)^\top$.

### 3.1.1 Key Generation and Encoding

To build such a key pair $(\mathbf{A}, \mathbf{s})$, we do as follows. We first generate an MLWE sample $\mathbf{b} = \mathbf{A}_{\text{gen}}\mathbf{s}_{\text{gen}} + \mathbf{e}_{\text{gen}} \mod q$, where $\mathbf{A}_{\text{gen}} \leftarrow U(\mathcal{R}_q^{k \times (k-1)})$ and $(\mathbf{s}_{\text{gen}}, \mathbf{e}_{\text{gen}}) \leftarrow U(S_{\eta}^{\ell-1} \times S_{\eta}^k)$. We then define $\mathbf{A} = (-2\mathbf{b} + q\mathbf{j} | 2\mathbf{A}_{\text{gen}} | 2\mathbf{I}_k)$ mod $2q$ as well as $\mathbf{s}^\top = (1|\mathbf{s}_{\text{gen}}^\top|\mathbf{e}_{\text{gen}}^\top)$. This is a valid verification key pair for HAETAE, but the choice of even modulus $2q$ makes it hard to truncate the least significant bits of $\mathbf{b}$ as in Dilithium.

To enable the verification key truncation, we modify the key generation algorithm, as follows. We use an extra randomness $\mathbf{a}_{\text{gen}} \leftarrow U(\mathcal{R}_q^k)$ and let $\mathbf{b}-\mathbf{a}_{\text{gen}} = \mathbf{A}_{\text{gen}}\mathbf{s}_{\text{gen}}+\mathbf{e}_{\text{gen}} \mod q$. For any decomposition $\mathbf{b} = \mathbf{b}_1 + \mathbf{b}_0$, we then define $\mathbf{A} = (2(\mathbf{a}_{\text{gen}} - \mathbf{b}_1) + q\mathbf{j} | 2\mathbf{A}_{\text{gen}} | 2\mathbf{I}_k)$ as well as $\mathbf{s}^\top = (1|\mathbf{s}_{\text{gen}}^\top|(\mathbf{e}_{\text{gen}} - \mathbf{b}_0)^\top)$. One sees that $\mathbf{A} \mathbf{s} = q\mathbf{j}$ mod $2q$. In practice, the verification key is then comprised of $\mathbf{b}_1$ and the seed that allows generating $\mathbf{A}_{\text{gen}}$ and $\mathbf{a}_{\text{gen}}$. The secret key is the seed used to generate $\mathbf{s}$ and $(\mathbf{A}_{\text{gen}}, \mathbf{a}_{\text{gen}})$.

It remains to choose the decomposition of $\mathbf{b}$, that we see as an $nk$-dimensional vector with coordinates in $[0, q-1]$. We set the coordinates of $\mathbf{b}_1$ as follows. If some coordinate of $\mathbf{b}$ is even, then we take the same value for the corresponding coordinate of $\mathbf{b}_1$. Else, we
take the rounding of this coordinate to the nearest multiple of 4 as value for $\mathbf{b}_1$. Next we set $\mathbf{b}_0 = \mathbf{b} - \mathbf{b}_1$ and we note that coordinates of $\mathbf{b}_0$ lie in $[-1, 1]$, i.e., $\mathbf{b}_0 \in S_1^k$. We can then write $\mathbf{b} = \mathbf{b}_0 + 2\mathbf{b}'_1$, where $\mathbf{b}'_1$ is encoded using $\lceil \log_2(q) - 1 \rceil$ bits per coordinate, i.e. one less bit than $\mathbf{b}$. This is computed coordinate-wise with $\mathbf{b}_0 = (-1)^{\lfloor b/2 \rfloor \bmod 2} \mathbf{b} \bmod 2$. In all of the following, we let $(\text{LowBits}^{\text{vk}}(\mathbf{b}), \text{HighBits}^{\text{vk}}(\mathbf{b}))$ denote $(\mathbf{b}_0, \mathbf{b}_1)$.

When $\mathbf{b}$ is uniform, we notice that the coordinates of $\mathbf{b}_0$ roughly follow a (centered) binomial law with parameters $(2, 1/2)$, which experimentally leads to smaller choices for $\gamma$, which we discuss and introduce below.

Note that the truncation reduces each coefficient of $\mathbf{b}$ by 1 bit. So the verification key becomes shorter, but not significantly. Thus, we use the truncation for lower security levels and keep the no-truncation version for the highest level. In the following, we refer to the truncated version as $d = 1$ and the non-truncated version as $d = 0$, where $d$ is the vk truncation bit.

### 3.1.2 Rejection Sampling on the Key

A critical step of our scheme is bounding $\|cs\|_2$, where $s$ is generated as before and $c \in \mathcal{R}$ is a polynomial with coefficients in $\{0, 1\}$ and has less than or equal to $\tau$ nonzero coefficients. The lower this bound is, the smaller the signature is, which in turn leads to the harder forging. In the key generation algorithm, we apply the following rejection condition for some heuristic value $\gamma$, bounding $\|cs\|_2 \le \gamma\sqrt{\tau}$:

$$ \mathcal{N}(\mathbf{s}) := \tau \cdot \sum_{i=1}^{m} \max_{0 \le j < 2n}^{i\text{-th}} \|\mathbf{s}(\omega_j)\|_2^2 + r \cdot \max_{0 \le j < 2n}^{(m+1)\text{-th}} \|\mathbf{s}(\omega_j)\|_2^2 \le \gamma^2 n, $$

where $m = \lfloor n/\tau \rfloor$, $r = n \bmod \tau$, $\omega_j$'s are the primitive $2n$-th roots of unity ($1 \le j \le n$). Note that $s(\omega_j)$ is defined as $(s_1(\omega_j), \dots, s_{k+\ell}(\omega_j)) \in \mathbb{C}^{k+\ell}$ given the secret key $\mathbf{s} = (s_1, \dots, s_{k+\ell}) \in \mathcal{R}^{k+\ell}$. Below, we prove that the left hand side is a bound on $\frac{n}{\tau} \cdot \|cs\|_2^2$ and that this condition leads to asserting $\|cs\|_2 \le \gamma\sqrt{\tau}$.

**Lemma 3.** For any challenge $c \in \{0, 1\}^n$ with Hamming weight $\tau$ and a secret $\mathbf{s} \in S_{\eta}^{k+\ell}$, the value $\|cs\|_2^2$ is upper bounded by

$$ \frac{\tau}{n} \left( \tau \cdot \sum_{i=1}^{m} \max_{0 \le j < 2n}^{i\text{-th}} \|\mathbf{s}(\omega_j)\|_2^2 + r \cdot \max_{0 \le j < 2n}^{(m+1)\text{-th}} \|\mathbf{s}(\omega_j)\|_2^2 \right), $$

where $m = \lfloor n/\tau \rfloor$, $r = n \bmod \tau$, and $\omega_j$'s are the primitive $2n$-th roots of unity.

**Proof.** We first rewrite $\|cs\|_2^2$ as:

$$ \|cs\|_2^2 = \frac{\sum_j |c(\omega_j)|^2 \cdot \|s(\omega_j)\|_2^2}{n}, $$

where $s(\omega_j) = (s_1(\omega_j), \dots, s_{k+\ell}(\omega_j))$. We have that $\sum_{j=1}^n |c(\omega_j)|^2 = n\tau$ and $|c(\omega_j)|^2 = |\omega_{j,1} + \dots + \omega_{j,\tau}|^2 \le \tau^2$. We can bound $\sum_{j=1}^n |c(\omega_j)|^2 \cdot \|s(\omega_j)\|_2^2$ by rearranging the order. Let $m = \lfloor n/\tau \rfloor$ and $r = n \bmod \tau$. Then $m$ is the maximum number of $|c(\omega_j)|^2$'s that can be $\tau^2$. By sorting $\|s(\omega_j)\|_2$ in a decreasing order,

$$ \|s(\omega_{\sigma(1)})\|_2 \ge \|s(\omega_{\sigma(2)})\|_2 \ge \dots \ge \|s(\omega_{\sigma(n)})\|_2, $$

where $\sigma$ is a permutation for the indices, we have

$$ \sum_{j=1}^{n} |c(\omega_j)|^2 \cdot \|s(\omega_j)\|_2^2 \le \sum_{j=1}^{m} |c(\omega_{\sigma(j)})|^2 \cdot \|s(\omega_{\sigma(j)})\|_2^2 + \sum_{j=m+1}^{n} |c(\omega_{\sigma(j)})|^2 \cdot \|s(\omega_{\sigma(m+1)})\|_2^2. $$
Then it reaches the maximum when the $m$ largest $\|\mathbf{s}(\omega_j)\|_2^2$'s are multiplied with $\tau^2$'s, i.e.,

$$ \sum_{j=1}^{n} |c(\omega_j)|^2 \cdot \|\mathbf{s}(\omega_j)\|_2^2 \le \sum_{j=1}^{m} \tau^2 \cdot \|\mathbf{s}(\omega_{\sigma(j)})\|_2^2 + \left( \sum_{j=1}^{n} |c(\omega_j)|^2 - m\tau^2 \right) \cdot \|\mathbf{s}(\omega_{\sigma(m+1)})\|_2^2 \\ = \tau^2 \cdot \sum_{j=1}^{m} \|\mathbf{s}(\omega_{\sigma(j)})\|_2^2 + r \cdot \tau \cdot \|\mathbf{s}(\omega_{\sigma(m+1)})\|_2^2. $$

This concludes the proof. □

## 3.2 Sampling in a Discrete Hyperball

In order to generate a hyperball uniform sample $\mathbf{y}$, we apply a rounding-and-reject strategy to the discretization of the continuous hyperball uniform sampling from Figure 1, which allows to generate rightly distributed samples. Our approach in sampling is to avoid the use of floating point arithmetic for two reasons: First, many microarchitectures do not provide floating-point units and even if so, the execution time of floating-point instructions may be data-dependent and thus unsuitable [AKM$^{+15}$] for a constant-time implementation. Floating-point computation would also prohibit a masked implementation, that is protected against power side-channel attacks, because known masking techniques are only applicable to integers. And second, the required precision is higher than achievable even in IEEE double. In order to do so, we replace the continuous Gaussian sampler from Lemma 1 and instead use discrete Gaussian distributions, as we know that they approximate well continuous Gaussian distribution for large standard deviation.

**Discretizing the Output.** Once we obtain an “hyperball” sample, we choose to round it. Then, if the resulting sample lies too close to the border of the hyperball, we reject it. This ensures that for any possible sample, they have the same amount of pre-rounding predecessors. This also decreases the precision but the output is now discrete in a hyperball with a somewhat-smaller radius. We simply increase the starting radius to compensate.

<figure><img src="image_4.png" /><figcaption>**Figure 3:** Discrete hyperball uniform sampling</figcaption></figure>

We study in the following lemma the rejection probability of this step.

**Lemma 4.** Let $n$ be the degree of $\mathcal{R}$, $M_0 \ge 1$, $B, m, N > 0$. At each iteration, the algorithm from Figure 3 succeeds with probability $\ge 1/M_0$ and the distribution of the output is $U(\mathcal{B}_{(1/N)\mathcal{R},m}(B))$ if we set

$$ N \ge \frac{\sqrt{mn}}{2B} \cdot \frac{M_0^{1/(mn)} + 1}{M_0^{1/(mn)} - 1}. $$

The proof of this lemma can be found in Appendix C.

## 3.3 Challenge Sampling

Challenges in HAETAE are polynomials $c \in \mathcal{R}$ with binary coefficients and exactly $\tau$ of them are nonzero. As simply hashing the message and the commitment only yields a
SampleBinaryChallenge$_{τ}$(ρ)

// for HAETAE-120 or HAETAE-180

1: Initialize **c** = c₀**c**₁...c₂₅₅ = 00...0

2: for i = 256 − τ to 255 do

3: j ← {0, ..., i}

4: cᵢ = cⱼ

5: cⱼ = 1

6: Return **c**

// for HAETAE-260

1: Initialize **c** = c₀**c**₁...c₂₅₅ = H(ρ)

2: if wt(**c**) > 128 then

3: c = c ⊗ 11...1

4: else if wt(**c**) = 128 then

5: c = c ⊗ c₀**c**₀...**c**₀

6: Return **c**

<caption>**Figure 4:** Challenge sampling algorithm</caption>

binary string ρ, we now explain how to format it to get such a challenge. Since n = 256
across all three parameter sets, the challenge space has size (n/τ) exceeding the required
entropy 2192 and 2225 for HAETAE-120 and HAETAE-180, respectively. To sample such
challenges we rely on the (binary version of) SampleInBall algorithm from Dilithium, which
we specify in the first half of Figure 4.

For HAETAE-260, however, we require 255 bits of entropy for the challenge space,
which cannot be reached with the fixed Hamming weights for n = 256. To achieve it, we
replace the challenge space by a set containing exactly half of the bitstrings of length 256.
Specifically, we choose a set containing all elements of Hamming weight strictly less than
128 and half of the elements of Hamming weight 128, using the following algorithm. Given
a 256-bits hash with Hamming weight w, do the following. If w < 128, we do nothing, and
if w > 128, we flip all the bits. If w = 128, we decide whether to flip or not, depending on
the first bit. Exactly half of all binary polynomials are reachable this way, which means
that the challenge set has size 2255 as desired. The algorithm is specified in the second
half of Figure 4.

As a side note, this means that the hash function with which we instantiate the Fiat-Shamir transform is the composition of these two steps, hashing and formatting. Looking ahead, this corresponds to steps 6 and 7 of Figure 8. Contrary to Dilithium, we do not stray away from the Fiat-Shamir transform and include the challenge *c* in the signature as it is no bigger than *ρ* when encoded.

3.4 Bimodal Hyperball Rejection Sampling

Recently, Devevey et al. [DFPS22] conducted a study of rejection sampling in the context of lattice-based Fiat-Shamir with Aborts signatures. They observe that (continuous) uniform distributions over hyperballs can be used to obtain compact signatures, with a relatively simple rejection procedure. To make masking easier, HAETAE uses (discretized) uniform distributions over hyperballs, in the bimodal context. The proof of the following lemma is available in Appendix C.

**Lemma 5 (Bimodal Hyperball Rejection Sampling).** Let *n* be the degree of *R*, *c* > 1,
$r, t, m > 0$, and $B \ge \sqrt{B'^2 + t^2}$. Define $M = 2(B/B')^{mn}$ and set

$$N \ge \frac{1}{c^{1/(mn)} - 1} \frac{\sqrt{mn}}{2} \left( \frac{c^{1/(mn)}}{B'} + \frac{1}{B} \right).$$

Let $v \in \mathbb{R}^m \cap B_{(1/N)\mathbb{R},m}(t)$. Let $p: \mathbb{R}^m \to \{0, 1/2, 1\}$ be defined as follows

$$p(\mathbf{z}) = \begin{cases} 0 & \text{if } \|\mathbf{z}\| \ge B', \\ 1/2 & \text{else if } \|\mathbf{z} - \mathbf{v}\| < B \land \|\mathbf{z} + \mathbf{v}\| < B, \\ 1 & \text{otherwise.} \end{cases}$$

Then there exists $M' \le cM$ such that the output distributions of the two algorithms from Figure 6 are identical.

<figure><img src="image_5.png" /><figcaption>Figure 5: The HAETAE eyes</figcaption></figure>

Figure 5 illustrates (the continuous version) of the rejection sampling that we consider. The black empty circles have radii equal to $B$ and the green circle has radius $B'$. We sample a vector $z$ uniformly inside one of the black circles (with probability $1/2$ for each) and keep $z$ with $p(z) = 1/2$ if $z$ lies in the blue zone, with probability $p(z) = 1$ if it lies in the green zone, and with probability $p(z) = 0$ everywhere else.

We now have all necessary ingredients in Figures 1, 3, 5, and 6 to make sure the resulting distribution of $z$ is indeed uniform over the discretized hyperball. Thanks to Lemma 4 and Lemma 5, we already know the level of precision required for $y$ to maintain the provable security of HAETAE.

## 3.5 High and Low Bits

Recall that a HAETAE signature is principally a vector $z$, whose lower part is replaced with a (smaller) hint. HAETAE makes use of two different high and low bits decompositions: one helps encoding a signature while the other is used when computing a hint. Following [ETWY22], the first is helpful in the sense that if we correctly choose the number of low bits, they will be distributed almost uniformly and can then be excluded from the encoding step. The high bits on the other hand, will then follow a distribution with a very small variance and we apply the rANS encoding on them only, making it much more efficient as the size of the alphabet greatly shrunk.

A($v$):

1: $y \leftarrow U(B_{(1/N)\mathbb{R},m}(B))$

2: $b \leftarrow U(\{0, 1\})$

3: $z \leftarrow y + (-1)^b v$

B:

1: $z \leftarrow U(B_{(1/N)\mathbb{R},m}(B'))$

<caption>Figure 6: Bimodal hyperball rejection sampling</caption>
The second decomposition allows to reduce the alphabet size of the resulting hint, and thus to reduce the size of its encoding.

We use the following base method of decomposing an element in high and low bits. We first recall the Euclidean division with a centered remainder.

**Lemma 6.** Let $a \ge 0$ and $b > 0$. It holds that

$$a = \left\lfloor \frac{a+b/2}{b} \right\rfloor \cdot b + (a \bmod \pm b),$$

and this writing as $a = bq + r$ with $r \in [-b/2, b/2)$ is unique.

We define our decomposition for compressing the upper part of the signature.

**Definition 7** (High and low bits). Let $r \in \mathbb{Z}$ and $\alpha$ be a power of two integer. Define $r_1 = \lfloor (r + \alpha/2)/\alpha \rfloor$ and $r_0 = r \bmod \pm \alpha$. Finally, define the tuple:

$$(\text{LowBits}(r, \alpha), \text{HighBits}(r, \alpha)) = (r_0, r_1).$$

We extend these definitions to vectors by applying them component-wise. We state that this decomposition lets us recover the original element and bound the components of the decomposition in Lemma 7. The proof is available in Appendix C.

**Lemma 7.** Let $\alpha$ be a power of two. Let $q > 2$ be a prime with $\alpha|2(q-1)$ and $r \in \mathbb{Z}$. Then it holds that

$$r = \alpha \cdot \text{HighBits}(r, \alpha) + \text{LowBits}(r, \alpha), \\ \text{LowBits}(r, \alpha) \in [-\alpha/2, \alpha/2), \\ r \in [0, 2q-1] \implies \text{HighBits}(r, \alpha) \in [0, (2q-1)/\alpha].$$

We define $\text{HighBits}^{z1}(r) = \text{HighBits}(r, 256)$ and $\text{LowBits}^{z1}(r) = \text{LowBits}(r, 256)$.

### 3.5.1 High and Low Bits for h

In order to produce the hint that we send instead of the lower part of $z$, we could use the previous bit decomposition. However, as noted in [DKL$^+$18, Appendix B] in a preliminary version, a slight modification allows to further reduce the entropy of the hint.

The idea is to pack the high bits in the range $[0, 2(q-1)/\alpha_h)$. This is possible if we use the range $[-\alpha_h/2 - 2, 0)$ to represent the integers that are close to $2q - 1$.

**Definition 8** (High and low bits for $h$). Let $r \in \mathbb{Z}$. Let $q$ be a prime and $\alpha_h|2(q-1)$ be a power of two. Let $m = 2(q-1)/\alpha_h$, $r_1 = \text{HighBits}(r \bmod 2q, \alpha_h)$, and $r_0 = \text{LowBits}(r \bmod 2q, \alpha_h)$. If $r_1 = m$, let $(r'_0, r'_1) = (r_0 - 2, 0)$. Else, $(r'_0, r'_1) = (r_0, r_1)$. We define:

$$(\text{LowBits}^h(r), \text{HighBits}^h(r)) = (r'_0, r'_1).$$

As before, we extend these definitions to vectors by applying them component-wise. We state that this decomposition lets us recover the original element and bound the decomposition components.

**Lemma 8.** Let $r \in \mathbb{Z}$. Let $q$ be a prime, $\alpha_h|2(q-1)$ be a power of two and define $m = 2(q-1)/\alpha_h$. It holds that

$$r = \alpha_h \cdot \text{HighBits}^h(r) + \text{LowBits}^h(r) \bmod 2q, \\ \text{LowBits}^h(r) \in [-\alpha/2 - 2, \alpha/2), \\ \text{HighBits}^h(r) \in [0, m-1].$$

The proof of Lemma 8 is available in Appendix C.
# 4 The HAETAE Signature Scheme

In this section, we describe three different versions of HAETAE. As a warm-up, we give an uncompressed, un-truncated version of HAETAE, implementing the Fiat-Shamir with aborts paradigm in the bimodal hyperball-uniform setting. We then give the full description of optimized and deterministic HAETAE as we implemented it. Finally, we discuss the parts of the signing algorithm which can be pre-computed.

## 4.1 Uncompressed Description

As a first approach, we give a high-level, uncompressed, description of our signature scheme in Figure 7. In all of the following sections, we let $\mathbf{j} = (1, 0, \dots, 0) \in \mathbb{R}^k$, as well as $k, \ell$ be two dimensions, $N > 0$ the fix-point precision and $\tau > 0$ the challenge min-entropy parameter. The parameters $B, B'$, and $B''$ refer to the radii of hyperballs. Let $q$ be an odd prime and $\alpha_h|2(q-1)$ is a power of two. We recall the key rejection function based on Lemma 3:

$$ \mathcal{N}: \mathbf{s} \mapsto \tau \cdot \sum_{i=1}^{m} \max_{j}^{i\text{-th}} \|\mathbf{s}(\omega_j)\|_2^2 + r \cdot \max_{j}^{(m+1)\text{-th}} \|\mathbf{s}(\omega_j)\|_2^2. $$

With the parameter $\gamma$, we bound $\mathcal{N}(\mathbf{s}) \le \gamma^2 n$, which ensures that $\|\mathbf{cs}\|_2 \le \gamma\sqrt{\tau}$ for all $c \in \mathbb{R}_2$ satisfying $\mathrm{wt}(c) \le \tau$. The key generation algorithm is a simplified version from Section 3.1, which removes the verification key truncation, for conceptual simplicity.

Effectively, this requires computing a complex (fix-point) 512-point Fast Fourier Transform (FFT) for each polynomial in $\mathbf{s}$, where the input is padded with zeros. The absolute value of the FFT outputs is accumulated point-wise, which yields the vector that is the input to the above function $f$. In fact, this can be optimized this by replacing the 512-point FFT by a 256-point one, where the $j$-th input coefficient $x_j$ is multiplied by $e^{-\frac{i\pi}{256}j}$, which is functionally equivalent.

## 4.2 Specification of HAETAE

We now give the full description of the signature scheme HAETAE in Figure 8 with the following building blocks:

* Hash function $H_{\mathrm{gen}}$ for generating the seeds and hashing the messages,

* Hash function $H$ for signing, returning a seed $\rho$ for sampling a challenge,

* Extendable output function expandA for deriving $\mathbf{a}_{\mathrm{gen}}$ and $\mathbf{A}_{\mathrm{gen}}$ from seed$_A$,

* Extendable output function expandS for deriving $(\mathbf{s}_{\mathrm{gen}}, \mathbf{e}_{\mathrm{gen}}) \in S_{\eta}^{\ell-1} \times S_{\eta}^{k}$ from seed$_{sk}$ and counter$_{sk}$,

* Extendable output function expandYbb for deriving $\mathbf{y}, \mathbf{b}$ and $\mathbf{b}'$ from seed$_{ybb}$ and counter,

The above building blocks can be implemented with symmetric primitives.

Note that at Step 6 of the Verify algorithm, the division by 2 is well-defined as the operand is even.

## 4.3 Theoretical Analysis

In this section, we prove the theoretical correctness and security of HAETAE.
**KeyGen(1^λ):**

1: $(\mathbf{A}_{\text{gen}}) \leftarrow \mathcal{R}_q^{k \times (\ell-1)}$ and $(\mathbf{s}_{\text{gen}}, \mathbf{e}_{\text{gen}}) \leftarrow S_{\eta}^{\ell-1} \times S_{\eta}^k$

2: $\mathbf{b} = \mathbf{A}_{\text{gen}} \cdot \mathbf{s}_{\text{gen}} + \mathbf{e}_{\text{gen}} \in \mathcal{R}_q^k$

3: $\mathbf{A} = (-2\mathbf{b} + q\mathbf{j} | 2\mathbf{A}_{\text{gen}} | 2\mathbf{I}_k) \mod 2q$

4: $\mathbf{s} = (\mathbf{s}_{\text{gen}}, \mathbf{e}_{\text{gen}})$

5: **if** $\mathcal{N}(\mathbf{s}) > \gamma^2 n$ **then** restart

6: **return** $\mathbf{sk} = (\mathbf{A}, \mathbf{s})$, $\mathbf{vk} = \mathbf{A}$

**Sign(sk, M):**

1: $\mathbf{y} \leftarrow U(\mathcal{B}_{(1/N)\mathcal{R}, (k+\ell)}(B))$

2: $\mathbf{w} \leftarrow \mathbf{A}|\mathbf{y}|$

3: $c = H(\mathbf{w}, M) \in \mathcal{R}_2$

4: $\mathbf{z} = (\mathbf{z}_1, \mathbf{z}_2) = \mathbf{y} + (-1)^b \mathbf{cs}$ for $b \leftarrow U(\{0, 1\})$

5: **if** $\|\mathbf{z}\|_2 \ge B'$ **then** restart

6: **else if** $\|2\mathbf{z} - \mathbf{y}\|_2 < B$ **then** restart with probability 1/2

7: **return** $\sigma = (\lfloor \mathbf{z} \rfloor, c)$

**Verify(vk, M, \sigma = (\mathbf{z}, c)):**

1: $\tilde{\mathbf{w}} = \mathbf{A}\mathbf{z} - q\mathbf{c}\mathbf{j} \mod 2q$

2: **return** $(c = H(\tilde{\mathbf{w}}, M)) \wedge (\|\mathbf{z}\| < B + \frac{\sqrt{n(k+\ell)}}{2})$

<caption>**Figure 7:** Uncompressed description of HAETAE.</caption>

### 4.3.1 Correctness and Runtime

**Correctness.** Before showing the correctness of the HAETAE scheme, we prove the following intermediary result.

**Lemma 9.** We borrow the notations from Figure 8. If we run Verify(vk, M, σ) on the signature σ returned by Sign(sk, M) for an arbitrary message M and an arbitrary key-pair (sk, vk) returned by KeyGen(1^λ), then the following relations hold:

1) $\mathbf{w}_1 = \text{HighBits}^h(\mathbf{w})$,

2) $w'\mathbf{j} = \text{LSB}(\lfloor y_0 \rfloor) \cdot \mathbf{j} = \text{LSB}(\mathbf{w}) = \text{LSB}(\mathbf{w} - 2\lfloor z_2 \rfloor),$

3) $2\lfloor z_2 \rfloor - 2\tilde{z}_2 = \text{LowBits}^h(\mathbf{w}) - \text{LSB}(\mathbf{w}) \text{ assuming } B' + \alpha_h/4 + 1 \le B'' < q/2$.

**Proof.** Let $m = 2(q-1)/\alpha_h$. Let us prove the first statement. By definition of h, it holds that $\mathbf{w}_1 = \text{HighBits}^h(\mathbf{w}) \mod m$. However, the latter part of the equality already lies in $[0, m-1]$ by Lemma 8. The first part lies in the same range as we reduce $\mod^+ m$. Hence, the equality stands over $\mathbb{Z}$ too.

We move on to the second statement. By considering only the first component of $\mathbf{z} = \mathbf{y} + (-1)^b \mathbf{cs}$, we obtain, modulo 2:

$$\tilde{z}_0 = \lfloor z_0 \rfloor = \lfloor y_0 \rfloor + (-1)^b c = \lfloor y_0 \rfloor + c.$$

Moreover, considering everywhere a 2 appears in the definition of A, we obtain that

$$\mathbf{w} = \mathbf{A}_1 \lfloor \mathbf{z}_1 \rfloor - q \mathbf{c} \mathbf{j} = (\lfloor z_0 \rfloor - c) \mathbf{j} \mod 2.$$

For the last statement, let us use the two preceding results. In particular, we note

$$\mathbf{w}_1 \cdot \alpha_h + w'\mathbf{j} = \mathbf{w} - \text{LowBits}^h(\mathbf{w}) + \text{LSB}(\mathbf{w}).$$
**KeyGen(1^λ):**

1: seed ← {0, 1}^{ρ_0} ▷ KeyGen for d = 1

2: (seed<sub>A</sub>, seed<sub>sk</sub>, K) = H<sub>gen</sub>(seed)

3: ($\mathbf{a}_{\text{gen}} | \mathbf{A}_{\text{gen}}$) := expandA(seed<sub>A</sub>) ∈ $\mathbb{R}_q^{k \times \ell}$

4: counter<sub>sk</sub> = 0

5: ($\mathbf{s}_{\text{gen}}, \mathbf{e}_{\text{gen}}$) := expandS(seed<sub>sk</sub>, counter<sub>sk</sub>)

6: $\mathbf{b} = \mathbf{a}_{\text{gen}} + \mathbf{A}_{\text{gen}} \cdot \mathbf{s}_{\text{gen}} + \mathbf{e}_{\text{gen}} \in \mathbb{R}_q^k$

7: ($\mathbf{b}_0, \mathbf{b}_1$) = (LowBits<sup>vk</sup>(b), HighBits<sup>vk</sup>(b))

8: $\mathbf{A} = (2(\mathbf{a}_{\text{gen}} - 2\mathbf{b}_1) + \mathbf{q}\mathbf{j}) \mod 2q$

9: $\mathbf{s} = (\mathbf{s}_{\text{gen}}, \mathbf{e}_{\text{gen}} - \mathbf{b}_0)$

10: if $\mathcal{N}(\mathbf{s}) > \gamma^2 n$ then counter<sub>sk</sub>++ and Go to 5

11: return sk = (s, K), vk = (seed<sub>A</sub>, b<sub>1</sub>)

**Sign(sk, M):**

1: $\mu = H_{\text{gen}}(\text{seed}_{\mathbf{A}}, \mathbf{b}_1, M)$

2: $\text{seed}_{ybb} = H_{\text{gen}}(K, \mu)$

3: counter = 0

4: ($\mathbf{y}, \mathbf{b}, \mathbf{b}'$) := expandYbb(seed<sub>ybb</sub>, counter)

5: $\mathbf{w} \leftarrow \mathbf{A}|\mathbf{y}$

6: $\rho = H(\text{HighBits}^h(\mathbf{w}), \text{LSB}(\lfloor y_0 \rfloor), \mu)$

7: $c = \text{SampleBinaryChallenge}_\tau(\rho)$

8: $\mathbf{z} = (\mathbf{z}_1, \mathbf{z}_2) = \mathbf{y} + (-1)^b \mathbf{c}\mathbf{s}$

9: $\mathbf{h} = \text{HighBits}^h(\mathbf{w}) - \text{HighBits}^h(\mathbf{w} - 2\lfloor \mathbf{z}_2 \rfloor) \mod^+ \frac{2(q-1)}{\alpha_h}$

10: if $\|\mathbf{z}\|_2 \ge B'$ then

11: counter++ and Go to 4

12: else if $\|2\mathbf{z} - \mathbf{y}\|_2 < B \land b' = 0$ then

13: counter++ and Go to 4

14: else

15: $x = \text{Encode}(\text{HighBits}^{z1}(\lfloor \mathbf{z}_1 \rfloor))$

16: $\mathbf{v} = \text{LowBits}^{z1}(\lfloor \mathbf{z}_1 \rfloor)$

17: return $\sigma = (x, \mathbf{v}, \text{Encode}(\mathbf{h}), c)$

**Verify(vk, M, σ = (x, v, h, c)):**

1: $\tilde{z}_1 = \text{Decode}(x) \cdot 256 + \mathbf{v}$ and $\tilde{\mathbf{h}} = \text{Decode}(h)$

2: ($\mathbf{a}_{\text{gen}} | \mathbf{A}_{\text{gen}}$) = expandA(seed<sub>A</sub>)

3: $\mathbf{A}_1 = (2(\mathbf{a}_{\text{gen}} - 2\mathbf{b}_1) + \mathbf{q}\mathbf{j}) \mod 2q$

4: $\mathbf{w}_1 = \tilde{\mathbf{h}} + \text{HighBits}^h(\mathbf{A}_1\tilde{z}_1 - q\mathbf{c}\mathbf{j}) \mod^+ \frac{2(q-1)}{\alpha_h}$

5: $w' = \text{LSB}(\tilde{z}_0 - c)$

6: $\tilde{z}_2 = (\mathbf{w}_1 \cdot \alpha_h + w'\mathbf{j} - (\mathbf{A}_1\tilde{z}_1 - q\mathbf{c}\mathbf{j})) / 2 \mod^\pm q$

7: $\tilde{z} = (\tilde{z}_1, \tilde{z}_2)$

8: $\tilde{\mu} = H_{\text{gen}}(\text{seed}_{\mathbf{A}}, \mathbf{b}_1, M)$

9: $\tilde{\rho} = H(\mathbf{w}_1, w', \tilde{\mu})$

10: return $(c = \text{SampleBinaryChallenge}_\tau(\tilde{\rho})) \land (\|\tilde{z}\| < B'')$

**Figure 8:** Full description of deterministic HAETAE. The KeyGen algorithm is slightly different for $d = 0$ (HAETAE-260), which do not truncate **b**. See Section 3.1.1 for details.

We note that the last two elements have same parity, as the former one has the same parity as LowBits(w, α<sub>h</sub>). By Lemma 8 their sum has infinite norm ≤ α<sub>h</sub>/2 + 2. Hence from its definition, it holds that

$$2\tilde{z}_2 = 2\lfloor z_2 \rfloor - \text{LowBits}^h(\mathbf{w}) + \text{LSB}(\mathbf{w}) \mod^\pm 2q.$$
Finally, this holds over the integers as the right-hand side has infinite norm at most $2B' + \alpha_h/2 + 2 < q$. $\square$

**Theorem 2 (Completeness).** Assume that $B'' = B' + \sqrt{n(k+\ell)}/2 + \sqrt{nk}(\alpha_h/4+1) < q/2$. Then the signature schemes of Figure 8 is complete, i.e., for every message $M$ and every key-pair $(sk, vk)$ returned by KeyGen$(1^{\lambda})$, we have:

$$ \text{Verify}(vk, M, \text{Sign}(sk, M)) = 1. $$

**Proof.** We use the notations of the algorithms. The first and second equations from Lemma 9 state that $\rho = \tilde{\rho}$ and thus

$$ c = \text{SampleBinaryChallenge}_{\tau}(\tilde{\rho}). $$

On the other hand, we use the last equation from the same lemma to bound the size of $\tilde{z}$. We have:

$$ \begin{aligned} \|\tilde{z}\| & \le \|z\| + \|z - [z]\| + \|[z] - \tilde{z}\| \\ & \le B' + \sqrt{n(k+\ell)} \cdot \|z - [z]\|_{\infty} + \|[z_2] - \tilde{z}_2\| \\ & \le B' + \frac{\sqrt{n(k+\ell)}}{2} + \sqrt{nk} \cdot \|\text{LowBits}^h(w)\|_{\infty} \\ & \le B' + \frac{\sqrt{n(k+\ell)}}{2} + \sqrt{nk} \cdot \left(\frac{\alpha_h}{4} + 1\right). \end{aligned} $$

The definition of $B''$ implies that the scheme is correct. $\square$

**Runtime.** A non-trivial task is analyzing the runtime of Fiat-Shamir with aborts schemes. As shown in [DFPS23, Section 6.1], degenerate cases exist where the signing algorithm does not terminate. In particular, it is impossible, even in the ROM, to show that the generic signing algorithm has polynomial expected runtime. However, in the case of HAETAE, all starting points $y$ lying in the Euclidean ball of radius $B' - \gamma\sqrt{\tau}$ have probability at least $1/2$ of being accepted in the end, whatever shift $\pm sc$ is added, whatever instance of the hash function $H$ is chosen. This gives rise to the following two points.

* With $M'$ defined as in Lemma 5, the probability of doing more than $i$ iterations is bounded from above by $(1 - 1/M')^i + 2^{-\alpha M'^3}$, where $\alpha$ is the commitment min-entropy.

* The signing algorithm has a finite expected runtime.

These are insufficient to conclude that the number of iterations is $M'$ on average, but this is nonetheless what happens for our choice of parameters.

### 4.3.2 Theoretical Security

We analyze the security of HAETAE by following standard arguments and proof techniques. We start by detailing the underlying canonical identification scheme that makes up HAETAE and give their properties in Lemma 10. We then show that HAETAE is UF-NMA secure in Lemma 11. Finally, we put everything together and give the security bound in Theorem 3 based on the reduction from [BBD$^{+23}$]. Reminders on canonical identification schemes and the Fiat-Shamir with aborts transform can be found in Appendix F.

In Figure 10, we first describe in Figure 10a an “uncompressed” version of the identification scheme, as well as the HAETAE canonical identification scheme in Figure 10b.
<figure><img src="image_6.png" /><figcaption>**Figure 9:** Compression and decompression algorithms.</figcaption></figure>

The latter uses the **Compress** and **Decompress** functions, as described in Figure 9. We omit the instance generator for both CID, as it is exactly the key generation algorithm from HAETAE, except that do not do truncation for simplicity. Adding it can be done by noting that $a_{gen}$ gives uniform low bits that would otherwise be missing.

We sum up the properties of the CID from Figure 10b.

**Lemma 10.** *The HAETAE canonical identification scheme from Figure 10b satisfies the following properties.*

**Commitment Min-entropy.** The commitment $(w_0, w_1)$ has min-entropy $\ge n$.

**paHVZK.** Assuming $B^2 \ge B'^2 + \gamma^2\tau$, the HAETAE CID satisfies the paHVZK property with the simulator described in Figure 11.

**Computational Unique Response.** Let $\mathcal{A}$ be an adversary against the CUR property of the scheme. There exist two adversaries $\mathcal{B}$ and $\mathcal{B}'$ with roughly the same runtime such that:

$$ \mathrm{Adv}_{\mathrm{HAETAE}}^{\mathrm{CUR}}(\mathcal{A}) \le \mathrm{Adv}_{n,q,k,l-1,\eta}^{\mathrm{MLWE}}(\mathcal{B}) + \mathrm{Adv}_{n,q,k,l,2B''}^{\mathrm{MSIS}}(\mathcal{B}'). $$

**Proof.** Let us prove each point.

**Commitment Min-entropy.** Recall that $w_0 = \mathrm{LSB}(\lfloor y_0 \rfloor)$ is a binary polynomial of degree $\le n$. As the coefficients of $y_0$ are large and distributed following the distribution of a subset of a uniform-hyperball, we expect the coefficients of $w_0$ to be roughly uniform, hence the lower bound on the commitment min-entropy.

**paHVZK.** We first prove that the CID from Figure 10a satisfies paHVZK. Consider the simulator described in Figure 11.

The distribution of real non-aborting transcripts and the output distribution of $\mathrm{Sim}_\lambda(\mathrm{vk}, c)$ are identical under the condition on the radii. Indeed, by conditioning the distribution of the output of algorithms $\mathcal{A}$ and $\mathcal{B}$ from Lemma 5 on not being $\perp$, the conditional (on $\mathcal{A}$ and $c$) distributions of $\mathbf{z}$ in the two cases are identical, and we note that $(\mathbf{w}, c, \mathbf{z})$ is a deterministic function of $(\mathcal{A}, c, \mathbf{z})$.

Finally, given an uncompressed transcript $(\mathbf{w}, c, \mathbf{z})$ for the Figure 10a CID, we note that $((\mathrm{HighBits}^h(\mathbf{w})), \mathrm{LSB}(w_0)), c, \mathrm{Compress}(\mathbf{z}, c))$ is a valid transcript for the HAETAE CID. Indeed, note that $w_0 = \lfloor y_0 \rfloor \mod 2$ by definition of $\mathcal{A}$. Moreover, applying this deterministic transform turns the distribution of real transcripts for the uncompressed CID to the distribution of real transcripts for the compressed CID. By an immediate reduction, the HAETAE CID also satisfies paHVZK.
<figure><img src="image_7.png" /><figcaption>(a) Uncompressed HAETAE</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(b) Compressed HAETAE</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Figure 11:** Uncompressed HAETAE simulator.</figcaption></figure>

**CUR.** Given $((\mathbf{w}_1, w_0), c, \sigma, \sigma')$ such that $\mathbf{Az} - q\mathbf{cj} = \mathbf{w}_1\alpha_h + w_0\mathbf{j} = \mathbf{Az}' - q\mathbf{cj} \bmod 2q$, we get $\mathbf{A}(\mathbf{z} - \mathbf{z}') = 0 \bmod 2q$, which we can reduce $\mod q$:

$$(-\mathbf{b}|\mathbf{A}_{\text{gen}}|\mathbf{I}\mathbf{d}_k)(\mathbf{z} - \mathbf{z}') = 0 \bmod q.$$

We prove that $\mathbf{z} \neq \mathbf{z}' \bmod q$. Let $\mathbf{z} = (\mathbf{z}_1, \mathbf{z}_1)$ and $\mathbf{z}' = (\mathbf{z}'_1, \mathbf{z}'_2)$. Let $\sigma = (x, \mathbf{v}, h)$ and $\sigma' = (x', \mathbf{v}', h)$. If $\mathbf{z}_1 = \mathbf{z}'_1$ then $x = x'$ and $\mathbf{v} = \mathbf{v}'$ due to the encoding being unique. This means that $h \neq h'$, which in turn will give two different values for $\mathbf{z}_2$ and $\mathbf{z}'_2$ as the other values composing $\mathbf{z}_2$ and $\mathbf{z}'_2$ are identical.

However, $(\mathbf{A}_{\text{gen}}, \mathbf{b})$ is a MLWE$_{n,q,k,l-1,\eta}$ instance instead of being uniform. Both adversaries $\mathcal{B}$ and $\mathcal{B}'$ can run $\mathcal{A}$ by simulating a random oracle in the case of $\mathcal{B}$ and by forwarding the queries to its own oracle in the case of $\mathcal{B}'$. Then, if $\mathcal{A}$ was successful, adversary $\mathcal{B}$ outputs “MLWE” while $\mathcal{B}'$ computes the MSIS solution as described above, and if $\mathcal{A}$ is unsuccessful, adversary $\mathcal{B}$ outputs “unif” while $\mathcal{B}'$ aborts. By the triangular inequality, we get the desired inequality. $\square$

<figure><img src="image_10.png" /></figure>
We reduce the UF-NMA security of the signature scheme to the BimodalSelfTargetMSIS problem.

**Lemma 11 (UF-NMA security).** Let $\mathcal{A}$ be an adversary against the UF-NMA security of HAETAE. There exist two adversaries $\mathcal{B}$ and $\mathcal{B}'$ with essentially the same runtime as $\mathcal{A}$ such that:

$$ \mathrm{Adv}_{\mathrm{HAETAE}}^{\mathrm{UF-NMA}}(\mathcal{A}) \le \mathrm{Adv}_{n,q,k,\ell-1,\eta}(\mathcal{B}) + \mathrm{Adv}_{H,n,q,k,\ell,B''}^{\mathrm{BimodalSelfTargetMSIS}}(\mathcal{B}'). $$

**Proof.** Let us first describe $\mathcal{B}'$. On input the public matrix $\mathbf{A}$, it calls $\mathcal{A}$ on it. The adversary $\mathcal{B}'$ defines the random oracle $H' : (\mathbf{w}_1, w_0, \mu) \mapsto H(\mathbf{w}_1\alpha_h + w_0\mathbf{j} \bmod 2q, \mu)$, to take care of the compression that does not appear in the BimodalSelfTargetMSIS problem. This can be simulated by $\mathcal{B}$ by applying the right function on the queries of $\mathcal{A}$ and forwarding it to its own random oracle $H$.

When $\mathcal{A}$ outputs a valid forgery $\sigma^* = ((x, \mathbf{v}, h), c)$ for some message $\mu^*$, adversary $\mathcal{B}'$ runs Decompress($\mathbf{A}$, $(x, \mathbf{v}, h), c$) to get a vector $\mathbf{z}$ such that $\|\mathbf{z}\| \le B''$ and $H'(\mathrm{HighBits}^h(\mathbf{w}^*), \mathrm{LSB}(w_0^*), \mu) = c$, where we let $\mathbf{w}^* = \mathbf{Az} - q\mathbf{cj} \bmod 2q$. By construction $\mathbf{w}^* = \mathrm{HighBits}^h(\mathbf{w}^*)\alpha_h + \mathrm{LSB}(w_0^*)\mathbf{j} \bmod 2q$, meaning that $c = H(\mathbf{w}^*, \mu)$. Then $(\mathbf{z}, c, \mu^*)$ is exactly a solution to the BimodalSelfTargetMSIS$_{H,n,q,k,\ell,B''}$ problem.

Note that $\mathcal{A}$ is called on a “lossy” instance of HAETAE, where the verification key $\mathbf{b}$ does not have a signing key associated and is actually uniform. This difference in setting exactly corresponds to the MLWE$_{n,q,k,\ell-1,\eta}$ problem. As such the design of $\mathcal{B}$ is as follows: on input $(\mathbf{A}_{\mathrm{gen}}, \mathbf{b})$, it puts together the verification key $\mathbf{A}$ and calls $\mathcal{A}$ on it. It can simulate a random oracle for it, and outputs “MLWE” if $\mathcal{A}$ is successful at forging, “unif” otherwise. $\square$

We combine the previous results with Theorem 4 to get the following security bound for HAETAE.

**Theorem 3.** Let $\mathcal{A}$ be an adversary against the UF-CMA security of HAETAE making $Q_s$ signature queries and $Q_h$ hash queries. Let $\alpha$ be the commitment min-entropy of HAETAE. Let $B^2 \ge B'^2 + \gamma^2\tau$. There exist two adversaries $\mathcal{B}$ and $\mathcal{B}'$ such that

$$ \mathrm{Adv}_{\mathrm{HAETAE}}^{\mathrm{UF-CMA}}(\mathcal{A}) \le \mathrm{Adv}_{n,q,k,\ell-1,\eta}(\mathcal{B}) + \mathrm{Adv}_{H,n,q,k,\ell,B''}^{\mathrm{BimodalSelfTargetMSIS}}(\mathcal{B}') \\ + \frac{2^{-\alpha/2+1}Q_s}{1-\beta}\sqrt{Q_h+1+\frac{Q_s}{1-\beta}} + 2^{-\alpha/2+1}(Q_h+1)\sqrt{\frac{Q_s}{1-\beta}}. \quad (4.1) $$

If $\mathcal{A}$ is an adversary against the sUF-CMA security of HAETAE, then there exist two more adversaries $\mathcal{B}''$ and $\mathcal{B}'''$ such that the previous bound holds by adding the extra term $\mathrm{Adv}_{n,q,k,\ell-1,\eta}^{\mathrm{MLWE}}(\mathcal{B}'') + \mathrm{Adv}_{n,q,k,\ell,2B''}^{\mathrm{MSIS}}(\mathcal{B}'')$.

## 4.4 HAETAE with Pre-computation

We observe that in the randomized signing process of HAETAE, many operations do not depend on the message $M$, and some do not even depend on the signing key. This enables efficient “offline” procedures, i.e., precomputations that speed up the “online” phase.

Specifically, there are two levels of offline signing that can be applied to randomized HAETAE:

1. **Generic.** If neither the message $M$ nor the signing key is chosen in advance, it is still possible to perform hyperball sampling. This removes the most time-consuming operation from the online phase.
**Sign<sup>offline</sup>(vk):**

1: $(\mathbf{a}_{\text{gen}} | \mathbf{A}_{\text{gen}}) = \text{expandA}(\text{seed}_{\mathbf{A}})$

2: $\mathbf{A}_1 = (2(\mathbf{a}_{\text{gen}} - 2\mathbf{b}_1) + q\mathbf{j} | 2\mathbf{A}_{\text{gen}}) \bmod 2q$

3: $\text{List} = (\quad)$

4: **for** iter in $[L]$ **do**

5: $\mathbf{y} \leftarrow U(\mathcal{B}_{(1/N)\mathcal{R}, (k+\ell)}(B))$

6: $\mathbf{w} = \mathbf{A}|\mathbf{y}$

7: $\mathbf{w}_1 = \text{HighBits}^h(\mathbf{w})$

8: $\text{List.append}(\mathbf{y}, \mathbf{w}, \mathbf{w}_1, \text{LSB}(\lfloor y_0 \rfloor))$

9: **return** $\text{List}$

**Sign<sup>online</sup>(sk, List, M):**

1: $\mu = H_{\text{gen}}(\text{seed}_{\mathbf{A}}, \mathbf{b}_1, M)$

2: $\text{tuple} = (\mathbf{y}, \mathbf{w}, \text{tuple}_3, \text{tuple}_4) \leftarrow \text{List}$

3: $\text{List.delete}(\text{tuple})$

4: $c = \text{SampleBinaryChallenge}_{\tau}(H(\text{tuple}_3, \text{tuple}_4, \mu))$

5: $(b, b') \leftarrow \{0, 1\}^2$

6: $\mathbf{z} = (\mathbf{z}_1, \mathbf{z}_2) = \mathbf{y} + (-1)^b c \mathbf{s}$

7: $\mathbf{h} = \text{tuple}_3 - \text{HighBits}^h(\mathbf{w} - 2|\mathbf{z}_2|) \bmod \frac{2(q-1)}{\alpha_h}$

8: **if** $\|\mathbf{z}\|_2 \ge B'$ **then** **Go to 2**

9: **else if** $\|2\mathbf{z} - \mathbf{y}\|_2 < B \land b' = 0$ **then** **Go to 2**

10: **else**

11: $x = \text{Encode}(\text{HighBits}^{z1}(|\mathbf{z}_1|))$

12: $\mathbf{v} = \text{LowBits}^{z1}(|\mathbf{z}_1|)$

13: **return** $\sigma = (x, \mathbf{v}, \text{Encode}(\mathbf{h}), c)$

<caption>**Figure 12:** Randomized, on/off-line signing.</caption>

2. **Designated signing key.** Here, only the message $M$ is unknown during offline signing, while the signing key is fixed. This allows us to perform even more pre-computations by using only the verification key, as shown in Figure 12. Most notably, there is no longer a matrix-vector multiplication in the online phase.

We showcase the offline and online parts of the (randomized) version of HAETAE in Figure 12.

## 4.5 Parameter Sets

To choose parameters reaching the desired NIST security levels, we estimated the costs of practical attacks, as in Dilithium, Falcon, and many other NIST-submitted schemes. In particular, our methodology is directly inspired from the one used in Dilithium, and we sum it up in the following.

Looking at Equation 4.1, we note that we have highly underestimated the commitment min-entropy of the scheme in Lemma 10 as we ignored its biggest part $\mathbf{w}_1$, and we choose to ignore terms on the second line as we are confident that they are small enough. We first evaluate the cost of attacks on MLWE, i.e. key-recovery attacks. Second, to evaluate the cost of forgery attacks, i.e. attacks on BimodalSelfTargetMSIS, we use the fact that the only known way to solve BimodalSelfTargetMSIS is to solve MSIS. Heuristically, the hash function is not aware of the algebraic structure of its input, and the random oracle assumption that $c$ is uniform and independent from the input is sound. Thus, an adversary has no choice but to choose some $\mathbf{w}$, hash its high and low bits along with some message, and try to compute a short preimage of $\mathbf{w} - q\mathbf{j} \bmod 2q$. If the adversary succeeds, the preimage is in particular
<table><caption>**Table 4:** HAETAE parameters sets. Hardness is measured with the Core-SVP methodology and a refined analysis is given for LWE. The numbers in parenthesis for SIS are for the strong unforgeability property.</caption><thead><tr><th colspan="2">Security</th><th>120</th><th>180</th><th>260</th></tr></thead><tbody><tr><td>n</td><td>Degree of <i>R</i> (2.1)</td><td>256</td><td>256</td><td>256</td></tr><tr><td>(k, l)</td><td>Dimensions of <b>z</b><sub>2</sub>, <b>z</b><sub>1</sub> (4.2)</td><td>(2,4)</td><td>(3,6)</td><td>(4,7)</td></tr><tr><td>q</td><td>Modulus for MLWE &amp; MSIS (2.3)</td><td>64513</td><td>64513</td><td>64513</td></tr><tr><td>η</td><td>Range of sk coefficients (2.1)</td><td>1</td><td>1</td><td>1</td></tr><tr><td>τ</td><td>Weight of c (3.3)</td><td>58</td><td>80</td><td>128</td></tr><tr><td>γ</td><td>sk rejection parameter (3.1)</td><td>48.858</td><td>57.707</td><td>55.13</td></tr><tr><td>d</td><td>Resulting key acceptance rate (3.1)</td><td>0.1</td><td>0.1</td><td>0.1</td></tr><tr><td>M</td><td>Truncated bits of vk (3.1)</td><td>1</td><td>1</td><td>0</td></tr><tr><td>B</td><td>Expected # of repetitions (3.4)</td><td>6.0</td><td>5.0</td><td>6.0</td></tr><tr><td>B'</td><td>y radius (3.4)</td><td>9846.02</td><td>18314.98</td><td>22343.66</td></tr><tr><td>B''</td><td>Rejection radius (3.4)</td><td>9838.98</td><td>18307.70</td><td>22334.95</td></tr><tr><td>α</td><td>Verify radius (4.2)</td><td>12777.52</td><td>21906.65</td><td>24441.49</td></tr><tr><td>α<sub>h</sub></td><td>z<sub>1</sub> compression factor (3.5)</td><td>256</td><td>256</td><td>256</td></tr><tr><td>α<sub>h</sub></td><td>h compression factor (3.5)</td><td>512</td><td>512</td><td>512</td></tr><tr><td colspan="5"><strong>Forgery: SIS Hardness (Core-SVP)</strong></td></tr><tr><td>BKZ block-size b (GSA)</td><td></td><td>409 (333)</td><td>617 (512)</td><td>878 (735)</td></tr><tr><td>Classical Core-SVP</td><td></td><td>119 (97)</td><td>180 (149)</td><td>256 (214)</td></tr><tr><td>Quantum Core-SVP</td><td></td><td>105 (85)</td><td>158 (131)</td><td>225 (188)</td></tr><tr><td colspan="5"><strong>Key-recovery: LWE Hardness (Core-SVP and refined)</strong></td></tr><tr><td>BKZ block-size b (GSA)</td><td></td><td>428</td><td>810</td><td>988</td></tr><tr><td>Classical Core-SVP</td><td></td><td>125</td><td>236</td><td>288</td></tr><tr><td>Quantum Core-SVP</td><td></td><td>109</td><td>208</td><td>253</td></tr><tr><td>BKZ block-size b (simulation)</td><td></td><td>439</td><td>834</td><td>1019</td></tr><tr><td>log<sub>2</sub> Classical Gates</td><td></td><td>159</td><td>270</td><td>322</td></tr><tr><td>log<sub>2</sub> Classical Memory</td><td></td><td>99</td><td>177</td><td>214</td></tr></tbody></table>

an MSIS<sub>n,q,k,l+1,√B''+1</sub> solution for the matrix [w|A]. Finally, we evaluate the cost of MSIS with a bound twice as loose to evaluate the strong unforgeability of the HAETAE scheme. Our cryptanalysis of these problems follows the approach taken in Dilithium. We provide a modification of their security estimation script<fnref n="1" />, where we also updated the cost of quantum attacks following recent works [CL21]. These estimations follow the CoreSVP approach. In the case of MLWE, we also give refined estimates, computed in a branch<fnref n="2" /> of the leaky LWE estimator from [DDGR20].

We propose three different parameter sets with varying security levels, where we prioritize low signature and verification key sizes over faster execution time. The parameter choices are versatile, adaptable and allow size vs. speed trade-offs at consistent security levels. For example at cost of larger signatures, a smaller repetition rate *M* is possible and thus a faster signing process. This versatility is a notable advantage over Falcon and Mitaka.

Like in Dilithium, our modulus *q* is constant over the parameter sets and allows an optimized NTT implementation shared for all sets. With only 16-bit in size, our modulus also allows storing coefficients memory-efficiently without compression.

<footnote n="1">¹Available in the submission package.</footnote>

<footnote n="2">²https://github.com/jdevevey/refined-haetae</footnote>
# 5 Implementation Details

In this section, we detail how to efficiently implement HAETAE. However, we leave an extensive specification of implementation aspects to a separate document. The most notable remark from an implementation point of view is that **b** can be transmitted in NTT domain if no rounding is applied, and most arithmetic is carried out modulo *q*, and recovering the values modulo $2q$ is only required for computing the low and high bits. In the following, we detail about the hyperball sampler, packing, and the performance of our reference implementation.

## 5.1 Hyperball Sampler

Essentially, the hyperball sampling procedure consists of four steps:

1. Sample $n(k + \ell) + 2$ discrete Gaussians with $\sigma = 2^{76}$, sum up their squares, and drop two samples eventually.

2. Compute the inverse of the square root of the sum of squares, multiply the result by $B_0 + \sqrt{nm}/(2N)$.

3. Multiply every sample from Step 1 by the result of Step 2.

4. Check the $\ell_2$ norm of the resulting vector, start from Step 1 if this is bigger than $B_0N$.

In the following, we explain how the Gaussian sampling and the approximation of the inverse of the square root can be implemented efficiently. Besides, we choose to generate each of the $k + \ell$ polynomials independently, which helps parallelizing the randomness generation for implementations that use vectorization and hardware implementations. Then, for the first two polynomials, we generate one more Gaussian sample each, which is never stored but included in the sum of squared samples.

### 5.1.1 Discrete Gaussian Sampling

As we will lose precision when computing the inverse square root of a Gaussian sample, we require a Gaussian sampler with high fix-point precision. This is achieved by sampling over $\mathbb{Z}$ with a large standard deviation and then scaling the resulting sample to our convenience. We use [Ros20, Algorithm 12] to sample from a discrete Gaussian distribution with $\sigma = 2^{76}, k = 2^{72}$.

In essence, we start by sampling a discrete Gaussian $x$ with $\sigma = 16$ using a Cumulative Distribution Table (CDT) and a uniform $y \in \{0, \dots, 2^{72} - 1\}$ and set the Gaussian sample candidate as $r = x2^{72} + y$. Subsequently, this candidate is accepted with probability $\exp(-y(y + x2^{73})/2^{153})$. Fortunately, we achieve a very low rejection rate of less than 5%.

Specifically, the CDT we use has 64 entries and uses a precision of 16 bit. Then, to compute the sample candidate's square and the input to the exponential, we first compute $r^2$ and round the result to 76-bit precision, which is accumulated later if the sample is accepted. Subsequently, $r^2 - 2^{76}x^2$ yields the input to the exponential.

**Approximating the Exponential.** For this, we need to approximate the exponential function $e^{-x}$ by a polynomial $f(x)$ on the closed interval $[c - \frac{w}{2}, c + \frac{w}{2}]$, with center $c$ and width $w$. We first determine an upper bound for the polynomial order required to approximate $e^{-x}$, given an upper bound for the absolute error. We obtain $f(x)$ by truncating the expansion of $e^{-x}$ into a series of Chebyshev polynomials of the first
kind $T_n(x)$ with linearly transformed input, as this is known to yield small absolute approximation errors for a given polynomial order. We find:

$$e^{-x} = -e^{-c} + 2e^{-c} \sum_{n=0}^{\infty} (-1)^n I_n\left(\frac{w}{2}\right) T_n\left(\frac{x-c}{w/2}\right) \quad x \in [c - \frac{w}{2}, c + \frac{w}{2}]$$

where $I_n(z)$ are modified Bessel functions of the first kind, which rapidly converge to zero for growing $n$. We recall $\|T_n(x)\| \le 1$ for $\|x\| \le 1$. For intervals $[0, w]$ with not too large widths we find $2e^{-c}I_{m+1}(\frac{w}{2})$ to be a useful estimate of the maximum absolute error, when truncating the series at order $m > 1$. This relation allows us to directly limit $m$ according to the interval to cover and the maximum permissible error.

We then determine the polynomial $f(x)$ of at most order $m$ by using the Chebyshev approximation formula, which has been shown to result in a nearly optimal approximation polynomial in the case of the exponential function [Li04]. The number of fraction bits is chosen to match the error. The numerical evaluation is performed in fixed-point arithmetic using the Horner's scheme and multiplying with shifts to retain significant bits. When shifting right, we round half up, which retains about one additional bit of accuracy when compared to truncation.

Barthe et al. [BBE$^{+}$19] introduced the GALACTICS toolbox to derive suitable polynomials approximating $e^{-x}$. They numerically evaluate and modify trial polynomials, minimizing the relative error, until an acceptable level is reached. The polynomials are evaluated using a Horner's scheme, similar to this work, but rely on truncation. When comparing to polynomials derived using the GALACTICS toolbox, our approximation has a slightly smaller absolute error for intervals of interest in this work, while maintaining the same polynomial order and constant time properties. This holds even when introducing rounding to the GALACTICS evaluation of polynomials. Moreover, our approach is somewhat less heuristic than the GALACTICS method. Practically, as can be seen in Listing 1, the approximation consists of six signed 48-bit multiplications with subsequent rounding (smulh48), several constant shifts with rounding and constant additions.

<caption>**Listing 1:** Fix-point approximation of the exponential function with 48 bit of precision.</caption>

```c
static uint64_t approx_exp(const uint64_t x) {
    int64_t result;
    result = -0x0000B6C6340925AELL;
    result = ((smulh48(result, x) + (1LL << 2)) >> 3) + 0x0000B4BD4DF85227LL;
    result = ((smulh48(result, x) + (1LL << 2)) >> 3) - 0x0000887F727491E2LL;
    result = ((smulh48(result, x) + (1LL << 1)) >> 2) + 0x0000AAAA643C7E8DLL;
    result = ((smulh48(result, x) + (1LL << 1)) >> 2) - 0x0000AAAAA98179E6LL;
    result = ((smulh48(result, x) + 1LL) >> 1) + 0x0000FFFFFFFFF2E7ALL;
    result = ((smulh48(result, x) + 1LL) >> 1) - 0x0000FFFFFFFFF85FLL;
    result = ((smulh48(result, x))) + 0x0000FFFFFFFFFFFFFCLL;
    return result;
}
```

**Finalization.** If the sample is accepted eventually, it is (implicitly) scaled by the factor $2^{-76}$ to obtain a continuous sample from the standard normal distribution. Moreover, we only need to store the upper 64 bits of the sample and round off the rest.

In summary, each Gaussian sample candidate requires **72 bit** randomness for the lower part of the candidate ($y$), **16 bit** randomness for the CDT sampling, and **48 bit** randomness for rejecting the candidate conditionally according to the output of the exponential. This results in a vast randomness demand per hyperball sample, and explains the dominance of hashing in the cycle count performance.
<table><caption>**Table 5:** Symbol mapping and encoding size parameters.</caption><thead><tr><th>Scheme</th><th>cut<sub>h</sub></th><th>offset<sub>h</sub></th><th>|{S<sub>h</sub>(n)}</th><th>cut<sub>z<sub>1</sub></sub></th><th>|{S<sub>z<sub>1</sub></sub>(n)}</th><th>base<sub>h</sub></th><th>base<sub>z<sub>1</sub></sub></th></tr></thead><tbody><tr><td>HAETAE-120</td><td>6</td><td>239</td><td>13</td><td>6</td><td>13</td><td>7</td><td>132</td></tr><tr><td>HAETAE-180</td><td>8</td><td>235</td><td>17</td><td>8</td><td>17</td><td>127</td><td>376</td></tr><tr><td>HAETAE-260</td><td>16</td><td>471</td><td>33</td><td>9</td><td>19</td><td>358</td><td>501</td></tr></tbody></table>

### 5.1.2 Approximating the Inverse of the Square Root

To turn the vector of standard normal distributed variates into a hyperball sample candidate, we must compute its norm. For this, we accumulate all squared samples and approximate the inverse of the square root of the accumulated value. The approximation result is then multiplied by the constant $r' + \sqrt{nm/(2N)}$, which yields the scaling factor that is multiplied to each Gaussian sample. For the inverse square root, we deploy Newton's method, which is a well-known technique for that purpose. However, Newton's method requires a starting approximation that is, with each iteration, turned into a better approximation. Fortunately, we know that the sum of $nm + 2$ independent squared standard normal variables follows a $\chi^2$ distribution with expected value $nm + 2$. Hence, the starting approximation can be fixed and precomputed as $1/\sqrt{nm+2}$. The number of iterations for a targeted precision can be determined experimentally. Therefore, we performed the approximation for the first input values that have negligible probabilities either for the cumulative distribution function of $\chi^2(nm + 2)$ or its survival function, and checked how many iterations are required to still reach reasonable precision.

## 5.2 Signature Packing and Sizes

The last step of the signature generation is to compress and pack the elements of the signature. A packed HAETAE signature consists of the challenge $c$, the low bits of $z_1$ ($LN$ coefficients), the high bits of $z_1$ and $h$ ($KN$ coefficients). Because the distributions of the values in the high bits of $z_1$ and the coefficients in $h$ are both very dense, we can compress both polynomial vectors with encoding. Figure 13 displays the frequencies for the possible values for both vectors in HAETAE-120. Before compressing the values, we map them to a smaller symbol space and thereby reject the very unlikely values and the corresponding signatures. For $h$ we cut out most of the values in the middle of the range, for HAETAE-120 this reduces the size of the symbol space from 252 to 13.

$$S_h(n) = \begin{cases} n, & \text{for } 0 \le n \le \text{cut}_h \\ \perp, & \text{for } \text{cut}_h < n \le \text{cut}_h + \text{offset}_h \\ n - \text{offset}_h, & \text{for } \text{cut}_h + \text{offset}_h < n \end{cases}$$

For the high bits of $z_1$ we tail-cut the distribution left and right of the center at 0, and then shift the remaining values to the non-negative range beginning at 0. For HAETAE-120 this reduces the size of the symbol space from 37 to 13.

$$S_{z_1}(n) = \begin{cases} \perp, & \text{for } n < -\text{cut}_{z_1} \\ n + \text{cut}_{z_1}, & \text{for } -\text{cut}_{z_1} \le n \le \text{cut}_{z_1} \\ \perp, & \text{for } \text{cut}_{z_1} < n \end{cases}$$

The parameters for these mappings are defined in Table 5. At the signature verification, the mapping must be reverted after decoding the compressed symbols.

The reason for these mappings is mainly to get significantly smaller precomputation tables for the rANS encoding and decoding. Also, all symbols can now be represented with 8-bits, which simplifies the rANS implementation. Furthermore, for the high bits of $z_1$, a mapping to non-negative values is necessary to be able to use rANS encoding. The effect on the resulting signature size is insignificant.
<figure><img src="image_11.png" /><figcaption>**Figure 13:** Distribution of the coefficients of $h$ and $HB(z_1)$ in HAETAE-120.</figcaption></figure>

The size of the compressed high bits of $z_1$ and $h$ varies and must be included in the signature, to allow a correct unpacking and decoding. The size of one compressed polynomial vector is often more than 255 bytes, and can thus not be expressed by one byte. Its variance however, is limited, and thus we encode the size the compressed high bits of $z_1$ and $h$ as positive offset to a fixed base value. This unsigned offset value fits into one byte in most of the cases, if not, the signature gets rejected. The base values can be found in Table 5.

The final signature is then built as following: The first 32 bytes contain the seed for the challenge polynomial $c$. Following, we have $LN$ bytes for the low bits of $z_1$. The next first byte consists of the offset to the base size for the encoding of the high bits of $z_1$ and the second byte is the offset for $h$. Then we have the encoding of the high bits of $z_1$ and directly afterwards the encoding of $h$, both with varying sizes, which are indicated beforehand. Lastly, the signature is padded with zero bytes to reach the fixed signature size, if any bytes remain. Signatures that would exceed the fixed limit get rejected.

To prevent signature forgeries, during signature unpacking and decoding multiple sanity checks have to be performed: the zero padding must be correct, the decoding must not fail and decode the expected number of coefficients while using exactly the amount of bytes indicated with the offset. Furthermore, rANS decoding must end with the fixed predefined start value to be unique. Our rANS encoding is based on an implementation by Fabian Giesen [Gie14].

To set the fixed signature size as reported in Table 6, we evaluated the distribution empirically and determined a threshold that requires a rejection in less than 0.1% of the
<table><caption>**Table 6:** NIST security level, signature and key sizes (bytes) of HAETAE, Dilithium, and Falcon.</caption><thead><tr><th>Scheme</th><th>Lvl.</th><th>vk</th><th>Signature</th><th>Sum</th><th>Secret key</th></tr></thead><tbody><tr><td>HAETAE-120</td><td>2</td><td>992</td><td>1,474</td><td>2,466</td><td>1,408</td></tr><tr><td>HAETAE-180</td><td>3</td><td>1,472</td><td>2,349</td><td>3,821</td><td>2,112</td></tr><tr><td>HAETAE-260</td><td>5</td><td>2,080</td><td>2,948</td><td>5,028</td><td>2,752</td></tr><tr><td>Dilithium-2</td><td>2</td><td>1,312</td><td>2,420</td><td>3,732</td><td>2,528</td></tr><tr><td>Dilithium-3</td><td>3</td><td>1,952</td><td>3,293</td><td>5,245</td><td>4,000</td></tr><tr><td>Dilithium-5</td><td>5</td><td>2,592</td><td>4,595</td><td>7,187</td><td>4,864</td></tr><tr><td>Falcon-512</td><td>1</td><td>897</td><td>666</td><td>1,563</td><td>1,281</td></tr><tr><td>Falcon-1024</td><td>5</td><td>1,792</td><td>1,280</td><td>3,072</td><td>2,305</td></tr></tbody></table>

cases. Figure 14 displays the raw signature size distribution of 20000 executions (without the size-based rejection sampling).

<figure><img src="image_12.png" /><figcaption>**Figure 14:** Raw signature size distribution over 20000 executions. We set the bound for the size-based rejection to result in a rejection rate of less than 0.1%.</figcaption></figure>

In Table 6 we compare the signature and key sizes of HAETAE, Dilithium, and Falcon. The verification keys in HAETAE are 20% (HAETAE-260) to 25% (HAETAE-120 and HAETAE-180) smaller, than their counterparts in Dilithium. The advantage of the hyperball sampling manifests itself in the signature sizes, HAETAE has 29% to 39% smaller signatures than Dilithium. Less relevant are the secret key sizes, that are almost half the size in HAETAE compared to Dilithium. A direct comparison to Falcon for the same claimed security level is only possible for the highest parameter set, Falcon-1024 has a signature of less than half the size compared to HAETAE-260, and its verification key is about 14% smaller.
## 5.3 Performance Reference Implementation

We developed an unoptimized, portable and constant-time implementation in C for HAETAE and report median and average cycle counts of one thousand executions for each parameter set in Table 7. Due to the key and signature rejection steps, the median and average values for key generation and signing respectively differ clearly, whereas the two values are much closer for the verification.

<table><caption>**Table 7:** Reference implementation speeds. Median and average cycle counts of 1000 executions for HAETAE, Dilithium, and Falcon. Cycle counts were obtained on one core of an Intel Core i7-10700k, with TurboBoost and hyperthreading disabled.</caption><thead><tr><th>Scheme</th><th></th><th>KeyGen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td rowspan="2">HAETAE-120</td><td>med</td><td>1,403,402</td><td>6,039,674</td><td>376,486</td></tr><tr><td>ave</td><td>1,827,567</td><td>9,458,682</td><td>376,631</td></tr><tr><td rowspan="2">HAETAE-180</td><td>med</td><td>2,368,038</td><td>9,161,312</td><td>691,652</td></tr><tr><td>ave</td><td>3,448,185</td><td>11,611,868</td><td>692,014</td></tr><tr><td rowspan="2">HAETAE-260</td><td>med</td><td>3,101,280</td><td>11,444,678</td><td>895,098</td></tr><tr><td>ave</td><td>4,088,383</td><td>17,229,712</td><td>896,622</td></tr><tr><td rowspan="2">Dilithium-2</td><td>med</td><td>343,222</td><td>1,191,218</td><td>376,008</td></tr><tr><td>ave</td><td>343,639</td><td>1,527,406</td><td>376,543</td></tr><tr><td rowspan="2">Dilithium-3</td><td>med</td><td>630,170</td><td>2,061,816</td><td>612,538</td></tr><tr><td>ave</td><td>630,607</td><td>2,603,237</td><td>612,852</td></tr><tr><td rowspan="2">Dilithium-5</td><td>med</td><td>945,776</td><td>2,522,834</td><td>987,154</td></tr><tr><td>ave</td><td>949,662</td><td>3,080,734</td><td>988,250</td></tr><tr><td rowspan="2">Falcon-512</td><td>med</td><td>53,778,476</td><td>17,332,716</td><td>103,056</td></tr><tr><td>ave</td><td>60,301,272</td><td>17,335,484</td><td>103,184</td></tr><tr><td rowspan="2">Falcon-1024</td><td>med</td><td>154,298,384</td><td>38,014,050</td><td>224,378</td></tr><tr><td>ave</td><td>178,516,059</td><td>38,009,559</td><td>224,840</td></tr></tbody></table>

For a fair comparison, we also performed measurements on the same system with identical settings of the reference implementation of Dilithium<fnref n="1" /> and the implementation with emulated floating-point operations, and thus also fully portable, of Falcon<fnref n="2" />, as given in Table 7. The performance of the signature verification for HAETAE is very close to Dilithium throughout the parameter sets. HAETAE-180 verification is 13% slower than its counter-part, HAETAE-260 on the other hand, is 9% faster than the respective Dilithium parameter set. For key generation and signature computation, our current implementation of HAETAE is clearly slower than Dilithium. We measure a slowdown of factors three to five. In comparison to Falcon, however, HAETAE has 38-50 times faster key generation and around three times faster signing speed. For the verification, Falcon outperforms both Dilithium and HAETAE by roughly a factor of four.

A closer look at the key generation reveals that the complex Fast Fourier Transformation, that is required for the rejection step, is with 53% by far the most expensive operation and a sensible target for optimized implementations.

Profiling the signature computation reveals that the slowdown compared to Dilithium is mainly caused by the sampling from a hyperball, where about 80% of the computation time is spent. The hyperball sampling itself is dominated by the generation of randomness, which we derive from the extendable output function SHAKE256 [Dwo15], which is also used in the Dilithium implementation. Almost 60% of the signature computation time is spent in SHAKE256.

Based on the profiling and benchmarking of subcomponents, we estimate the performance of a randomized HAETAE implementation with pre-computation. The generic

<footnote n="1">¹https://github.com/pq-crystals/dilithium/tree/master/ref</footnote>

<footnote n="2">²https://falcon-sign.info/falcon-round3.zip</footnote>
version, which is independent of the key, would already achieve a speedup of a factor five for its online signing, because the expensive hyperball sampling can be done offline. For the pre-computation variant with a designated signing key, additionally, a lot of matrix-vector multiplications and therefore most of the transformations from and to the NTT domain, can be precomputed. We estimate about 12% of the full deterministic signing running time, for the online signing in this case.

# 6 Optimized Implementation for AVX2

Advanced Vector Extensions 2 (AVX2) is an extension to the x86 instruction set architecture and available in processors since 2011. It provides Single Instruction Multiple Data (SIMD) operations on 256-bit registers, and thus allows to e.g. do an operation on eight 32-bit values in parallel. In this section we explain, how to exploit this parallelization.

The three major components, that significantly determine the computation time of HAETAE are Keccak, the NTT and the hyperball sampling. For the first two components we can fall back to existing optimized code. For the NTT in particular, we can reuse the implementation in Dilithium with only slight adaptions with regard to constants. In the following we demonstrate how to implement the third component, the hyperball sampling efficiently using AVX2 instructions.

## 6.1 Vectorized Hyperball Sampling

After the parallel generation of the randomness, generally, we have two options to parallelize the hyperball sampling. First, we can sample four different polynomials in parallel, and second, we can generate the Gaussian samples within a polynomial in parallel, since they are generated independently. We opt for the first approach.

As the sampling process is relatively complex, we cannot load input vectors, generate samples from them, and eventually store the samples. Instead, we pass several times over the internal memory state, dividing the procedure into seven separate steps:

1. parsing of the input randomness: separating the three parts for each sample candidate into separate memory locations such that later steps can process them quickly,

2. CDT sampling,

3. constructing the sample candidate, its square, and the input to the exponential approximation,

4. approximate the exponential,

5. generate masks which candidates to reject,

6. accumulate the squares of the non-rejected samples, and

7. storing only the accepted samples into the correct final memory positions.

In the following, we detail Steps 2, 3, and 4.

### 6.1.1 Parallel CDT Sampling

Although we perform 16-bit CDT sampling, we cannot use the 16-fold parallel `vpcmpgtw` comparison, since it is a *signed* comparison, and use `vpcmpgtd` instead, which operates on eight signed 32-bit integers. As we want to sample four samples in parallel, we store the CDT and the input randomness redundantly, such that we can perform the comparison
with all 64 entries with 32 comparisons. However, since AVX2 only offers 16 vector registers, we have to perform this comparison in three chunks.

`vpcmpgtd c, a, b` writes -1 to c if the respective vector element in a is in fact greater than its counterpart in b, and else 0. Thus, we can use `vpaddd` to accumulate these results, but they will be negative. For the final chunk, we use `vpsrlq` to line up the two intermediate results, then add them and negate them.

### 6.1.2 Multi-precision Squaring

Since the sample candidate is 72 bits long and AVX2 only supports 32-bit multiplication, we perform vectorized multi-precision arithmetic. Therefore, we split the candidate into its low 32 bits, the middle 16 bits, and the upper 31 bits. For the schoolbook multiplication, we perform the six partial multiplications with `vpmuludq` consecutively, such that they can be executed pipelined and in parallel. The subsequent recombination and rounding can be performed with a sequence of 16 instructions of shifts (`vpsrlq`, `vpsllq`), additions (`vpaddq`), and ANDs (`vpand`).

### 6.1.3 Vectorized Approximation of the Exponential

The exponential approximation as explained in Section 5.1 consists of six signed 48-bit multiplications, which is not supported natively by AVX2. Consequently, we implement this operation with a vectorized multi-precision approach.

More specifically, we know that the first operand of this multiplication is signed, and the second is not. Thus, splitting the second operand into a low and a high half is trivial, but for the signed operand, this requires a slightly more sophisticated approach: Here, the upper half is obtained by an arithmetic right-shift by 24. By shifting this result left again by 24 (shifting in zeros), and subtracting the result from the original value, we obtain the lower half.

Since AVX2 does not offer a signed right shift over 64-bit entries, we generate a mask of sign bits and simulate a signed right shift by performing a bitwise OR. Unfortunately, we require this operation three times during a single signed multiplication operation. Notably, AVX512 offers a signed right shift, which will speed up this operation considerably.

Eventually, we perform a vectorized signed 48-bit multiplication using 32 instructions, out of which 17 are used for the emulation of a signed right shift. Moreover, we use seven variable and three constant vector registers (out of which one is the second input, cf. Listing 1), which leaves six registers for other constants. Apart from the multiplication, we only make use of addition and shifts (`vpaddq`, `vpsrlq`).

## 6.2 Performance and Comparison AVX2

The impact of the parallelized Keccak can be observed by looking at the cycle costs for unpacking the matrix $A$, which is between five to seven times faster compared to the reference implementation. For e.g. HAETAE-120, the costs went down from around 132k cycles to 24k cycles. The picture is similar for the hyperball sampling, where we measure a speed-up of factor six to eight. The cycle counts for one function call in HAETAE-120 are around 1640k in the reference and 270k in the optimized implementation. The highly optimized NTT taken from Dilithium, is almost 19 times faster than the one in our portable reference code.

Table 8 provides cycle numbers for the AVX2 optimized implementations of HAETAE, Dilithium <fnref n="1" /> and Falcon <fnref n="2" />. Compared to our reference implementation, the signature

<footnote n="1">¹https://github.com/pq-crystals/dilithium/tree/master/avx2</footnote>

<footnote n="2">²https://falcon-sign.info/falcon-round3.zip</footnote>
<table><caption>**Table 8:** AVX2 optimized implementation speeds. Median and average cycle counts of 1000 executions for HAETAE, Dilithium, and Falcon. Cycle counts were obtained on one core of an Intel Core i7-10700k, with TurboBoost and hyperthreading disabled.</caption><thead><tr><th>Scheme</th><th></th><th>KeyGen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td rowspan="2">HAETAE-120</td><td>med</td><td>535,210</td><td>1,306,112</td><td>108,840</td></tr><tr><td>ave</td><td>733,350</td><td>1,916,063</td><td>108,890</td></tr><tr><td rowspan="2">HAETAE-180</td><td>med</td><td>820,570</td><td>1,793,342</td><td>167,722</td></tr><tr><td>ave</td><td>1,122,867</td><td>2,198,920</td><td>167,787</td></tr><tr><td rowspan="2">HAETAE-260</td><td>med</td><td>872,280</td><td>2,049,008</td><td>207,146</td></tr><tr><td>ave</td><td>1,202,911</td><td>3,013,239</td><td>207,229</td></tr><tr><td rowspan="2">Dilithium-2</td><td>med</td><td>87,020</td><td>200,242</td><td>92,148</td></tr><tr><td>ave</td><td>86,937</td><td>252,905</td><td>92,190</td></tr><tr><td rowspan="2">Dilithium-3</td><td>med</td><td>146,560</td><td>334,898</td><td>148,810</td></tr><tr><td>ave</td><td>146,688</td><td>402,012</td><td>148,883</td></tr><tr><td rowspan="2">Dilithium-5</td><td>med</td><td>233,976</td><td>415,228</td><td>232,146</td></tr><tr><td>ave</td><td>233,895</td><td>484,119</td><td>232,241</td></tr><tr><td rowspan="2">Falcon-512</td><td>med</td><td>24,663,306</td><td>863,076</td><td>100,540</td></tr><tr><td>ave</td><td>26,637,878</td><td>863,420</td><td>100,709</td></tr><tr><td rowspan="2">Falcon-1024</td><td>med</td><td>71,013,520</td><td>1,740,188</td><td>228,086</td></tr><tr><td>ave</td><td>78,797,658</td><td>1,740,520</td><td>228,326</td></tr></tbody></table>

generation is around five times faster in the optimized implementation. For the signature verification we observe an acceleration of around three to four.

The comparison with Dilithium does not change distinctly with respect to the reference implementations. Key generation and signature generation are about six times faster with Dilithium and the speed differences in the verification are up to 24% with the optimized implementations. Falcon on the other hand is considerably faster at the signature generation with its AVX2 implementation, compared to its portable reference code. The performance of the reference code in Table 7 showed around three times faster signature generation for HAETAE compared to Falcon. Optimized for AVX2 and also using the floating-point unit, Falcon becomes faster than HAETAE for signature generation. Key generation is still at least forty times faster with HAETAE compared to Falcon, and the verification speed is very similar for both schemes.

We note, however, that both Dilithium and Falcon went through a multi-year process of incrementally optimized implementations, whereas this process has just started for HAETAE. Moreover, when we apply the heuristic that sending one byte via internet costs at least 1000 cycles [BBC+20, Sec. 5.4], remarkably, HAETAE is already nearly as performant as Dilithium in terms of signing plus sending the signature.

# 7 Embedded Implementation on Cortex-M4

To evaluate the suitability of HAETAE for embedded environments we developed an implementation for the STM32f4-Discovery board, featuring 128 KiB RAM and a Cortex-M4F processor which implements the ARMv7E-M ISA and operates on 32-bit words. We use the PQM4 framework [KRSS19] for development and evaluation, as it is the de facto standard for comparison of post-quantum cryptography schemes on Cortex-M4 processors. The Cortex-M4F, in contrast to the Cortex-M4, features a floating-point unit. Its floating point registers can be used to store and load intermediate values within a single cycle to reduce the pressure on the 13 general purpose registers.

The profiling of the reference implementation already indicates that replacing the portable Keccak implementation with one optimized for the Cortex-M4 is an important
and straightforward step towards fast execution time. The two other major components
that are highly relevant are the polynomial arithmetic and the Gaussian sampler, both
will be discussed in the following.

**7.1 Polynomial Arithmetic**

In this section, we will address the issue of how to implement the required arithmetic
operations on these rings and mappings between them on a Cortex-M4 platform.

**Modular Reductions.** In modular arithmetic, the Barret reduction [Bar87], the Montgomery modular multiplication [Mon85], and related techniques are indispensable for efficient computation, the first for reducing given numbers, the second for yielding the reduced result of a multiplication with a constant mod$q$. The algorithms avoid computationally expensive divisions by $q$ and replace them with a multiplication by a suitably chosen number and division by powers of two, which can be realized with shift operations. Both methods initially reduce the result to the interval $[0, 2q]$ and perform the full reduction with a conditional subtraction, which can be done in constant time. In many cases one can forgo the final reduction for intermediate results, an approach dubbed lazy reduction.

The prime chosen in the HAETAE scheme is $q = 64513 = 0xC01$, the largest unsigned 16-bit prime with a $512^{th}$ root of unity. Fully reduced elements of $\mathbb{Z}_q$ can be stored efficiently in 16-bit in the bottom or top half of a 32-bit register.

Unfortunately, this does not carry over to arithmetic operations. A lazy reduction or an addition already requires 17 bits to store the result, a combination of a lazily reduced multiplication followed by an addition requires 18 bits. The recent advance of the Plantard multiplication [Pla21] is not useful within this work, as the prime in HAETAE is not compatible. Plantard multiplication requires $q < \frac{2R}{1+\sqrt{5}} \approx 0.618R$, i.e., $q \le 40503$ for $R = 2^{16}$. So the prime of HAETAE is too large for this use-case with Cortex-M4 16-bit DSP-instructions. The same goes for Seiler's variant [Sei18] of signed Montgomery modular multiplication, which is only well-defined for $q < \frac{R}{2}$.

**16-bit vs 32-bit.** Quite a few post-quantum schemes use primes that are 13-bit values or smaller. In this case, one can both store and manipulate the coefficients graciously and efficiently as two signed 16-bit values packed into one 32-bit register, as the Cortex-M4 offers a wide range of instructions intended for Digital Signal Processor (DSP) applications, like mixed multiplication of upper and lower halves of two registers that can be used for this purpose. In the case of HAETAE, trade-offs need to be found between the compactness of 16-bit storage and doubled speed of access for consecutive coefficients on the one hand, and the required overhead to fully reduce the coefficients before writing them to memory.

If coefficients are written once and afterwards are read repeatedly without alterations, the 16-bit representation can be worthwhile. When polynomials of the public key are expanded, the coefficients are sampled in fully reduced state, we therefore store them in halfwords.

While it is feasible to use a modified Montgomery reduction with unsigned 16-bit integers as input and 17 bits output (or a 16-bit value with overflow flag), there are no corresponding instructions available to exploit this. In contrast, the Montgomery reduction in the Dilithium implementation for the Cortex-M4 uses $R = 2^{32}$ and takes only three instructions. We determined the overhead associated with full reductions required to store coefficients as 16-bit values to be too large to outperform the 32-bit variant for the NTT. The same applies to other polynomial arithmetic operations in HAETAE, besides the expanded polynomials of the public key, we therefore operate on 32-bit coefficients.
NTT. HAETAE, as other lattice-based schemes, extensively employs polynomial multipli-
cation. The NTT is a generalization of the FFT and is the state-of-the-art technique to
perform this operation, speeding up the computation considerably, as compared to, e.g.,
schoolbook multiplication. The addition and multiplication of polynomials transformed
into the NTT domain are carried out coefficient-wise, greatly reducing the cost of the
latter operation. The overhead to perform the transform and inverse transform, where
required, is usually outweighed by the performance gain in the multiplication. HAETAE is
specified such that large parts of the public key are expanded directly to the NTT domain.

Fortunately, the closeness to Dilithium, which also uses polynomials of degree $n = 256$, allows us the reuse its highly optimized assembly code for the NTT developed for the Cortex-M4 by Abdulrahman et al. [AHKS22], which improves over previous work [GKOS18]. The code adjustments required for operation in HAETAE are limited to adjusting constants like the prime being used, the root of unity, which is chosen as 426 (the primitive $512^{th}$ root of unity of $q = 64513$) and the twiddle factors.

Replacing the portable C code from the reference implementation with optimized
assembly derived from the Dilithium implementation reduces the cycle count per invocation
from 37506 cycles to 8047 cycles, a speed-up by a factor of **4.6**. For the inverse NTT, the
cycle count dropped from 43116 to 8369, a speed-up by a factor of **5.1**.

## 7.2 Gaussian Sampler

The major numerical components of the Gaussian sampler are the CDT sampler for
sampling the most significant bits and the fixed-point exponential function used in the
rejection step. As both components are called repeatedly, both have been implemented in
assembly code.

The CDT sampler accumulates ones and zeros, depending on comparisons of a uniformly
sampled 16-bit random value to tabled threshold values. We use the uadd16, usub16 and
sel SIMD instructions from the Cortex-M4 instruction set to carry out two comparisons
and accumulations in parallel. We furthermore optimize the memory access and unroll
the loop. By doing so we reduce the instruction count from 800 cyles for the reference
implementation to 206 cyles, a speed-up by a factor of 3.9.

The exponential is approximated by a polynomial, which is evaluated using Horner's
scheme. The reference implementation of the exponential function uses fixed-point
arithmetic with 48 fraction bits. Values are embedded in 64-bit integers and 64x64
to 128-bit multiplication is used. The latter operation has no native support on the
Cortex-M4. To circumvent this limitation, the Cortex-M4 implementation splits the value
into two signed components at the start of each multiplication, namely the most significant
bits ah = a >> 24 and the least significant bits as al = a - ah. For the accumulation of
the results a 64-bit integer is used again, taking advantage of the smlal instruction. This
repeated switch between representations allows for efficient computation of the individual
Horner's scheme iterations. Whereas the reference implementation of the exponential
function takes 1658 cycles to execute, this is reduced to 563 instructions in the optimized
Cortex-M4 code, a speed-up by a factor of 2.9.

## 7.3 Stack Optimization

Besides execution time, also the memory footprint is an important metric for constrained
devices. The target device in this work has 128 KiB of RAM available as stack memory.
In this context, data structures typically encountered in lattice based cryptography need
to be considered as rather large. A single polynomial in HAETAE takes 512 B or 1 KiB of
memory to store, depending on whether the data is represented as 16-bit or 32-bit values.
So vectors or matrices of polynomials can occupy a considerable share of the available
RAM, if stored in their entirety. In this section we explore how to minimize memory use; in some cases significant trade-offs between memory usage and execution speed can be made.

The reference implementation of HAETAE is designed with an emphasis on readability and close similarity to the mathematical specification. This results in top level functions, which consist of long monolithic blocks with many large data structures, which do not necessarily have overlapping lifetimes, but nevertheless occupy stack space for the entire function lifecycle. Most stack memory is required for the signature generation. Due to the unnecessarily high stack usage of the reference implementation, HAETAE-180 and HAETAE-260 do not run on the STM32f4-Discovery board without optimizations.

To reduce the memory footprint we executed two strategies. First, we carefully analyzed the liveness of each relevant variable and refactored the monolithic code into subroutines to reduce the scope of variables and thereby the total stack usage. This slightly impacts the readability of the code, but does not affect the speed.

In a second variant we additionally opted for a more aggressive memory reduction, by recomputing polynomials on demand, this obviously comes with performance costs. We adapt the data structures to be primarily polynomial oriented instead of vector and matrix oriented representations. Recomputations are done during public key usage, where we generate each polynomial on demand, and during hyperball sampling, where we sample each polynomial twice, once for the evaluation of the normalization factor and a second time to sample the actual y values. Since the hyperball sampling is computationally very expensive, this leads to a severe overhead in runtime.

## 7.4 Performance and Comparison Cortex-M4

Table 9 shows the maximum stack size of our two Cortex-M4 implementations of HAETAE and values reported in the PQM4 framework about Dilithium and Falcon. With speed-opt, we refer to our implementation, that is optimized for the Cortex-M4 and includes multiple stack-size optimizations, but does not trade speed for better memory requirements. stack-opt refers to the version, where we additionally exploit speed vs memory trade-offs.

First, we can observe that the memory requirements of HAETAE are small enough to run on the STM32f4-Discovery board for all parameter sets, even in the speed-opt version. Second, the stack sizes for HAETAE are in the same order of magnitude as Dilithium and Falcon. Compared to speed-opt HAETAE, Dilithium requires around two to three times more memory during key generation, and a similar overhead for signature verification. The difference is at most 20% for signature generation, for this operation Dilithium requires less memory than HAETAE for the first two parameter sets.

Our stack-opt version reduces the stack-size up to 34% during signature generation and key generation, but does not differ for the verification. However, this comes with higher costs in terms of computation time.

Falcon stands out for its stack-size below 10 KiB for both parameter sets during verification.

Table 9 shows the cycles spend by our two Cortex-M4 implementations of HAETAE and values reported in the PQM4 framework<fnref n="1" /> for Dilithium and Falcon. Our version using aggressive stack reduction techniques based on recomputations does not impact the signature verification time, but almost doubles the computation time for the signature generation. The time overhead for key generation is up to 30%. Similar to our AVX2 optimized implementation, the relative performance comparison of HAETAE to Dilithium and Falcon does not change drastically.

<footnote n="1">¹https://github.com/mupq/pqm4/blob/master/benchmarks.md</footnote>
<table><caption>**Table 9:** Maximum stack size in bytes and average kilo cycle counts of 1000 (100 for Falcon) executions for Cortex-M4 implementations of HAETAE, Dilithium, and Falcon.</caption><thead><tr><th rowspan="2">Scheme</th><th rowspan="2"></th><th colspan="3">Stack size</th><th colspan="3">Cycle count</th></tr><tr><th>KeyGen</th><th>Sign</th><th>Verify</th><th>KeyGen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td rowspan="2">HAETAE-120</td><td>speed-opt</td><td>19,796</td><td>54,564</td><td>22,532</td><td>8,905</td><td>27,312</td><td>1,054</td></tr><tr><td>stack-opt</td><td>17,364</td><td>40,732</td><td>22,532</td><td>10,819</td><td>51,017</td><td>1,054</td></tr><tr><td rowspan="2">HAETAE-180</td><td>speed-opt</td><td>29,612</td><td>69,631</td><td>31,020</td><td>17,666</td><td>34,466</td><td>2,026</td></tr><tr><td>stack-opt</td><td>22,444</td><td>57,116</td><td>31,020</td><td>22,860</td><td>65,855</td><td>2,026</td></tr><tr><td rowspan="2">HAETAE-260</td><td>speed-opt</td><td>34,108</td><td>102,964</td><td>36,428</td><td>22,851</td><td>50,175</td><td>2,733</td></tr><tr><td>stack-opt</td><td>22,356</td><td>68,380</td><td>36,428</td><td>23,213</td><td>99,472</td><td>2,733</td></tr><tr><td>Dilithium-2</td><td></td><td>38,408</td><td>49,380</td><td>36,212</td><td>1,598</td><td>4,112</td><td>1,572</td></tr><tr><td>Dilithium-3</td><td></td><td>60,836</td><td>68,836</td><td>57,724</td><td>2,830</td><td>6,588</td><td>2,691</td></tr><tr><td>Dilithium-5</td><td></td><td>97,692</td><td>115,932</td><td>92,788</td><td>4,826</td><td>8,779</td><td>4,706</td></tr><tr><td>Falcon-512</td><td></td><td>18,416</td><td>42,508</td><td>4,724</td><td>155,758</td><td>38,979</td><td>481</td></tr><tr><td>Falcon-1024</td><td></td><td>36,296</td><td>82,532</td><td>8,820</td><td>480,072</td><td>85,125</td><td>995</td></tr></tbody></table>

# 8 Conclusion

With HAETAE, we close an important gap between the two state-of-the-art digital signature schemes Dilithium and Falcon. Novel contributions in key generation and rejection sampling allow us to reach significantly smaller signature and verification key sizes, while still allowing physical side-channel protected implementations for IoT use-cases. Moreover, our first set of optimized implementations exhibits that our proposed algorithms run in feasible time both on embedded and high-end platforms and compete with existing schemes when considering sending latency.

A possible direction to achieve a similar signature sizes with HAETAE could be following the BLISS approach, using the bimodal Gaussians in the module LWE setting with the compression techniques, which we did not go through to avoid computing a secret-dependent transcendental function during signature rejection to enhance the implementation security.

# Acknowledgements

Part of this work was done while Damien Stehlé was in École Normale Supérieure de Lyon and Institut Universitaire de France, and Julien Devevey was in École Normale Supérieure de Lyon, and Dongyeon Hong and MinJune Yi were in CryptoLab Inc. Julien Devevey and Damien Stehlé were supported by the AMIRAL ANR grant (ANR-21-ASTR-0016), the PEPR quantique France 2030 programme (ANR-22-PETQ-0008) and the PEPR Cyber France 2030 programme (ANR-22-PECY-0003). Tim Güneysu, Markus Krausz, Georg Land and Marc Möller have been supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy - EXC 2092 CASA - 390781972, by the German Federal Ministry of Education and Research BMBF through the projects 6GEM (16KISK038) and FlexKI (01IS22086I), and by the European Commission under the grant agreement number 101070374 (CONVOLVE). Jung Hee Cheon and Hyeongmin Choe were supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2022R1A5A6000840).

# References

[ABC$^{+23}$] Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Tobias Schneider, Markus Schönauer, François-
Xavier Standaert, and Christine van Vredendaal. Protecting dilithium against leakage revisited sensitivity analysis and improved implementations. *IACR TCHES*, 2023(4):58-79, 2023.

[AHKS22] Amin Abdulrahman, Vincent Hwang, Matthias J. Kannwischer, and Amber Sprenkels. Faster kyber and dilithium on the cortex-M4. In Giuseppe Ateniese and Daniele Venturi, editors, *ACNS 22*, volume 13269 of LNCS, pages 853-871. Springer, Heidelberg, June 2022.

[AKM+15] Marc Andrysco, David Kohlbrenner, Keaton Mowery, Ranjit Jhala, Sorin Lerner, and Hovav Shacham. On subnormal floating point and abnormal timing. In *2015 IEEE Symposium on Security and Privacy*, pages 623-639. IEEE, 2015.

[ASY22] Shweta Agrawal, Damien Stehlé, and Anshu Yadav. Round-optimal lattice-based threshold signatures, revisited. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, *ICALP 2022*, volume 229 of LIPIcs, pages 8:1-8:20. Schloss Dagstuhl, July 2022.

[Bar87] Paul Barrett. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In Andrew M. Odlyzko, editor, *CRYPTO'86*, volume 263 of LNCS, pages 311-323. Springer, Heidelberg, August 1987.

[BBC+20] Daniel J. Bernstein, Billy Bob Brumley, Ming-Shing Chen, Chitchanok Chuengsatiansup, Tanja Lange, Adrian Marotzke, Bo-Yuan Peng, Nicola Tuveri, Christine van Vredendaal, and Bo-Yin Yang. NTRU Prime: round 3. https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf, 2020.

[BBD+23] Manuel Barbosa, Gilles Barthe, Christian Doczkal, Jelle Don, Serge Fehr, Benjamin Grégoire, Yu-Hsuan Huang, Andreas Hülsing, Yi Lee, and Xiaodi Wu. Fixing and mechanizing the security proof of Fiat-Shamir with aborts and Dilithium. In Helena Handschuh and Anna Lysyanskaya, editors, *CRYPTO 2023, Part V*, volume 14085 of LNCS, pages 358-389. Springer, Heidelberg, August 2023.

[BBE+19] Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Mélissa Rossi, and Mehdi Tibouchi. GALACTICS: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, *ACM CCS 2019*, pages 2147-2164. ACM Press, November 2019.

[BGV12] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, *ITCS 2012*, pages 309-325. ACM, January 2012.

[BP18] Leon Groot Bruinderink and Peter Pessl. Differential fault attacks on deterministic lattice signatures. *IACR TCHES*, 2018(3):21-43, 2018. https://tches.iacr.org/index.php/TCHES/article/view/7267.

[CL21] André Chailloux and Johanna Loyer. Lattice sieving via quantum random walks. In Mehdi Tibouchi and Huaxiong Wang, editors, *ASIACRYPT 2021, Part IV*, volume 13093 of LNCS, pages 63-91. Springer, Heidelberg, December 2021.
[DDGR20] Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. LWE with side information: Attacks and concrete security estimation. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 329–358. Springer, Heidelberg, August 2020.

[DDLL13] Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. Lattice signatures and bimodal Gaussians. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 40–56. Springer, Heidelberg, August 2013.

[DFPS22] Julien Devevey, Omar Fawzi, Alain Passelègue, and Damien Stehlé. On rejection sampling in lyubashevsky's signature scheme. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV, volume 13794 of LNCS, pages 34–64. Springer, Heidelberg, December 2022.

[DFPS23] Julien Devevey, Pouria Fallahpour, Alain Passelègue, and Damien Stehlé. A detailed analysis of Fiat-Shamir with aborts. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 327–357. Springer, Heidelberg, August 2023.

[DKL$^{+18}$] Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR TCHES, 2018(1):238–268, 2018. https://tches.iacr.org/index.php/TCHES/article/view/839.

[dPEK$^{+}$] Rafaël del Pino, Thomas Espitau, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, Mélissa Rossi, and Markku-Juhani Saarinen. Raccoon: A side-channel secure signature scheme. Submission to the NIST Additional Post-Quantum Digital Signature Schemes standardization process. Available at https://raccoonfamily.org/wp-content/uploads/2023/07/raccoon.pdf.

[DPS23] Julien Devevey, Alain Passelègue, and Damien Stehlé. G+G: A fiat-shamir lattice signature based on convolved gaussians. In ASIACRYPT (7), volume 14444 of Lecture Notes in Computer Science, pages 37–64. Springer, 2023.

[Dud14] Jarek Duda. Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, 2014. ArXiv preprint, available at https://arxiv.org/abs/1311.2540.

[Dwo15] Morris J Dworkin. SHA-3 standard: Permutation-based hash and extendable-output functions. FIPS 202, 2015.

[EFG$^{+22}$] Thomas Espitau, Pierre-Alain Fouque, François Gérard, Mélissa Rossi, Akira Takahashi, Mehdi Tibouchi, Alexandre Wallet, and Yang Yu. Mitaka: A simpler, parallelizable, maskable variant of falcon. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, pages 222–253. Springer, Heidelberg, May / June 2022.

[ENST23] Thomas Espitau, Guilhem Niot, Chao Sun, and Mehdi Tibouchi. Square unstructured integer euclidean lattice signature. Submission to the NIST's post-quantum cryptography standardization process, 2023.

[ETWY22] Thomas Espitau, Mehdi Tibouchi, Alexandre Wallet, and Yang Yu. Shorter hash-and-sign lattice-based signatures. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 245–275. Springer, Heidelberg, August 2022.
[FHK+18] Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, Zhenfei Zhang, et al. Falcon: Fast-fourier lattice-based compact signatures over NTRU. *Submission to the NIST's post-quantum cryptography standardization process*, 36(5), 2018.

[Gie14] Fabian Giesen. Interleaved entropy coders. *arXiv preprint arXiv:1402.3392*, 2014.

[GKOS18] Tim Güneysu, Markus Krausz, Tobias Oder, and Julian Speith. Evaluation of lattice-based signature schemes in embedded systems. In *25th IEEE International Conference on Electronics, Circuits and Systems, ICECS 2018, Bordeaux, France, December 9-12, 2018*, pages 385–388. IEEE, 2018.

[GS23] Jason Goertzen and Douglas Stebila. Post-quantum signatures in DNSSEC via request-based fragmentation. In Thomas Johansson and Daniel Smith-Tone, editors, *Post-Quantum Cryptography - 14th International Workshop, PQCrypto 2023, College Park, MD, USA, August 16-18, 2023, Proceedings*, volume 14154 of *Lecture Notes in Computer Science*, pages 535–564. Springer, 2023.

[HDS23] Abiodoun Clement Hounkpevi, Sidoine Djimnaibeye, and Michel Seck. EagleSign: A new post-quantum ElGamal-like signature over lattices. *Submission to the NIST's post-quantum cryptography standardization process*, 2023.

[HPP+23] Thomas Pornin Huang, Eamonn W Postlethwaite, Thomas Prest, Ludo N Pulles, and Wessel van Woerden. HAWK., 2023. Version 1.0.1 (July 19, 2023).

[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Joe Buhler, editor, *ANTS-III*, volume 1423 of *LNCS*, pages 267–288. Springer, 1998.

[KA21] Emre Karabulut and Aydin Aysu. FALCON Down: Breaking FALCON post-quantum signature scheme through side-channel attacks. In *2021 58th ACM/IEEE Design Automation Conference (DAC)*, pages 691–696, 2021.

[KLS+23] Markus Krausz, Georg Land, Florian Stolz, Dennis Naujoks, Jan Richter-Brockmann, Tim Güneysu, and Lucie Johanna Kogelheide. Generic accelerators for costly-to-mask PQC components. *IACR Cryptol. ePrint Arch.*, page 1287, 2023.

[KRSS19] Matthias J. Kannwischer, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. pqm4: Testing and benchmarking NIST PQC on ARM cortex-M4. Cryptology ePrint Archive, Report 2019/844, 2019. https://eprint.iacr.org/2019/844.

[Li04] Ren-Cang Li. Near optimality of chebyshev interpolation for elementary function computations. *IEEE Trans. Computers*, 53(6):678–687, 2004.

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

[Lyu09] Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In Mitsuru Matsui, editor, *ASIACRYPT 2009*, volume 5912 of LNCS, pages 598–616. Springer, Heidelberg, December 2009.
[Lyu12] Vadim Lyubashevsky. Lattice signatures without trapdoors. In David Pointcheval and Thomas Johansson, editors, *EUROCRYPT 2012*, volume 7237 of LNCS, pages 738-755. Springer, Heidelberg, April 2012.

[MGTF19] Vincent Migliore, Benoît Gérard, Mehdi Tibouchi, and Pierre-Alain Fouque. Masking Dilithium - efficient implementation and side-channel evaluation. In Robert H. Deng, Valérie Gauthier-Umaña, Martín Ochoa, and Moti Yung, editors, *ACNS 19*, volume 11464 of LNCS, pages 344-362. Springer, Heidelberg, June 2019.

[Mon85] Peter L Montgomery. Modular multiplication without trial division. *Mathematics of computation*, 44(170):519-521, 1985.

[MUTS22] Soundes Marzougui, Vincent Ulitzsch, Mehdi Tibouchi, and Jean-Pierre Seifert. Profiling side-channel attacks on Dilithium: A small bit-fiddling leak breaks it all. Cryptology ePrint Archive, Report 2022/106, 2022. https://eprint.iacr.org/2022/106.

[Pla21] Thomas Plantard. Efficient word size modular arithmetic. *IEEE Transactions on Emerging Topics in Computing*, 9(3):1506-1518, 2021.

[Por19] Thomas Pornin. New efficient, constant-time implementations of Falcon. Cryptology ePrint Archive, Paper 2019/893, 2019.

[Pre17] Thomas Prest. sharper bounds in lattice-based cryptography using the Rényi divergence. In Tsuyoshi Takagi and Thomas Peyrin, editors, *ASIACRYPT 2017, Part I*, volume 10624 of LNCS, pages 347-374. Springer, Heidelberg, December 2017.

[Pre23] Thomas Prest. A key-recovery attack against mitaka in the t-probing model. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, *PKC 2023, Part I*, volume 13940 of LNCS, pages 205-220. Springer, Heidelberg, May 2023.

[PST20] Christian Paquin, Douglas Stebila, and Goutam Tamvada. Benchmarking post-quantum cryptography in TLS. In *Post-Quantum Cryptography: 11th International Conference, PQCrypto 2020, Paris, France, April 15-17, 2020, Proceedings 11*, pages 72-91. Springer, 2020.

[Ros20] Melissa Rossi. *Extended Security of Lattice-Based Cryptography*. PhD thesis, École Normale Supérieure de Paris, 2020.

[RS23] Keegan Ryan and Adam Suhl. Round 1 (additional signatures) official comment: EHT, 2023.

[Sch90] Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Gilles Brassard, editor, *CRYPTO'89*, volume 435 of LNCS, pages 239-252. Springer, Heidelberg, August 1990.

[Sch00] Werner Schindler. A timing attack against RSA with the chinese remainder theorem. In *Cryptographic Hardware and Embedded Systems—CHES 2000: Second International Workshop Worcester, MA, USA, August 17-18, 2000 Proceedings 2*, pages 109-124. Springer, 2000.

[Sei18] Gregor Seiler. Faster AVX2 optimized NTT multiplication for ring-LWE lattice cryptography. Cryptology ePrint Archive, Report 2018/039, 2018. https://eprint.iacr.org/2018/039.
[SF23] Igor Semaev, and Martin Feussner. Digital signature algorithms EHTV3 and EHTV4 submission to NIST PQC. *Submission to the NIST's post-quantum cryptography standardization process*, 2023.

[Tib23] Mehdi Tibouchi. Round 1 (additional signatures) official comment: EagleSign, 2023.

[VGS17] Aaron R Voelker, Jan Gosmann, and Terrence C Stewart. Efficiently sampling vectors and coordinates from the *n*-sphere and *n*-ball. *Centre for Theoretical Neuroscience-Technical Report*, 01 2017.

[Wes21] Bas Westerbaan. Sizing up post-quantum signatures. Technical report, Cloudflare, 2021.

[YJL$^{+23}$] Yang Yu, Huiwen Jia, Leibo Li, Delong Ran, Zhiyuan Qiu, Shiduo Zhang, Xiuhan Lin, and Xiaoyun Wang. HuFu: Hash-and-sign signatures from powerful gadgets. Algorithm specifications and supporting documentation., 2023. Version 1.1 (September 2, 2023).

## A Recent lattice-based signatures

In this section, we give a size comparison of the recent lattice-based signature schemes. In Table 10, we compare the verification key and signature sizes (in bytes) of some selected lattice signature schemes, including the NIST's on-ramp candidates. Note that we additionally showcase some disadvantages, e.g., some recent analyses reported at pqc-forum (some are verified by the submitters, and others are not) or the use of new family of assumptions, which may degrade the claimed security.

<table><caption>Table 10: Size comparison of recent lattice-based signatures.</caption><thead><tr><th rowspan="2">Scheme</th><th colspan="3">Levels 1 & 2</th><th colspan="3">Level 3</th><th colspan="3">Level 5</th><th rowspan="2">Ref.</th></tr><tr><th>vk</th><th>sig.</th><th>sum ↑</th><th>vk</th><th>sig.</th><th>sum</th><th>vk</th><th>sig.</th><th>sum</th></tr></thead><tbody><tr><td>EHTv4<sup>1</sup></td><td>1,110</td><td>369</td><td>1,479</td><td>—</td><td>—</td><td>—</td><td>1,110</td><td>369</td><td>1,479</td><td>[SF23]</td></tr><tr><td>Falcon<sup>2</sup></td><td>897</td><td>666</td><td>1,563</td><td>—</td><td>—</td><td>—</td><td>897</td><td>666</td><td>1,563</td><td>[FHK<sup>+18</sup>]</td></tr><tr><td>HAWK<sup>3</sup></td><td>1,024</td><td>555</td><td>1,579</td><td>—</td><td>—</td><td>—</td><td>1,024</td><td>555</td><td>1,579</td><td>[HPP<sup>+23</sup>]</td></tr><tr><td>Mitaka<sup>4</sup></td><td>896</td><td>713</td><td>1,609</td><td>—</td><td>—</td><td>—</td><td>896</td><td>713</td><td>1,609</td><td>[EFG<sup>+22</sup>]</td></tr><tr><td><strong>HAETAE</strong></td><td>992</td><td>1,474</td><td>2,466</td><td>1,472</td><td>2,349</td><td>3,821</td><td>2,080</td><td>2,948</td><td>5,028</td><td><strong>ours</strong></td></tr><tr><td>Dilithium</td><td>1,312</td><td>2,420</td><td>3,732</td><td>1,952</td><td>3,293</td><td>5,245</td><td>2,592</td><td>4,595</td><td>7,187</td><td>[DKL<sup>+18</sup>]</td></tr><tr><td>EagleSign<sup>5</sup></td><td>1,824</td><td>2,144</td><td>3,968</td><td>2,842</td><td>2,336</td><td>5,160</td><td>3,616</td><td>3,488</td><td>7,104</td><td>[HDS23]</td></tr><tr><td>Raccoon</td><td>2,256</td><td>11,524</td><td>13,780</td><td>3,160</td><td>14,544</td><td>17,704</td><td>4,064</td><td>20,330</td><td>24,394</td><td>[dPEK<sup>+</sup>]</td></tr><tr><td>SQUIRRELS</td><td>682K</td><td>1,019</td><td>683K</td><td>1,600K</td><td>1,554</td><td>1,602K</td><td>—</td><td>—</td><td>—</td><td>[ENST23]</td></tr><tr><td>HUFU<sup>6</sup></td><td>1,059K</td><td>2,450</td><td>1,061K</td><td>2,177K</td><td>3,540</td><td>2,181K</td><td>3,573K</td><td>4,520</td><td>3,578K</td><td>[YJL<sup>+23</sup>]</td></tr></tbody></table>

## B Security against Physical Attacks

Implementation security is a crucial aspect of making cryptosystems feasible in real-world applications. A significant advantage of HAETAE is that it can be protected against power side-channel attacks efficiently and with reasonable overhead. In this context, we emphasize the similarity of HAETAE to Dilithium. Hence, past works analyzing concrete

<footnote n="1">¹ reported attack [RS23] ² infeasible to mask, uses floating-point arithmetic ³ new assumptions</footnote>

<footnote>smLIP, omSVP ⁴ hard to mask, proposed masked Gaussian sampler recently broken [Pre23] ⁵ reported</footnote>

<footnote>attack [Tib23] ⁶ uses floating-point arithmetic</footnote>
attacks [BP18, MUTS22], but also countermeasures [MGTF19, ABC$^{+23}$], mainly apply to
HAETAE as well.

While there is no known method to efficiently mask Falcon, Mitaka [EFG$^{+22}$] was designed to be easy to protect against implementation attacks, while still having the advantage of similarly small signatures as Falcon. For Mitaka, the crux regarding side-channel security is sampling Gaussian-distributed values. Together with Mitaka, an efficient, masked algorithm for discrete Gaussian sampling was presented. However, Prest broke its security proof recently [Pre23]. In this respect, HAETAE has the strong advantage that Gaussian sampling only needs to be secured against the much stronger Simple Power Analysis (SPA) attacker model, which allows for simpler countermeasures, while Mitaka’s side-channel security will always depend on a masked sampler.

While a fully protected implementation of HAETAE is out of scope for this paper, we
briefly sketch its feasibility.

**Protecting the Arithmetic.** Most notably, HAETAE does not deploy floating-point arithmetic at any point, and only few secrets require fix-point arithmetic. Remarkably, addition of fix-point arithmetic can be masked relatively easy, and HAETAE never requires a multiplication of fix-point values.

During signing, the most critical operation is multiplying the (public) challenge polynomial $c$ with $s$ and subsequently adding the result to $y$. Since this operation may leak information about the secret key statistically over many executions, implementers must protect it accordingly. As countermeasures against these so-called Differential Power Analysis (DPA) attacks, masking has been proven effective.

This operation is straightforward to mask at arbitrary order by splitting the secret key
polynomials into multiple additive shares in $\mathcal{R}_q$. A masked implementation then stores
the NTT of each share of $s$ and multiplies them to $c$, obtaining a shared $cs$. Following
this, the inverse NTT is applied share-wise. Since $y$ is a polynomial vector in $(1/N)\mathcal{R}$,
it is not trivially possible to add our shares of $cs \in \mathcal{R}_q^{k+l}$. On the other hand, $y$ is not a
secret-key-dependent value. Therefore, it is not required to be protected against DPA but
only against the much stronger attacker model of a SPA. In fact, coefficient-wise shuffling
of the addition might be sufficient at this point.

Independent of whether the addition is shuffled or masked, this involves a masking
conversion from $\mathbb{Z}_q$ to $\mathbb{Z}_{2^{32}}$. Subsequently, the computation of $2z - y$ and the bound checks
can be shuffled without applying costly masking.

**Protecting the Hyperball Sampler.** The same idea applies to the whole hyperball
sampling procedure. Since the order of the Gaussian samples is, in principle, irrelevant,
they can be generated in random order. This is particularly an advantage for randomized
HAETAE.

For the deterministic version, a masked CDT sampler, and a masked approximation
of the exponential function are required. The former was shown to be feasible recently
by Krausz et al. [KLS$^{+23}$], while the latter is a sequence of multiplications, shifting by a
constant amount, and addition by constants, which is expected to be costly but feasible.

It is noteworthy that the random oracle hash (which outputs the challenge) is only
required to be protected against SPA as well. Since the input order into the hash function
cannot be randomized, the preceding values must still be protected by masking. Therefore,
if no masked hyperball sampling has been performed, we propose to perform a shuffled
point-wise multiplication of **A** and **y**, directly followed by freshly masking the resulting
coefficients. Then, a share-wise inverse NTT and a masking conversion to the Boolean
domain will be performed, which enables a secure HighBits operation. For the LSBs of
$y_0$, generating a fresh Boolean masking during the shuffled generation of the hyperball
sample's coefficients is sufficient.
# C Additional Proofs

## C.1 Useful Lemma

We will rely on the following claim.

**Lemma 12.** Let $n$ be the degree of $\mathcal{R}$. Let $m, N, r > 0$ and $\mathbf{v} \in \mathcal{R}^m$. Then the following statements hold:

$$1. \quad |(1/N)\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r)| = |\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(Nr)|,$$

$$2. \quad |\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r, \mathbf{v})| = |\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r)|,$$

$$3. \quad \mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(r - \frac{\sqrt{mn}}{2})) \le |\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r)| \le \mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(r + \frac{\sqrt{mn}}{2})).$$

**Proof.** For the first statement, note that we only scaled $(1/N)\mathcal{R}^m$ and $\mathcal{B}_{\mathcal{R},m}(r)$ by a factor $N$. For the second statement, note that the translation $\mathbf{x} \mapsto \mathbf{x} - \mathbf{v}$ maps $\mathcal{R}^m$ to $\mathcal{R}^m$.

We now prove the third statement. For $x \in \mathcal{R}^m$, we define $T_{\mathbf{x}}$ as the hypercube of $\mathcal{R}_{\mathcal{R}}^m$ centered in $\mathbf{x}$ with side-length 1. Observe that the $T_{\mathbf{x}}$'s tile the whole space when $\mathbf{x}$ ranges over $\mathcal{R}^m$ (the way boundaries are handled does not matter for the proof). Also, each of those tiles has volume 1. As any element in $T_{\mathbf{x}}$ is at Euclidean distance at most $\sqrt{mn}/2$ from $\mathbf{x}$, the following inclusions hold:

$$\mathcal{B}_{\mathcal{R},m}\left(r - \frac{\sqrt{mn}}{2}\right) \subseteq \bigcup_{\mathbf{x} \in \mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r)} T_{\mathbf{x}} \subseteq \mathcal{B}_{\mathcal{R},m}\left(r + \frac{\sqrt{mn}}{2}\right).$$

Taking the volumes gives the result. $\square$

## C.2 Proof of Lemma 4

**Proof.** To ease the notation, let us use $B = r'$. Let $\mathbf{y} \in \mathcal{B}_{\mathcal{R},m}(Nr' + \sqrt{mn}/2)$ and set $\mathbf{z} = [\mathbf{y}]$. Note that $\mathbf{z}$ is sampled (before the rejection step) with probability

$$\frac{\mathrm{Vol}(T_{\mathbf{z}} \cap \mathcal{B}_{\mathcal{R},m}(Nr' + \sqrt{mn}/2))}{\mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(Nr'))},$$

where $T_{\mathbf{z}}$ is the hypercube of $\mathcal{R}_{\mathcal{R}}^m$ centered in $\mathbf{z}$ with side-length 1. By the triangle inequality, this probability is equal to $1/\mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(Nr' + \sqrt{mn}/2))$ when $\mathbf{z} \in \mathcal{B}_{\mathcal{R},m}(Nr')$. Hence the distribution of the output is exactly $U(\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(Nr'))$, as each element is sampled with equal probability and as the algorithm almost surely terminates (its runtime follows a geometric law of parameter the rejection probability).

It remains to consider the acceptance probability.

$$\frac{\sum_{\mathbf{y} \in \mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(Nr')} \mathrm{Vol}(T_{\mathbf{y}} \cap \mathcal{B}_{\mathcal{R},m}(Nr' + \sqrt{mn}/2))}{\mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(Nr' + \sqrt{mn}/2))}.$$

By the triangle inequality and Lemma 12, it is

$$\frac{|\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(Nr')|}{\mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(Nr' + \sqrt{mn}/2))} \ge \left( \frac{Nr' - \sqrt{mn}/2}{Nr' + \sqrt{mn}/2} \right)^{mn}.$$

Note that by our choice of $N$, this is $\ge 1/M_0$. $\square$
### C.3 Proof of Lemma 5

**Proof.** Figure 6 is the bimodal rejection sampling algorithm applied to the source distribution $U((1/N)\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r'))$ and target distribution $U((1/N)\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r))$ (see, e.g., [DFPS22]). It then suffices that the support of the bimodal shift of the source distribution by $v$ contains the support of the target distribution. It is implied by $r' \ge \sqrt{r^2 + t^2}$.

We now consider the number of expected iterations, i.e., the maximum ratio between the two distributions. To guide the intuition, note that if we were to use continuous distributions, the acceptance probability $1/M'$ would be bounded by $1/M$. In our case, the acceptance probability can be bounded as follows (using Lemma 12):

$$ \frac{1}{M'} = \frac{|(1/N)\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r)|}{2|(1/N)\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(r')|} = \frac{|\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(Nr)|}{2|\mathcal{R}^m \cap \mathcal{B}_{\mathcal{R},m}(Nr')|} \\ \ge \frac{\mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(Nr - \sqrt{mn}/2))}{2\mathrm{Vol}(\mathcal{B}_{\mathcal{R},m}(Nr' + \sqrt{mn}/2))} \\ = \frac{1}{2} \left( \frac{Nr - \sqrt{mn}/2}{Nr' + \sqrt{mn}/2} \right)^{mn}. $$

It now suffices to bound the latter term from below by $1/(cM) = 1/(2c(r'/r)^{mn})$. This inequality is equivalent to:

$$ c \ge \frac{1}{2} \cdot \left( \frac{r}{r - \sqrt{mn}/(2N)} \right)^{mn} \cdot \left( \frac{r' + \sqrt{mn}/(2N)}{r'} \right)^{mn}, $$

and to:

$$ N \ge \frac{1}{c^{1/(mn)} - 1} \cdot \frac{\sqrt{mn}}{2} \left( \frac{c^{1/(mn)}}{r} + \frac{1}{r'} \right), $$

which allows to complete the proof. □

### C.4 Proof of Lemma 7

**Proof.** By Lemma 6, there exists a unique representation

$$ r = \lfloor (r + \alpha/2)/\alpha \rfloor \alpha + (r \mod \alpha^{\pm}) \alpha. $$

By identifying HighBits($r, \alpha$) and LowBits($r, \alpha$) in the above equation, we obtain the first result.

By definition of $\mod \alpha^{\pm}$, we have the second range.

Finally, since $r \mapsto \lfloor (r + \alpha/2)/\alpha \rfloor$ is a non-decreasing function, it is sufficient to show that $\lfloor (2q - 1 + \alpha/2)/\alpha \rfloor \le \lfloor (2q - 1)/\alpha \rfloor$. We have $(2q - 1 + \alpha/2) \le \lfloor (2q - 1)/\alpha \rfloor \alpha + \alpha - 1$ by assumption on $q$. Dividing by $\alpha$ and taking the floor yields the result. □

### C.5 Proof of Lemma 8

**Proof.** Let $r \in [0, 2q - 1]$. Let $r_0, r_1, r'_0$, and $r'_1$ defined as in Definition 8. If $r'_0 = r_0$ and $r'_1 = r_1$, the equality $r'_0 + r'_1 \cdot \alpha_h = r_0 + r_1 \cdot \alpha_h \mod 2q$ holds vacuously.

If not, then $r'_0 = r_0 - 2$ and $r'_1 = r_1 - 2(q - 1)/\alpha_h$ and $r'_0 + r'_1 \alpha_h = r_0 + r_1 \alpha_h - 2q$. By Lemma 7, we get the first equality.

The second property stems from the second property in Lemma 7. The modifications to $r_0$ make $r'_0$ lie in the range $[-\alpha_h/2 - 2, \alpha_h/2)$.

The last property stems from the third property in Lemma 7 and the fact that if $r_1 = m$, then we have $r'_1 = 0$. □
## D Additional Implementation Specification

Algorithm 1 describes how to implement the unpacking of $\hat{\mathbf{A}}$, and in Algorithm 2 we demonstrate how to apply the CRT.

<caption>**Algorithm 1** Unpacking routine for $\hat{\mathbf{A}}$.</caption>

```
unpackA_d(seed_A, ψ)
1: if d = 0 then
2:     $\hat{\mathbf{A}}_{gen}$ := expandA_d(seed_A)
3:     $\hat{\mathbf{b}}$ := ψ
4: else
5:     ($\mathbf{a}_{gen}, \hat{\mathbf{A}}_{gen}$) := expandA_d(seed_A)
6:     $\hat{\mathbf{b}}$ := 2 · NTT($\mathbf{a}_{gen} - \psi \cdot 2^d$) mod q
7:     return $\hat{\mathbf{A}} \in \mathcal{R}_q^{k \times l} := (\hat{\mathbf{b}} | 2 \cdot \hat{\mathbf{A}}_{gen}) \bmod q$
```

## E Notes Regarding Hardware Implementations

Hashing and generation of randomness are the most time-consuming operations of HAETAE. Therefore, we assume that hardware implementations will bring significant speedup and can be competitive to Dilithium, particularly through efficient Keccak cores. Furthermore, hardware implementations will benefit significantly from applying the offline approach. Naturally, a module generating hyperball samples can be instantiated and run parallel to the online phase, thus, hiding its latency behind the online phase. Moreover, high-speed applications could adopt the offline approach with designated signing key, including the multiplication of $\mathbf{A}$ and $\mathbf{y}$, to further reduce the latency of the online phase.

<caption>**Algorithm 2** Mapping from ($\mathcal{R}_q^k, \mathcal{R}_q$) to $\mathcal{R}_{2q}^k$</caption>

```
fromCRT(w, x)
1: parse w as vector of integers $\bar{w}$ of size $kn$
2: parse x as vector of integers $\bar{x}$ of size $n$
3: for $i := 0$ to $n-1$ do
4:     if LSB($\bar{x}_i$) = LSB($\bar{w}_i$) then
5:         $\bar{w}'_i := \bar{w}_i$
6:     else
7:         $\bar{w}'_i := \bar{w}_i + q$
8:     for $j := 1$ to $k-1$ do
9:         for $i := 0$ to $n-1$ do
10:             if LSB($\bar{w}_{nj+i}$) = 0 then
11:                 $\bar{w}'_{nj+i} := \bar{w}_{nj+i}$
12:             else
13:                 $\bar{w}'_{nj+i} := \bar{w}_{nj+i} + q$
14:     arrange $\bar{w}'$ to $w'$, an element in $\mathcal{R}_{2q}^k$
15:     return $w'$
```
<figure><img src="image_13.png" /><figcaption>**Figure 15:** Interaction between $P$ and $V$. We let $\langle P(x, y) \leftrightarrow V(x) \rangle_{f(.)}$ denote the transcript $(w, c, z)$.</figcaption></figure>

# F Cryptographic Reminders

In this section, we recall the definition of a canonical identification scheme, which is the main building brick of HAETAE and the Fiat-Shamir with aborts transform, which allows one to turn a canonical identification scheme into a signature scheme.

## F.1 Canonical Identification Schemes

We start by defining a canonical identification scheme.

**Definition 9 (Canonical Identification Scheme with Aborts (CID))**. A canonical identification scheme ID for a relation $R$ is a three rounds interactive protocol between a prover $P$ and a verifier $V$, as defined in Figure 15. The challenge is generated from $f(w)$ set as the distribution $U(C)$ for some challenge set $C$. The prover holds a pair $(x, y) \in R$ while the verifier only has $x$, where the pair $(x, y)$ was generated by a PPT algorithm $Gen$, called an instance generator. The event $"z = \perp"$ is called an abort, and its probability $\beta$ is called the probability of aborting.

The canonical identification schemes considered in this work are such that given $c$ and $z$, there is only one $w$ such that $V$ accepts, which can be efficiently computed from $c$ and $z$.

We need the following flavor of zero knowledge, denoted perfect accepting honest verifier zero-knowledge.

**Definition 10 (Perfect Accepting Honest Verifier Zero-Knowledge)**. Let ID be a canonical identification scheme. It satisfies paHVZK if there exists a PPT simulator $Sim$ such that the output distribution of $(w, c, z)$ resulting from the interaction $\langle P(x, y) \leftrightarrow V(x) \rangle_{U(C)}$ conditioned on $z \neq \perp$ and $(w', c', z')$ generated by $Sim(x)$ for any $(x, y)$ generated by $Gen(1^{\lambda})$ are identical.

In the case of the HAETAE CID, the challenge $c$ can be sampled uniformly from the challenge space $C$ and passed over as input to the simulator $Sim$.

To avoid using the same commitment twice, we require the min-entropy of the commitment to be high.

**Definition 11 (Commitment Min-Entropy)**. For $\alpha \ge 0$, we say that an identification scheme ID with instance generator $Gen$ has commitment min-entropy $\alpha$ if $H_{\infty}[w|(w, c, z) \leftarrow \langle P(x, y) \leftrightarrow V(x) \rangle_{U(C)}] \ge \alpha$, for all $(x, y) \leftarrow Gen(1^{\lambda})$.

Finally we need the notion of computational unique response to enable the strong unforgeability property of the final signature scheme.

**Definition 12 (Computational Unique Response)**. Let ID be a canonical identification scheme with instance generator $Gen$. The advantage $Adv_{ID}^{CUR}(\mathcal{A})$ of an adversary $\mathcal{A}$ against
<figure><img src="image_14.png" /><figcaption>**Figure 16:** Fiat-Shamir with Aborts tranform FS[ID, H].</figcaption></figure>

the CUR property of ID is its probability of computing $(w, c, z, z')$ such that $V(x)$ accepts both $(w, c, z)$ and $(w, c, z')$ and $z \neq z'$ on input $x$ generated from $(x, y) \leftarrow \text{Gen}(1^{\lambda})$.

## F.2 The Fiat-Shamir Transform

We now briefly recall how to turn a canonical identification scheme into a full-fledge signature scheme. To do so, the signing scheme runs the interactive protocol and outputs the transcript minus the commitment. The challenge is however generated by hashing the message along with the commitment to prevent an adversary from tampering with it.

We recall the assumptions necessary to show the unforgeability of the resulting signature in the following theorem. The following theorem works in the case of quantum adversaries working in the QROM, but tighter statements can be obtained when restricting to classical adversaries in the ROM.

**Theorem 4** (Adapted from [BBD$^+$23, Theorem 2]). Let ID be a canonical identification scheme with $\alpha$ commitment min-entropy and that satisfies paHVZK with probability of aborting $\beta$. For any quantum adversary $\mathcal{A}$ against the UF-CMA security of FS[ID, $H$] in the QROM making $Q_s$ signature queries and $Q_h$ hash queries, there exists an adversary $\mathcal{B}$ against the UF-NMA security of FS[ID, $H$] in the QROM such that:

$$ \mathrm{Adv}_{\mathrm{FS}[\mathrm{ID}, H]}^{\mathrm{UF-CMA}}(\mathcal{A}) \le \mathrm{Adv}_{\mathrm{FS}[\mathrm{ID}, H]}^{\mathrm{UF-NMA}}(\mathcal{B}) + \frac{2^{-\alpha/2+1} Q_s}{1-\beta} \sqrt{Q_h + 1 + \frac{Q_s}{1-\beta}} + 2^{-\alpha/2+1} (Q_h+1) \sqrt{\frac{Q_s}{1-\beta}} $$

Furthermore, if $\mathcal{A}$ is an adversary against the sUF-CMA security, there exists an adversary $\mathcal{B}'$ against the CUR property of ID such that the previous bound holds by adding $\mathrm{Adv}_{\mathrm{ID}}^{\mathrm{CUR}}(\mathcal{B}')$ on the right-hand side.

The strong unforgeability statement comes from the fact that in the last game of their proof, the reduction fails if and only if the forgery uses the same commitment (and thus reprogrammed challenge) than the signature query. As this requires a different answer, this corresponds to an attack against the computational unique response property of the canonical identification scheme.

## G Fixed-point Sampling Analysis

In this appendix, we quantify the precision needed to sample from the uniform-hyperball distribution by sampling from the discrete Gaussian distribution.

We first describe the representation of numbers and operations. A fixed-point number in precision $p$ will consist in a $p$-bit signed integer $k \in \mathbb{Z} \cap [-2^{p-1}, 2^{p-1})$ along with an implicit scaling exponent $e$: the represented number is $x = k \cdot 2^{e-p} \in [-2^{e-1}, 2^{e-1})$. The data can for example be stored in a $p$-bit integer in two's complement representation. The scaling exponent $e$ is not stored, it only exists on paper. For convenience, a precision $p$ fixed-point number $x$ with implicit exponent $e$ will be referred to as a $(p, e)$-number.
When performing arithmetic operations on fixed-point numbers, particular care must be taken with overflows: in the analysis, we make sure that during the algorithm execution, any $(p, e)$-number $x$ will satisfy $|x| < 2^{e-1}$. The following assumes no overflow occurs. We can add, subtract and negate $(p, e)$-numbers exactly (note that we only consider the situation where the operands of those operations share the same exponent). We assume that we can multiply $(p, e_0)$-number $x_0$ with a $(p, e_1)$-number $x_1$ into a $(p, e_\times)$-number $x_\times$ as if the multiplication was exact and then rounded to a nearest representable number. Finally, we assume that we can compute an inverse square-root of a $(p, e)$-number $x$ into a $(p, e')$-number $y$ with possibly slightly more error than that. This is summarized as follows:

$$x_0 \oplus x_1 = x_0 + x_1; \quad x_0 \ominus x_1 = x_0 - x_1; \quad \ominus x = -x; \\ |(x_0 \otimes_{e_0, e_1}^{e_\times} x_1) - (x_0 \cdot x_1)| \le 2^{e_\times - p-1}; \quad |(1/\sqrt{\cdot})_{e_\times}^{e_t} - 1/\sqrt{x}| \le 2^{e_t - p}.$$

## G.1 Discrete Gaussian samples as rounded Gaussian samples

The hyperball-uniform sampler relies on an algorithm that samples from the continuous Gaussian distribution. In our fixed-point sampling algorithm, we make do with fixed-point approximations to sample from the discrete Gaussian distribution, as described in Section 5.1.1. We analyze how this changes the final distribution in the following lemma, which could be rephrased using the smooth Rényi divergence introduced in [DFPS22].

**Lemma 13.** Let $\sigma > 0$. Let $D_{\mathbb{Z},\sigma}$ (resp. $D_\sigma$) be the distribution $D$ over $\mathbb{Z}$ (resp. $\mathbb{R}$) such that $D(k) \sim \exp(-k^2/(2\sigma^2))$ for all $k \in \mathbb{Z}$ (resp. $k \in \mathbb{R}$). Then we have:

$$\Pr_{k \leftarrow D_{\mathbb{Z},\sigma}} [|k| \ge 14 \cdot \sigma] \le 2^{-140} \quad \text{and} \quad \max_{|k| \le 14 \cdot \sigma} \frac{D_{\mathbb{Z},\sigma}(k)}{[D_\sigma](k)} \le \frac{1}{1 - 8/\sigma}.$$

**Proof.** Using the discrete Gaussian tail bound from [Lyu12, Lemma 4.4], the weight of $D_{\mathbb{Z},\sigma}$ out of the interval $[-14 \cdot \sigma, 14 \cdot \sigma]$ is $\le 2^{-140}$. Using the Poisson Summation Formula, we have that:

$$\forall k \in \mathbb{Z}, \quad D_{\mathbb{Z},\sigma}(k) \le \frac{\exp(-k^2/(2\sigma^2))}{\sigma\sqrt{2\pi}}.$$

Further, for $k \in \mathbb{Z} \cap [-14 \cdot \sigma, 14 \cdot \sigma]$, the following inequalities hold:

$$\begin{align*}
[D_\sigma](k) &= \frac{1}{\sigma\sqrt{2\pi}} \int_{k-1/2}^{k+1/2} \exp(-x^2/(2\sigma^2))dx \\
&\ge \frac{\exp(-k^2/(2\sigma^2))}{\sigma\sqrt{2\pi}} \cdot \exp(-(|k|+1/4)/(2\sigma^2)) \\
&\ge \frac{\exp(-k^2/(2\sigma^2))}{\sigma\sqrt{2\pi}} \cdot (1 - \frac{|k|+1/4}{2\sigma^2}) \\
&\ge \frac{\exp(-k^2/(2\sigma^2))}{\sigma\sqrt{2\pi}} \cdot (1 - \frac{8}{\sigma}).
\end{align*}$$

This completes the proof. $\square$

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

Lemma 13 implies that a signature forger for the imperfect Gaussian sampler succeeds with essentially the same probability with the ideal Gaussian sampler.

## G.2 Normalization of Gaussian samples

In the following, we assume that we have access to arbitrarily many statistically independent $(p, e)$-numbers $\bar{y}_i$ that approximate (perfect) samples $y_i$ from $D_1 = \mathcal{N}(0, 1)$. We first
consider the algorithm of Figure 1 with radius 1, using fixed-point arithmetic. We show that the vector $\bar{y}$ output by the approximate algorithm is close to the vector $\mathbf{y}$ output by the exact algorithm. As $\mathbf{y}$ is uniformly distributed in a hyperball, the computed vector $\bar{y}$ is an approximation to such a sample.

We first bound the quantities involved during the computations. These bounds are for the exact quantities. To avoid overflows, we actually need them for the corresponding computed quantities. We will see later that as the numerical errors are low, the bounds still essentially hold. The bounds are probabilistic, and hold with probability extremely close to 1.

**Lemma 14.** Let $d_{\min} = 6 \cdot 256 + 2$ and $d_{\max} = 11 \cdot 256 + 2$. The following bounds hold for all $d \in [d_{\min}, d_{\max}]$:

$$ \Pr_{y \leftarrow D_1} [|y| \ge 2^4] < 2^{-188}, $$

$$ \Pr_{\substack{y_i \leftarrow D_1 \\ \forall i \in [d]}} [\|\mathbf{y}\|^2 \ge 2^{12}] < 2^{-144}, \quad \Pr_{\substack{y_i \leftarrow D_1 \\ \forall i \in [d]}} [\|\mathbf{y}\|^2 \le 2^9] < 2^{-144}. $$

$$ \Pr_{\mathbf{z} \leftarrow U(\mathcal{B}_{d-2}(1))} [|z_1| \ge 2^{-2}] < 2^{-150}. $$

**Proof.** The first probability is $1 - \text{erf}(2^4/\sqrt{2})$. The two others are bounded with the Laurent-Massart bounds for the chi-squared distribution, i.e., for all $d, t$:

$$ \Pr_{\substack{y_i \leftarrow D_1 \\ \forall i \in [d]}} [\|\mathbf{y}\|^2 \ge d + 2\sqrt{dt} + 2t] \le \exp(-t) \quad \text{and} \quad \Pr_{\substack{y_i \leftarrow D_1 \\ \forall i \in [d]}} [\|\mathbf{y}\|^2 \le d - 2\sqrt{dt}] \le \exp(-t). $$

For the last bound, we use [DFPS22, Lemma A.13]. The probability is exactly $I_{1-1/\eta^2}((d+1)/2, 1/2)$ where $I$ refers to the regularized incomplete Beta function and $1/\eta$ is probabilistic magnitude upper bound. We then use numerical computations. $\square$

Throughout the execution of the approximate version of the algorithm of Figure 1, we fix the precision to $p \ge 64$. The implicit exponents vary depending on the algorithm step: the $y_i$'s are represented by $(p, 5)$-numbers, their squares by $(p, 13)$-numbers, the squared-norm $\|\mathbf{y}\|^2$ by a $(p, 13)$-number, the inverse-norm $1/\|\mathbf{y}\|$ by a $(p, -3)$-number and the output coordinates on $(p, -1)$-numbers.

Assume that we have $|\bar{y}_i - y_i| \le \epsilon_0$ for all $i$, for some $\epsilon_0 \ge 2^{-p+5}/2 = 2^{-p+4}$. To avoid overflows of $\bar{y}_i$'s, it suffices that $|y_i| \le 2^4 - 2^{-p+5} - \epsilon_0$. The first bound from Lemma 14 still holds for any $\epsilon_0 \le 2^{-5}$.

We now consider the computations of the approximations $\bar{y}_i^2$'s to the $y_i^2$'s. We have:

$$ \begin{aligned} |\bar{y}_i^2 - y_i^2| & \le |(\bar{y}_i \otimes_{5,5} \bar{y}_i) - \bar{y}_i^2| + |\bar{y}_i - y_i| \cdot |\bar{y}_i + y_i| \\ & \le 2^{-p+12} + |\bar{y}_i - y_i| \cdot [|\bar{y}_i - y_i| + 2|y_i|] \\ & \le 2^{-p+12} + 2^6 \cdot \epsilon_0. \end{aligned} $$

As addition is exact, we obtain:

$$ |\|\mathbf{y}\|^2 - \|\mathbf{y}\|^2| \le d_{\max} \cdot (2^{-p+12} + 2^6 \cdot \epsilon_0) =: \epsilon_1. $$

To avoid overflow of $\|\mathbf{y}\|^2$ and hence of the $\bar{y}_i^2$'s, it suffices that $\|\mathbf{y}\|^2 \le 2^{12} - 2^{-p-13} - \epsilon_1$. The second bound from Lemma 14 still holds for any $\epsilon_0 \le 2^{-5}$.
We continue with the inverse square root computation. The following holds:

$$
\begin{aligned}
\left| \frac{1}{\|\mathbf{y}\|} - \frac{1}{\|\mathbf{y}\|} \right| &\le \left| (1/\sqrt{\cdot})_{13}^{-3} (\|\mathbf{y}\|^2) - \frac{1}{\|\mathbf{y}\|} \right| + \left| \frac{1}{\|\mathbf{y}\|} - \frac{1}{\|\mathbf{y}\|} \right| \\
&\le 2^{-p-3} + \frac{\|\mathbf{y}\|^2 - \|\mathbf{y}\|^2}{2[\|\mathbf{y}\|^2 - \|\mathbf{y}\|^2 - \|\mathbf{y}\|^2]^{3/2}} \\
&\le 2^{-p-3} + \frac{\epsilon_1}{2[2^9 - \epsilon_1]^{3/2}} \\
&\le 2^{-p-3} + 2^{-15}(1+2^{-1})\epsilon_1 =: \epsilon_2,
\end{aligned}
$$

where the last inequality holds for any $\epsilon_0 \le 2^{-15}$. To avoid overflow of $\overline{1/\|\mathbf{y}\|}$, it suffices that $1/\|\mathbf{y}\| \le 2^{-4} - 2^{-p-3} - \epsilon_2$. The third bound from Lemma 14 holds for any $\epsilon_0 \le 2^{-15}$.

We finally evaluate the accuracy of the output vector $\bar{z}$ with respect to $z := (y_1, \dots, y_d)^\top / \|\mathbf{y}\|^2$. We have, for all $i$:

$$
\begin{aligned}
|\bar{z}_i - z_i| &\le |\bar{y}_i \otimes_{5,-3}^{-1} \overline{1/\|\mathbf{y}\|} - \bar{y}_i \cdot \overline{1/\|\mathbf{y}\|}| + |\bar{y}_i \cdot \overline{1/\|\mathbf{y}\|} - y_i/\|\mathbf{y}\| | \\
&\le 2^{-p-2} + |\overline{1/\|\mathbf{y}\|} - 1/\|\mathbf{y}\|| \cdot |\bar{y}_i| + |\bar{y}_i - y_i|/\|\mathbf{y}\| \\
&\le 2^{-p-2} + 2^5 \cdot \epsilon_2 + 2^{-4} \cdot \epsilon_0 =: \epsilon_3.
\end{aligned}
$$

To avoid overflow of $\bar{z}_i$, it suffices that $|z_i| \le 2^{-2} - 2^{-p-3} - \epsilon_3$. The fourth bound from Lemma 14 still holds for any $\epsilon_0 \le 2^{-20}$.

Note that $\epsilon_3$ is of the order of $2^{14}2^{-p}$. This is a crude upper bound, as it assumes that errors are always in the same direction.

## G.3 Rounding Continuous Hyperball-uniform

Let us now consider the algorithm from Figure 3. We consider a uniform $\mathbf{y}_0 \leftarrow U(\mathcal{B}_{R,m}(1))$, its representation $\bar{\mathbf{y}}_0$ such that $\|\mathbf{y}_0 - \bar{\mathbf{y}}_0\|_{\infty} \le \epsilon_4$, the scaled sample $\mathbf{y} = r'' \cdot \mathbf{y}_0$ and its representation $\bar{\mathbf{y}} = r'' \cdot \bar{\mathbf{y}}_0$, computed exactly, where we let $r'' = NB + \sqrt{mn}/2$. In particular $\|\mathbf{y} - \bar{\mathbf{y}}\|_{\infty} \le r''\epsilon_4$.

Now given any $\mathbf{t}$ with $\|\mathbf{t}\| \le r' = NB$, the probability that the random variable $\mathbf{y}$ gets rounded to it is exactly the inverse of the volume of the hyperball $V_{mn}(r'')$. However, when considering $\bar{\mathbf{y}}$, this probability lies in $[(1 - 2r''\epsilon_4)^{mn}/V_{mn}(r''), (1 + 2r''\epsilon_4)^{mn}/V_{mn}(r'')]$. The ratio of the probability densities thus always lies in $[(1 - 2r''\epsilon_4)^{mn}, (1 + 2r''\epsilon_4)^{mn}]$.

## G.4 Rejection Sampling with Approximate Source Distribution

Here, we study the evolution of the rejection sampling steps from Figure 3 and Figure 6 when used with real, approximate distributions.

**Theorem 5.** Let $M > 1$. Let $\delta_M \ge 1 \ge \delta_m > 0$. Let $Q_r, Q_i$ and $P_i$ such that for any $x \in \text{Supp}(P_i)$, $Q_r(x)/Q_i(x) \in [\delta_m, \delta_M]$ and $R_\infty(P_i\|Q_i) \le M$. Consider $P_r$, the probability distribution whose mass function is proportional to $x \mapsto P_i(x)/(MQ_i(x))Q_r(x)$. Then $P_r(x)/P_i(x) \in [\delta_m/\delta_M, \delta_M/\delta_m]$ for any $x \in \text{Supp}(P_i) = \text{Supp}(P_r)$.

Note that $P_r$ is the resulting distribution when using rejection sampling to go from $Q_i$ to $P_i$ with source distribution $Q_r$.

**Proof.** The normalization factor is

$$ \sum_{z \in \text{Supp}(P_i)} \frac{P_i(z)}{M} \cdot \frac{Q_r(z)}{Q_i(z)} \in \left[ \frac{\delta_m}{M}, \frac{\delta_M}{M} \right]. $$
As we consider positive values, its inverse then lies in $[M/\delta_M, M/\delta_m]$. We conclude by considering that $Q_r(x)/(MQ_i(x))$ lies in $[\delta_m/M, \delta_M/M]$ for any $x \in \text{Supp}(P_i)$. $\square$

This lemma is applied twice in a row, first to get the final discrete hyperball sample $\mathbf{y}$ and second to get the final signature $\mathbf{z}$. In the second case, note that instead of bounding from above and below the distribution of $\mathbf{z}$ (before rejection), we can use the bound we get for $\mathbf{y}$, due to data processing arguments.

### G.5 Putting Everything together

The final interval in which lies the ratio of real and ideal distributions of $\mathbf{z}$ is

$$ \left[ \left( \frac{1 - 2r''\epsilon_4}{1 + 2r''\epsilon_4} \right)^{2mn}, \left( \frac{1 + 2r''\epsilon_4}{1 - 2r''\epsilon_4} \right)^{2mn} \right], $$

where $\epsilon_4 \approx 2^{14-p}$, $r'' \le 2^{28}$ and $mn \le 2^{11}$. As $\max(1-1/x, x-1) = x-1$ for positive $x \le 1$, we apply [Pre17, Lemma 3] and follow their subsequently described strategy to derive the necessary precision. In order to get about $2^{-37}$ precision in the bounds after rejection sampling, it is necessary to choose $p \approx 14 + 28 + 37 + 1$, as the radius $r'' \le 2^{28}$. Going back to the $\sigma$ of our discrete Gaussian distribution, as elements sampled from it will have absolute value at most $14\sigma \approx p$, we choose $\sigma = 2^{76}$, which is also sufficiently big to use discrete Gaussians instead of rounded ones.