WAVE

Gustavo Banegas, Kevin Carrier, André Chailloux, Alain Couvreur, Thomas Debris-Alazard, Philippe Gaborit, Pierre Karpman, Johanna Loyer, Ruben Niederhagen, Nicolas Sendrier, et al.

► To cite this version:

Gustavo Banegas, Kevin Carrier, André Chailloux, Alain Couvreur, Thomas Debris-Alazard, et al. WAVE. 2023. hal-04278563

HAL Id: hal-04278563

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

Submitted on 10 Nov 2023

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

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

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

Round 1 Submission

**Gustavo Banegas**
*Qualcomm, France*

**Kévin Carrier**
*CY Cergy-Paris University, France*

**André Chailloux**
*Inria, France*

**Alain Couvreur**
*Inria, and Laboratoire d'Informatique de l'École polytechnique (LIX),
UMR 7161, CNRS, École polytechnique, Institut Polytechnique de Paris, Palaiseau, France*

**Thomas Debris-Alazard**
*Inria, and Laboratoire d'Informatique de l'École polytechnique (LIX),
UMR 7161, CNRS, École polytechnique, Institut Polytechnique de Paris, Palaiseau, France*

**Philippe Gaborit**
*University of Limoges, France*

**Pierre Karpman**
*Université Grenoble Alpes, France*

**Johanna Loyer**
*Inria, France*

**Ruben Niederhagen**
*Academia Sinica, Taiwan, and University of Southern Denmark, Denmark*

**Nicolas Sendrier**
*Inria, France*

**Benjamin Smith**
*Inria, and Laboratoire d'Informatique de l'École polytechnique (LIX),
UMR 7161, CNRS, École polytechnique, Institut Polytechnique de Paris, Palaiseau, France*

**Jean-Pierre Tillich**
*Inria, France*
**Contact:** wave-contact@inria.fr

**Coordinator:** thomas.debris@inria.fr

**Website:** https://wave-sign.org

**Version:** 1

**Release Date:** June 21, 2023
CONTENTS

Notation and Conventions 1

1. Introduction 3

2. The Wave Signature Scheme – Sketch 4

3. Design Rationale of Wave 5

4. Specifications 6

4.1. Useful Algorithms: Gaussian Elimination and Variants 7

4.2. Key Generation 8

4.3. Wave Signature 9

4.4. Wave Verification 15

5. Performance Analysis 16

6. Known Answer Tests Values 17

7. Proved Security 18

7.1. Signature Distribution and Rényi Divergence 18

7.2. Statement of the security reduction 19

8. Best Known Attacks 20

8.1. Classical attacks 20

8.2. Quantum attacks 21

9. Advantages and Limitations 22

References 23

Appendix A. Hashing to Ternary Vectors 25

Appendix B. Specification toward a Constant Time Implementation 26

B.1. Bitsliced Arithmetic over F₃ 26

B.2. Sampling Trits 27

B.3. Sampling Permutations and Permuting by Sorting 28

B.4. Master Key to Generate the Secret Matrices 31

B.5. Gaussian Elimination and its Variants in Constant Time 32

B.6. Wave Key Generation and Signing in Constant Time 38

Appendix C. Key Representation and Compressing Signatures 39

C.1. Key Representation 39

C.2. Compressing Signatures 39

Appendix D. Proof of Proposition 3 42
NOTATION AND CONVENTIONS

$x := y$ $x$ is defined to be equal to $y$

\#S Cardinality of the finite set S

$\mathbb{Z}$ The ring of integers

$[a, b]$ $[a, b] := \{i \in \mathbb{Z} \mid a \le i \le b\}$

$[a, b)$ $[a, b) := \{i \in \mathbb{Z} \mid a \le i < b\}$

$\mathbb{F}_q$ The $q$-ary finite field ($q = 3$ in all of our concrete parameter sets)

$\mathbf{x} \in \mathbb{F}_q^n$ $\mathbf{x} = (x_0, \dots, x_{n-1}) \in \mathbb{F}_q^n$, vectors in row notation generally use bold letters

$\mathbf{x}(i)$ Alternative notation for $x_i$, convenient when not a single letter, e.g. $\mathbf{e}_V(i)$

$\mathbf{x}_{\mathcal{J}}$ $(x_i)_{i \in \mathcal{J}}$ for $\mathcal{J} \subseteq [0, n)$

$(\mathbf{x} \parallel \mathbf{y})$ Concatenation of vectors $\mathbf{x}$ and $\mathbf{y}$

$\text{Supp}(\mathbf{x})$ Support of $\mathbf{x}$, the set $\{i \in [0, n), x_i \neq 0\}$

$|\mathbf{x}|$ Hamming weight of $\mathbf{x} \in \mathbb{F}_q^n$, $\#\text{Supp}(\mathbf{x})$

$a \cdot \mathbf{x}$ Scalar product $a \mathbf{x} := (ax_i)_{0 \le i < n}$ for $a \in \mathbb{F}_q$ and $\mathbf{x} \in \mathbb{F}_q^n$

$\mathbf{x} \star \mathbf{y}$ Component-wise product $\mathbf{x} \star \mathbf{y} := (x_i y_i)_{0 \le i < n}$ for $\mathbf{x}, \mathbf{y} \in \mathbb{F}_q^n$

$\langle \mathbf{x}, \mathbf{y} \rangle$ Inner product $\langle \mathbf{x}, \mathbf{y} \rangle := \sum_{i=1}^n x_i y_i \in \mathbb{F}_q$ for $\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{F}_q^n$

$\mathbf{M} \in \mathbb{F}_q^{r \times n}$ $(M_{i,j})_{0 \le i < r, 0 \le j < n}$, $r \times n$ matrix over $\mathbb{F}_q$. Matrices generally use capital bold letters

$\mathbf{M}(i, j)$ Alternative notation for $M_{i,j}$, convenient when not a single letter, e.g. $\mathbf{M}_V(i, j)$

$\text{row}(\mathbf{M}, i)$ i-th row of $\mathbf{M}$

$\text{col}(\mathbf{M}, i)$ i-th column of $\mathbf{M}$

$M_i$ Alternative notation for row$(\mathbf{M}, i)$

$\mathbf{M}_{\mathcal{J}}$ $(M_{i,j})_{0 \le i < r, j \in \mathcal{J}}$ for $\mathbf{M} \in \mathbb{F}_q^{r \times n}$ and $\mathcal{J} \subseteq [0, n)$

$\langle \mathbf{M} \rangle$ Raw span of $\mathbf{M}$

$\mathbf{x} \star \mathbf{M}$ Row-wise star product, $\mathbf{x} \star \mathbf{M} := (x_j M_{i,j})_{0 \le i < r, 0 \le j < n}$

$\mathbf{M}^\top$ Transposition of $\mathbf{M}$

$\mathfrak{S}_n$ Group of permutations of $[0, n)$

$\mathbf{x}^\pi$ $\mathbf{x}^\pi := (x_{\pi(i)})_{0 \le i < n}$, for $\mathbf{x} \in \mathbb{F}_q^n$ and $\pi \in \mathfrak{S}_n$

$\mathbf{M}^\pi$ $\mathbf{M}^\pi := (M_{i,\pi(j)})_{0 \le i < r, 0 \le j < n}$ for $\mathbf{M} \in \mathbb{F}_q^{r \times n}$ and $\pi \in \mathfrak{S}_n$

$x \xleftarrow{\mathcal{D}} X$ Variable $x$ sampled from the set $X$ according to the distribution $\mathcal{D}$

$x \xleftarrow{\mathcal{S}} X$ Variable $x$ sampled uniformly at random from the finite set $X$
**Information set**

An *information set* for a matrix $\mathbf{M} \in \mathbb{F}_q^{(r+g)\times n}$ (where $g \ge 0$) is a set $\mathcal{J} \subseteq [0, n)$ of cardinality $r$ such that $\mathbf{M}_{\mathcal{J}} \in \mathbb{F}_q^{(r+g)\times r}$ has full rank.

**Systematic form**

A matrix $\mathbf{M} \in \mathbb{F}_q^{r \times n}$ is in *systematic form* if $\mathbf{M} = (\mathbf{I}\mathbf{d}_r | \mathbf{R})$ where $\mathbf{I}\mathbf{d}_r$ is the $r \times r$ identity matrix.

**Linear code**

An $[n, k]_q$-code $\mathcal{C}$ is defined to be a $k$-dimensional subspace of $\mathbb{F}_q^n$.

**Generator matrix**

A *generator matrix* for a linear $[n, k]_q$-code $\mathcal{C}$ is a matrix $\mathbf{G} \in \mathbb{F}_q^{k \times n}$ whose rows form a basis of $\mathcal{C}$; that is,

$$ \mathcal{C} = \{ \mathbf{x}\mathbf{G} : \mathbf{x} \in \mathbb{F}_q^k \}. $$

**Dual code**

The *dual* of an $[n, k]_q$-code $\mathcal{C}$ is the $[n, n-k]_q$-code defined by

$$ \mathcal{C}^{\perp} := \{ \mathbf{c}^{\perp} \in \mathbb{F}_q^n : \forall \mathbf{c} \in \mathcal{C}, \langle \mathbf{c}, \mathbf{c}^{\perp} \rangle = 0 \}. $$

**Parity-check matrix**

A *parity-check matrix* for an $[n, k]_q$-code $\mathcal{C}$ is a matrix $\mathbf{H} \in \mathbb{F}_q^{(n-k)\times n}$ whose rows form a basis of the dual $\mathcal{C}^{\perp}$. Note that

$$ \mathcal{C} = \{ \mathbf{c} \in \mathbb{F}_q^n : \mathbf{H}\mathbf{c}^{\top} = \mathbf{0} \}. $$
# 1. INTRODUCTION

Wave is a code-based hash-and-sign signature scheme introduced in [DST19]. Wave instantiates the theoretical framework of Gentry, Peikert and Vaikuntanathan [GPV08] using a novel code-based trapdoor: its security is proven to inherit from the hardness of two well-identified problems for which the best known attacks rely on generic decoding algorithms [DST19]. With appropriate parameters, Wave can therefore offer high security against classical and quantum adversaries.

This document specifies the Wave scheme, and proposes highly conservative parameter sets for signatures targeting NIST post-quantum security levels I, III, and V. It also describes a portable C reference implementation for Wave instances with those parameters.

Wave enjoys **short signatures** and **fast verification**, even with conservative parameters. Table 2 gives a preview of our results: Wave signature sizes are highly competitive with structured lattice-based signatures such as Falcon [FHK$^+$17] and CRYSTALS/Dilithium [?], and signatures can be verified in milliseconds on a PC platform. Wave public keys are generator matrices for random-looking linear codes, so they are decidedly on the large side (especially given our conservative parameter choices): this is the main drawback of Wave. However, in use-cases where large public keys can be stored, Wave can be a strong candidate for high-security quantum-safe signatures.

<table><caption>TABLE 2. Signature length and verification speed results for Wave instances. Timings count millions of cycles used on average by the (non-optimized) reference implementation, running on an Intel Core i5-1135G7 platform at 2.40GHz. See §5 for more detailed figures.</caption><thead><tr><th>Wave instance</th><th>Wave822</th><th>Wave1249</th><th>Wave1644</th></tr><tr><th>Post-quantum security target</th><th>Level I</th><th>Level III</th><th>Level V</th></tr></thead><tbody><tr><td><strong>Signature length<sup>1</sup> (Bytes)</strong></td><td><strong>822</strong></td><td><strong>1249</strong></td><td><strong>1644</strong></td></tr><tr><td>Public key size (Bytes)</td><td>3 677 390</td><td>7 867 598</td><td>13 632 308</td></tr><tr><td>Key generation (MCycles)</td><td>14 468</td><td>47 222</td><td>108 642</td></tr><tr><td>Signing (MCycles)</td><td>1 161</td><td>3 507</td><td>7 397</td></tr><tr><td><strong>Verification</strong> (MCycles)</td><td><strong>205.8</strong></td><td><strong>464.1</strong></td><td><strong>813.3</strong></td></tr><tr><td><strong>Verification<sup>2</sup> (MCycles)</strong></td><td><strong>1.231</strong></td><td><strong>2.580</strong></td><td><strong>4.329</strong></td></tr></tbody></table>

We give a brief high-level overview of the scheme in §2, and explain the design rationale in §3. We formally specify the scheme in §4, present performance results for the reference implementation in §5, and link to Known Answer Tests in §6. To justify the security of our proposed instances, we summarize the security proof for Wave in §7 and survey the best known attacks in §8.

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

<footnote n="1">¹ Signatures are compressed to variable-length byte arrays, which may in fact be shorter than this bound.</footnote>

<footnote n="2">² Verification where the public key is pre-loaded in bitsliced format, and does not require conversion from the transport format: see §5 for details.</footnote>
## 2. THE WAVE SIGNATURE SCHEME – SKETCH

Wave is based on the GPV framework [GPV08]; as such, it is built on a trapdoor function. The Wave trapdoor, detailed in §3, is based on *permuted generalized* $(U|U+V)$-codes.

**Definition 1.** Let $n, k_U$, and $k_V$ be integers with $n$ even and $k_U, k_V \le n/2$. Let $U$ be an $[n/2, k_U]_q$-code with generator (resp. parity-check) matrix $\mathbf{G}_U$ (resp. $\mathbf{H}_U$), and let $V$ be an $[n/2, k_V]_q$-code with generator (resp. parity-check) matrix $\mathbf{G}_V$ (resp. $\mathbf{H}_V$). Let $\pi$ be a permutation in $\mathfrak{S}_n$, and let $\mathbf{b}$ and $\mathbf{c}$ be vectors in $\mathbb{F}_q^{n/2}$ with $\mathbf{c}(i) \neq 0$ for all $i \in [0, n/2)$.

The *permuted generalized* $(U|U+V)$-code associated to $(U, V, \pi, \mathbf{b}, \mathbf{c})$ is the $[n, k_U + k_V]_q$-code admitting the generator matrix $\mathbf{G}$ and parity-check matrix $\mathbf{H}$ defined by

$$ \mathbf{G} = \left( \begin{array}{c|c} \mathbf{G}_U & \mathbf{c} \star \mathbf{G}_U \\ \hline \mathbf{b} \star \mathbf{G}_V & \mathbf{d} \star \mathbf{G}_V \end{array} \right)^\pi \quad \text{and} \quad \mathbf{H} = \left( \begin{array}{c|c} \mathbf{d} \star \mathbf{H}_U & -\mathbf{b} \star \mathbf{H}_U \\ \hline -\mathbf{c} \star \mathbf{H}_V & \mathbf{H}_V \end{array} \right)^\pi $$

where $\mathbf{d} := \mathbf{1} + \mathbf{b} \star \mathbf{c}$.

A Wave public key is a parity-check matrix, in systematic form, of a *permuted generalized* $(U|U+V)$-code over $\mathbb{F}_3$. The associated private key is the underlying structure: the codes $U$ and $V$, vectors $\mathbf{b}$ and $\mathbf{c}$, and permutation $\pi$. Table 3 sketches the Wave signature scheme; the full specification begins in §4.

<table><caption>TABLE 3. Sketch of the Wave signature scheme.</caption><thead><tr><th colspan="8">System parameters:</th></tr><tr><th>field size</th><th>sec. level</th><th>codelength</th><th>weight</th><th>U-dimension</th><th>V-dimension</th><th>dimension</th></tr></thead><tbody><tr><td>q = 3</td><td>λ</td><td>n</td><td>w</td><td>k<sub>U</sub></td><td>k<sub>V</sub></td><td>k := k<sub>U</sub> + k<sub>V</sub></td></tr></tbody></table><p><strong>Private key:</strong> (U, V, π, b, c) defining a *permuted generalized* $(U|U+V)$-code.</p><p><strong>Public key:</strong> R ∈ F<sub>3</sub><sup>(n-k)×k</sup> such that (Id<sub>n-k</sub> | R) is a *parity-check matrix* of the *permuted generalized* $(U|U+V)$-code associated to the secret key.</p><p><strong>Signature</strong> on a message m under a public key R: σ = (salt, e) ∈ F<sub>2</sub><sup>2λ</sup> × F<sub>3</sub><sup>k</sup> such that</p><p>|e| + |Hash(m || salt) - eR<sup>T</sup>| = w. (1)</p><p><strong>Verification</strong> of a signature σ = (salt, e) on a message m under a public key R: Accept if (and only if) Equation (1) holds.</p>

The binary vector **salt** in the signature is a (random) salt required by the security proof. Given a signature (**salt**, **e**) on **m** under **R**, the vector **x** := (Hash(**m** || **salt**) - **eR**<sup>T</sup>, **e**) is in fact the unique vector of Hamming weight *w* satisfying **x**(Id<sub>n-k</sub> | **R**) = Hash(**m** || **salt**) and **x**<sub>[n-k,n)</sub> = **e**. The original description of Wave [DST19] took (**salt**, **x**) to be the signature. Here, however, we follow the approach of [BDNS21]: **x** can be immediately recovered from **m**, **salt**, and **e** (by definition), so (**salt**, **e**) can serve as the signature, thus reducing the signature size from 2λ bits and *n* trits to 2λ bits and *k* trits.

<figure><img src="image_4.png" /></figure>
### 3. DESIGN RATIONALE: THE WAVE TRAPDOOR

The design of Wave follows the “hash and sign” approach à la GPV [GPV08] in the same spirit as some lattice-based schemes including Falcon [FHK$^{+}$17], but in an error-correcting code-based context. While the trapdoors in [GPV08] and [FHK$^{+}$17] rely on short bases of lattices, the Wave trapdoor is based on permuted generalized ($U|U + V$)-codes (as in Definition 1).

**3.1. Weight and the general decoding problem.** Wave security inherits from the hardness of the Decoding Problem (DP): given an $[n, k]_q$-code $\mathcal{C}$ (a subspace of $\mathbb{F}_q^n$ of dimension $k$), a distance $w$, and a point $\mathbf{y}$ in the ambient space $\mathbb{F}_q^n$, the aim is to find a $\mathbf{x}$ in $\mathcal{C}$ at Hamming distance $w$ from $\mathbf{y}$, that is, differing from $\mathbf{y}$ on exactly $w$ coordinates.

After sixty years of research on DP, the best approach when the $\mathcal{C}$ has no special structure—and in particular, when it is random—is to take advantage of linearity: $\mathcal{C}$ is a vector space of dimension $k$, so one can simply compute $\mathbf{x} \in \mathcal{C}$ by fixing $k$ coordinates. If $\mathbf{y}$ is uniformly distributed over $\mathbb{F}_q^n$, then the resulting $\mathbf{x}$ has $\mathbf{x}(i) - \mathbf{y}(i)$ “controlled” on exactly $k$ coordinates, while the remaining $n-k$ coordinates are uniformly distributed. In particular, there will typically be $(n-k)(q-1)/q$ non-zero coordinates among these $n-k$ coordinates. Depending on the decoding problem to be solved, “close” (small $w$) or “far away” (large $w$), the best strategy is to carefully choose $\mathbf{x}(i)$ on the $k$ controlled coordinates $i$. If one chooses $j \le k$ coordinates where $\mathbf{x}(i) \ne \mathbf{y}(i)$, then $|\mathbf{x} - \mathbf{y}|$ is typically $j + \frac{q-1}{q}(n-k)$. We can therefore easily compute codewords at distances in $[\frac{q-1}{q}(n-k), k + \frac{q-1}{q}(n-k)]$. Any chosen distance $w$ outside this interval is unlikely to be reached, so the procedure must be repeated a prohibitive number of times for any probability of success.

Figure 1 illustrates the situation. Surprisingly, no known algorithm can solve DP for random codes in polynomial time (in $w$) outside the “easy” interval in the middle.

<figure><img src="image_5.png" /><figcaption>FIGURE 1. Hardness (with respect to $w$), given a random $[n, k]_q$-code $\mathcal{C} \subseteq \mathbb{F}_q^n$ and $\mathbf{y} \in \mathbb{F}_q^n$, of finding $\mathbf{x} \in \mathcal{C}$ at Hamming distance $w$ from $\mathbf{y}$.</figcaption></figure>

**3.2. The Wave trapdoor.** To construct a Wave trapdoor, we sample random codes $U$ and $V$ in $\mathbb{F}_q^{n/2}$ of dimensions $k_U$ and $k_V$, respectively, a permutation $\pi$ in $\mathfrak{S}_n$, and vectors $\mathbf{b}$ and $\mathbf{c}$ in $\mathbb{F}_q^{n/2}$ with $\mathbf{c}(i) \ne 0$ for $i \in [0, n/2)$. These are all kept secret, and the permuted generalized ($U|U + V$)-code

$$ \mathcal{C} := \left\{ \left( (\mathbf{x}_U + \mathbf{b} \star \mathbf{x}_V) \parallel (\mathbf{c} \star \mathbf{x}_U + \mathbf{d} \star \mathbf{x}_V) \right)^\pi : \mathbf{x}_U \in U \text{ and } \mathbf{x}_V \in V \right\} \subseteq \mathbb{F}_q^n $$

of length $n$ and dimension $k := k_U + k_V$ is made public (here $\mathbf{d} := \mathbf{1} + \mathbf{b} \star \mathbf{c}$).

Given a uniform random $\mathbf{y}$ in $\mathbb{F}_q^n$, we can find $\mathbf{x} \in \mathcal{C}$ at the chosen distance

$$ w := 2k_U + 2 \frac{q-1}{q} (n/2 - k_U) $$

from $\mathbf{y}$ using the following procedure, if we know $U, V, \pi, \mathbf{b}$, and $\mathbf{c}$:

(1) Compute any $\mathbf{x}_V \in V$.

<figure><img src="image_6.png" /></figure>
(2) From $\mathbf{y}$ and the knowledge of the secret permutation $\pi$, decompose $\mathbf{y}$ as as $(\mathbf{y}_L, \mathbf{y}_R)^\pi$ with $\mathbf{y}_L$ and $\mathbf{y}_R$ in $\mathbb{F}_q^{n/2}$.

(3) Using the knowledge of $\mathbf{x}_V$, compute some $\mathbf{x}_U \in U$ such that for $k_U$ of the coordinate indices $i$, we have

$$ \mathbf{x}_U(i) \neq \mathbf{y}_L(i) - \mathbf{b}(i)\mathbf{x}_V(i) \quad \text{and} \quad \mathbf{c}(i)\mathbf{x}_U(i) \neq \mathbf{y}_R(i) - \mathbf{d}(i)\mathbf{x}_V(i) \quad (2) $$

(4) Output $\mathbf{x} := ((\mathbf{x}_U + \mathbf{b} \star \mathbf{x}_V) \parallel (\mathbf{c} \star \mathbf{x}_U + \mathbf{d} \star \mathbf{x}_V))^{\pi} \in \mathcal{C}$.

By assumption $\mathbf{c}$ has only non-zero components and $\mathbf{d} = \mathbf{1} + \mathbf{b} \star \mathbf{c}$, so Condition (3) can be satisfied provided $q \ge 3$, which we assume from now on. Furthermore, as $(\mathbf{y}_L, \mathbf{y}_R)$ is uniformly distributed, $\mathbf{y}_L(i) - \mathbf{x}_U(i) - \mathbf{b}(i)\mathbf{x}_V(i)$ and $\mathbf{y}_R(i) - \mathbf{c}(i)\mathbf{x}_U(i) - \mathbf{d}(i)\mathbf{x}_V(i)$ will be uniformly distributed on the other $n/2 - k_U$ coordinates. The Hamming distance is invariant under permutations, so $|(\mathbf{y}_L \parallel \mathbf{y}_R)^\pi - ((\mathbf{x}_U + \mathbf{b} \star \mathbf{x}_V) \parallel (\mathbf{c} \star \mathbf{x}_U + \mathbf{d} \star \mathbf{x}_V))^{\pi}|$ will typically be $w$, as claimed.

Decoding without the secret structure $(U, V, \pi, \mathbf{b}, \mathbf{c})$ of the permuted generalized $(U|U + V)$-code $\mathcal{C}$ is hard, given the discussion above, if the value of $w$ falls outside the “easy” interval $[\frac{q-1}{q}(n-k), k + \frac{q-1}{q}(n-k)]$, where $k = k_U + k_V$. This condition holds when $k_U > k_V$, which is a requirement of Wave.

### 3.3. Signing with the trapdoor.
To sign a message $\mathbf{m}$, the signer hashes it (with a random salt salt) to a random vector $\mathbf{y} \in \mathbb{F}_q^n$. The trapdoor computes a codeword $\mathbf{x} \in \mathcal{C}$ at a distance of $w$ from $\mathbf{y}$. The signature of $\mathbf{m}$ is represented by $\mathbf{x}$. To verify the signature, we must check that $\mathbf{x}$ belongs to $\mathcal{C}$ and that the Hamming distance between $\mathbf{x}$ and the hash of $\mathbf{m}$ with salt is exactly $w$. If the public code $\mathcal{C}$ has no apparent structure to be exploited—that is, it is indistinguishable from a random code—then any adversary seeking to forge a signature must produce a codeword at distance $w$ from a random target, which has a prohibitive cost because $w$ is outside $[\frac{q-1}{q}(n-k), k + \frac{q-1}{q}(n-k)]$; this ensures the security of the signature scheme. (We give more detailed security analyses in §7 and §8.)

This naive signing algorithm is easily broken: a few signatures $\mathbf{x}$ in the permuted generalized $(U|U + V)$-code are enough to recover the trapdoor and thus break the scheme [DST17, §5.1]. In the same way as for other [GPV08]-like schemes, security requires the distribution of signatures to be independent of the trapdoor, so that signatures cannot leak any information on the secret. In particular, $\mathbf{x}_V$ and $\mathbf{x}_U$ must be carefully sampled.

In [DST19], a safe distribution of signatures was achieved through rejection sampling; but this can be problematic for implementation safety and efficiency, especially when constant-time signing is required. We will see that by carefully choosing some internal distributions we can achieve secure signature distributions, and thus avoid rejection sampling entirely without impacting security.

<figure><img src="image_7.png" /></figure>
## 4. SPECIFICATIONS

The specification of an instance of Wave, for any given security level $\lambda$, requires the following parameters:

* The main parameters $n, k, w$,

* additional parameters $k_U, k_V, g$ (used for key generation and signing),

* internal discrete distributions $D_V$ on $[0, k_V - g]$ and $D_U(t)$ on $[0, t]$, for $t$ in $[0, n/2]$,

* a decoder output support $\text{Accept} \subseteq [0, n/2] \times [0, w/2]$, and

* a cryptographic hash function $\text{Hash} : \{0, 1\}^* \to \mathbb{F}_3^{n-k}$.

Table 4 gives the values of these parameters in the Wave instances proposed for security levels I, III, and V.

<table><caption>TABLE 4. Wave system parameters, and their values for proposed instances. The corresponding internal distributions $D_V$ and $D_U$ and decoder output support Accept are described in §7, and are provided as precomputed values in the reference implementation. The hash function is defined in Appendix A.</caption><thead><tr><th rowspan="2">Instance</th><th colspan="3">Main parameters</th><th colspan="3">Additional parameters</th></tr><tr><th>Code length</th><th>Code dimension</th><th>Weight</th><th>U-dim.</th><th>V-dim.</th><th>gap</th></tr><tr><th></th><th>λ</th><th>n</th><th>k</th><th>w</th><th>k<sub>U</sub></th><th>k<sub>V</sub></th><th>g</th></tr></thead><tbody><tr><td>Wave822 (Level I)</td><td>128</td><td>8 576</td><td>4 288</td><td>7 668</td><td>2 966</td><td>1 322</td><td>40</td></tr><tr><td>Wave1249 (Level III)</td><td>192</td><td>12 544</td><td>6 272</td><td>11 226</td><td>4 335</td><td>1 937</td><td>40</td></tr><tr><td>Wave1644 (Level V)</td><td>256</td><td>16 512</td><td>8 256</td><td>14 784</td><td>5 704</td><td>2 552</td><td>40</td></tr></tbody></table>

A full implementation of an instance of Wave requires several algorithmic choices which affect efficiency and security (e.g. ensuring the constant-time property). For our reference implementation, they are given in appendix:

* The hash function in §A,

* bit-sliced ternary arithmetic in §B.1,

* sampling ternary vectors in §B.2,

* sampling and applying permutations in §B.3,

* master key for generating and permuting secret matrices §B.4,

* Gaussian elimination variants in §B.5.

The reference implementation prioritises **constant-time key generation** and **constant-time signing**. Other choices are possible, depending on the context and security requirements. The complexity bottleneck of both key generation and signing is (by far) Gaussian elimination; relaxing the constant-time constraint may significantly improve signing time.

4.1. **Useful Algorithms: Gaussian Elimination and Variants.** Gaussian elimination on an $r \times n$ full-rank matrix $A$ produces another matrix $A'$ whose rows span the same vector space and which contains an $r \times r$ identity sub-matrix, in the columns indexed by an information set $J \subseteq [0, n)$ of size $r$. This set corresponds to the “pivot” positions.

<figure><img src="image_8.png" /></figure>
We will define three Gaussian elimination algorithms: Systematic, Partial, and Extended. Appendix B.5.1 proposes constant-time versions of these algorithms.

**Systematic Gaussian elimination.** Algorithm 1 defines Gaussian elimination on a matrix $\mathbf{A} \in \mathbb{F}_3^{r \times n}$ permuted with $\sigma \in \mathfrak{S}_n$, using the columns of $\mathbf{A}^\sigma$ as pivot positions and “pushing” failing pivot positions to the right. A constant-time version appears in Appendix B.5.1.

<caption>**Algorithm 1 SystGaussElim – Systematic Gaussian Elimination**</caption>

Input: $\mathbf{A} \in \mathbb{F}_3^{r \times n}$ and $\sigma \in \mathfrak{S}_n$.
Output: $\mathbf{A}_{\text{syst}} \in \mathbb{F}_3^{r \times n}$ and $\pi \in \mathfrak{S}_n$.

Requirements:

(1) $\langle \mathbf{A}^\pi \rangle = \langle \mathbf{A}_{\text{syst}} \rangle$,

(2) $\mathbf{A}_{\text{syst}} = (\mathbf{Id}_r | \mathbf{B})$,

(3) $\pi$ is “close” to $\sigma$, and

$$ \pi(i) = \sigma(\ell_i) \text{ for all } i \in [0, r), \text{ where } \ell_i = \min \{j \in [0, n) \mid \text{rank}(\mathbf{A}_{[0,j]}^\sigma) = i\}, $$

$$ \pi(i) = \sigma(\ell_i) \text{ for all } i \in [r, n), \text{ where } \ell_i = \min ([0, n) \setminus \{\sigma^{-1} \circ \pi(j), j \in [0, i]\}). $$

**Remark 1.** Note that, over $\mathbb{F}_3$, the case $\pi = \sigma$ in Algorithm 1 happens 56% of the time.

**Partial Gaussian elimination.** Algorithm 2 defines Gaussian elimination $\mathbf{A} \in \mathbb{F}_3^{r \times n}$ but stopping $g$ steps before the end, that is, after $k - g$ pivots. A constant-time version appears in Appendix B.5.1.

<caption>**Algorithm 2 PartialGaussElim – Partial Gaussian Elimination**</caption>

Input: $\mathbf{A} \in \mathbb{F}_3^{r \times n}$ and $g \le r$ be an integer.
Output: $\mathbf{A}_{\text{partSyst}} \in \mathbb{F}_3^{r \times n}$ or $\perp$.

Requirements:

(1) Output is $\perp$ if and only if $\text{rank}(\mathbf{A}_{[0,r-g]}) < r - g$,

(2) $\langle \mathbf{A}_{\text{partSyst}} \rangle = \langle \mathbf{A} \rangle$,

(3) $\mathbf{A}_{\text{partSyst}} = \left( \frac{\mathbf{Id}_{r-g}}{0} \mid \mathbf{R} \right)$.

**Extended Gaussian elimination.** The Gaussian elimination algorithms above are not sufficient for Wave signing. We also need the “extended” Gaussian elimination defined by Algorithm 3, which outputs a matrix in extended systematic form.

**Definition 2 (Extended systematic form).** A matrix $\mathbf{A} \in \mathbb{F}_3^{r \times n}$ is in extended systematic form if

$$ \text{for all } i \in [0, r), \quad \begin{cases} \mathbf{A}(i, i) \neq 0 \implies \mathbf{A}(i, i) = 1 \text{ and } |\text{col}(\mathbf{A}, i)| = 1, \\ \mathbf{A}(i, i) = 0 \implies |\text{row}(\mathbf{A}, i)| = 0. \end{cases} \qquad (3) $$

We propose a constant-time version of Algorithm 3 in §B.5.2. Basically, Algorithm 3, on input $(\mathbf{A}, g)$ with $\mathbf{A} \in \mathbb{F}_3^{r \times n}$, tries to compute an extended systematic form by first adding $g$ extra (zero) rows and then performing a Gaussian elimination. It succeeds if and only if the first $r + g$ columns of this new matrix have the same rank as $\mathbf{A}$.

<figure><img src="image_9.png" /></figure>
**Algorithm 3** ExtGaussElim – Extended Gaussian Elimination

Input: $\mathbf{A} \in \mathbb{F}_3^{r \times n}$ and $g \le (n-r)$ be an integer.

Output: $\mathbf{A}_{\text{extSyst}} \in \mathbb{F}_3^{(r+g) \times n}$ or $\perp$.

Requirements:

(1) Output is $\perp$ if and only if $\text{rank}(\mathbf{A}_{[0,r]}) < r$,

(2) $\langle \mathbf{A}_{\text{extSyst}} \rangle = \langle \mathbf{A} \rangle$,

(3) $\mathbf{A}_{\text{extSyst}}$ is in extended systematic form.

4.2. **Wave Key Generation.** The secret key in Wave is defined to be the underlying structure of a permuted generalized $(U|U+V)$-code while the public key is—up to some transformation, oblivious of the secret—a parity-check matrix $(\mathbf{Id}_{n-k} | \mathbf{R})$ for this code. To improve verification speed we follow [BDNS21], taking as the public key a matrix $\mathbf{M}(\mathbf{R}) \in \mathbb{F}_3^{k \times (n-k)}$ that can be publicly computed from $\mathbf{R} \in \mathbb{F}_3^{(n-k) \times k}$ (and reciprocally) as in Definition 3.

**Definition 3.** If $\mathbf{R} \in \mathbb{F}_3^{(n-k) \times k}$, then we define $\mathbf{M}(\mathbf{R})$ to be the matrix in $\mathbb{F}_3^{k \times (n-k)}$ such that

$$ \left. \begin{array}{l} \text{row}(\mathbf{M}(\mathbf{R}), 2i) := \text{col}(\mathbf{R}, 2i) + \text{col}(\mathbf{R}, 2i + 1) \\ \text{row}(\mathbf{M}(\mathbf{R}), 2i + 1) := \text{col}(\mathbf{R}, 2i) - \text{col}(\mathbf{R}, 2i + 1) \end{array} \right\} \text{for } 0 \le i < \frac{k-1}{2} $$

and if $k$ is odd,

$$ \text{row}(\mathbf{M}(\mathbf{R}), k-1) := -\text{col}(\mathbf{R}, k-1). $$

**Algorithm 4** Key Generation

Output: $\left\{ \begin{array}{l} \text{pk} = \mathbf{M} \in \mathbb{F}_3^{k \times (n-k)}, \\ \text{sk} = (\mathbf{H}_U, \mathbf{G}_V, \pi, \mathbf{b}, \mathbf{c}) \in \mathbb{F}_3^{(n/2-k_U) \times n/2} \times \mathbb{F}_3^{k_V \times n/2} \times \mathcal{S}_n \times \mathbb{F}_3^{n/2} \times (\mathbb{F}_3 \setminus \{0\})^{n/2}. \end{array} \right.$

1: $\mathbf{G}_V \stackrel{\$}{\leftarrow} \mathbb{F}_3^{k_V \times n/2}$

2: $\mathbf{H}_V \leftarrow \text{Orthogonal}(\mathbf{G}_V) \quad \triangleright \mathbf{H}_V \in \mathbb{F}_3^{(n/2-k_V) \times n/2}$ of full rank such that $\mathbf{G}_V \mathbf{H}_V^\top = 0$

3: $\mathbf{H}_U \stackrel{\$}{\leftarrow} \mathbb{F}_3^{(n/2-k_U) \times n/2}$

4: $\mathbf{b} \stackrel{\$}{\leftarrow} \mathbb{F}_3^{n/2}$

5: $\mathbf{c} \stackrel{\$}{\leftarrow} (\mathbb{F}_3 \setminus \{0\})^{n/2}$

▷ Coordinates of $\mathbf{c}$ are non-zero

6: $\mathbf{d} \leftarrow \mathbf{1} + \mathbf{b} \star \mathbf{c}$

7: $\mathbf{H} \leftarrow \left( \frac{\mathbf{d} \star \mathbf{H}_U}{-\mathbf{c} \star \mathbf{H}_V} \middle| \frac{-\mathbf{b} \star \mathbf{H}_U}{\mathbf{H}_V} \right)$

8: $\sigma \stackrel{\$}{\leftarrow} \mathcal{S}_n$

9: $((\mathbf{Id}_k | \mathbf{R}), \pi) \leftarrow \text{SystGaussElim}(\mathbf{H}, \sigma)$

▷ Algorithm 1, $\pi$ may differ from $\sigma$

10: $\mathbf{M} \leftarrow \mathbf{M}(\mathbf{R})$

▷ As in Definition 3

11: return $(\mathbf{pk} = \mathbf{M}, \mathbf{sk} = (\mathbf{H}_U, \mathbf{G}_V, \pi, \mathbf{b}, \mathbf{c}))$

**About the secret key.** The secret key is defined to be $\mathbf{sk} = (\mathbf{H}_U, \mathbf{G}_V, \pi, \mathbf{b}, \mathbf{c})$. In practice, we sample the random matrices $\mathbf{H}_U$ and $\mathbf{G}_V$ using pseudorandom generator seeded with a master key $\mathbf{mk}$, so we can store the much more compact $(\mathbf{mk}, \pi, \mathbf{b}, \mathbf{c})$ as the secret key and regenerate $\mathbf{H}_U$ and $\mathbf{G}_V$ as needed. We sample the matrices using an XOF $f_{\mathbf{mk}}$ parametrized by $\mathbf{mk}$: for example, $f_{\mathbf{mk}}(\text{"U"} \parallel i)$ gives the $i$-th column of $\mathbf{H}_U$ (including the constant "U" provides domain separation). More precisely, we propose using SHAKE256($\mathbf{mk} \parallel \cdot$) for $f_{\mathbf{mk}}$.

<figure><img src="image_10.png" /></figure>
4.3. **Wave Signature.** Wave signing is built around a decoder algorithm, for which there are multiple equivalent descriptions; here, we describe it in terms of noisy codewords. There are two steps. First, a decoding relative to the code $V$ ($	ext{Decode}_V$), producing an error pattern $\mathbf{e}_V$; then, a decoding relative to the code $U$ and dependent on $\mathbf{e}_V$ ($\text{Decode}_U$), producing an error pattern $\mathbf{e}_U$. These error patterns are combined to produce the signature.

<caption>**Algorithm 5 Wave Signature**</caption>

Input: a message $\mathbf{m}, \mathbf{sk} = (\mathbf{H}_U, \mathbf{G}_V, \pi, \mathbf{b}, \mathbf{c})$
Output: $(\mathbf{s}, \text{salt})$
1: **repeat**
2: &nbsp;&nbsp;&nbsp;&nbsp;**salt** ← $\{0, 1\}^{2\lambda}$ &nbsp;&nbsp;&nbsp;&nbsp;▷ $\lambda \in \{128, 192, 256\}$ denotes the security level
3: &nbsp;&nbsp;&nbsp;&nbsp;**x** ← Hash($\mathbf{m} \parallel \text{salt}$) &nbsp;&nbsp;&nbsp;&nbsp;▷ $\mathbf{x} \in \mathbb{F}_3^{n-k}$
4: &nbsp;&nbsp;&nbsp;&nbsp;**y** = ($\mathbf{y}_L \parallel \mathbf{y}_R$) ← ($\mathbf{x} \parallel \mathbf{0}^k\pi^{-1}$) &nbsp;&nbsp;&nbsp;&nbsp;▷ $\mathbf{y}_L, \mathbf{y}_R \in \mathbb{F}_3^{n/2}$
5: &nbsp;&nbsp;&nbsp;&nbsp;**y**$_V$ ← $\mathbf{y}_R - \mathbf{c} \star \mathbf{y}_L$
6: &nbsp;&nbsp;&nbsp;&nbsp;**e**$_V$ ← $	ext{Decode}_V(\mathbf{y}_V, \mathbf{G}_V)$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 6
7: &nbsp;&nbsp;&nbsp;&nbsp;**y**$_U$ ← $\mathbf{y}_L - \mathbf{b} \star \mathbf{y}_V$ &nbsp;&nbsp;&nbsp;&nbsp;▷ simplification of $\mathbf{y}_U = (\mathbf{1} + \mathbf{c} \star \mathbf{b}) \star \mathbf{y}_L - \mathbf{b} \star \mathbf{y}_R$
8: &nbsp;&nbsp;&nbsp;&nbsp;**e**$_U$ ← $	ext{Decode}_U(\mathbf{y}_U, \mathbf{e}_V, \mathbf{b}, \mathbf{c}, \mathbf{H}_U)$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 7
9: &nbsp;&nbsp;&nbsp;&nbsp;**e**$_L$ ← $\mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$
10: &nbsp;&nbsp;&nbsp;&nbsp;**e**$_R$ ← $\mathbf{c} \star \mathbf{e}_L + \mathbf{e}_V$ &nbsp;&nbsp;&nbsp;&nbsp;▷ simplification of $\mathbf{e}_R = \mathbf{c} \star \mathbf{e}_U + (\mathbf{1} + \mathbf{b} \star \mathbf{c}) \star \mathbf{e}_V$
11: **until** ($|\mathbf{e}_V|, n/2 - w + |\mathbf{e}_L \star \mathbf{e}_R|$) ∈ Accept
12: **e** ← ($\mathbf{e}_L \parallel \mathbf{e}_R\pi$)
13: **s** ← $\mathbf{e}_{|n-k,n)}$
14: **return** $(\mathbf{s}, \text{salt})$

**Remark 2.** The signatures such that ($|\mathbf{e}_V|, n/2 - w + |\mathbf{e}_L \star \mathbf{e}_R|$) $\notin$ Accept are rejected and the signature process restarts. The probability of rejection is negligible in practice, less than $2^{-68}$ in our reference implementation. However, this rejection sampling is formally required to guarantee that the Rényi divergence between the output distributions of the actual algorithm and its “ideal” version is small enough (see §7).

**Proposition 1.** Let ($\mathbf{pk} = \mathbf{M}, \mathbf{sk} = (\mathbf{H}_U, \mathbf{G}_V, \pi, \mathbf{b}, \mathbf{c})$) be a valid Wave keypair. On input $\mathbf{m}$ and $\mathbf{sk}$, Algorithm 5 outputs $(\mathbf{s}, \text{salt})$ such that

$$|\mathbf{s}| + |\text{Hash}(\mathbf{m} \parallel \text{salt}) - \mathbf{s}\mathbf{R}^{\top}| = w$$

where $\mathbf{R}$ is such that $\mathbf{M} = \mathbf{M}(\mathbf{R})$ (as in Definition 3).

*Proof.* Propositions 2 and 3 show that Algorithms 6 ($\text{Decode}_V$) and 7 ($\text{Decode}_U$) output $\mathbf{e}_V$ and $\mathbf{e}_U$ satisfying

(i) $\mathbf{y}_V - \mathbf{e}_V \in \langle \mathbf{G}_V \rangle$,

(ii) $(\mathbf{y}_U - \mathbf{e}_U) \mathbf{H}_U^\top = \mathbf{0}_{n/2-k_U}$, and

(iii) $|\mathbf{e}| = |\mathbf{e}_L| + |\mathbf{e}_R| = w$.

In the notation of Algorithm 4,

$$\mathbf{H} = \left( \begin{array}{c|c} \mathbf{d} \star \mathbf{H}_U & -\mathbf{b} \star \mathbf{H}_U \\ \hline -\mathbf{c} \star \mathbf{H}_V & \mathbf{H}_V \end{array} \right)$$

where $\mathbf{d} = \mathbf{1} + \mathbf{b} \star \mathbf{c}$ and $\mathbf{H}_V$ satisfies

$$\mathbf{G}_V \mathbf{H}_V^\top = \mathbf{0}_{k \times (n-k)}.$$

<figure><img src="image_11.png" /></figure>
Therefore, according to Condition ??,

$$ (\mathbf{y}_V - \mathbf{e}_V) \mathbf{H}_V^\top = \mathbf{0}_{n/2-k_V}. \qquad (4) $$

Now

$$ \begin{aligned} & ((\mathbf{e}_L \| \mathbf{e}_R) - (\mathbf{y}_L \| \mathbf{y}_R)) \mathbf{H}^\top \\ &= (((\mathbf{e}_L - \mathbf{y}_L) \star \mathbf{d} - (\mathbf{e}_R - \mathbf{y}_R) \star \mathbf{b}) \mathbf{H}_U^\top \| ((-\mathbf{e}_L - \mathbf{y}_L) \star \mathbf{c} + (\mathbf{e}_R - \mathbf{y}_R)) \mathbf{H}_V^\top), \end{aligned} \qquad (5) $$

but

$$ \begin{aligned} & (\mathbf{e}_L - \mathbf{y}_L) \star \mathbf{d} - (\mathbf{e}_R - \mathbf{y}_R) \star \mathbf{b} = (\mathbf{e}_L - \mathbf{y}_L) \star (\mathbf{d} - \mathbf{c} \star \mathbf{b}) - (\mathbf{e}_V - \mathbf{y}_V) \star \mathbf{b} \\ &= \mathbf{e}_L - \mathbf{y}_L - (\mathbf{e}_V - \mathbf{y}_V) \star \mathbf{b} \\ &= \mathbf{e}_U - \mathbf{y}_U \end{aligned} \qquad (6) $$

and

$$ -(\mathbf{e}_L - \mathbf{y}_L) \star \mathbf{c} + \mathbf{e}_R - \mathbf{y}_R = \mathbf{e}_V - \mathbf{y}_V, \qquad (7) $$

so plugging Equations (7) and (8) into Equation (6) gives

$$ ((\mathbf{e}_L \| \mathbf{e}_R) - (\mathbf{y}_L \| \mathbf{y}_R)) \mathbf{H}^\top = ((\mathbf{e}_U - \mathbf{y}_U) \mathbf{H}_U^\top \| (\mathbf{e}_V - \mathbf{y}_V) \mathbf{H}_V^\top). $$

Now using Condition 4.3 and Equation (5) yields

$$ \begin{aligned} & ((\mathbf{e}_L \| \mathbf{e}_R)^\pi - (\mathbf{y}_L \| \mathbf{y}_R)^\pi) (\mathbf{H}^\pi)^\top = ((\mathbf{e}_L \| \mathbf{e}_R) - (\mathbf{y}_L \| \mathbf{y}_R)) \mathbf{H}^\top \\ &= \mathbf{0}_{n-k}. \end{aligned} \qquad (8) $$

By the definitions of $\pi$ and SystGaussElim, there exists a non-singular matrix $\mathbf{S} \in \mathbb{F}_3^{(n-k) \times (n-k)}$ corresponding to the Gaussian elimination such that

$$ \mathbf{S}\mathbf{H}^\pi = (\mathbf{Id}_{n-k} | \mathbf{R}). $$

Therefore Equation (9) becomes

$$ \begin{aligned} \mathbf{0}_{n-k} &= ((\mathbf{e}_L \| \mathbf{e}_R)^\pi - (\mathbf{y}_L \| \mathbf{y}_R)^\pi) (\mathbf{S}\mathbf{H}^\pi)^\top \\ &= ((\mathbf{e}_L \| \mathbf{e}_R)^\pi - (\mathbf{y}_L \| \mathbf{y}_R)^\pi) (\mathbf{Id}_{n-k} | \mathbf{R})^\top \end{aligned} $$

but since $\mathbf{e} = (\mathbf{e}_L \| \mathbf{e}_R)^\pi$ and $(\mathbf{y}_L \| \mathbf{y}_R)^\pi = (\mathbf{x} \| \mathbf{0}_k)$ we have

$$ \begin{aligned} \mathbf{0}_{n-k} &= (\mathbf{e} - (\mathbf{x} \| \mathbf{0}_k)) (\mathbf{Id}_{n-k} | \mathbf{R})^\top \\ &= \mathbf{e}_{[0,n-k)} - \mathbf{x} + \mathbf{e}_{[n-k,n)} \mathbf{R}^\top \\ &= \mathbf{e}_{[0,n-k)} - \text{Hash}(\mathbf{m} \| \text{salt}) + \mathbf{s}\mathbf{R}^\top. \end{aligned} $$

Therefore,

$$ \begin{aligned} |\mathbf{s}| + |\text{Hash}(\mathbf{m} \| \text{salt}) - \mathbf{s}\mathbf{R}^\top| &= |\mathbf{s}| + |\mathbf{e}_{[0,n-k)}| \\ &= |\mathbf{e}_{[n-k,n)}| + |\mathbf{e}_{[0,n-k)}| \\ &= |\mathbf{e}| \end{aligned} $$

and we conclude the proof by applying Condition 4.3. $\square$

**Leakage-free signatures.** One of the key properties of Wave is that the vector $\mathbf{e}$ in Instruction 12 of Algorithm 5 has been proven to be uniformly distributed over words of Hamming weight $w$ (see [DST19, §5]). In particular, its distribution is independent of the secrets involved in the signing process: even with the knowledge of the secret key, signatures

<figure><img src="image_12.png" /></figure>
are indistinguishable from random words of weight $w$. This property implies that Wave is a hash-and-sign signature scheme immune to leakage attacks. We stress, however, that this property only holds if Wave is properly implemented. Some implementation mistakes, such as incorrect sampling of random data in $\text{Decode}_U$ or $\text{Decode}_V$, may produce valid but biased signatures, opening the door to statistical attacks. Some possible biases are described in [DST17, §5.1].

4.3.1. Decoder for $V$. The input to $\text{Decode}_V$ in Instruction 6 of Algorithm 5 is a matrix $\mathbf{G}_V \in \mathbb{F}_3^{k_V \times n/2}$ and a word $\mathbf{y}_V \in \mathbb{F}_3^{n/2}$ and the output is a word $\mathbf{e}_V \in \mathbb{F}_3^{n/2}$ such that $\mathbf{y}_V - \mathbf{e}_V \in \langle \mathbf{G}_V \rangle$. It is also required (to avoiding leakage) that over all possible uniformly distributed inputs $(\mathbf{G}_V, \mathbf{y}_V)$, the weight distribution of the output $\mathbf{e}_V$ is close to the distribution $\mathcal{D}$ of $|\mathbf{e}_L + \mathbf{e}_R|$ when $(\mathbf{e}_L \| \mathbf{e}_R)$ is uniformly distributed over words of Hamming weight $w$ in $\mathbb{F}_3^n$.

The algorithm $\text{Decode}_V$ first splits $[0, n/2)$ in two by choosing uniformly a set $L \subseteq [0, n/2)$ of $k_V - g$ indices<fnref n="1" />. Without loss of generality, given $\mathbf{x} \in \mathbb{F}_3^{n/2}$, we define $\mathbf{x}^{(0)}$ and $\mathbf{x}^{(1)}$ by writing $\mathbf{x}$ (up to a permutation) as follows

$$ \mathbf{x} = \begin{array}{c} \begin{array}{c} k_V - g \\ \hline \mathbf{x}^{(0)} \end{array} & \begin{array}{c} n/2 - k_V + g \\ \hline \mathbf{x}^{(1)} \end{array} \end{array} \qquad (9) $$

with the left part $\mathbf{x}^{(0)}$ indexed by $L$. $\text{Decode}_V$ selects a word $\mathbf{e}_V = (\mathbf{e}^{(0)} \| \mathbf{e}^{(1)})$ such that $\mathbf{e}^{(1)}$ is uniformly distributed in $\mathbb{F}_3^{n/2-k_V+g}$ and $\mathbf{e}^{(0)}$ is chosen with a weight $t$ sampled from $\mathcal{D}_V$. The weight of $\mathbf{e}^{(1)}$ follows a binomial distribution with parameters $(n/2 - k_V + g, 2/3)$, say $\mathcal{B}_V$. The distribution $\mathcal{D}_V$ is chosen such that $\mathcal{D}_V + \mathcal{B}_V^2$ is close to $\mathcal{D}$.

**Algorithm 6** $\text{Decode}_V$

1: **function** $\text{Decode}_V(\mathbf{y}_V, \mathbf{G}_V)$
2: &nbsp;&nbsp;&nbsp;$t \leftarrow \mathcal{D}_V[0, k_V - g]$
3: &nbsp;&nbsp;&nbsp;**repeat**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\pi \leftarrow \mathfrak{S}_{n/2}$
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{y} \leftarrow \mathbf{y}_V^\pi$
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{G} \leftarrow \text{PartialGaussElim}(\mathbf{G}_V^\pi, g)$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**until** $\mathbf{G} \neq \perp$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{x} \leftarrow \mathfrak{S}_{(\mathbb{F}_3 \setminus \{0\})^t \times \{0\}^{k_V - g - t} \times \mathbb{F}_3^g}$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathbf{e} \leftarrow \mathbf{y} + (\mathbf{x} - \mathbf{y}^{(0)})\mathbf{G}$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $\mathbf{e}_V = \mathbf{e}^{\pi^{-1}}$
$\triangleright \langle \mathbf{G} \rangle = \langle \mathbf{G}_V^\pi \rangle$, $\mathbf{G} = \left( \begin{array}{c|c} \mathbf{Id}_{k_V - g} & \mathbf{R} \\ \hline \mathbf{0} & \end{array} \right)$
$\triangleright \mathbf{y} = (\mathbf{y}^{(0)} \| \mathbf{y}^{(1)}) \in \mathbb{F}_3^{n/2}$ with $\mathbf{y}^{(0)} \in \mathbb{F}_3^{k_V - g}$

**Proposition 2.** On input $(\mathbf{y}_V, \mathbf{G}_V)$, the vector $\mathbf{e}_V \in \mathbb{F}_3^{n/2}$ output by Algorithm 6 satisfies
$$ \mathbf{y}_V - \mathbf{e}_V \in \langle \mathbf{G}_V \rangle. $$

*Proof.* By definition, $\mathbf{y} - \mathbf{e} \in \langle \mathbf{G} \rangle = \langle \mathbf{G}_V^\pi \rangle$ in Instruction 9. The result follows on applying $\pi^{-1}$. $\square$

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

<footnote n="1">¹The gap $g$ is a system parameter such that the submatrix formed by any $k_V - g$ columns of $\mathbf{G}_V$ has full rank with overwhelming probability.</footnote>

<footnote n="2">²The distribution of $|\mathbf{x} + \mathbf{y}|$ when $\mathbf{x}$ and $\mathbf{y}$ are independently distributed according to $\mathcal{D}_V$ and $\mathcal{B}_V$.</footnote>
**Remark 3.** As it is described, Algorithm 6 samples a random permutation $\pi$ and implicitly defines a set $L = \pi([0, k_V - g])$. While $L$ must be distributed uniformly, this is not required for $\pi$ (which must only have $L$ as its first $k_V - g$ entries). In practice (as in §B.3.2), $\pi$ is sampled so that $\pi([0, k_V - g])$ and $\pi([0, t])$ are uniformly distributed in $[0, n/2)$ and $\pi([0, k_V - g])$, respectively.

**Remark 4.** Instructions 4 and 5 of Decode$_V$ sample a permutation and apply it to a vector; this may be implemented as a single subroutine. Using the procedure suggested in §B.3.2, the call would be

$$ (\pi, \mathbf{y}) \leftarrow \text{RandPerm}_V(n/2, k_V - g, t, \mathbf{y}_V) $$

where the arguments $k_V - g$ and $t$ are provided to ensure that both $\pi([0, k_V - g])$ and $\pi([0, t])$ are uniformly distributed (see Algorithm 27).

4.3.2. Decoder for $U$. The input of Decode$_U$ in Instruction 8 of Algorithm 5 is a matrix $\mathbf{H}_U \in \mathbb{F}_3^{(n/2-k_U) \times n/2}$ and a vector $\mathbf{y}_U \in \mathbb{F}_3^{n/2}$, and the output a vector $\mathbf{e}_U \in \mathbb{F}_3^{n/2}$ such that $(\mathbf{y}_U - \mathbf{e}_U) \mathbf{H}_U^\top = \mathbf{0}_{n/2-k_U}$. The target distribution for $\mathbf{e}_U$ is conditioned by the result $\mathbf{e}_V$ of the first decoding. It is shown in [DST19, §5] that, conditioned on $t := |\mathbf{e}_V|$, the output $\mathbf{e}_U$ is correctly distributed if and only if the number

$$ j = \#([0, n/2) \setminus (\text{Supp}(\mathbf{e}_V) \cup \text{Supp}(\mathbf{e}_U))) $$

of positions that are simultaneously null in $\mathbf{e}_U$ and $\mathbf{e}_V$ follows a prescribed distribution, dependent on $t$.

Algorithm 7 (Decode$_U$) splits $[0, n/2)$ in two by sampling an integer $\ell \in [0, t]$ according to $\mathcal{D}_U(t)$ where $t = |\mathbf{e}_V|$, and then uniformly sampling a set $L \subseteq [0, n/2)$ of $n/2 - k_U + g$ indices containing exactly $\ell$ elements of $\text{Supp}(\mathbf{e}_V)$. Without loss of generality, given $\mathbf{x} \in \mathbb{F}_3^{n/2}$ we define $\mathbf{x}^{(0)}$ and $\mathbf{x}^{(1)}$ by writing $\mathbf{x}$ (up to a permutation) as follows

$$ \mathbf{x} = \left\lfloor \frac{n/2 - k_U + g}{\ell} \mathbf{x}^{(0)} \right\rfloor \quad \left\lfloor \frac{k_U - g}{t - \ell} \mathbf{x}^{(1)} \right\rfloor \qquad (10) $$

with the left part $\mathbf{x}^{(0)}$ being indexed by $L$. The $t$ positions of $\text{Supp}(\mathbf{e}_V)$ are depicted with $\ell$ of them being on the left block and the other $t - \ell$ being full right but they could be anywhere within their blocks. The algorithm selects a word $\mathbf{e} = (\mathbf{e}^{(0)} \parallel \mathbf{e}^{(1)})$, which will be equal to $\mathbf{e}_U$ up to some permutation, such that $\mathbf{e}^{(0)}$ is uniformly distributed in $\mathbb{F}_3^{n/2-k_U+g}$ and $\mathbf{e}^{(1)}$ is chosen to reach the final signature weight (see below). The value of $j$ is controlled by $\ell$, which is distributed according to $\mathcal{D}_U(t)$. As for $V$, an appropriate choice of the distribution $\mathcal{D}_U(t)$ allows a distribution of $j$ that is close to the target distribution.

**About the choice of e**(1). The choice of $\mathbf{e}^{(1)} \in \mathbb{F}_3^{k_U - g}$ in Instruction 20 of Algorithm 7 is such that both $\mathbf{e}_L = \mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$ and $\mathbf{e}_R = \mathbf{c} \star \mathbf{e}_L + \mathbf{e}_V$ (from which a signature is built in Instructions 9-14 of Algorithm 5) have $k_U - g$ non-zero coordinates on $\pi([n/2 - k_U + g, n/2])$, as shown in Lemma 3. This will follow from the fact that $\mathbf{e}_U$ and $\mathbf{e}_V$ satisfy

$$ \begin{aligned} \mathbf{e}_U(i) &= (\mathbf{c}(i) - \mathbf{b}(i)) \mathbf{e}_V(i) & \text{if } i \in \pi([n/2 - k_U + g, n/2]) \cap \text{Supp}(\mathbf{e}_V), \\ \mathbf{e}_U(i) \in \mathbb{F}_3 \setminus \{0\} & \text{if } i \in \pi([n/2 - k_U + g, n/2]) \setminus \text{Supp}(\mathbf{e}_V). \end{aligned} \qquad (11) $$

**Proposition 3.** On input $(\mathbf{y}_U, \mathbf{e}_V, \mathbf{b}, \mathbf{c}, \mathbf{H}_U)$, Algorithm 7 outputs $\mathbf{e}_U$ satisfying

$$ (\mathbf{y}_U - \mathbf{e}_U) \mathbf{H}_U^\top = \mathbf{0}_{n/2 - k_U} \qquad (12) $$

<figure><img src="image_14.png" /></figure>
**Algorithm 7** Decode<sub>U</sub>

1: **function** Decode<sub>U</sub>(y<sub>U</sub>, e<sub>V</sub>, b, c, H<sub>U</sub>)
2:     t ← |e<sub>V</sub>|
3:     ℓ ← <sub>D<sub>U</sub><sup>(t)</sup></sub>[0, t]
4:     **repeat**
5:         π ← <sup>$</sup> {π ∈ S<sub>n/2</sub> | # π([0, n/2 - k<sub>U</sub> + g)) ∩ Supp(e<sub>V</sub>) = ℓ}
6:         y ← y<sub>U</sub>
7:         v ← ((c - b) ★ e<sub>V</sub>)<sup>π</sup>
8:         v<sup>(0)</sup> ← v<sub>[0, n/2 - k<sub>U</sub> + g)</sub>
9:         v<sup>(1)</sup> ← v<sub>[n/2 - k<sub>U</sub> + g, n/2)</sub>
10:        s ← (e<sub>V</sub> ★ e<sub>V</sub>)<sup>π</sup>
11:        s<sup>(0)</sup> ← s<sub>[0, n/2 - k<sub>U</sub> + g)</sub>
12:        s<sup>(1)</sup> ← s<sub>[n/2 - k<sub>U</sub> + g, n/2)</sub>
13:        H ← ExtGaussElim(H<sub>U</sub><sup>π</sup>, g)
14:        **until** H ≠ ⊥
15:        **repeat**
16:            z<sup>(0)</sup> ← (H<sub>i,i</sub>)<sub>0≤i<n/2−k<sub>U</sub>+g</sub>
17:            e<sup>(0)</sup> ← <sup>$</sup> F<sub>3</sub><sup>n/2−k<sub>U</sub>+g</sup>
18:            e<sup>(0)</sup> ← (1 − z<sup>(0)</sup>) ★ e<sup>(0)</sup>
19:            e<sup>(1)</sup> ← <sup>$</sup> (F<sub>3</sub> \ {0})<sup>k<sub>U</sub>−g</sup>
20:            e<sup>(1)</sup> ← v<sup>(1)</sup> + (1 − s<sup>(1)</sup>) ★ e<sup>(1)</sup>
21:            e<sup>(0)</sup> ← e<sup>(0)</sup> + (y − (e<sup>(0)</sup> || e<sup>(1)</sup>)) H<sup>T</sup>
22:            i ← |s<sup>(0)</sup> ★ e<sup>(0)</sup> − v<sup>(0)</sup>|
23:            j ← n/2 − k<sub>U</sub> + g − ℓ − |(1 − s<sup>(0)</sup>) ★ e<sup>(0)</sup>|
24:            **until** (2j + i = n − w)
25:            e ← (e<sup>(0)</sup> || e<sup>(1)</sup>)
26:            **return** e<sub>U</sub> = e<sup>π−1</sup>

    ▷ y ∈ F<sub>3</sub><sup>n/2</sup>
    ▷ v ∈ F<sub>3</sub><sup>n/2</sup>

    ▷ s ∈ {0, 1}<sup>n/2</sup>

    ▷ H ∈ F<sub>3</sub><sup>(n/2−k<sub>U</sub>+g)×n/2</sup>

    ▷ check final weight

Furthermore, if $\mathbf{e}_L := \mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$ and $\mathbf{e}_R := \mathbf{c} \star \mathbf{e}_L + \mathbf{e}_V$, then

$$|\mathbf{e}_L| + |\mathbf{e}_R| = w. \qquad (13)$$

Proof. See Appendix D. □

**Remark 5.** As it is described, Algorithm 7 samples an integer $ℓ$ according to $D_U(t)$, then, uniformly, a permutation $\pi$ such that $\#L \cap \text{Supp}(e_V) = ℓ$ where $L = \pi([0, n/2 - k_U + g])$. The set $L$ must be distributed uniformly with an intersection of size $ℓ$ with $\text{Supp}(e_V)$, but uniformity among all permutations is not required for $\pi$ which must only have $L$ as its first $n/2 - k_U + g$ entries.

<figure><img src="image_15.png" /></figure>
**Remark 6.** The $n/2-k_U+g$ leftmost positions, corresponding to $L$, include an information set (for $H_U$) plus $g$ additional coordinates

$$ \mathbf{x} = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.75, every node/.style={scale=0.75}]
  \node (top) at (0, 0.5) {$\mathbf{x}^{(0)}$};
  \node (bottom) at (0, -0.5) {$\mathbf{x}^{(1)}$};
  \node (left) at (-0.5, 0) {$g$};
  \node (right) at (0.5, 0) {$t-\ell$};
  \node (topleft) at (top) {$\left|\right|$};
  \node (topright) at (top) {$\left|\right|$};
  \node (bottomleft) at (bottom) {$\left|\right|$};
  \node (bottomright) at (bottom) {$\left|\right|$};
  \draw (top) -- (bottom);
  \draw (topleft) -- (bottomleft);
  \draw (topright) -- (bottomright);
  \draw (left) -- (right);
  \node at (0, -0.3) {$k_U-g$};
  \node at (0, 0.3) {$n/2-k_U+g$};
\end{tikzpicture} \quad (14) $$

The $g$ extra coordinates are depicted on the left here, but they could be anywhere; they are not necessarily disjoint from the $\ell$ positions of $\text{Supp}(\mathbf{e}_V)$. Vector operations will use the vectors $\mathbf{z}^{(0)} \in \mathbb{F}_2^{n/2-k_V+g}$ and $\mathbf{s} = (\mathbf{s}^{(0)} \parallel \mathbf{s}^{(1)}) \in \mathbb{F}_2^{n/2}$ as masks to select the various regions.

**Remark 7.** There is a rejection condition $n - 2j - i = w$ to ensure the final weight is correct. This condition is oblivious of private information: its failure doesn't require a new permutation or Gaussian elimination, only fresh values of $\mathbf{e}^{(0)}$ and $\mathbf{e}^{(1)}$.

**Remark 8.** Instructions 5, 6, 7 and 10 sample a permutation and apply it to several vectors. This may be implemented as a single subroutine. Using the procedure suggested in §B.3.3, the call would be

$$ (\pi, \mathbf{x}') \leftarrow \text{RandPerm}_U(n/2, n/2 - k_U + g, \ell, \text{Supp}(\mathbf{e}_V), \mathbf{x}) $$

where the vectors $\mathbf{y}_V$, $(\mathbf{c} - \mathbf{b}) \star \mathbf{e}_V$, and $\mathbf{e}_V \star \mathbf{e}_V$ are packed into $\mathbf{x}$ (that is, $\mathbf{x}(i) = (\mathbf{y}_V(i) \parallel (c_i - b_i)\mathbf{e}_V(i) \parallel \mathbf{e}_V(i)^2)$) and the output $\mathbf{x}'$ is unpacked to produce the permuted vectors (see Algorithm 28).

4.4. **Wave Verification.** To verify Wave signatures, we follow the approach of [BDNS21].

<caption>**Algorithm 8 Verification for Wave signatures.**</caption>

Input: $\mathbf{m} \in \{0, 1\}^*$, $\sigma = (\text{salt}, \mathbf{s}) \in \{0, 1\}^{2\lambda} \times \mathbb{F}_3^k$, $\mathbf{M} \in \mathbb{F}_3^{k \times (n-k)}$
Output: True or False
1: $\mathbf{x} \leftarrow \text{Hash}(\mathbf{m} \parallel \text{salt})$
2: for $0 \le i < (k-1)/2$ do
3: &nbsp;&nbsp;&nbsp;&nbsp;▷ handle entries of $\mathbf{s}$ in pairs $(\hat{\mathbf{s}}(2i), \hat{\mathbf{s}}(2i+1)) \leftarrow (\mathbf{s}(2i) + \mathbf{s}(2i+1), \mathbf{s}(2i) - \mathbf{s}(2i+1)) \succ (2i, 2i+1)$-th entries of $\hat{\mathbf{s}}$
4: &nbsp;&nbsp;&nbsp;&nbsp;if $\hat{\mathbf{s}}(2i) = 1$ then
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x} \leftarrow \mathbf{x} + \text{row}(\mathbf{M}, 2i) $$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ add $2i$-th row of $\mathbf{M}$
6: &nbsp;&nbsp;&nbsp;&nbsp;if $\hat{\mathbf{s}}(2i) = 2$ then
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x} \leftarrow \mathbf{x} - \text{row}(\mathbf{M}, 2i) $$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ subtract $2i$-th row of $\mathbf{M}$
8: &nbsp;&nbsp;&nbsp;&nbsp;if $\hat{\mathbf{s}}(2i+1) = 1$ then
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x} \leftarrow \mathbf{x} + \text{row}(\mathbf{M}, 2i+1) $$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ add $(2i+1)$-th row of $\mathbf{M}$
10: &nbsp;&nbsp;&nbsp;&nbsp;if $\hat{\mathbf{s}}(2i+1) = 2$ then
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x} \leftarrow \mathbf{x} - \text{row}(\mathbf{M}, 2i+1) $$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ subtract $(2i+1)$-th row of $\mathbf{M}$
12: &nbsp;&nbsp;&nbsp;&nbsp;if $k$ is odd then
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{s}(k-1) = 1 $$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ handle last entry if necessary
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x} \leftarrow \mathbf{x} + \text{row}(\mathbf{M}, k-1) $$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if $\mathbf{s}(k-1) = 2$ then
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x} \leftarrow \mathbf{x} - \text{row}(\mathbf{M}, k-1) $$
17: &nbsp;&nbsp;&nbsp;&nbsp;return $|\mathbf{s}| + |\mathbf{x}| = w$

<figure><img src="image_16.png" /></figure>
**Proposition 4.** Given a putative Wave signature $(\mathbf{s}, \mathbf{salt})$ on a message $\mathbf{m}$ under a valid Wave public key $\mathbf{M}$, Algorithm 8 returns true if and only if

$$|\mathbf{s}| + |\text{Hash}(\mathbf{m} \parallel \mathbf{salt}) - \mathbf{s}\mathbf{R}^{\top}| = w$$

where $\mathbf{R}$ is such that $\mathbf{M} = \mathbf{M}(\mathbf{R})$ (as in Definition 3).

*Proof.* In the notation of Algorithm 8, let $\hat{\mathbf{s}}$ be defined by

$$\left. \begin{array}{l} \hat{\mathbf{s}}(2i) := \mathbf{s}(2i) + \mathbf{s}(2i + 1) \\ \hat{\mathbf{s}}(2i + 1) := \mathbf{s}(2i) - \mathbf{s}(2i + 1) \end{array} \right\} \text{for } 0 \le i < \frac{k-1}{2}$$

and let $\hat{\mathbf{s}}(k-1) := \mathbf{s}(k-1)$ if $k$ is odd. At the end of the execution of Algorithm 8, we have

$$\mathbf{x} = \text{Hash}(\mathbf{m} \parallel \mathbf{salt}) + \hat{\mathbf{s}}\mathbf{M}. \qquad (15)$$

Notice that

$$\mathbf{s}\mathbf{R}^{\top} = -\hat{\mathbf{s}}\mathbf{M}. \qquad (16)$$

because (from Definition 3)

$$\begin{aligned} \hat{\mathbf{s}}(2i) \cdot \text{row}(\mathbf{M}, 2i) + \hat{\mathbf{s}}(2i + 1) \cdot \text{row}(\mathbf{M}, 2i + 1) \\ = -(\mathbf{s}(2i) \cdot \text{col}(\mathbf{R}, 2i) + \mathbf{s}(2i + 1) \cdot \text{col}(\mathbf{R}, 2i + 1)) \end{aligned}$$

for $0 \le i < (k-1)/2$, and

$$\hat{\mathbf{s}}(k-1) \cdot \text{row}(\mathbf{M}, k-1) = -\mathbf{s}(k-1) \cdot \text{col}(\mathbf{R}, k-1)$$

if $k$ is odd. Combining Equations (15) and (16) and using Proposition 1 concludes the proof. □

Algorithm 8 implicitly uses Equation (16) to replace the standard Wave verification equation

$$|\mathbf{s}| + |\text{Hash}(\mathbf{m} \parallel \mathbf{salt}) - \mathbf{s}\mathbf{R}^{\top}| = w$$

with the equivalent equation

$$|\mathbf{s}| + |\text{Hash}(\mathbf{m} \parallel \mathbf{salt}) + \hat{\mathbf{s}}\mathbf{M}| = w.$$

The point of verifying with the product $\hat{\mathbf{s}}\mathbf{M}$ rather than $\mathbf{s}\mathbf{R}^{\top}$ is explained in [BDNS21]: since the vector $\mathbf{s}$ is supposed to have high weight, the vector $\hat{\mathbf{s}}$ has many zeroes, and so $\hat{\mathbf{s}}\mathbf{M}$ is easier to compute than $\mathbf{s}\mathbf{R}^{\top}$. The coefficients of the vector $\hat{\mathbf{s}}$ can easily be computed on the fly as the signature vector $\mathbf{s}$ is read (or decompressed).

Indeed, in any given Wave signature verification using Algorithm 8, roughly $|\mathbf{s}|/2$ of the $\hat{\mathbf{s}}(i)$ are zero, so almost half of the rows of the public key $\mathbf{M}$ are never read, let alone operated on. Given the size of Wave public keys, the latency involved in loading key data from memory is often a bottleneck in practice.

<figure><img src="image_17.png" /></figure>
## 5. PERFORMANCE ANALYSIS

Our performance analysis is based on the reference implementation, which is written in pure portable C99, and not optimized for any specific architecture; in particular, it does not take advantage of vectorization such as Intel AVX instructions (which were shown in [BDNS21] to significantly improve Wave implementation performance).

Table 6 provides signature and key sizes for each instance for easy reference. Note that the compressed encoding for signatures yields variable-length signatures, and we list the maximum sizes here (see Appendix ?? for further details).

<table><caption>TABLE 5. Key and signature sizes for Wave instances.</caption><thead><tr><td>Instance</td><td>Signature (B)</td><td>Private key (B)</td><td>Public key (B)</td></tr></thead><tbody><tr><td>Wave822</td><td>≤ 822</td><td>18 900</td><td>3 677 390</td></tr><tr><td>Wave1249</td><td>≤ 1 249</td><td>27 630</td><td>7 867 598</td></tr><tr><td>Wave1644</td><td>≤ 1 644</td><td>36 360</td><td>13 632 308</td></tr></tbody></table>

Table 5 presents cycle counts for our programs on an Intel i5-1135G7 platform. We provide two counts for signature verification. The first corresponds to the crypto_sign_open function from the NIST API, which must first decode the public key from its transport format (i.e., trits packed into a byte array, five trits to a byte, as in Appendix ??) to an array of bitsliced ternary vectors (as in Appendix B.1). This process is expensive—especially given the size of the public key—and much more expensive than the subsequent testing of the verification equation!

Given the size of the public key, Wave is probably best-suited to applications where the public key is stored on the device in advance of verification (rather than being transmitted with the message). In these cases, we have the option of converting from transport to format at the time of storage, rather than re-converting for each verification. The second Verification column in Table 5 corresponds to this scenario: the bitsliced public key is already loaded, and the cycle count corresponds to pure verification using the verify function. While the bitsliced representation imposes a space overhead of 25%, the massive speedup of over two full orders of magnitude may more than justify this approach.

<figure><img src="image_18.png" /></figure>
<table><caption>TABLE 6. Cycle counts for the Wave reference implementation. Programs were executed on an Intel i5-1135G7 with CPU frequency 2.4 GHz and maximum CPU frequency 4.2 GHz running Arch Linux (kernel 6.3.1). We compiled the code using GCC version 13.1.1 with compiler options `-O3` and `-march=native`. Each program was run 100 times with random inputs (using random 100-byte messages). Cycles were counted using the `rdtsc` instruction included in the file `cpucycles.h`.</caption><thead><tr><th>Instance</th><th></th><th>Key generation</th><th>Signing</th><th>Verification (transport PK)</th><th>Verification (bitsliced PK)</th></tr></thead><tbody><tr><td rowspan="4">Wave822</td><td>Average</td><td>14 468 000 043</td><td>1 160 793 621</td><td>205 829 565</td><td>1 230 598</td></tr><tr><td>Median</td><td>13 946 196 718</td><td>1 156 182 078</td><td>206 097 247</td><td>1 197 396</td></tr><tr><td>Lowest</td><td>13 672 518 457</td><td>1 094 264 195</td><td>191 450 426</td><td>1 037 092</td></tr><tr><td>Highest</td><td>18 921 643 347</td><td>1 367 744 577</td><td>236 350 926</td><td>1 975 376</td></tr><tr><td rowspan="4">Wave1249</td><td>Average</td><td>47 222 134 806</td><td>3 507 016 206</td><td>464 110 855</td><td>2 580 092</td></tr><tr><td>Median</td><td>46 285 891 873</td><td>3 534 752 493</td><td>467 362 945</td><td>2 580 640</td></tr><tr><td>Lowest</td><td>44 658 551 430</td><td>3 233 442 565</td><td>420 729 318</td><td>2 390 594</td></tr><tr><td>Highest</td><td>55 561 328 781</td><td>3 695 446 731</td><td>491 116 604</td><td>2 913 327</td></tr><tr><td rowspan="4">Wave1644</td><td>Average</td><td>108 642 333 507</td><td>7 936 541 947</td><td>813 301 900</td><td>4 328 892</td></tr><tr><td>Median</td><td>106 259 626 687</td><td>7 851 475 371</td><td>806 856 892</td><td>4 325 131</td></tr><tr><td>Lowest</td><td>104 525 692 173</td><td>7 608 672 796</td><td>782 171 263</td><td>4 054 341</td></tr><tr><td>Highest</td><td>117 900 860 252</td><td>8 225 419 171</td><td>817 790 558</td><td>4 611 381</td></tr></tbody></table>

<table><caption>TABLE 7. Hyperlinks to KATs with SHA2-256 checksums.</caption><thead><tr><th>Instance</th><th>Hyperlink</th><th>sha256sum</th></tr></thead><tbody><tr><td>Wave822</td><td>PQCsignKAT_18900</td><td>ace94f3e8e1f692632758decb5471e7408bb7669f4d3a59647046e20bb0404b5</td></tr><tr><td>Wave1249</td><td>PQCsignKAT_27629</td><td>75e85be5bdcf30fcbdc898ee7d84a2475cf917af06c1349eb9ded34605798e17</td></tr><tr><td>Wave1644</td><td>PQCsignKAT_36359</td><td>e67a83c9abdf143b4ab01ff5f2692d54534a3de1c3943165d907f077cee07356</td></tr></tbody></table>

## 6. KNOWN ANSWER TESTS

Wave may be implemented in many different ways, but it is crucial to respect the constraints imposed by the chosen parameters. Further, when utilizing a pseudorandom generator, it is important to ensure the reproducibility of the results.

In order to achieve this reproducibility, we provide Known Answer Test (KAT) values for each instance of Wave on our website. Table 7 provides hyperlinks to the KATs, with SHA2-256 checksums of each KAT file (which may be recomputed with `sha256sum`) to ensure integrity.

<figure><img src="image_19.png" /></figure>
## 7. PROVABLE SECURITY

We now present a security argument for Wave against classical and quantum adversaries. We consider the standard EUF-CMA definition for signature schemes, where adversaries with access to a signing oracle must forge a signature on a new (non-queried) message. Since we are designing a post-quantum signature scheme, we will work in the Quantum Random Oracle Model (QROM), where the main hash function Hash used in our signature scheme is modelled as a truly random function with black-box access only; quantum adversaries have quantum access to this black box.

For quantum adversaries, $\lambda$ bits of security corresponds to a quantum adversary running in time $2^{\lambda}$. As per NIST guidelines, adversaries are restricted to $q_S = 2^{64}$ classical signing queries, no matter the intended security level.

**7.1. Hard problems.** We begin by defining the problems to which we will reduce the EUF-CMA security of Wave. First, recall the classic decoding problem DP over $\mathbb{F}_3$:

**Problem 1.** The Decoding Problem DP$(n, k, w)$ is:

* Input: $(\mathbf{H}, \mathbf{s})$ where $\mathbf{H}$ resp. $\mathbf{s}$ are uniformly distributed over $\mathbb{F}_3^{(n-k)\times n}$ resp. $\mathbb{F}_3^{n-k}$.

* Output: a vector $\mathbf{e}$ in $\mathbb{F}_3^n$ of Hamming weight $w$ such that $\mathbf{e}\mathbf{H}^\top = \mathbf{s}$.

Forging a Wave signature on a given message resembles solving a DP instance where $\mathbf{H}$ and $\mathbf{s}$ represent the public key and the hash of that message, respectively. However, our adversary's goal is to forge a signature on a freely chosen message, so it is more appropriate to consider a multi-target variant of DP.

**Problem 2.** The Decoding One Out of Many Problem DOOM$(n, k, w, N)$ is:

* Input: $(\mathbf{H}, \mathbf{s}_1, \dots, \mathbf{s}_N)$ where $\mathbf{H}$ resp. the $\mathbf{s}_i$ are uniformly distributed over $\mathbb{F}_3^{(n-k)\times n}$ resp. $\mathbb{F}_3^{n-k}$.

* Output: a vector $\mathbf{e} \in \mathbb{F}_3^n$ of Hamming weight $w$, and $i \in [1, N]$ such that $\mathbf{e}\mathbf{H}^\top = \mathbf{s}_i$.

Forging Wave signatures does not directly imply solving DP or DOOM, because Wave public keys are parity-check matrices not of truly random codes<fnref n="3" />, but of permuted generalized $(U|U+V)$-codes (see Definition 1). However, if Wave public keys are indistinguishable from random parity-check matrices, then security reduces to DOOM. (This is similar to McEliece-like cryptosystems [?, ?], where security reduces to the decoding problem provided distinguishing Goppa codes from random is sufficiently hard.)

**Problem 3** (The Distinguishing Wave Keys Problem DWK$(n, k_U, k_V)$). Given $\mathbf{H} \in \mathbb{F}_3^{(n-(k_U+k_V))\times n}$, decide whether $\mathbf{H}$ has been chosen uniformly at random or among parity-check matrices of permuted generalized $(U|U+V)$-codes where $U$ resp. $V$ has dimension $k_U$ resp. $k_V$.

**7.2. Signature Distribution and Rényi Divergence.** Wave security reduces to the hardness of Problems 2 and 3. We use the Rényi divergence to achieve a tight reduction, as in [?, ?, ?] for LWE and lattice-based cryptosystems. Recall that if $\mathcal{P}$ and $\mathcal{Q}$ are distributions with $\text{Supp}(\mathcal{P}) \subseteq \text{Supp}(\mathcal{Q})$, then their Rényi divergence of order $\alpha$ (where $\alpha > 0$ and $\alpha \neq 1$) is

$$R_{\alpha}(\mathcal{P} || \mathcal{Q}) := \left( \sum_{x \in \text{Supp}(\mathcal{P})} \frac{\mathcal{P}(x)^{\alpha}}{\mathcal{Q}(x)^{\alpha-1}} \right)^{1/(\alpha-1)}.$$

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

<footnote n="3">³A code is *random* if its parity-check matrix is uniformly drawn at random.</footnote>
Wave signing uses internal distributions $D_V$ and $D_U$ to ensure signatures are properly distributed. Algorithm 5 constructs vectors $\mathbf{e}_V$ (using Algorithm 6, governed by $D_V$) and $\mathbf{e}_U$ (using Algorithm 7, governed by $D_U$), and then defines $\mathbf{e}_L := \mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$ and $\mathbf{e}_R := \mathbf{c} \star \mathbf{e}_U + (\mathbf{1} + \mathbf{b} \star \mathbf{c}) \star \mathbf{e}_V$. As shown in [DST19, §5.1], for Algorithm 5 to return signatures distributed as random words of Hamming weight $w$, it suffices that the distributions $Q$ and $Q^{\text{ideal}}$ match, where

* $Q$ is the distribution of $|\mathbf{e}_V|$ and $n/2 - w + |\mathbf{e}_L \star \mathbf{e}_R|$ in Algorithm 5 given $D_U$ and $D_V$; and

* $Q^{\text{ideal}}$ is the distribution of $|\mathbf{e}_L - \mathbf{c} \star \mathbf{e}_R|$ and $n/2 - w + |\mathbf{e}_L \star \mathbf{e}_R|$ on random words $(\mathbf{e}_L \parallel \mathbf{e}_R)$ of Hamming weight $w$.

Cutting $Q$ to some interval $\text{Accept} \subseteq [0, n/2] \times [0, w/2]$ (as in Instruction 11 of Algorithm 5) to ensure that its support is included the support of $Q^{\text{ideal}}$, we obtain

$$R_{2\lambda}(Q||Q^{\text{ideal}}) = 1 + \varepsilon_{\text{Renyi}}. \qquad (17)$$

The internal distributions $D_V$ and $D_U$ must therefore be chosen to ensure that $\varepsilon_{\text{Renyi}}$ is sufficiently small. In our reference implementation, the $D_V$ and $D_U$ included in Wave822, Wave1249, and Wave1644 all give

$$\varepsilon_{\text{Renyi}} \le 2^{-68}.$$

### 7.3. Statement of the security reduction.

**Theorem 1.** Fix any $\lambda \in \mathbb{N}$, and consider a quantum adversary $\mathcal{A}$ running in time $2^\lambda$ limited to $q_S = 2^{64}$ classical signing queries that tries to break the EUF-CMA security of an instance of Wave. In the QROM, we have

$$\text{Adv}_{\text{Wave}}^{\text{EUF-CMA}}(\mathcal{A}) \le \sqrt{2}(1 - \varepsilon_{\text{Renyi}})^{qs} \left( \text{Adv}^{\text{DOOM}}(2^\lambda) + \text{Adv}^{\text{DWK}}(2^\lambda) + \frac{q_S^2}{2^{\lambda_0}} \right)$$

where

* $\text{Adv}_{\text{Wave}}^{\text{EUF-CMA}}(\mathcal{A})$ is the probability that $\mathcal{A}$ breaks the EUF-CMA security of Wave;

* $\varepsilon_{\text{Renyi}}$ is defined in Equation (17);

* $\text{Adv}^{\text{DOOM}}(2^\lambda)$ is the maximum probability that a quantum algorithm running in time $2^\lambda$ solves DOOM (Problem 2) for the Wave parameters $n, k$, and $w$ (the parameter $N$ is not restricted, and in the quantum setting we even allow adversaries quantum access to the syndromes: that is, adversaries can efficiently compute the unitary $|i\rangle|0\rangle \to |i\rangle|s_i\rangle$);

* $\text{Adv}^{\text{DWK}}(2^\lambda)$ is $|p - \frac{1}{2}|$, where $p$ is the maximum probability that a quantum algorithm running in time $2^\lambda$ solves DWK (Problem 3) for the Wave parameters;

* $\lambda_0$ is the size of the salt. In our case, we always have $\lambda_0 \ge 256$ hence $\frac{q_S^2}{2^{\lambda_0}} \le 2^{-128}$.

The above also holds for classical adversaries in the Random Oracle Model (if the best considered attacks against Problems 2 and 3 are also classical).

Theorem ?? is proven by combining two existing results (which hold both in the ROM against classical adversaries and the QROM against quantum adversaries):

(1) The results of [?] show that if Wave produces an ideal distribution of signatures (i.e., $Q$ matches $Q^{\text{ideal}}$) then it reduces tightly to Problems 2 and 3.

(2) Then, the results of [?, Section 3.3 of the Eprint version] show that moving from an ideal signing distribution to a real distribution (i.e., replacing $Q^{\text{ideal}}$ with $Q$) induces a multiplicative loss of $\sqrt{2}(1 - \varepsilon_{\text{Renyi}})^{qs}$ in the EUF-CMA advantage.

<figure><img src="image_21.png" /></figure>
The internal distributions in Wave822, Wave1249, and Wave1644 all have $\epsilon_{Renyi} \le 2^{-68}$, so $(1 + \epsilon_{Renyi})^{qs} \le \sqrt{2}$. Plugging this into Theorem ?? yields

$$ \mathrm{Adv}_{\mathrm{Wave}}^{\mathrm{EUF-CMA}}(\mathcal{A}) \le 2 \left( \mathrm{Adv}^{\mathrm{DOOM}}(2^{\lambda}) + \mathrm{Adv}^{\mathrm{DWK}}(2^{\lambda}) + \frac{q_S^2}{2^{\lambda_0}} \right) $$

for all three instances, so their security tightly reduces to Problems 2 and 3. We discuss the best known attacks on these problems in §8.

## 8. BEST KNOWN ATTACKS

We now present the best known attacks on DOOM (which we call message attacks) and DWK (which we call key attacks). Both classes of attacks rely on algorithms to solve DP. While this classic problem has been widely studied [?, Ste89, Dum91, FS09, Ber10, ?, MMT11, BJMM12, ?, ?, KT17, BM18, Kir18, ?, CDMT22], much less has been done for DP with the code parameters used in Wave (for instance, working over $\mathbb{F}_3$ instead of $\mathbb{F}_2$) [BCDL19, Bri21, CDE21, ?, Sen23].

### 8.1. Classical attacks.
The best known attacks on DP and DOOM use the Information Set Decoding (ISD) framework of [FS09], which is a refinement of Prange's algorithm [?]. The idea is to find a single solution to DP in $\mathbb{F}_3^n$ with weight $w$ by identifying exponentially many solutions to a simplified DP instance in $\mathbb{F}_3^\ell$ with weight $p$, for chosen $\ell \le n$ and $p \le w$. For each potential solution, we can efficiently verify if it yields a complete solution to DP. This entire process is repeated until a solution is discovered. Several algorithms exist for listing solutions to this sub-problem: [Ste89] and [Dum91] take advantage of the birthday paradox while [MMT11] and [BJMM12] combine the so-called representation technique with merging techniques.

In the binary case ($q = 2$), the best known ISD ([BM18] with the correction in [CDMT22, Appendix B]) lists solutions to the sub-problem by searching for pairs of near-neighbours in some lists. Near-neighbours-based decoders designed for the ternary setting may have better asymptotic complexities than the ISD techniques mentioned above. However, an efficient near-neighbours search algorithm requires fuzzy hashing functions that associate close vectors. One of the best known ways to design a good fuzzy hashing function is to use a list decoder of a polar code, resulting in an $O(n \log(n))$ overhead (compared to other ISDs) that we take into account when setting parameters.

#### 8.1.1. Classical message attacks.
The ISD framework with Wagner's algorithm [BCDL19] is the best known algorithm to find solutions for the sub-DP instance in the Wave context ($w/n \approx 0.89$ and $k/n = 1/2$). This involves creating lists of vectors corresponding to $\mathbf{e}'' \in \mathbb{F}_3^{k+\ell}$ with $|\mathbf{e}''| = p$. In the DOOM solver of [Sen11], one of the lists is filled with some restrictions $\mathbf{s}_i''$s of the $\mathbf{s}_i$ over their last $k+\ell$ coordinates. The lists are then filtered to include only $\mathbf{e}''$ for which $\mathbf{e}''\mathbf{H}''^\top = \mathbf{s}_i''$ for some $i$ (the sub-problem), where $\mathbf{H}'' \in \mathbb{F}_3^{(n-k) \times (k+\ell)}$ is some sub-matrix of $\mathbf{H}$. The lists are merged using a binary merging tree, keeping only the pairs of vectors whose first coordinates sum to zero. Ultimately, we obtain a list of vectors from which we can deduce multiple solutions to the DP sub-instance, and thus to the full DP instance. Otherwise, the process is repeated until a solution is found.

#### 8.1.2. Classical key attacks.
One way to solve DWK, i.e. to distinguish the public key $\mathbf{H}$ (a parity-check matrix of some permuted generalized $(U|U+V)$-code) from a randomly uniform matrix in $\mathbb{F}_3^{(n-k) \times n}$ is to exhibit a codeword of form $(\mathbf{u}, \mathbf{u})$ of weight $t$, where $t$ is a parameter that can be chosen. Indeed, these words may be more likely to appear in

<figure><img src="image_22.png" /></figure>
a ($U|U+V$)-code than in a random code [Sen23]. The best known classical attack uses ISD to find such vectors satisfying $eH^\top = 0$. Within this range of parameters, Wagner's algorithm [SS81] does not perform better than just having two merging steps and using the representation technique of [MMT11]. This attack computes multiple solutions to the DP sub-instance, and then checks if one of the candidate solutions satisfies the general DP.

## 8.2. Quantum attacks.
Code-based problems, and more specifically decoding problems, have resisted quantum attacks very well so far. The best known quantum attacks on these various decoding problems are also based on ISD. Many quantum algorithms have been studied; for simpler examples such as Prange's algorithm, a direct application of quantum amplitude amplification gives a quadratic advantage [Ber10], but we cannot get the same improvement for advanced ISD algorithms which list many solutions to a sub-problem. This has been extensively studied for a binary alphabet in [KT17], and extended in [Kir18, ?]. Quantum algorithms for DP and DOOM have also been studied in the ternary setting of Wave [CDE21, Bri21].

### 8.2.1. Quantum message attacks.
We employ the quantum ISD framework, where the sub-problem solver utilizes the quantum Wagner algorithm [CDE21]. In this quantum setting, the list of $s_i$ is replaced by their quantum superposition, and the number of such elements can exceed the number in the classical setting. The classical lists are merged, and the merging of a classical list with the list in quantum superposition is accomplished using Grover's algorithm [Gro96] to yield a quantum superposition of candidate solutions. If the probability of success is lower than $1-o(1)$, we apply amplitude amplification before the measurement to obtain a DP solution. We rely on the analysis of [CDE21] as well as the DOOM analysis of [Bri21], which provides the best quantum algorithm in this scenario.

### 8.2.2. Quantum key attacks.
To find a codeword ($u, \bar{u}$) of weight $t$, the best known attack also uses quantum ISD, finding the solutions to the sub-problem using quantum Wagner [CDE21]. As above, amplitude amplification can be applied to get a DP solution with high probability. Again, we combine the analyses of [CDE21] and (the classical) [Sen23] to study the best quantum algorithms here.

## 8.3. Claimed security levels.
Table 8 lists the claimed security levels $\lambda$ for Wave822, Wave1249, and Wave1644 against the attacks listed above. All our best classical and quantum attacks require $\text{poly}(n)2^{\alpha n+o(n)}$ elementary operations for some $\alpha$, where $n$ is the code length. We ignore the $\text{poly}(n)$ factor and the $o(n)$ when estimating our security levels. Omitting these large overheads make our parameters very conservative.

We also ignore the cost of memory access, even though these algorithms can use a very large amount of memory: for example, the DOOM attack above requires space equal to its running time. In the quantum setting, these overheads are increased by the fact that the best known quantum attacks use a large amount of QRAM (Quantum Random Access Memory), whose feasibility is still in question [JR23]. This makes our security levels even more conservative in the quantum setting.

<figure><img src="image_23.png" /></figure>
<table><caption>TABLE 8. Claimed security levels for Wave instances. In this context, $\lambda$ bits of security indicate that the most efficient known attacks on DOOM and key distinguishing all require a minimum time of $2^{\lambda}$ to execute.</caption><thead><tr><th></th><th>NIST<br>Post-Quantum</th><th>Classical<br>(bits)</th><th>Quantum<br>(bits)</th></tr></thead><tbody><tr><td>Wave822</td><td>Level I</td><td>128</td><td>77</td></tr><tr><td>Wave1249</td><td>Level III</td><td>192</td><td>117</td></tr><tr><td>Wave1644</td><td>Level V</td><td>256</td><td>157</td></tr></tbody></table>

# 9. ADVANTAGES AND LIMITATIONS

## 9.1. Advantages.

* **Short signature length:** at most 822 bytes for NIST Level I, and scaling linearly with the security parameter.

* **Fast verification**, with scope for further significant speed-ups in dedicated implementations (as in [BDNS21]).

* **Proven secure** under well identified code-based hardness assumptions, in the ROM and the QROM with tight reductions.

* The scheme is **immune to statistical attacks** by design, and the reference implementation is immune to statistical attacks from any adversary limited to $2^{64}$ queries to a signing oracle.

## 9.2. Limitations.

* Large public keys: 3.6MB for NIST Level I, and scaling quadratically with the security parameter.

* Signing and key generation rely on inherently slow Gaussian elimination on large matrices. Accelerating these primitives while ensuring implementation safety is a significant challenge.

* We assume the hardness of DWK, distinguishing permuted generalized $(U|U+V)$-codes from random codes. This assumption is fairly new (it was introduced in 2018) but we have reasons to argue for its hardness: for example, these permuted generalized $(U|U+V)$-codes have a lot of inner entropy. The only exploitable structure seems to be the existence of small codewords, which we already fully exploit in our security analysis. We believe our parameters are extremely conservative with respect to these codes, providing a comfortable security margin against possible attacks on a relatively new problem, but further analysis may show that we can reduce parameter sizes, thus improving key sizes and performance.

* The parameters include the internal discrete distributions $D_V$ and $D_U(t)$, which condition the decoder output distribution (which must be close to uniform to guarantee security: see §7), Adding rejection sampling if necessary. The internal distributions in our implementation were computed by an ad-hoc procedure (taking a few hours). They produce an output distribution which is close enough to uniform, with a Rényi divergence $\le 1 + 2^{-68}$, without rejection sampling. At the moment,

<figure><img src="image_24.png" /></figure>
the internal distributions are given as tables of numbers. Tools will be provided to guarantee their correctness.

REFERENCES

[BCDL19] Rémi Bricout, André Chailloux, Thomas Debris-Alazard, and Matthieu Lequesne. Ternary syndrome decoding with large weights. In Kenneth G. Paterson and Douglas Stebila, editors, Selected Areas in Cryptography - SAC 2019 - 26th International Conference, Waterloo, ON, Canada, August 12-16, 2019, Revised Selected Papers, volume 11959 of Lecture Notes in Computer Science, pages 437-466. Springer, 2019.

[BDNS21] Gustavo Banegas, Thomas Debris-Alazard, Milena Nedeljković, and Benjamin Smith. Wavelet: Code-based postquantum signatures with fast verification on microcontrollers. Cryptology ePrint Archive, Report 2021/1432, 2021. https://ia.cr/2021/1432.

[Ber] Daniel J. Bernstein. djbsort. Software library for sorting arrays of integers or floating-point numbers. https://sorting.cr.yp.to/.

[Ber10] Daniel J. Bernstein. Grover vs. mceliece. PQCrypto, pages 73-80, 2010.

[BJMM12] Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer. Decoding random binary linear codes in $2^{n/20}$: How $1+1=0$ improves information set decoding. In Advances in Cryptology - EUROCRYPT 2012, LNCS. Springer, 2012.

[BM18] Leif Both and Alexander May. Decoding linear codes with high error rate and its impact for LPN security. In Tanja Lange and Rainer Steinwandt, editors, Post-Quantum Cryptography 2018, volume 10786 of LNCS, pages 25-46, Fort Lauderdale, FL, USA, April 2018. Springer.

[Bri21] Rémi Bricout. Comment utiliser des algorithmes quantiques pour remplir son sac à dos et décodeur des syndromes. Theses, Sorbonne Université, March 2021.

[CDE21] André Chailloux, Thomas Debris-Alazard, and Simona Etinski. Classical and quantum algorithms for generic syndrome decoding problems and applications to the lee metric. In Jung Hee Cheon and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20-22, 2021, Proceedings, volume 12841 of Lecture Notes in Computer Science, pages 44-62. Springer, 2021.

[CDMT22] Kevin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, and Jean-Pierre Tillich. Statistical decoding 2.0: Reducing decoding to LPN. In Advances in Cryptology - ASIACRYPT 2022, LNCS. Springer, 2022.

[DST17] T. Debris-Alazard, N. Sendrier, and J.-P. Tillich. The problem with the surf scheme. preprint, November 2017. arXiv:1706.08065.

[DST19] Thomas Debris-Alazard, Nicolas Sendrier, and Jean-Pierre Tillich. Wave: A new family of trapdoor one-way preimage sampleable functions based on codes. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 21-51, Kobe, Japan, December 2019. Springer.

[Dum91] I Dumer. On minimum distance decoding of linear codes. Proc. 5th JointSoviet-Swedish Int. Workshop Inform. Theory, Moscow, page 50-52, 1991.

[FHK$^{+}$17] Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. First round submission to the NIST post-quantum cryptography call, November 2017.

[FS09] Matthieu Finiasz and Nicolas Sendrier. Security bounds for the design of code-based cryptosystems. In M. Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, volume 5912 of LNCS, pages 88-105. Springer, 2009.

[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 197-206. ACM, 2008.

[Gro96] Lov Grover. A fast quantum mechanical algorithm for database search. Proc. 28th Annual ACM Symposium on the Theory of Computing STOC, pages 212-219, 1996.

[JR23] Samuel Jaques and Arthur G. Rattew. Qram: A survey and critique. preprint, 2023.

[Kir18] Elena Kirshanova. Improved quantum information set decoding. PQCrypto, 2018.

[KT17] Ghazal Kachigar and Jean-Pierre Tillich. Quantum information set decoding algorithms. preprint, arXiv:1703.00263 [cs.CR], February 2017.

<figure><img src="image_25.png" /></figure>
[Lem19] Daniel Lemire. Fast random integer generation in an interval. *ACM Trans. Model. Comput. Simul.*, 29(1):3:1–3:12, 2019.

[MMT11] Alexander May, Alexander Meurer, and Enrico Thomae. Decoding random linear codes in $O(2^{0.054n})$. In Dong Hoon Lee and Xiaoyun Wang, editors, *Advances in Cryptology - ASIACRYPT 2011*, volume 7073 of LNCS, pages 107–124. Springer, 2011.

[Pra62] Eugene Prange. The use of information sets in decoding cyclic codes. *IEEE*, 1962.

[Sen11] Nicolas Sendrier. Decoding one out of many. *PQCrypto*, 2011.

[Sen23] Nicolas Sendrier. Wave parameter selection. *preprint*, 2023.

[SS81] Richard Schroeppel and Adi Shamir. A $T = O(2^{n/2})$, $S = O(2^{n/4})$ algorithm for certain NP-complete problems. *SIAM J. Comput.*, 10(3):456–464, 1981.

[Ste89] J Stern. A method for finding codewords of small weight. *Coding theory and applications*, 388:106–113, 1989.

[WSN18] Wen Wang, Jakub Szefer, and Ruben Niederhagen. FPGA-based Niederreiter cryptosystem using binary Goppa codes. In Tanja Lange and Rainer Steinwandt, editors, *PQCrypto*, volume 10786 of LNCS, pages 77–98. Springer, 2018.

<figure><img src="image_26.png" /></figure>
APPENDIX A. HASHING TO TERNARY VECTORS

In order to sign any messages with Wave, we need to define a hash function into $\mathbb{F}_3^{n-k}$.
We use the hash function as defined in [BDNS21, §3.1]. We recall here its specifications.

The Hash (Algorithm 9) defines a cryptographic hash function $\{0, 1\}^* \to \mathbb{F}_3^{n-k}$ by wrap-
ping the standard SHA3-512 hash function with the following two functions:

(1) **Ternarize**: $\{0, 1\}^* \times \mathbb{Z}_{\ge 0} \to \mathbb{F}_3^*$ (Algorithm 10) views its input $((x_0, x_1, \dots), \tau)$ as the vector of coefficients in the little-endian binary expansion of an integer $x$, together with a length $\tau$, and returns the ternary vector of length $\tau$ representing the little-endian ternary expansion of $x \bmod 3^\tau$,

(2) **Expand**: $\{0, 1\}^{2\lambda} \to \mathbb{F}_3^\tau$ (Algorithm 11) is a pseudorandom function ($\lambda$ denotes the security parameter). Expand applies SHAKE256 to its input to produce a long stream of pseudorandom bytes, which we view as integers in $[0, 256)$. The non-negative integers less than $3^5 = 243$ are in bijection with $\mathbb{F}_3^5$, so if a byte is less than 243 we convert it to an element of $\mathbb{F}_3^5$ with Ternarize and concatenate it to the output; otherwise we skip the byte. We continue processing bytes until we have produced $\tau$ elements of $\mathbb{F}_3$ (discarding the last few trits if $\tau$ is not a multiple of 5).

The collision- and preimage-resistance of Hash are derived from the properties of SHA3-512 using standard (conatenation) hash combiner arguments (see e.g. [?, §4] and [?]). Ternarize simply transcodes its input, so the composition of Ternarize and SHA3-512 preserves the security properties of SHA3-512. The composition of Expand and SHA3-512 has weaker preimage and collision resistance (because bytes in $[243, 256)$ are discarded), but it still has strong pseudorandomness properties, and it is relatively fast to compute. The concatenation of the two has the security of the strong hash, and the good pseudorandomness of both.

<table><caption>**Algorithm 9 Hashing from $\{0, 1\}^*$ to $\mathbb{F}_3^{n-k}$ in Wave.**</caption><tr><td>1:</td><td><b>function Hash(m)</b></td><td>▷ <b>m</b> &isin; {0, 1}<sup>*</sup></td></tr><tr><td>2:</td><td><i>h</i> &larr; Truncate(SHA3-512(<b>m</b>), 2&lambda;)</td><td>▷ Truncate SHA3-512 output to first 2&lambda; bits</td></tr><tr><td>3:</td><td><b>t</b> &larr; Ternarize (<i>h</i>, &lfloor;2&lambda;/log<sub>2</sub>(3)&rfloor;)</td><td>▷ Algorithm 10</td></tr><tr><td>4:</td><td><b>p</b> &larr; Expand (<i>h</i>, <i>n</i> &minus; <i>k</i> &minus; &lfloor;2&lambda;/log<sub>2</sub>(3)&rfloor;)</td><td>▷ Algorithm 11</td></tr><tr><td>5:</td><td><b>return</b> (<b>t</b>, <b>p</b>)</td><td></td></tr></table>

<table><caption>**Algorithm 10 Converting integer values to ternary vectors of a specified length, corresponding to the little-endian ternary expansion of the input.**</caption><tr><td>1:</td><td><b>function</b> Ternarize(<i>x</i>, <i>&tau;</i>)</td><td>▷ <i>x</i> &ge; 0 and <i>&tau;</i> &gt; 0</td></tr><tr><td>2:</td><td><b>v</b> &larr; 0 &isin; F<sub>3</sub><sup><i>&tau;</i></sup></td><td></td></tr><tr><td>3:</td><td><b>for</b> 0 &le; <i>i</i> &lt; <i>&tau;</i> <b>do</b></td><td></td></tr><tr><td>4:</td><td>(<i>x</i>, <b>v</b>(<i>i</i>)) &larr; (&lfloor;<i>x</i>/3&rfloor;, <i>x</i> mod 3)</td><td></td></tr><tr><td>5:</td><td><b>return</b> <b>v</b></td><td>▷ <b>v</b> &isin; F<sub>3</sub><sup><i>&tau;</i></sup> &cong; {0, 1, 2}<sup><i>&tau;</i></sup> such that <i>x</i> = &sum;<sub><i>i</i>=1</sub><sup><i>&tau;</i></sup> <b>v</b>(<i>i</i>)3<sup><i>i</i>-1</sup></td></tr></table>

<figure><img src="image_27.png" /></figure>
**Algorithm 11** Expand a binary seed to a pseudo-random stream of ternary values. The random bytestream may be instantiated with an XOF or a stream cipher. The expected number of bytes drawn from the stream is $(256\tau)/(243 \times 5) \approx 0.21\tau$.

1: **function Expand(h, τ)** ▷ $h \in \{0, 1\}^{2\lambda}$ and $\tau > 0$

2: **stream** = pseudorandom bytestream obtained via SHAKE256($h$)

3: $(\mathbf{p}, r) \leftarrow ((), \tau)$ ▷ **p**: empty vector over $\mathbb{F}_3$

4: **while** $r > 0$ **do**

5: $b \leftarrow$ next byte from **stream**, viewed as an integer in $[0, 255]$

6: **if** $b < 243$ **then**

7: $(\mathbf{p}, r) \leftarrow (\mathbf{p}, \text{Ternarize}(b, \min(5, r)), r)$ ▷ Algorithm 10

8: **return** **p** ▷ $\mathbf{p} \in \mathbb{F}_3^\tau$

## APPENDIX B. SPECIFICATION TOWARD A CONSTANT TIME IMPLEMENTATION

### B.1. Bitsliced Arithmetic over $\mathbb{F}_3$
The reference implementation uses the following bitsliced $\mathbb{F}_3$-vector arithmetic. An element $a$ of $\mathbb{F}_3$ is represented as a pair of bits $(a_h, a_\ell)$:

$$0 \leftrightarrow (0, 0), \quad 1 \leftrightarrow (0, 1), \quad 2 \leftrightarrow (1, 1).$$

All the arithmetic can be expressed with binary operations, addition, multiplication, and inclusive or denoted `|`. Addition and subtraction in $\mathbb{F}_3$ requires 7 binary operations, negation in $\mathbb{F}_3$ requires 1 binary operation, and multiplication in $\mathbb{F}_3$ requires 3 binary operations.

$$c = a + b \iff \left\{ \begin{array}{l} c_h = (a_\ell + b_h)(a_h + b_\ell) \\ c_\ell = (a_\ell + b_\ell) | (a_h + b_\ell + b_h) \end{array} \right.$$

$$c = a - b \iff \left\{ \begin{array}{l} c_h = (a_\ell + b_\ell + b_h)(a_h + b_\ell) \\ c_\ell = (a_\ell + b_\ell) | (a_h + b_h) \end{array} \right.$$

$$c = -a \iff \left\{ \begin{array}{l} c_h = a_h + a_\ell \\ c_\ell = a_\ell \end{array} \right.$$

$$c = a \times b \iff \left\{ \begin{array}{l} c_h = (a_h + b_h)a_\ell b_\ell \\ c_\ell = a_\ell b_\ell \end{array} \right.$$

This representation and the corresponding arithmetic fits well with bit slicing techniques and the above operations apply conveniently to vectors. A ternary vector $\mathbf{x} = (x_i)_{0 \le i < n}$ where $x_i \leftrightarrow (x_{i,h}, x_{i,\ell})$ is represented by $(\mathbf{x}_h, \mathbf{x}_\ell)$ with $\mathbf{x}_h = (x_{i,h})_{0 \le i < n}$ and $\mathbf{x}_\ell = (x_{i,\ell})_{0 \le i < n}$.

<figure><img src="image_28.png" /></figure>
The vector operations can be computed for logical operations & and ⊕ on binary words:

$$c = a + b \iff \left\{ \begin{array}{l} c_h = (a_\ell \oplus b_h) \& (a_h \oplus b_\ell) \\ c_\ell = (a_\ell \oplus b_\ell) | (a_h \oplus b_\ell \oplus b_h) \end{array} \right.$$

$$c = a - b \iff \left\{ \begin{array}{l} c_h = (a_\ell \oplus b_\ell \oplus b_h) \& (a_h \oplus b_\ell) \\ c_\ell = (a_\ell \oplus b_\ell) | (a_h \oplus b_h) \end{array} \right.$$

$$c = -a \iff \left\{ \begin{array}{l} c_h = a_h \oplus a_\ell \\ c_\ell = a_\ell \end{array} \right.$$

$$c = a \star b \iff \left\{ \begin{array}{l} c_h = (a_h \oplus b_h) \& a_\ell \& b_\ell \\ c_\ell = a_\ell \& b_\ell \end{array} \right.$$

**B.2. Sampling Trits.** The purpose is to efficiently produce—close to—independent and uniform trits from independent and uniform bits. The description assumes a binary pseudorandom generator prng initialized with seed, e.g. any XOF with input seed. The instruction `randbits(a, prng)` draws the next a bits of prng and returns the corresponding integer in $[0, 2^a)$. It can be used in Algorithm 12 to produce a pseudorandom ternary vector of length n from seed. This algorithm admits as parameters the integers a and b, it will

<table><caption>**Algorithm 12** Pseudorandom Sampling of Ternary Vectors</caption><tr><td><pre><code>function prng<sub>3</sub>(n, seed)</code></pre><pre><code>prng ← prng_init(seed)</code></pre><pre><code>i ← 0</code></pre><pre><code>repeat</code></pre><pre><code>x<sub>i</sub>, ..., x<sub>i+b-1</sub> ← randtrits(a, b, prng)</code></pre><pre><code>i ← i + b</code></pre><pre><code>until i ≥ n</code></pre><pre><code>return x<sub>0</sub>, ..., x<sub>b-1</sub></code></pre></td><td><pre><code>function randtrits(a, b, prng)</code></pre><pre><code>repeat</code></pre><pre><code>y ← randbits(a, prng)</code></pre><pre><code>until y &lt; 3<sup>b</sup></code></pre><pre><code>for i = 0, ..., b - 1 do</code></pre><pre><code>x<sub>i</sub> = y mod 3</code></pre><pre><code>y = ⌊y/3⌋</code></pre><pre><code>return x<sub>0</sub>, ..., x<sub>b-1</sub></code></pre></td></tr></table>

output independent uniform trits if $3^b \ge 2^a$.

**Limitation.** If Algorithm 12 is used in a cryptographic context it will leak some information about seed as the number of rejection in the calls to `randtrits()` will depend of seed. To avoid leakage of possibly meaningful secret information we will favor conversions which are oblivious to their inputs and outputs.

B.2.1. *Oblivious Conversion.* The conversion algorithm can be made oblivious to the prng output by removing the rejection as shown in Algorithm 13.

<table><caption>**Algorithm 13** Binary to Ternary Conversion Without Rejection</caption><thead><tr><th>With modulo</th><th>Without modulo</th></tr></thead><tbody><tr><td><pre><code>function randtrits(a, b, prng)</code></pre><pre><code>y ← randbits(a, prng)</code></pre><pre><code>for i = 0, ..., b - 1 do</code></pre><pre><code>x<sub>i</sub> ← y mod 3</code></pre><pre><code>y ← ⌊y/3⌋</code></pre><pre><code>return x<sub>0</sub>, ..., x<sub>b-1</sub></code></pre></td><td><pre><code>function randtrits(a, b, prng)</code></pre><pre><code>y ← randbits(a, prng)</code></pre><pre><code>for i = 0, ..., b - 1 do</code></pre><pre><code>y ← 3 · (y mod 2<sup>a</sup>)</code></pre><pre><code>x<sub>i</sub> ← ⌊y/2<sup>a</sup>⌋</code></pre><pre><code>return x<sub>0</sub>, ..., x<sub>b-1</sub></code></pre></td></tr></tbody></table>

<figure><img src="image_29.png" /></figure>
**Limitation.** With this modification, no information will leak, however the output won't be uniformly distributed. The variant without modulo has the same distribution overall and avoids the division by 3, see [Lem19]. In both case, the entropy is

$$H_{a,b} = -\frac{r(q+1)}{2^a} \log_2 \frac{q+1}{2^a} - \frac{(3^b-r)q}{2^a} \log_2 \frac{q}{2^a} = b \cdot (\log_2 3 - \delta_{a,b})$$

where $q$ and $r$ denote the quotient and the remainder of the Euclidean division of $2^a$ by $3^b$, $2^a = q3^b + r$. The quantity $\delta_{a,b}$ measures the loss of entropy per trit, for instance $\delta_{64,32} = 8.510^{-12}$.

### B.2.2. Bitsliced Conversion.
Whenever required, the reference implementation will use Algorithm 14 to draw random bits with the appropriate method and convert them to ternary. The function `randtrits()` generates 128 random bits, two 64-bit words, and interleaves two calls to `convert()`, each consuming 64 bits with the property stated in Proposition 5, to return a bitsliced ternary vector of length 64, as defined in §B.1.

<table><caption>**Algorithm 14** Bitsliced Ternary Conversion ($a = 64, b = 32$)</caption><thead><tr><th colspan="2">Algorithm 14</th><th>Constants (hexadecimal):</th></tr></thead><tbody><tr><td>1:</td><td>function randtrits(prng)</td><td>Lo = 0x5555555555555555</td></tr><tr><td>2:</td><td>x &larr; randbits(a, prng)</td><td>Hi = 0xAAAAAAAAAAAAAAAAAA</td></tr><tr><td>3:</td><td>r &larr; convert(x)</td><td>E2 = 0x0404040404040404</td></tr><tr><td>4:</td><td>x' &larr; randbits(a, prng)</td><td>E3 = 0x0808080808080808</td></tr><tr><td>5:</td><td>r' &larr; convert(x')</td><td>E4 = 0x1010101010101010</td></tr><tr><td>6:</td><td>y<sub>h</sub> &larr; ((r & Hi) &gt;&gt; 1) &oplus; (r' &amp; Hi)</td><td>E5 = 0x2020202020202020</td></tr><tr><td>7:</td><td>y<sub>l</sub> &larr; (r &amp; Lo) &oplus; ((r' &amp; Lo) &lt;&lt; 1) &oplus; y<sub>h</sub></td><td>E6 = 0x4040404040404040</td></tr><tr><td>8:</td><td>return y</td><td>E7 = 0x8080808080808080</td></tr><tr><td>1:</td><td>function convert(x)</td><td>Y2 = 0x0101010101010101</td></tr><tr><td>2:</td><td>r &larr; 0</td><td>Y3 = 0x0707070707070707</td></tr><tr><td>3:</td><td>for i = 0, ..., 7 do</td><td>Y4 = 0x2525252525252525</td></tr><tr><td>4:</td><td>(x, v<sub>i</sub>) &larr; mul<sub>64</sub>(x, 81)</td><td></td></tr><tr><td>5:</td><td>r &larr; v<sub>i</sub> &oplus; (r &lt;&lt; 8)</td><td></td></tr><tr><td>6:</td><td>y &larr; (((r+Y<sub>4</sub>) &amp; (r+2Y<sub>4</sub>) &amp; E<sub>6</sub>) &oplus; ((r+2Y<sub>4</sub>) &amp; E<sub>7</sub>))</td><td>For 0 &le; x, y, u, v &lt; 2<sup>64</sup></td></tr><tr><td>7:</td><td>r &larr; r + (y &gt;&gt; 6) &times; 37</td><td>(u, v) &larr; mul<sub>64</sub>(x, y)</td></tr><tr><td>8:</td><td>y &larr; (((r+Y<sub>3</sub>) &amp; (r+2Y<sub>3</sub>) &amp; E<sub>4</sub>) &oplus; ((r+2Y<sub>3</sub>) &amp; E<sub>5</sub>))</td><td>if u + 2<sup>64</sup>v = xy</td></tr><tr><td>9:</td><td>r &larr; r + (y &gt;&gt; 4) &times; 7</td><td></td></tr><tr><td>10:</td><td>y &larr; (((r+Y<sub>2</sub>) &amp; (r+2Y<sub>2</sub>) &amp; E<sub>2</sub>) &oplus; ((r+2Y<sub>2</sub>) &amp; E<sub>3</sub>))</td><td></td></tr><tr><td>11:</td><td>r &larr; r + (y &gt;&gt; 2)</td><td></td></tr><tr><td>12:</td><td>return r</td><td></td></tr></tbody></table>

**Proposition 5.** On input $x = \sum_{i=0}^{63} x_i 2^i$, a 64-bit integer, the function `convert()` of Algorithm 14 returns a 64-bit integer $r = \sum_{i=0}^{31} u_i 4^i$ such that $x/2^{64} = \sum_{i \ge 0} u_i / 3^{i+1}$ with $u_i \in \{0, 1, 2\}$. If $x$ is uniformly distributed in $\{0, 1\}^{64}$ then the random variable $(u_i)_{0 \le i < 32}$ which takes its value in $\{0, 1, 2\}^{32}$ has an entropy

$$H = 32 (\log_2 3 - \delta) \text{ with } \delta \approx 8.510^{-12}.$$

Note that the uniform distribution over $\{0, 1, 2\}^{32}$ has entropy $32 \log_2 3$.

### B.3. Sampling Permutations and Permuting by Sorting.
We give in this section specifications (as implemented in the reference implementation) to sample permutations in constant time. Recall that key generation and signing in Wave involve many permutation

<figure><img src="image_30.png" /></figure>
samples, sometimes uniform as in Algorithm 4 or sometimes with some constraint as in Algorithms 6 and 7.

In this section, $\mathbb{F}$ is defined as any finite arbitrary alphabet. In practice $\mathbb{F}$ is chosen as $\mathbb{F}_3^\ell$ for some small $\ell$, typically it is equal to one or two.

We propose to sample permutations by sorting. Notice that it delegates all security related implementation issues to the sorting algorithm. In particular, sorting networks allows the sorting of an array with complexity $O(n(\log n)^2)$ which is oblivious to the data being sorted. Efficient cryptography oriented implementations are available, see `djbsort` [Ber] for instance. Another option is merge sort, as in [WSN18] for instance.

<caption>**Algorithm 15 RandPerm – Permutation Sampling by Sorting**</caption>

1: **function** RandPerm($n, \mathbf{z}$) $\triangleright \mathbf{z} \in \mathbb{F}^n$
2: **repeat**
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$r_i \leftarrow \S[0, 2^B)$
5: &nbsp;&nbsp;&nbsp;&nbsp;$$x \leftarrow \text{sort}((r_i, i, z_i)_{0 \le i < n})$$
6: &nbsp;&nbsp;&nbsp;&nbsp;**until** ($r_{j-1} \ne r_j, 0 < j < n$)
7: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, n-1$ **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(*, \sigma(i), y_i) \leftarrow x_i$
9: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(\sigma, \mathbf{y})$
$\triangleright \sigma \in \mathfrak{S}_n, \mathbf{y} = \mathbf{z}^\sigma$

B.3.1. *Sampling Permutations for Algorithm 4 (Key Generation).* Algorithm 15 produces a uniform permutation. The sample is rejected if some $r_i$ for $i \in [0, n)$ collide. The rejection probability is upper bounded by a constant smaller than $1/2$ if $B \ge 2 \log_2 n$. If the sampler admits a vector as additional input, it returns the vector permuted according to the sampled permutation.

B.3.2. *Sampling Permutations for Algorithm 6 (Decode$_V$).* The call `RandPerm$_V(n, k, t)$` will return a permutation $\pi$ of $[0, n)$ such that $(t \le k)$

(i) $\pi([0, k))$ is uniformly selected in $[0, n)$,

(ii) $\pi([0, t))$ is uniformly selected in $\pi([0, k))$.

If a vector $\mathbf{z} \in \mathbb{F}^n$ is provided as input, the permuted vector $\mathbf{y} = \mathbf{z}^\pi$ is returned in addition to $\pi$.

**Connection with Decode$_V$.** Using notation of Algorithm 6, Instructions 4 and 5 will be replaced by

$$ (\pi, \mathbf{y}) \leftarrow \text{RandPerm}_V(n/2, k_V - g, t, y_V). $$

The returned permutation does not need to be uniformly distributed, but simply, as specified above, namely $\pi([0, k_V - g))$ and $\pi([0, t))$ are uniformly distributed in $[0, n)$. These conditions are ensured by Instruction 6 of Algorithm 16. Also, no information must leak about $t$, $y_V$, or the permutation $\pi$.

<figure><img src="image_31.png" /></figure>
<caption>**Algorithm 16** RandPerm<sub>V</sub></caption>

1: **function** RandPerm<sub>V</sub>(n, k, t, **z**)
2:     **repeat**
3:         **for** i = 0, ..., n - 1 **do**
4:             $r_i \leftarrow \binom{s}{0, 2^B}$
5:             **x** ← **sort**<sub>((r_i, i, z_i)_{0 \le i < n})</sub>
6:             **until** $r_{k-1} \ne r_k$ and $r_{t-1} \ne r_t$
7:             **for** i = 0, ..., n - 1 **do**
8:                 $(*, \pi(i), y_i) \leftarrow x_i$
9:             **return** $(\pi, \mathbf{y})$

$\triangleright k < n, t \le k, \mathbf{z} \in \mathbb{F}^n$

$\triangleright B$ an integer, external parameter

$\triangleright$ sort according to $r_i$

If the sorting algorithm is oblivious to the data it processes, then this is also the case for Algorithm 16 with the exception of the test $r_{t-1} \ne r_t$ at Instruction 6 which must be implemented without revealing information about $t$.

B.3.3. *Sampling Permutations for Algorithm 7 (Decode<sub>U</sub>)*. The call `RandPerm<sub>U</sub>(n, k, ℓ, J)` will return a permutation $\pi$ of $[0, n)$ such that

(i) $\pi([0, k - \ell))$ is uniformly selected in $[0, n) \setminus J$,

(ii) $\pi([k - \ell, k))$ is uniformly selected in $J$.

If a vector $\mathbf{z} \in \mathbb{F}^n$ is provided, the permuted vector $\mathbf{y} = \mathbf{z}^\pi$ is returned in addition to $\pi$. The algorithm will proceed in two steps

(1) Permute $[0, n)$ randomly with the positions of $J$ coming last,

(2) Swap the last $\ell$ entries of the following blocks, the first one is given by coordinates $[0, k)$ and the second one by $[k, n)$, to ensure $\ell$ elements of $J$ in the first $k$ entries.

Instruction 6 will make a check after Step (ii) to ensure that the first $k - \ell$ entries of the permutation are uniformly distributed in $[0, n) \setminus J$ (true if and only if $r_{k-\ell-1} \ne r_{k-\ell}$ and the last $\ell$ entries of the permutation are uniformly distributed in $J$ (true if and only if $r_{n-\ell-1} \ne r_{n-\ell}$).

**Connection with** `Decode<sub>U</sub>`. Using notation of Algorithm 7, Instructions 5, 6, 7 and 10 will be replaced by

$$ (\pi, \mathbf{x}) \leftarrow \text{RandPerm}_U(n/2, n/2 - k_U + g, \ell, \text{Supp}(\mathbf{e}_V), \mathbf{x}) $$

where $x_i = (\mathbf{y}_V(i), (c_i - b_i)\mathbf{e}_V(i), \mathbf{e}_V(i)^2), i \in [0, n/2)$. It is required that the first $n/2 - k_V + g$ entries of $\pi$ consist of $\ell$ positions uniformly chosen in $\text{Supp}(\mathbf{e}_V)$ and $n/2 - k_U + g - \ell$ positions uniformly chosen in $[0, n) \setminus \text{Supp}(\mathbf{e}_V)$. Algorithm 17 complies to those constraints. Also, no information must leak about $\ell$, $J$, $\mathbf{x}$, or the permutation $\pi$.

If the sorting algorithm is oblivious to the data it processes, then this is also the case for Algorithm 17 with the exception of the tests $r_{k-\ell-1} \ne r_{k-\ell}$ and $r_{n-\ell-1} \ne r_{n-\ell}$ at Instruction 6 which must be implemented without revealing information about $\ell$.

<figure><img src="image_32.png" /></figure>
**Algorithm 17** RandPerm<sub>U</sub>

Input: integers $n, k < n, \ell, J \subseteq [0, n)$, $\mathbf{z} \in \mathbb{F}^n$ ▷ assume $\#J \le n-k$

Output: $(\pi(i))_{0 \le i < n}, \mathbf{y} = \mathbf{z}^{\pi}$ with $\pi \in \mathfrak{S}_n$ such that $\#\pi([0, k)) \cap J = \ell$

1: **repeat**

2: **for** $i = 0, \dots, n-1$ **do**

3: $r_i \leftarrow \begin{array}{l} \$ \\ [0, 2^B) \end{array}$ ▷ B an integer, external parameter

4: $r_i \leftarrow r_i + (i \in J)$ ? $2^B : 0$ ▷ coordinates in $J$ will be last after sorting

5: $\mathbf{x} \leftarrow \text{sort}((r_i, i, z_i)_{0 \le i < n})$ ▷ sort according to $r_i$ in increasing order

6: **until** $r_{k-\ell-1} \ne r_{k-\ell}$ and $r_{n-\ell-1} \ne r_{n-\ell}$

7: **for** $i = 0, \dots, k-1$ **do** ▷ fix size loop for constant time

8: $(x_{k-1-i}, x_{n-1-i}) \leftarrow (i < \ell) ? (x_{n-1-i}, x_{k-1-i}) : (x_{k-1-i}, x_{n-1-i})$ ▷ swap if $i < \ell$

9: **for** $i = 0, \dots, n-1$ **do**

10: $(*, \pi(i), y_i) \leftarrow x_i$

11: **return** $(\pi, \mathbf{y})$

B.3.4. *Permuting Vectors.* It is also possible to permute a vector according to a permutation by sorting. If the input permutation $\pi$ is given as a sequence of integers $(\pi(i))_{0 \le i < n}$, sorting this sequence will apply the inverse permutation. Interestingly, applying the inverse of a given permutation is what is needed most of the time in *Wave*. As an additional (almost free) feature, Algorithm 18 may return the inverse permutation as a sequence of integers.

**Algorithm 18** VectInvPerm – Apply (the Inverse of) a Permutation to a Vector

1: **function** VectInvPerm($\mathbf{z}, \pi$) ▷ $\mathbf{z} \in \mathbb{F}^n, \pi \in \mathfrak{S}_n$

2: $\mathbf{x} \leftarrow \text{sort}((\pi(i), i, z_i)_{0 \le i < n})$ ▷ sort according to first coordinate in increasing order

3: **for** $i = 0, \dots, n-1$ **do**

4: $(*, \sigma(i), y_i) \leftarrow x_i$

5: **return** $\mathbf{y}, \sigma$ ▷ $\mathbf{y} = \mathbf{z}^{\pi^{-1}} \sigma = \pi^{-1}$

B.3.5. *Permuting the Columns of a Matrix.* As for the coordinates of a vector, permuting the columns of a matrix can be achieved in constant time with an oblivious sorting algorithm. The principle of Algorithm 18 can be applied, but with an alphabet $\mathbb{F}$ large enough to accommodate the columns of a matrix. The reference implementation uses an ad hoc procedure deriving from `djbsort` [Ber] to produce a sorting network and uses it to conditionally swap the columns of a matrix.

B.4. **Master Key to Generate the Secret Matrices.** As the key generation (Algorithm 4) is described, the secret matrices $\mathbf{H}_U$ and $\mathbf{G}_V$ are needed only once per signature in Algorithm 5, when a Gaussian elimination is performed. Columns are permuted just before the elimination. Suppose that a master key $\mathbf{m}\mathbf{k}$ is used for generating matrices $\mathbf{H}_U$ and $\mathbf{G}_V$, its $i$-th column is equal to $f_{\mathbf{m}\mathbf{k}}(\mathbf{X}, i)$, $\mathbf{X} \in \{\mathbf{H}_U, \mathbf{G}_V\}$ where $f_{\mathbf{m}\mathbf{k}}(\cdot)$ is some, appropriately keyed (here $\mathbf{m}\mathbf{k}$), one-way function. The $i$-th column of $\mathbf{X}^{\pi}$ is equal to $f_{\mathbf{m}\mathbf{k}}(\mathbf{X}, \pi(i))$ and the matrix $\mathbf{X}^{\pi}$ can be generated without leaking information about $\pi$ assuming that the execution of $f_{\mathbf{m}\mathbf{k}}(\mathbf{X}, i)$ leaks no information on $i$. For instance assuming we want to generate $\mathbf{G}_V$ and $\mathbf{H}_U$ at run time (using `prng3()` as in Algorithm 12):

<figure><img src="image_33.png" /></figure>
* the i-th column of $G_V$ is the output of $\text{prng}_3(k_V, mk \parallel 0 \parallel i)$

* the i-th column of $H_U$ is the output of $\text{prng}_3(n/2 - k_U, mk \parallel 1 \parallel i)$

where $\parallel$ denotes the concatenation. Concatenating a '0' or a '1' separates the pseudorandom generator domains for cases 'V' and 'U'.

### B.5. Gaussian Elimination and its Variants in Constant Time.
It is assumed that the reader is familiar with the basic concepts. The Gaussian elimination on an $r \times n$ full rank matrix $A$ will produce another matrix $A'$ spanning the same vector space and which contains an $r \times r$ identity sub-matrix, indexed by some set $J$. The pivot positions are the elements of $J$, ordered from top to bottom. The pivots are selected in order one at a time. A failing pivot is a column (position) that is dependent of the previously selected pivot columns and that could not be included in the identity block. Note that for a given information set $J$ the transformed matrix is essentially unique. Changing the order of the pivots in $J$ will simply change the row order accordingly in the resulting matrix. Recall that, $M_i$ denotes the i-th row of the matrix $M$.

#### B.5.1. Systematic Gaussian Elimination.
In the key generation routine, Algorithm 4, the purpose is to reach a (strict) systematic form for an input matrix of size $r \times n$ (assuming it has full rank $r$), that is a matrix $A_{\text{syst}} = (\text{Id}_r | \mathbf{R})$ where $\text{Id}_r$ is the $r \times r$ identity matrix and such that $A$ and $A_{\text{syst}}$ span the same row vector space. This systematic form exists if and only if the leftmost $r \times r$ block of $A$ is non-singular. Else a few columns of $A$ may have to be permuted to reach the desired form.

In the current context the columns of a matrix $A$ are permuted with $\sigma \in \mathcal{S}_n$ before the Gaussian elimination and the call in Instruction 9 of Algorithm 4 is

$$ (A_{\text{syst}} = (\text{Id}_r | \mathbf{R}), \pi) \leftarrow \text{SystGaussElim}(A, \sigma) $$

where $A^\pi$ and $A_{\text{syst}}$ span the same row-space and $\pi \in \mathcal{S}_n$ is "close" to $\sigma$; the Gaussian elimination uses the columns of $A^\sigma$ as pivots from left to right and "push" the failing pivot positions right, yielding

$$ \forall i \in [0, r), \pi(i) = \sigma(\ell) \text{ where } \ell = \min \{j \in [0, n) \mid \text{rank}(A_{\sigma(j)}) = i\} $$

and

$$ \forall i \in [0, r)n, \pi(i) = \sigma(\ell) \text{ where } \ell = \min \{[0, n) \setminus \{\sigma^{-1} \circ \pi(j), j \in [0, i]\} \}. $$

**Key security.** If $(A, \pi)$ is private and $A_{\text{syst}}$ is public and obtained as above, it should be noted that $\pi$ is not uniformly distributed in $\mathcal{S}_n$. However, no security penalty incurs as $A_{\text{syst}}$ would be the result of the Gaussian elimination on $SA^\sigma$ for any non-singular $r \times r$ matrix $S$. Revealing $SA^\sigma$ for random uniform $\sigma$ and $S$ is innocuous (within the security assumptions) and publishing $A_{\text{syst}}$ rather than $SH^\sigma$ provides an information that anyone could have computed easily from public data.

**Implementation security.** Still the implementation of the Gaussian elimination could give rise to timing or cache attacks. For instance, if $A = H$ as in Instruction 8 of Algorithm 4, the special form and content of $H$ could induce secret dependent timing variations, typically because some columns of $d \star H_U$ or $b \star H_U$ can be null depending on secret information. This could be easily avoided by multiplying $H$ on the left by a random non singular matrix $S$ before the Gaussian elimination, or, probably less expensive, by a careful implementation of the Gaussian elimination, making sure that the timing and memory

<figure><img src="image_34.png" /></figure>
access pattern of each pivot elimination is independent of the coordinates of this particular column. Note that timing or memory access variations due to pivot failures do not need to be masked as they would also happen if the Gaussian elimination was applied to $SH^σ$, and this latter matrix could be safely revealed.

**Basic Gaussian elimination in constant time.** Algorithm 19 uses the constant time routine `Reduce_j()` defined in §B.5.2. This algorithm will be used in a context (Instruction 9 in Algorithm 4) where it can be not oblivious to pivot failure, but oblivious to everything else: an adversary can only learn which column indices led to a failing pivot. Indeed, this algorithm will be used to output the public key, when revealing pivot failures it only reveals positions where a Gaussian elimination may fail on the public matrix.

<caption>**Algorithm 19** Systematic Gaussian Elimination in constant time</caption>

1: **function** CTSystGaussElim($M, \pi$) $\triangleright M \in \mathbb{F}_3^{k \times n}$
2:     $j \leftarrow 0$
3:     $\ell \leftarrow n - 1$
4:     **while** $j < k$ **and** $j < \ell$ **do**
5:         **for** $i = j + 1, \dots, k - 1$ **do**
6:             $M_j, M_i \leftarrow \text{Reduce}_j(M_j, M_i)$ $\triangleright$ defined in §B.5.2
7:         **if** $M_{j,j} \neq 0$ **then**
8:             $M_j \leftarrow M_{j,j}^{-1} M_j$
9:             **for** $i = 0, \dots, j - 1$ **do**
10:                 $M_i \leftarrow M_i - M_{i,j} M_j$
11:             $j \leftarrow j + 1$
12:         **else**
13:             $M \leftarrow \text{SwapColumns}(M, j, \ell)$
14:             $\ell \leftarrow \ell - 1$
15:             $\pi \leftarrow \pi \circ (j \, \ell)$ $\triangleright \pi(j), \pi(\ell) \leftarrow \pi(\ell), \pi(j)$
16:         **return** $(M, \pi)$

**Gaussian elimination with abort in constant time.** Algorithm 20 is a variant of Algorithm 19 but with abort. Algorithm 20 will be used in a context, the generation of $H_V$ in Instruction 2 of Algorithm 4, where rejection is not allowed unless to weaken the security reduction. Basically, $H_V$ is computed by performing a Gaussian elimination of $G_V$ and revealing the failing pivot indices may reveal information on the particular permutation drawn for a secret matrix generation. It is why the algorithm always compute pivots with Instructions 5 and 6 (defined in §B.5.2). The computation of these pivots may fail. It is why the algorithm also outputs some integer $p$. Checking that $p$ is equal to $k$ or not enables to verify the success or not of the Gaussian elimination.

**Partial Gaussian elimination in constant time.** The constant time partial Gaussian elimination on $M \in \mathbb{F}_3^{k \times n}$ will stop the process $g$ steps before the end, that is after $k - g$ pivots in constant time (Instructions 5 and 6). In the current context Algorithm 21 will be called with a value of $g$ such the first $k - g$ pivots may fail (with a probability $\approx 1/2^{64}$) but the algorithm will stop in any case after $k - g$ iterations. The algorithm also outputs an integer $p$ which gives the number of successful pivots. Checking that $p$ is equal or not to $k - g$ enables to verify the success or not of the partial Gaussian elimination.

<figure><img src="image_35.png" /></figure>
<caption>**Algorithm 20** Gaussian Elimination “with Abort” in constant time</caption>

1: **function** CTGE<sub>abort</sub>(M) ▷ M ∈ F<sub>3</sub><sup>k×n</sup>
2:     p ← 0
3:     **for** ℓ = 0, ..., k − 1 **do**
4:         **for** i = ℓ + 1, ..., k − 1 **do**
5:             M<sub>ℓ</sub>, M<sub>i</sub> ← Reduce<sub>ℓ</sub>(M<sub>ℓ</sub>, M<sub>i</sub>) ▷ defined in §B.5.2
6:             M<sub>ℓ</sub> ← Normalize<sub>ℓ</sub>(M<sub>ℓ</sub>)
7:             p ← p + M<sub>ℓ,ℓ</sub>
8:             **for** i = 0, ..., ℓ − 1 **do**
9:                 M<sub>i</sub> ← M<sub>i</sub> − M<sub>i,ℓ</sub> M<sub>ℓ</sub>
10:             **return** (M, p)

<caption>**Algorithm 21** Partial Gaussian Elimination in constant time</caption>

1: **function** CTPartialGaussElim(M, g) ▷ M ∈ F<sub>3</sub><sup>k×n</sup>
2:     p ← 0
3:     **for** ℓ = 0, ..., k − g − 1 **do**
4:         **for** i = ℓ + 1, ..., k − 1 **do**
5:             M<sub>ℓ</sub>, M<sub>i</sub> ← Reduce<sub>ℓ</sub>(M<sub>ℓ</sub>, M<sub>i</sub>) ▷ defined in §B.5.2
6:             M<sub>ℓ</sub> ← Normalize<sub>ℓ</sub>(M<sub>ℓ</sub>)
7:             p ← p + M<sub>ℓ,ℓ</sub>
8:             **for** i = 0, ..., ℓ − 1 **do**
9:                 M<sub>i</sub> ← M<sub>i</sub> − M<sub>i,ℓ</sub> M<sub>ℓ</sub>
10:             **return** (M, p)

**Application to Algorithm 6** (CTDecode<sub>V</sub>). As Decode<sub>V</sub> was specified in Algorithm 6, the matrix G<sub>V</sub> is permuted, then a *g*-partial systematic form is computed. For a constant time implementation failure and rejection is not allowed. To this end, Instruction 6 will be replaced by

$$ (G, p) \leftarrow CTPartialGaussElim(G_{V}^{\pi}, g) $$

which tries to compute the permuted matrix $G_V^\pi$, possibly using a master key mk, in a *g*-partial systematic form. Checking that *p* is equal to $k_V - g$ will enable to test if the algorithm has been successful. It will lead to a constant time specification of Decode<sub>V</sub> as CTD碼<sub>V</sub> in Algorithm 27.

B.5.2. *Extended Gaussian Elimination in Constant Time.* The Gaussian elimination algorithms in constant time proposed above are not sufficient for the signing algorithm, in particular Algorithm 7 which needs to compute the *g*-extended systematic form (see Definition 2) of some matrix. In this context, rejection is also not allowed without weakening the security reduction, and revealing the failing pivot indices may reveal information on the particular permutation drawn for a particular signature generation. We must produce an algorithm which is completely oblivious to its input. This is achieved by adding zero rows at the bottom of the matrix (according to Lemma 2 in Appendix D, a matrix $A \in F_3^{(r+g)\times n}$ in extended systematic form has exactly *g* zero rows) and then performing a Gaussian elimination oblivious to the failing pivots.

<figure><img src="image_36.png" /></figure>
Algorithm 22, on input $(\mathbf{A}', g)$ with $\mathbf{A}' \in \mathbb{F}_3^{r \times n}$, tries to compute an extended systematic form of $\mathbf{A}'$ by first adding $g$ extra (zero) rows to form a matrix $\mathbf{A} \in \mathbb{F}_3^{(r+d) \times n}$. It succeeds if and only if the first $r + g$ columns of $\mathbf{A}$ have the same rank as $\mathbf{A}'$. If it fails, the output $\mathbf{A}$ will be such that $\langle \mathbf{A}' \rangle = \langle \mathbf{A} \rangle$ but it won't be in extended systematic form; the weight

$$ \# \{i \in [0, r+g), A_{i,i} \neq 0\} $$

of the main diagonal will be equal to $\text{rank}(\mathbf{A}'_{[0,r+g)}) < r$.

<caption>**Algorithm 22** Extended Gaussian Elimination in constant time</caption>

1: **function** CTExtGaussElim($\mathbf{A}', g$) 
2: $\mathbf{A} \leftarrow \text{stack}(\mathbf{A}', 0^{g \times n})$ 
3: $p \leftarrow 0$ 
4: **for** $\ell = 0, \dots, r+g-1$ **do** 
5: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = \ell+1, \dots, r+g-1$ **do** 
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$A_\ell, A_i \leftarrow \text{Reduce}_\ell(A_\ell, A_i)$ 
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$A_\ell \leftarrow \text{Normalize}_\ell(A_\ell)$ 
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$p \leftarrow p + A_{\ell,\ell}$ 
9: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0, \dots, \ell-1$ **do** 
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$A_i \leftarrow A_i - A_{i,\ell} \cdot A_\ell$ 
11: **return** $(\mathbf{A}, p)$ 
$\triangleright \mathbf{A}' \in \mathbb{F}_3^{r \times n}, g \le n-r$ 
$\triangleright \mathbf{A} = \begin{bmatrix} \mathbf{A}' \\ \mathbf{0} \end{bmatrix}$ 
$r$ rows 
$g$ rows

The functions $\text{Normalize}_\ell$ and $\text{Reduce}_\ell$ are defined as

$$ \text{Normalize}_{\ell}(\mathbf{x}) := \begin{cases} \mathbf{x} & \text{if } x_{\ell} = 0 \\ x_{\ell}^{-1} \cdot \mathbf{x} & \text{if } x_{\ell} \neq 0 \end{cases} \\ \text{Reduce}_{\ell}(\mathbf{x}, \mathbf{y}) := \begin{cases} (\mathbf{y}, \mathbf{x}) & \text{if } x_{\ell} = 0 \\ (\mathbf{x}, \mathbf{y} - (y_{\ell}x_{\ell}^{-1}) \cdot \mathbf{x}) & \text{if } x_{\ell} \neq 0 \end{cases} $$

Both functions enjoy simple secure implementations, for instance, using properties of $\mathbb{F}_3$:

$$ \text{Normalize}_{\ell}(\mathbf{x}) = (1 + x_{\ell} - x_{\ell}^{2}) \cdot \mathbf{x} \\ \text{Reduce}_{\ell}(\mathbf{x}, \mathbf{y}) = (x_{\ell}^{2} \cdot \mathbf{x} + (1 - x_{\ell}^{2}) \cdot \mathbf{y}, (1 - x_{\ell}^{2} - x_{\ell}y_{\ell}) \cdot \mathbf{x} + x_{\ell}^{2} \cdot \mathbf{y}) $$

and thus the whole procedure can be securely implemented.

**Proposition 6.** If $\mathbf{A}' \in \mathbb{F}_3^{r \times n}$ is such that $r = \text{rank}(\mathbf{A}') = \text{rank}(\mathbf{A}'_{[0,r+g]})$, then the output $\mathbf{A}$ of Algorithm 22 on input $(\mathbf{A}', g)$ is an extended systematic form of $\mathbf{A}'$.

*Proof.*

(1) Let us first remark that if $(\mathbf{x}', \mathbf{y}') = \text{Reduce}_\ell(\mathbf{x}, \mathbf{y})$ then $(\mathbf{x}', \mathbf{y}')$ spans the same space as $(\mathbf{x}, \mathbf{y})$ and $y'_\ell = 0$. The matrix $\mathbf{A}$ is modified in place. Initially it spans the same vector space as $\mathbf{A}'$, and this property remains true during all the computation, as Instruction 6, 7, and 10 will not change the spanned space. So we have $\langle \mathbf{A} \rangle = \langle \mathbf{A}' \rangle$ at all times. It remains to prove that $\mathbf{A}$ is in extended systematic form.

<figure><img src="image_37.png" /></figure>
Proof. The first $r+g$ column of $\mathbf{B}$ have rank $\ell-j = \text{rank}(\mathbf{B})$. To comply with the rank condition of the statement, the first $r+g$ columns of $\mathbf{A}$ must have rank $r = \text{rank}(\mathbf{A})$, thus the first $r+g-\ell$ columns of $\mathbf{C}$ must have rank $r-\text{rank}(\mathbf{B}) = r+j-\ell = \text{rank}(\mathbf{C})$, and in particular $r+j-\ell \ge r+g-\ell$, that is $g \ge j$. If $g=j$ then the first $r+g-\ell$ columns of $\mathbf{C}$ would have rank $r+g-\ell$. This cannot happen if the first column of $\mathbf{C}$ is null, hence $g>j$. $\square$

Instructions 5, 6 and 7 will move $\mathbf{C}$ down by one row and, because $g-j > 0$, insert one of the $g-j$ all-zero bottom rows as the new $\ell$-th row

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

With $A_\ell$ null now, Instructions 8 and 9 do nothing and at the end of the $\ell$-th iteration the matrix $\mathbf{A}$ becomes

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

Since $\mathbf{B}'$ is obtained by adding an all-zero row at the bottom of $\mathbf{B}$, it remains in extended systematic form. The rank default of $\mathbf{B}'$ is increased by one and becomes $j+1 = \ell+1 - \text{rank}(\mathbf{B}')$.

When $\ell = r-g$, everything vanishes except $\mathbf{B}$ in (18), and thus $\mathbf{A}$ is in extended systematic form. $\square$

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

**Application to Algorithm 7 (CTDecode<sub>U</sub>)**. As $\text{Decode}_U$ was specified in Algorithm 7, the matrix $\mathbf{H}_U$ is permuted, then a $g$-extended systematic form is computed. For a constant time implementation failure and rejection is not allowed. To this end, Instruction 13 will be replaced by

$$ (\mathbf{H}, p) \leftarrow \text{CTExtGaussElim}(\mathbf{H}_U^\pi, g) $$

which tries to compute the permuted matrix $\mathbf{H}_U^\pi$, possibly using a master key $\mathbf{mk}$, in a $g$-extended systematic form. Checking that $p$ is equal to $n/2-k_U$ will enable to test if the algorithm has been successful. It will lead to a constant time specification of $\text{Decode}_U$ as $\text{CTDecode}_U$ in Algorithm 28.

B.6. **Wave Key Generation and Signing in Constant Time.** Algorithms 23 and 26 are a specification of Wave Key Generation and Signing in constant time. Contrary to the

<figure><img src="image_41.png" /></figure>
specifications of the main part of the document, it is specified how to produce matrices $G_V$ and $H_U$ thanks to a master key (see §B.4), how to sample permutations (see §B.3), how to perform Gaussian elimination and its variants (see §B.5) as well as sampling random elements in their domain (see §B.2). Let us stress that all algorithms are implementation choices, there are a particular instantiation of algorithms presented in the main part of the document and they were specified to reach a constant time implementation.

<caption>**Algorithm 23** Key Generation in constant time</caption>

Output:
$$
\begin{aligned}
& \text{pk} = \mathbf{M} \in \mathbb{F}_3^{k \times (n-k)} \\
& \text{sk} = (\text{mk}, \mathbf{b}, \mathbf{c}, \pi) \in \mathbb{F}_3^{\lambda} \times \mathbb{F}_3^{n/2} \times \mathbb{F}_2^{n/2} \times \mathcal{G}_n \\
& \text{repeat} \\
& 2: \quad \text{mk} \leftarrow \$\{0, 1\}^{\lambda} \\
& \qquad \triangleright \pi_{id} \text{ the identity permutation} \\
& 3: \quad \mathbf{G} \leftarrow \text{RandMatPerm}(k_V, n/2, \text{mk} \parallel 0, \pi_{id}) \\
& \qquad \triangleright \text{Algorithm 24} \\
& 4: \quad (\mathbf{G}_V, p) \leftarrow \text{CTGE}_{\text{abort}}(\mathbf{G}) \\
& \qquad \triangleright \text{Algorithm 21} \\
& 5: \quad \textbf{until} \ p = k_V \\
& 6: \quad (\text{Id}_{k_V} | \mathbf{R}_V) \leftarrow \mathbf{G}_V \\
& 7: \quad \mathbf{H}_V \leftarrow (-\mathbf{R}_V^{\top} | \text{Id}_{n/2-k_V}) \\
& 8: \quad \mathbf{b} \leftarrow \$\mathbb{F}_3^{n/2} \\
& 9: \quad \mathbf{c} \leftarrow \$ (\mathbb{F}_3 \setminus \{0\})^{n/2} \\
& 10: \quad \mathbf{d} \leftarrow \mathbf{1} + \mathbf{b} \star \mathbf{c} \\
& 11: \quad \pi, \mathbf{x} \leftarrow \text{RandPerm}(n, (\mathbf{d}, -\mathbf{b})) \\
& \qquad \triangleright \text{Algorithm 15, } \mathbf{x} = (\mathbf{d}, -\mathbf{b})^{\pi} \\
& 12: \quad (\mathbf{M}, \pi) \leftarrow \text{WavePublicKey}(\text{mk}, \mathbf{H}_V, \pi, \mathbf{x}, \mathbf{c}) \\
& \qquad \triangleright \text{Algorithm 25, } \pi \text{ may change} \\
& 13: \quad \textbf{return} (\text{pk} = \mathbf{R}, \text{sk} = (\text{mk}, \mathbf{b}, \mathbf{c}, \pi))
\end{aligned}
$$

<caption>**Algorithm 24** Pseudorandom (Permuted) Matrix</caption>

1: **function** RandMatPerm(n, k, seed, π)
2:     **for** i = 0, ..., n − 1 **do**
3:         **x**<sub>i</sub> ← prng<sub>3</sub>(k, seed || π(i))
4:         ▷ Algorithm 12 (p. 27)
5:     **return** MatrixFromColumns(<b>x</b><sub>0</sub>, ..., <b>x</b><sub>n − 1</sub>)

<figure><img src="image_42.png" /></figure>
**Algorithm 25 Public Key Computation**

1: **function** WavePublicKey(mk, $G_V$, $\pi$, $\mathbf{x}$, $\mathbf{c}$)
2:     **for** $i = 0, \dots, n-1$ **do**
3:         $j \leftarrow \pi(i)$ mod $(n/2)$
4:         $\mathbf{y}_i \leftarrow \text{prng}_3(n/2 - k_U, \text{mk} \parallel 1 \parallel j)$
5:         $\mathbf{y}_i \leftarrow x_i \cdot \mathbf{y}_i$
6:         $\mathbf{H}_{\text{up}} \leftarrow \text{MatrixFromColumns}(\mathbf{y}_0, \dots, \mathbf{y}_{n-1})$
7:         $\mathbf{H}_{\text{down}} \leftarrow \text{MatPerm}((-\mathbf{c} \star \mathbf{H}_V | \mathbf{H}_V), \pi)$
8:         $\mathbf{H}_{\text{sec}} \leftarrow \left( \frac{\mathbf{H}_{\text{up}}}{\mathbf{H}_{\text{down}}} \right)$
9:         $((\mathbf{Id}_{n-k} | \mathbf{R}), \pi) \leftarrow \text{SystGaussElim}(\mathbf{H}_{\text{sec}}, \pi)$
10:        $\mathbf{M} \leftarrow \mathbf{M}(\mathbf{R})$
11:        **return** $(\mathbf{M}, \pi)$

$\triangleright$ Algorithm 12 (p. 27)

$\triangleright$ Oblivious permutation, §B.3.5

$\triangleright$ Algorithm 19, $\pi$ may change

$\triangleright$ As in Definition 3

**Algorithm 26 Wave Signature**

Input: : a message $\mathbf{m}$, $\mathbf{sk} = (\mathbf{mk}, \mathbf{b}, \mathbf{c}, \pi)$
Output: : $(\mathbf{s}, \text{salt})$
1: **repeat**
2:     $\mathbf{salt} \leftarrow \mathbb{F}_2^{2\lambda}$
3:     $\mathbf{x} \leftarrow \text{Hash}(\mathbf{m} \parallel \mathbf{salt})$
4:     $\mathbf{y} = (\mathbf{y}_L \parallel \mathbf{y}_R), \sigma \leftarrow \text{VectInvPerm}((\mathbf{x} \parallel \mathbf{0}^k), \pi)$
5:     $\sigma = \pi^{-1}$
6:     $\mathbf{y}_V \leftarrow \mathbf{y}_R - \mathbf{c} \star \mathbf{y}_L$
7:     $\mathbf{e}_V \leftarrow \text{CTDecode}_V(\mathbf{y}_V, \mathbf{mk})$
8:     $\mathbf{y}_U \leftarrow \mathbf{y}_L - \mathbf{b} \star \mathbf{y}_V$
9:     $\mathbf{e}_U \leftarrow \text{CTDecode}_U(\mathbf{y}_U, \mathbf{e}_V, \mathbf{b}, \mathbf{c}, \mathbf{mk})$
10:    $\mathbf{e}_L \leftarrow \mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$
11:   $\mathbf{e}_R \leftarrow \mathbf{c} \star \mathbf{e}_L + \mathbf{e}_V$
12:   $\mathbf{e}, * \leftarrow \text{VectInvPerm}((\mathbf{e}_L \parallel \mathbf{e}_R), \sigma)$
13:   $\mathbf{s} \leftarrow \mathbf{e}_{|n-k,n)}$
14:   **return** $(\mathbf{s}, \text{salt})$

$\triangleright$ $\lambda \in \{128, 192, 256\}$ denotes the security levels

$\triangleright \mathbf{x} \in \mathbb{F}_3^{n-k}$

$\triangleright$ Algorithm 18, $\mathbf{y} = (\mathbf{x} \parallel \mathbf{0}^k)^\sigma$,

$\triangleright$ Algorithm 27

$\triangleright$ simplification of $\mathbf{y}_U = (\mathbf{1} + \mathbf{c} \star \mathbf{b}) \star \mathbf{y}_L - \mathbf{b} \star \mathbf{y}_R$

$\triangleright$ Algorithm 28

$\triangleright$ simplification of $\mathbf{e}_R = \mathbf{c} \star \mathbf{e}_U + (\mathbf{1} + \mathbf{b} \star \mathbf{c}) \star \mathbf{e}_V$

$\triangleright$ Algorithm 18, $\sigma = \pi^{-1}$

$\triangleright$ Accept

APPENDIX C. KEY REPRESENTATION AND COMPRESSING SIGNATURES

C.1. **Key Representation.** To store public and private keys as byte arrays, we need to convert trits into bytes efficiently. We do this using a simple arithmetic encoding, packing five trits $v_0, \dots, v_4$ in $\{0, 1, 2\}$ into the one-byte integer $v_0 + 3v_1 + 9v_2 + 27v_3 + 81v_4$. This approach uses 242 of the 256 values that one byte can take, giving a storage efficiency of $242/256 = 94.5\%$. We could achieve a higher efficiency by packing more trits together in larger words, at the cost of more computation (and the specification of a byte order). On balance, we decided that five-trits-per-byte provides a good trade-off between storage efficiency, computational cost, and specification complexity.

C.2. **Compressing Signatures.** As with keys, Wave signatures can be stored and transmitted using the five-trits-per-byte encoding above. This would result in a signature size of, e.g., ⌈4288/5⌋ = 845 bytes (plus 32 salt bytes) for Wave822 (at NIST security Level I).

<figure><img src="image_43.png" /></figure>
<caption>**Algorithm 27** Decode<sub>V</sub> in constant time</caption>

1: **function** CTDecode<sub>V</sub>(y<sub>V</sub>, mk)
2: t ← <sub>D<sub>V</sub></sub>[0, k<sub>V</sub> − g]
3: **repeat**
4: &nbsp;&nbsp;&nbsp;&nbsp;(π, y) ← RandPerm<sub>V</sub>(n/2, k<sub>V</sub> − g, t, y<sub>V</sub>) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 16
5: &nbsp;&nbsp;&nbsp;&nbsp;G<sub>V</sub> ← RandMatPerm(n/2, k<sub>V</sub>, mk || 0, π) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 24
6: &nbsp;&nbsp;&nbsp;&nbsp;(G, p) ← CTPartialGaussElim(G<sub>V</sub>, g) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 21
7: **until** p = k<sub>V</sub> − g
8: &nbsp;&nbsp;&nbsp;&nbsp;x ← $^{\$}(\mathbb{F}_3 \setminus \{0\})^t \times \{0\}^{k_V - g - t} \times \mathbb{F}_3^g$
9: &nbsp;&nbsp;&nbsp;&nbsp;e ← y + (x − y<sup>(0)</sup>)G &nbsp;&nbsp;&nbsp;&nbsp;▷ y = (y<sup>(0)</sup>, y<sup>(1)</sup>) ∈ F<sub>3</sub><sup>n/2</sup> with y<sup>(0)</sup> ∈ F<sub>3</sub><sup>k<sub>V</sub> − g</sup>
10: &nbsp;&nbsp;&nbsp;&nbsp;e<sub>V</sub>, * ← VectInvPerm(e, π) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 18 (p. 31), e<sub>V</sub> = e<sup>π−1</sup>
11: **return** e<sub>V</sub>

<caption>**Algorithm 28** Decode<sub>U</sub> in constant time</caption>

1: **function** CTDecode<sub>U</sub>(y<sub>U</sub>, e<sub>V</sub>, b, c, mk)
2: t ← |e<sub>V</sub>|
3: ℓ ← <sub>D<sub>U</sub>(t)</sub>[0, t]
4: **repeat**
5: &nbsp;&nbsp;&nbsp;&nbsp;x = pack(y<sub>V</sub>, (c − b) ⋆ e<sub>V</sub>, e<sub>V</sub> ⋆ e<sub>V</sub>) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 17
6: &nbsp;&nbsp;&nbsp;&nbsp;(π, x) ← RandPerm<sub>U</sub>(n/2, n/2 − k<sub>U</sub> + g, ℓ, Supp(e<sub>V</sub>), x) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 17
7: &nbsp;&nbsp;&nbsp;&nbsp;y, v, s ← unpack(x) &nbsp;&nbsp;&nbsp;&nbsp;▷ y = y<sub>V</sub><sup>π</sup>; v = ((c − b) ⋆ e<sub>V</sub>)<sup>π</sup>; s = (e<sub>V</sub> ⋆ e<sub>V</sub>)<sup>π</sup>
8: &nbsp;&nbsp;&nbsp;&nbsp;H<sub>U</sub> ← RandMatPerm(n/2, n/2 − k<sub>U</sub>, mk || 1, π) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 24
9: &nbsp;&nbsp;&nbsp;&nbsp;(H, p) ← CTExtGaussElim(H<sub>U</sub>, d) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 22
10: **until** p = n/2 − k<sub>U</sub>
11: **repeat**
12: &nbsp;&nbsp;&nbsp;&nbsp;z<sup>(0)</sup> ← (H<sub>i,i</sub>)<sub>0≤i<n/2−k<sub>U</sub>+g</sub>
13: &nbsp;&nbsp;&nbsp;&nbsp;e<sup>(0)</sup> ← $^{\$}\mathbb{F}_3^{n/2−k<sub>U</sub>+g}$
14: &nbsp;&nbsp;&nbsp;&nbsp;e<sup>(0)</sup> ← (1 − z<sup>(0)</sup>) ⋆ e<sup>(0)</sup>
15: &nbsp;&nbsp;&nbsp;&nbsp;e<sup>(1)</sup> ← $^{\$}(\mathbb{F}_3 \setminus \{0\})^{k<sub>U</sub>−g}$
16: &nbsp;&nbsp;&nbsp;&nbsp;e<sup>(1)</sup> ← v<sup>(1)</sup> + (1 − s<sup>(1)</sup>) ⋆ e<sup>(1)</sup>
17: &nbsp;&nbsp;&nbsp;&nbsp;e<sup>(0)</sup> ← e<sup>(0)</sup> + (y − (e<sup>(0)</sup> || e<sup>(1)</sup>))H<sup>T</sup>
18: &nbsp;&nbsp;&nbsp;&nbsp;i ← |s<sup>(0)</sup> ⋆ e<sup>(0)</sup> − v<sup>(0)</sup>| &nbsp;&nbsp;&nbsp;&nbsp;▷ check final weight
19: &nbsp;&nbsp;&nbsp;&nbsp;j ← n/2 − k<sub>U</sub> + g − ℓ − |(1 − s<sup>(0)</sup>) ⋆ e<sup>(0)</sup>| &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 18, e<sub>U</sub> = e<sup>π−1</sup>
20: **until** (2j + i = n − w) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 18, e<sub>U</sub> = e<sup>π−1</sup>
21: &nbsp;&nbsp;&nbsp;&nbsp;e<sub>U</sub>, * ← VectInvPerm(e, π) &nbsp;&nbsp;&nbsp;&nbsp;▷ Algorithm 18, e<sub>U</sub> = e<sup>π−1</sup>
22: **return** e<sub>U</sub>

&nbsp;&nbsp;&nbsp;&nbsp;▷ \{ all vectors x ∈ {y, v, s, e} split as x = (x<sup>(0)</sup> || x<sup>(1)</sup>) with x<sup>(0)</sup> of length n/2 − k<sub>U</sub> + g and x<sup>(1)</sup> of length k<sub>U</sub> − g, the vector z<sup>(0)</sup> has length n/2 − k<sub>U</sub> + g.

But Wave signature vectors have high weight by definition, so their true entropy is lower than that of a random ternary vector. This makes signature compression a viable option. We considered several standard compression techniques, including arithmetic coding and combinadics, before settling on Huffman coding.

<figure><img src="image_44.png" /></figure>
We use a static Huffman encoding to encode three trits at a time, with codewords based on the expected average weight of a signature. Therefore, no information about the encoding needs to be transmitted with a compressed signature: hard-coded encoding and decoding routines can be used (see util/compress.c in the reference implementation).

The lossless compression of the signature involves only public information, so has no impact on the security of the overall signature scheme. This encoding is purely a trade-off between computational effort and resulting signature length. Better compression may be achieved by tweaking the parameters of the compression routine, or by using a different compression algorithm. The theoretical upper limit of the signature size for any signature encoding is the length of a non-compressed signature, the lower limit is defined by the entropy of an individual signature.

### C.3. Bounding signature lengths.
The use of Huffman coding (and variations in Wave signature vector weights) results in a varying signature length. We limit the maximum signature size by defining CRYPTO_BYTES in such a way that at fewer than one in $2^{61}$ signatures are expected to exceed the maximum signature length. In this case, re-signing with a new salt gives a short compressed signature with high probability, without leaking any information on the private key.

To model perfect compression, we define the parameter $p = \frac{w}{n}$, where w is the weight and n is the length. This gives trit probabilities $\mathbb{P}(0) = 1-p$, $\mathbb{P}(1) = \frac{p}{2}$, and $\mathbb{P}(2) = \frac{p}{2}$, so the average encoding for a word of length $\frac{n}{2}$ and weight t is

$$ \left(\frac{n}{2} - t\right) \log_2 \left(\frac{1}{1-p}\right) + t \log_2 \left(\frac{2}{p}\right). $$

On the other hand, the probability that a signature vector has weight exactly t is

$$ \mathbb{P}(\text{signature weight} = t) = \binom{\frac{n}{2}}{t} p^t (1-p)^{\frac{n}{2}-t}. $$

To define the maximum signature size for Wave822 (NIST Level I), we first computed the probability that a random Wave822 signature would compress perfectly to a given length. We then compressed many random Wave822 signature vectors to determine how close our Huffman compression is to a perfect compression, used this difference as an offset from the theoretical signature length with probability $2^{-61}$, and took the resulting signature length of 790 bytes (plus salt) as our maximum signature length for Wave822. We scaled the maximum length for the other security levels accordingly.

Table ?? lists some candidate bounds on signature lengths, together with the corresponding probabilities of rejection and re-signing.

<figure><img src="image_45.png" /></figure>
<table><caption>TABLE 9. Probability of rejection and re-signing for various signature length bounds.</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">Security</th><th colspan="3">Signature length bound (B)</th><th rowspan="2">P(Re-signing)</th></tr><tr><th>Salt</th><th>Vector</th><th>Total</th></tr></thead><tbody><tr><td rowspan="2">Wave822</td><td rowspan="2">Level I</td><td>32</td><td>741</td><td>773</td><td>2<sup>-1.096</sup></td></tr><tr><td>32</td><td>790</td><td>822</td><td>2<sup>-61.9</sup></td></tr><tr><td rowspan="2">Wave1249</td><td rowspan="2">Level III</td><td>64</td><td>1085</td><td>1149</td><td>2<sup>-1.66</sup></td></tr><tr><td>64</td><td>1185</td><td>1249</td><td>2<sup>-130</sup></td></tr><tr><td rowspan="2">Wave1644</td><td rowspan="2">Level V</td><td>64</td><td>1424</td><td>1488</td><td>2<sup>-1.113</sup></td></tr><tr><td>64</td><td>1580</td><td>1644</td><td>2<sup>-128</sup></td></tr></tbody></table>

## APPENDIX D. PROOF OF PROPOSITION 3

We use in this section notations of Algorithm 7.

**Proposition 3.** On input $(\mathbf{y}_U, \mathbf{e}_V, \mathbf{b}, \mathbf{c}, \mathbf{H}_U)$, Algorithm 7 outputs $\mathbf{e}_U$ satisfying

$$ (\mathbf{y}_U - \mathbf{e}_U) \mathbf{H}_U^\top = \mathbf{0}_{n/2-k_U} \qquad (13) $$

Furthermore, if $\mathbf{e}_L := \mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$ and $\mathbf{e}_R := \mathbf{c} \star \mathbf{e}_L + \mathbf{e}_V$, then

$$ |\mathbf{e}_L| + |\mathbf{e}_R| = w. \qquad (14) $$

The proof of this proposition will rely on the following lemmas.

**Lemma 2.** Let $\mathbf{A}_{\text{extSyst}} \in \mathbb{F}_3^{(r+g) \times n}$ be the output of Algorithm 3 given as input $\mathbf{A} \in \mathbb{F}_3^{r \times n}$ with $r = \text{rank}(\mathbf{A}) < n$. Let,

$$ J = \{i \in [0, r+g), \quad \mathbf{A}_{\text{extSyst}}(i, i) \neq 0\}. $$

We have,

$$ \#J = r $$

and

$$ \forall \mathbf{s} \in \mathbb{F}_3^{r+g}, \quad \text{Supp}(\mathbf{s}) \subseteq J \implies (\mathbf{s}, \mathbf{0}_{n-r-g}) \mathbf{A}_{\text{extSyst}}^\top = \mathbf{s}. $$

*Proof.* First, $\langle \mathbf{A}_{\text{extSyst}} \rangle = \langle \mathbf{A} \rangle$ and $r = \text{rank}(\mathbf{A}) < n$. We deduce that $\text{rank}(\mathbf{A}_{\text{partSyst}})$ is equal to $r < r+g$. Therefore, as the matrix $\text{rank}(\mathbf{A}_{\text{partSyst}})$ is in extended systematic form (see Definition 2), it has exactly $r$ non-zero rows, and $g$ zero rows. Furthermore, the set $J$ is an information set for $\mathbf{A}_{\text{extSyst}}$. We deduce that it has cardinal $\text{rank}(\mathbf{A}_{\text{partSyst}}) = r$ and as the columns of $\mathbf{A}_{\text{extSyst}}$ restricted to it form an identity matrix we have

$$ \forall \mathbf{s} \in \mathbb{F}_3^{r+g}, \quad \text{Supp}(\mathbf{s}) \subseteq J \Rightarrow (\mathbf{s}, \mathbf{0}_{n-r-g}) \mathbf{A}_{\text{extSyst}}^\top = \mathbf{s} $$

which concludes the proof. $\square$

In what follows we use notation of Algorithm 7 (Decode$_{U}$).

**Lemma 3.** Let $\mathbf{e}_L = \mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$ and $\mathbf{e}_R = \mathbf{c} \star \mathbf{e}_L + \mathbf{d} \star \mathbf{e}_V$ where $c_a \neq 0$ for all $a$. We have, $\forall i \in \pi([n/2 - k_U + g, n/2]), \mathbf{e}_L(i)\mathbf{e}_R(i) \neq 0$.

<figure><img src="image_46.png" /></figure>
Proof. First,

$$ \forall i \in [n/2 - k_U + g, n/2), \quad \mathbf{e}_U(\pi(i)) = \mathbf{e}(\pi^{-1}(\pi(i))) = \mathbf{e}(i) = \mathbf{e}^{(1)}(i - n/2 + k_U - g). $$

Now by definition of $\mathbf{e}^{(1)}$ it exists $\mathbf{x} \in (\mathbb{F}_3 \setminus \{0\})^{k_U - g}$ such that

$$ \mathbf{e}^{(1)} = \mathbf{v}^{(1)} + (\mathbf{1} - \mathbf{s}^{(1)}) \star \mathbf{x}. $$

But,

$$ \mathbf{v}^{(1)}(i - n/2 + k_U - g) = \mathbf{v}(i) = (\mathbf{c} - \mathbf{b}) \star \mathbf{e}_V(\pi(i)) $$

and

$$ \mathbf{s}^{(1)}(i - n/2 + k_U - g) = \mathbf{s}(i) = \mathbf{e}_V(\pi(i))^2 $$

Combining these four equations shows Equation (12) which concludes the proof. $\square$

**Lemma 4.** Let $\mathbf{e}_L = \mathbf{e}_U + \mathbf{b} \star \mathbf{e}_V$ and $\mathbf{e}_R = \mathbf{c} \star \mathbf{e}_L + \mathbf{e}_V$ where $c_a \neq 0$ for all $a$. In Instruction 22 and 23, $i$ and $j$ verify

$$ j = \# \{a \in [0, n/2) : \mathbf{e}_L(a) = \mathbf{e}_R(a) = 0\} \quad (19) $$

and

$$ i = \# \{a \in [0, n/2) : \mathbf{e}_L(a) \neq \mathbf{e}_R(a) \text{ and } \mathbf{e}_L(a)\mathbf{e}_R(a) = 0\}. \quad (20) $$

Proof. Let us first prove Equation (19). Let,

$$ m := \# \{a \in [0, n/2) : \mathbf{e}_L(a) = \mathbf{e}_R(a) = 0\}. $$

Our aim is to show that $m = j$. First, according to Lemma 3,

$$ m = \# \{a \in \pi([0, n/2 - k_U + g)) : \mathbf{e}_L(a) = \mathbf{e}_R(a) = 0\}. \quad (21) $$

We have for all $b \in [0, n/2 - k_U + g)$,

$$ \begin{aligned} \mathbf{e}_L(\pi(b)) &= \mathbf{e}_U(\pi(b)) + (\mathbf{b} \star \mathbf{e}_V)(\pi(b)) \\ &= \mathbf{e}^{(0)}(b) + (\mathbf{b} \star \mathbf{e}_V)(\pi(b)) \end{aligned} \quad (22) $$

and

$$ \begin{aligned} \mathbf{e}_R(\pi(b)) &= (\mathbf{c} \star \mathbf{e}_L)(\pi(b)) + \mathbf{e}_V(\pi(b)) \\ &= \mathbf{c}(\pi(b))\mathbf{e}^{(0)}(b) + (1 + \mathbf{b}(\pi(b))\mathbf{c}(\pi(b)))\mathbf{e}_V(\pi(b)). \end{aligned} \quad (23) $$

Combining these two equations with Equation (21) and the fact that $c_a \neq 0$ for all $a$ shows

$$ m = \# \{b \in [0, n/2 - k_U + g) : \mathbf{e}_V(\pi(b)) = 0 \text{ and } \mathbf{e}^{(0)}(b) = 0\}. $$

Therefore,

$$ \begin{aligned} m = n/2 - k_U + g - & \underbrace{\# \{b \in [0, n/2 - k_U + g) : \mathbf{e}_V(\pi(b)) \neq 0\}}_{=l \text{ (see Instruction 5)}} \\ & - \underbrace{\# \{b \in [0, n/2 - k_U + g) : \mathbf{e}_V(\pi(b)) = 0 \text{ and } \mathbf{e}^{(0)}(b) \neq 0\}}_{=|(1-\mathbf{s}^{(0)})\star\mathbf{e}^{(0)}|} \end{aligned} $$

showing that $m = j$ as defined in Instruction 23.

<figure><img src="image_47.png" /></figure>
Let us prove now Equation (20). Let,

$$q := \# \{ a \in [0, n/2) : \mathbf{e}_L(a) \neq \mathbf{e}_R(a) \text{ and } \mathbf{e}_L(a)\mathbf{e}_R(a) = 0 \}.$$

Our aim is to show that $q = i$. First, according to Lemma 3,

$$\begin{aligned} q &= \# \{ a \in \pi([0, n/2 - k_U + g)) : \mathbf{e}_L(a) \neq \mathbf{e}_R(a) \text{ and } \mathbf{e}_L(a)\mathbf{e}_R(a) = 0 \} \\ &= q_1 + q_2 \end{aligned}$$

where,

$$\left\{ \begin{array}{l} q_1 := \# \{ a \in \pi([0, n/2 - k_U + g)) : \mathbf{e}_L(a) = 0 \text{ and } \mathbf{e}_R(a) \neq 0 \}, \\ q_2 := \# \{ a \in \pi([0, n/2 - k_U + g)) : \mathbf{e}_L(a) \neq 0 \text{ and } \mathbf{e}_R(a) = 0 \}. \end{array} \right.$$

Using Equations (22) and (23) and the fact that $c_a \neq 0$ for all $a$, we obtain,

$$q_1 = \# \left\{ b \in [0, n/2 - k_U + g) : \mathbf{e}_V(\pi(b)) \neq 0 \text{ and } \mathbf{e}^0(b) = -(\mathbf{b} \star \mathbf{e}_V)(\pi(b)) \right\}.$$

$$q_2 = \# \left\{ b \in [0, n/2 - k_U + g) : \mathbf{e}_V(\pi(b)) \neq 0 \text{ and } \mathbf{e}^0(b) = -((\mathbf{c} + \mathbf{b}) \star \mathbf{e}_V)(\pi(b)) \right\}.$$

Notice now that when $\mathbf{e}_V(\pi(b)) \neq 0$, as $c_a \neq 0$ for all $a$, we necessarily have

$$-(\mathbf{b} \star \mathbf{e}_V)(\pi(b)) \neq (\mathbf{c} - \mathbf{b}) \star \mathbf{e}_V(\pi(b))$$

and,

$$-( (\mathbf{c} + \mathbf{b}) \star \mathbf{e}_V )(\pi(b)) \neq ( (\mathbf{c} - \mathbf{b}) \star \mathbf{e}_V )(\pi(b)). $$

Therefore,

$$q = q_1 + q_2$$

$$= \# \left\{ b \in [0, n/2 - k_U + g) : \mathbf{e}_V(\pi(b)) \neq 0 \text{ and } \mathbf{e}^0(b) \neq ((\mathbf{c} - \mathbf{b}) \star \mathbf{e}_V)(\pi(b)) \right\}.$$

which is equal $|\mathbf{s}^{(0)} \star \mathbf{e}^{(0)} - \mathbf{v}^{(0)}| = i$ and it concludes the proof. $\square$

**Lemma 5.** In Instruction 18, $\mathbf{e}^{(0)}$ verifies,

$$\mathbf{e}^{(0)}(\mathbf{H}_{[0,n/2-k_U+g)})^{\top} = \mathbf{0}_{n/2-k_U+g}.$$

<figure><img src="image_48.png" /></figure>
Proof. First, in Instruction 18, $\mathbf{e}^{(0)}$ is equal to

$$ (\mathbf{1} - \mathbf{z}^{(0)}) \star \mathbf{f} $$

for some $\mathbf{f} \in \mathbb{F}_3^{n/2-k_U+g}$. The matrix $\mathbf{H}$ has been obtained in Instruction 13 via a ExtGaussElim (Algorithm 3), therefore it is in extended systematic form (see Definition 2). In particular, $\mathbf{H}_{[0,n/2-k_U+g)}$ is full of zero except on the diagonal where there are potentially some 1's. Therefore, by definition of $\mathbf{z}^{(0)}$ in Instruction ??,

$$ (\mathbf{1} - \mathbf{z}^{(0)}) \star \mathbf{f} = \mathbf{f} (\mathrm{Id}_{n/2-k_U+g} - \mathbf{H}_{[0,n/2-k_U+g)})^{\top} $$

Furthermore, using once again that $\mathbf{H}_{[0,n/2-k_U+g)}$ has only 0 or 1 on its diagonal, and otherwise is 0, we obtain

$$ (1 - \mathbf{z}^{(0)}) \star \mathbf{f} (\mathbf{H}_{[0,n/2-k_U+g)})^{\top} = \mathbf{0}_{n/2-k_U+g} $$

which concludes the proof of the lemma.

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

Equipped with Lemmas 3, 4 and 5 we are now ready to prove Proposition 3.

Proof of Proposition 3. Let us first show Equation (13). By Lemma 4 and Instruction 24 we have

$$ n - |(\mathbf{e}_L, \mathbf{e}_R)| = 2j + i \quad \text{and} \quad 2j + i = n - w $$

showing that $|\mathbf{e}_L| + |\mathbf{e}_R| = w$.

Let us now prove Equation (??) given in the proposition. Notice that $\mathbf{y}_U = \mathbf{y}^{\pi^{-1}}$ and $\mathbf{e}_U = \mathbf{e}^{\pi^{-1}}$ where $\mathbf{e}$ is given in Instruction ?? . Therefore,

$$ (\mathbf{y}_U - \mathbf{e}_U) \mathbf{H}_U^{\top} = (\mathbf{y} - \mathbf{e}) (\mathbf{H}_U^{\pi})^{\top}. \quad (24) $$

Recall now that $\mathbf{H}$ has been computed in Instruction 13 via ExtGaussElim (Algorithm 3), and therefore is in extended systematic form (see Definition 2). Let,

$$ J = \{i \in [0, n/2 - k_U + g), \ H_{i,i} \neq 0\}. $$

By definition, we have

$$ \left\{ \begin{array}{l} \forall i \in J: \ H_{i,i} = 1 \text{ and } |\mathrm{col}(\mathbf{H}, i)| = 1, \\ \forall i \in [0, n/2 - k_U + g) \setminus J: \ |\mathrm{row}(\mathbf{H}, i)| = 0. \end{array} \right. $$

where $\mathrm{col}(\mathbf{H}, i)$ (resp. $\mathrm{row}(\mathbf{H}, i)$) is defined as the $i$-th column (resp. row) of $\mathbf{H}$. But as $\langle \mathbf{H} \rangle = \langle \mathbf{H}_U^\pi \rangle$, the set $J$ is an information set of $\mathbf{H}_U^\pi$. We deduce that it exists a non-singular $\mathbf{S} \in \mathbb{F}_3^{(n/2-k_U) \times (n/2-k_U)}$ such that $\mathbf{S}\mathbf{H}_U^\pi \in \mathbb{F}_3^{(n/2-k_U) \times n/2}$ verifies

$$ \forall j \in J, \quad \mathrm{row}(\mathbf{S}\mathbf{H}_U^\pi, j) = \mathrm{row}(\mathbf{H}, j) $$

Therefore,

$$ \forall j \in J, \quad (\mathbf{y} - \mathbf{e})\mathbf{H}^{\top}(j) = 0 \implies (\mathbf{y} - \mathbf{e}) (\mathbf{H}_U^{\pi})^{\top} = \mathbf{0}_{n/2-k_U} \quad (25) $$

Let $\mathbf{e}_{new}^{(0)}$ as in Instruction ?? and $\mathbf{e}_{old}^{(0)}$ as in Instruction 18. According to Lemma 5,

$$ \mathbf{e}_{new}^{(0)} = \mathbf{e}_{old}^{(0)} + \mathbf{y}\mathbf{H}^{\top} - \mathbf{e}^{(1)}(\mathbf{H}_{[n/2-k_U+g,n/2]})^{\top} \quad (26) $$

where $\mathbf{e}^{(1)}$ is given in Instruction 20. Notice now that $(\mathbf{e}$ is given in Instruction ??)

$$ \mathbf{e}\mathbf{H}^{\top} = \mathbf{e}_{new}^{(0)} (\mathbf{H}_{[0,n/2-k_U+g)})^{\top} + \mathbf{e}^{(1)} (\mathbf{H}_{[n/2-k_U+g,n/2]})^{\top} $$

<figure><img src="image_50.png" /></figure>
Using Equation (??) and Lemma 5, we get

$$ \mathbf{e}_{new}^{(0)}(\mathbf{H}_{[0,n/2-k_U+g)})^{\top} = \mathbf{y}\mathbf{H}^{\top}(\mathbf{H}_{[0,n/2-k_U+g]})^{\top} - \mathbf{e}^{(1)}(\mathbf{H}_{[n/2-k_U+g,n/2]})^{\top}(\mathbf{H}_{[0,n/2-k_U+g]})^{\top} $$

Therefore,

$$ (\mathbf{y} - \mathbf{e}) \mathbf{H}^{\top} = \mathbf{y}\mathbf{H}^{\top} - \mathbf{y}\mathbf{H}^{\top}(\mathbf{H}_{[0,n/2-k_U+g]})^{\top} + \mathbf{e}^{(1)}(\mathbf{H}_{[n/2-k_U+g,n/2]})^{\top} - \mathbf{e}^{(1)}(\mathbf{H}_{[n/2-k_U+g,n/2]})^{\top}(\mathbf{H}_{[0,n/2-k_U+g]})^{\top} \quad (27) $$

Recall now that,

$$ \forall i \in J: H_{i,i} = 1 \text{ and } |\mathrm{col}(\mathbf{H}, i)| = 1 $$

We deduce that for any $\mathbf{x} \in \mathbb{F}_3^{n/2-k_U+g}$,

$$ \forall j \in J, \quad \mathbf{x}(\mathbf{H}_{[0,n/2-k_U+g]})^{\top}(j) = \mathbf{x}(j). $$

Plugging this in Equation (??) shows that

$$ \forall j \in J, \quad (\mathbf{y} - \mathbf{e})\mathbf{H}^{\top}(j) = 0. $$

Therefore, according to (26),

$$ (\mathbf{y} - \mathbf{e}) (\mathbf{H}_{U}^{\pi})^{\top} = \mathbf{0}_{n/2-k_U} $$

which concludes the proof by using Equation (25). □

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

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