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

HAL
open science

# Wave Parameter Selection

Nicolas Sendrier

► To cite this version:

Nicolas Sendrier. Wave Parameter Selection. PQCrypto 2023 - 14th International Conference on Post-Quantum Cryptography, Aug 2023, College Park, United States. pp.91-110, 10.1007/978-3-031-40003-2_4. hal-04525954

HAL Id: hal-04525954

https://inria.hal.science/hal-04525954

Submitted on 29 Mar 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Wave Parameter Selection*

Nicolas Sendrier

Inria**

nicolas.sendrier@inria.fr

**Abstract.** Wave is a provably EUF-CMA (existential unforgeability under adaptive chosen message attacks) digital signature scheme based on codes [15]. It is a hash-and-sign primitive and its security is built according to a GPV-like framework [19] under two assumptions related to coding theory: (i) the hardness of finding a word of prescribed Hamming weight and prescribed syndrome, and (ii) the pseudo-randomness of ternary generalized $(U|U+V)$ codes. Forgery attacks (i)—or message attacks—consist in solving the ternary decoding problem for large weight [7], while, to the best of our knowledge, key attacks (ii) will try to exhibit words that are characteristic of $(U|U+V)$ codes, which are called type-$U$ or type-$V$ codewords in the present paper. In the current state-of-the-art, the best known attacks both reduce to various flavours of Information Set Decoding (ISD) algorithms for different regime of parameters. In this paper we give estimates for the complexities of the best known ISD variants for those regimes. Maximizing the computational effort, thus the security, for both attacks lead to conflicting constraints on the parameters. We provide here a methodology to derive optimal trade-offs for selecting parameters for the Wave signature scheme achieving a given security. We apply this methodology to the current state-of-the-art and propose some effective parameters for Wave. For $\lambda = 128$ bits of classical security, the signature is 737 bytes long, scaling linearly with the security, and the public key size is 3.6 Mbytes, scaling quadratically with the security.

## 1 Introduction

The signature scheme Wave is built from a family of trapdoor one-way preimage sampleable function [15]. It is a hash-and-sign digital signature scheme and, in contrast with [12], it easily scales with the security parameter. It is provably EUF-CMA under code-based hardness assumptions, namely the hardness of decoding and the indistinguishability of generalized ternary $(U|U+V)$ codes. The scheme enjoys some very attractive features: (1) very short signatures, less than 1 kbyte for 128 bits of security, and (2) fast verification, less than 1 millisecond [2]. The main drawback is a very large public key, of several megabytes.

<footnote>* This work has been partially supported by the French Agence Nationale de la Recherche through the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.</footnote>

<footnote>** Project-Team COSMIQ, Inria de Paris, 2 rue Simone Iff, 75012 Paris</footnote>
# Wave Parameter Selection*

Nicolas Sendrier

Inria**

nicolas.sendrier@inria.fr

**Abstract.** Wave is a provably EUF-CMA (existential unforgeability under adaptive chosen message attacks) digital signature scheme based on codes [15]. It is a hash-and-sign primitive and its security is built according to a GPV-like framework [19] under two assumptions related to coding theory: (i) the hardness of finding a word of prescribed Hamming weight and prescribed syndrome, and (ii) the pseudo-randomness of ternary generalized $(U|U+V)$ codes. Forgery attacks (i)—or message attacks—consist in solving the ternary decoding problem for large weight [7], while, to the best of our knowledge, key attacks (ii) will try to exhibit words that are characteristic of $(U|U+V)$ codes, which are called type-$U$ or type-$V$ codewords in the present paper. In the current state-of-the-art, the best known attacks both reduce to various flavours of Information Set Decoding (ISD) algorithms for different regime of parameters. In this paper we give estimates for the complexities of the best known ISD variants for those regimes. Maximizing the computational effort, thus the security, for both attacks lead to conflicting constraints on the parameters. We provide here a methodology to derive optimal trade-offs for selecting parameters for the Wave signature scheme achieving a given security. We apply this methodology to the current state-of-the-art and propose some effective parameters for Wave. For $\lambda = 128$ bits of classical security, the signature is 737 bytes long, scaling linearly with the security, and the public key size is 3.6 Mbytes, scaling quadratically with the security.

## 1 Introduction

The signature scheme Wave is built from a family of trapdoor one-way preimage sampleable function [15]. It is a hash-and-sign digital signature scheme and, in contrast with [12], it easily scales with the security parameter. It is provably EUF-CMA under code-based hardness assumptions, namely the hardness of decoding and the indistinguishability of generalized ternary $(U|U+V)$ codes. The scheme enjoys some very attractive features: (1) very short signatures, less than 1 kbyte for 128 bits of security, and (2) fast verification, less than 1 millisecond [2]. The main drawback is a very large public key, of several megabytes.

<footnote>* This work has been partially supported by the French Agence Nationale de la Recherche through the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.</footnote>

<footnote>** Project-Team COSMIQ, Inria de Paris, 2 rue Simone Iff, 75012 Paris</footnote>
In this paper we explore the best known attacks on the Wave signature
scheme and provide some practical parameters based on the current state-of-the-
art, as well as a methodology to adjust those parameters to any target security
or if the state-of-the-art evolves. There are two ways to attack the Wave scheme:

1. Message attacks, or forgery attacks, which consist in solving a generic decoding problem. Those problems are for ternary codes and for large weights, and the best solver [7] uses information set decoding (ISD) [27] combined with Wagner's generalized birthday algorithm (GBA) [31].

2. Structural attacks, or key attacks, which consist in defeating the indistin-
guishability assumption. To the best of our knowledge, the most efficient
way to achieve that is to exhibit codewords in the public code (i.e. the code
deriving from the public key) that have an expectedly low, or high, weight.
Such codewords are likely to be among the, so-called, type-U or type-V code-
words, and are susceptible to reveal information about the hidden (U|U+V)
structure. In practice, those key attacks boil down to finding codewords of
specified weight in a generic code, for which the best solvers again derive
from ISD.

We will observe that the two classes of attacks above provide conflicting con-
straints on the system parameters, and the choice of secure parameters derives
from a trade-off between those constraints.

*Related Works.* Code-based digital signatures first appeared in [30]: the Stern authentication protocol using the Fiat-Shamir transform [17]. The first hash-and-sign signature based on codes was proposed in [12] but does not scale very well, making it unpractical. There have been improvements to Stern's scheme, [1] using cyclic codes and a 5-pass protocol, and more recently [16] using the MPC-in-the-head paradigm [20]. The latter allows schemes with signatures shorter than the latter, around 10 kbytes or a bit less. Those techniques have relatively larger signature sizes compared to Wave, but much smaller public keys. Let us also mention the LESS scheme [4] with similar characteristic but a security based on the hardness of code equivalence rather than the hardness of decoding.

The paper is organized as follows. We first recall in §2 basic information
about codes and hard problems, the definition of (U|U + V) codes and their
main properties, and a description of the Wave signature scheme. Then in §3 we
give a framework to estimate the cost of ISD in the q-ary case, adapted from
existing literature, presenting the variants that are relevant for the study of
Wave's security. Finally, in §4, we provide estimates for the computational cost
of the best known attacks and a methodology to derive practical parameters for
the Wave digital signature scheme.

## 2 Preliminaries

Many statements in this section are often admitted as coding theory folklore.
We point out [14] to the reader for a precise and rigorous presentation of some
of those statements.
In this paper we explore the best known attacks on the Wave signature
scheme and provide some practical parameters based on the current state-of-the-
art, as well as a methodology to adjust those parameters to any target security
or if the state-of-the-art evolves. There are two ways to attack the Wave scheme:

1. Message attacks, or forgery attacks, which consist in solving a generic decoding problem. Those problems are for ternary codes and for large weights, and the best solver [7] uses information set decoding (ISD) [27] combined with Wagner's generalized birthday algorithm (GBA) [31].

2. Structural attacks, or key attacks, which consist in defeating the indistin-
guishability assumption. To the best of our knowledge, the most efficient
way to achieve that is to exhibit codewords in the public code (i.e. the code
deriving from the public key) that have an expectedly low, or high, weight.
Such codewords are likely to be among the, so-called, type-U or type-V code-
words, and are susceptible to reveal information about the hidden (U|U+V)
structure. In practice, those key attacks boil down to finding codewords of
specified weight in a generic code, for which the best solvers again derive
from ISD.

We will observe that the two classes of attacks above provide conflicting con-
straints on the system parameters, and the choice of secure parameters derives
from a trade-off between those constraints.

*Related Works.* Code-based digital signatures first appeared in [30]: the Stern authentication protocol using the Fiat-Shamir transform [17]. The first hash-and-sign signature based on codes was proposed in [12] but does not scale very well, making it unpractical. There have been improvements to Stern's scheme, [1] using cyclic codes and a 5-pass protocol, and more recently [16] using the MPC-in-the-head paradigm [20]. The latter allows schemes with signatures shorter than the latter, around 10 kbytes or a bit less. Those techniques have relatively larger signature sizes compared to Wave, but much smaller public keys. Let us also mention the LESS scheme [4] with similar characteristic but a security based on the hardness of code equivalence rather than the hardness of decoding.

The paper is organized as follows. We first recall in §2 basic information
about codes and hard problems, the definition of (U|U + V) codes and their
main properties, and a description of the Wave signature scheme. Then in §3 we
give a framework to estimate the cost of ISD in the q-ary case, adapted from
existing literature, presenting the variants that are relevant for the study of
Wave's security. Finally, in §4, we provide estimates for the computational cost
of the best known attacks and a methodology to derive practical parameters for
the Wave digital signature scheme.

## 2 Preliminaries

Many statements in this section are often admitted as coding theory folklore.
We point out [14] to the reader for a precise and rigorous presentation of some
of those statements.
NOTATION

$\mathbf{F}_q$ The q-ary finite field

$\mathbf{x} \in \mathbf{F}_q^n$ $\mathbf{x} = (x_0, \dots, x_n)_{0 \le i < n} \in \mathbf{F}_q^n$, vectors generally use bold letters

$|\mathbf{x}|$ Hamming weight of $\mathbf{x} \in \mathbf{F}_q^n$, $|\mathbf{x}| = |\{i, 0 \le i < n \mid x_i \neq 0\}|$

$\mathcal{E}_{q; n, t}$ $\mathcal{E}_{q; n, t} = \{\mathbf{e} \in \mathbf{F}_q^n, |\mathbf{e}| = t\}$

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

$\mathbf{M} \in \mathbf{F}_q^{r \times n}$ $(M_{i,j})_{0 \le i < r, 0 \le j < n}$, $r \times n$ matrix over $\mathbf{F}_q$

$\langle \mathbf{M} \rangle$ The vector space spanned by the rows of matrix $\mathbf{M}$

A matrix $\mathbf{M} \in \mathbf{F}_q^{r \times n}$ is in systematic form if its writes as $\mathbf{M} = (\mathbf{I}_d | \mathbf{R})$ where $\mathbf{I}_d$ is the $r \times r$ identity matrix

Reduced row echelon form

A matrix in $\mathbf{F}_q^{r \times n}$ is in reduced row echelon form if its $r$ leftmost independent columns form an identity matrix

$\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} \in \mathbf{F}_q^{r \times n}$, $\mathbf{x} \in \mathbf{F}_q^n$, $\mathbf{M} = \mathbf{F}_q^{r \times n}$

$\mathcal{S}_n$ Group of permutations of $\{0, \dots, n - 1\}$

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

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

$\mathcal{X}^{\pi} = \{\mathbf{x}^{\pi} \mid \mathbf{x} \in \mathcal{X}\}$, $\mathcal{X} \subset \mathbf{F}_q^n$, $\pi \in \mathcal{S}_n$

## 2.1 Error Correcting Code

A q-ary linear $[n, k]$ code $C$ is a $k$-dimensional subspace of $\mathbf{F}_q^n$. A *generator matrix* $\mathbf{G} \in \mathbf{F}_q^{k \times n}$ of $C$ is such that $\langle \mathbf{G} \rangle = C$ and a *parity check matrix* $\mathbf{H} \in \mathbf{F}_q^{(n-k) \times n}$ of $C$ is such that $\langle \mathbf{H} \rangle^{\perp} = C$, i.e.

$$C = \{\mathbf{x}\mathbf{G} \mid \mathbf{x} \in \mathbf{F}_q^k\} \text{ and } C = \{\mathbf{y} \in \mathbf{F}_q^n \mid \mathbf{y}\mathbf{H}^{\top} = 0\}.$$

For any $\mathbf{y} \in \mathbf{F}_q^n$ the quantity $\mathbf{y}\mathbf{H}^{\top}$ is called the *syndrome* of $\mathbf{y}$ (relatively to $\mathbf{H}$). The *dual code* of $C$ is $C^{\perp} = \langle \mathbf{H} \rangle$, the orthogonal of $C$.

*Weight Distribution.* When the code $C$ is chosen uniformly at random, the expected number of its codewords of weight $i$ is asymptotically [14]:

$$W_i(C) = \mathbb{E}[|\{\mathbf{c} \in C \mid |\mathbf{c}| = i\}|] = \frac{\binom{n}{i} (q-1)^i}{q^{n-k}}.$$

The actual number of codewords of a specific weight might differ for structured codes. If this difference is measurable, this could be used to distinguish a given code $C$ from random.

## 2.2 Decoding Problem

The decoding problem over $\mathbf{F}_q$ is defined as follows:
NOTATION

$\mathbf{F}_q$ The q-ary finite field

$\mathbf{x} \in \mathbf{F}_q^n$ $\mathbf{x} = (x_0, \dots, x_n)_{0 \le i < n} \in \mathbf{F}_q^n$, vectors generally use bold letters

$|\mathbf{x}|$ Hamming weight of $\mathbf{x} \in \mathbf{F}_q^n$, $|\mathbf{x}| = |\{i, 0 \le i < n \mid x_i \neq 0\}|$

$\mathcal{E}_{q; n, t}$ $\mathcal{E}_{q; n, t} = \{\mathbf{e} \in \mathbf{F}_q^n, |\mathbf{e}| = t\}$

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

$\mathbf{M} \in \mathbf{F}_q^{r \times n}$ $(M_{i,j})_{0 \le i < r, 0 \le j < n}$, $r \times n$ matrix over $\mathbf{F}_q$

$\langle \mathbf{M} \rangle$ The vector space spanned by the rows of matrix $\mathbf{M}$

A matrix $\mathbf{M} \in \mathbf{F}_q^{r \times n}$ is in systematic form if its writes as $\mathbf{M} = (\mathbf{I}_d | \mathbf{R})$ where $\mathbf{I}_d$ is the $r \times r$ identity matrix

Reduced row echelon form

A matrix in $\mathbf{F}_q^{r \times n}$ is in reduced row echelon form if its $r$ leftmost independent columns form an identity matrix

$\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} \in \mathbf{F}_q^{r \times n}$, $\mathbf{x} \in \mathbf{F}_q^n$, $\mathbf{M} = \mathbf{F}_q^{r \times n}$

$\mathcal{S}_n$ Group of permutations of $\{0, \dots, n - 1\}$

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

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

$\mathcal{X}^{\pi} = \{\mathbf{x}^{\pi} \mid \mathbf{x} \in \mathcal{X}\}$, $\mathcal{X} \subset \mathbf{F}_q^n$, $\pi \in \mathcal{S}_n$

## 2.1 Error Correcting Code

A q-ary linear $[n, k]$ code $C$ is a $k$-dimensional subspace of $\mathbf{F}_q^n$. A *generator matrix* $\mathbf{G} \in \mathbf{F}_q^{k \times n}$ of $C$ is such that $\langle \mathbf{G} \rangle = C$ and a *parity check matrix* $\mathbf{H} \in \mathbf{F}_q^{(n-k) \times n}$ of $C$ is such that $\langle \mathbf{H} \rangle^{\perp} = C$, i.e.

$$C = \{\mathbf{x}\mathbf{G} \mid \mathbf{x} \in \mathbf{F}_q^k\} \text{ and } C = \{\mathbf{y} \in \mathbf{F}_q^n \mid \mathbf{y}\mathbf{H}^{\top} = 0\}.$$

For any $\mathbf{y} \in \mathbf{F}_q^n$ the quantity $\mathbf{y}\mathbf{H}^{\top}$ is called the *syndrome* of $\mathbf{y}$ (relatively to $\mathbf{H}$). The *dual code* of $C$ is $C^{\perp} = \langle \mathbf{H} \rangle$, the orthogonal of $C$.

*Weight Distribution.* When the code $C$ is chosen uniformly at random, the expected number of its codewords of weight $i$ is asymptotically [14]:

$$W_i(C) = \mathbb{E}[|\{\mathbf{c} \in C \mid |\mathbf{c}| = i\}|] = \frac{\binom{n}{i} (q-1)^i}{q^{n-k}}.$$

The actual number of codewords of a specific weight might differ for structured codes. If this difference is measurable, this could be used to distinguish a given code $C$ from random.

## 2.2 Decoding Problem

The decoding problem over $\mathbf{F}_q$ is defined as follows:
**Problem 1 (Decoding Problem – DP(q; n, k, t)).** A finite field $\mathbf{F}_q$ and three integers $n, k, t$ such that $n > k > 0$ and $0 \le t \le n$.

**Instance:** $(\mathbf{H}, \mathbf{s}) \in \mathbf{F}_q^{(n-k) \times n} \times \mathbf{F}_q^{n-k}$

**Solution:** $\mathbf{e} \in \mathbf{F}_q^n$ such that $|\mathbf{e}| = t$ and $\mathbf{e}\mathbf{H}^\top = \mathbf{s}$.

We denote $\text{Dec}(q; \mathbf{H}, \mathbf{s}, t)$ an instance of the above problem and also, for convenience, the set of its solutions.

The problem $\text{DP}(q; n, k, t)$ is hard if solving $\text{Dec}(q; \mathbf{H}, \mathbf{s}, t)$ is hard on average with $\mathbf{H}$ uniformly distributed in $\mathbf{F}_q^{(n-k) \times n}$ and $\mathbf{s} = \mathbf{x}\mathbf{H}^\top$ with $\mathbf{x}$ uniformly distributed in $\mathcal{E}_{q;n,t}$, the set of words of weight $t$. When the cardinality of $\mathcal{E}_{q;n,t}$ is (sufficiently) larger than $q^{n-k}$, this is the same as having $\mathbf{s}$ uniformly distributed $\mathbf{F}_q^{n-k}$, see for instance [14, §2.5].

In practice, when $k/n$ and $t/n$ are positive constants, the best known algorithms have an average complexity exponential in $n$ when $t < \frac{q-1}{q}(n-k)$ or $t > k + \frac{q-1}{q}(n-k)$ and polynomial in $n$ when $\frac{q-1}{q}(n-k) \le t \le k + \frac{q-1}{q}(n-k)$.

**Codeword Finding.** Finding codewords of given weight correspond to instances of DP with a zero syndrome $\mathbf{s}$. This problem is also hard and, in practice and in the general case, solvers are the same as for DP.

**Decoding One Out of Many.** The variant of the decoding problem with multiple instances is relevant for the security of code-based signature schemes. This problem was considered in the binary case in [21, 28].

**Problem 2 (DOOM Problem – $\text{DP}_N(q; n, k, t)$).** A finite $\mathbf{F}_q$ field and three integers $n, k, t$ such that $n > k > 0$ and $0 \le t \le n$. A number $N > 0$ of instances.

**Instance:** $(\mathbf{H}, \mathbf{s}_1, \dots, \mathbf{s}_N) \in \mathbf{F}_q^{(n-k) \times n} \times (\mathbf{F}_q^{n-k})^N$

**Solution:** $\mathbf{e} \in \mathbf{F}_q^n$ such that $|\mathbf{e}| = t$ and $\mathbf{e}\mathbf{H}^\top \subset \{\mathbf{s}_1, \dots, \mathbf{s}_N\}$.

By extension, we denote $\text{DP}_\infty(q; n, k, t)$ the unlimited DOOM problem in which the solver is free to decide the value of $N$. If we denote $\text{WF}_N$ the average computational effort for solving $\text{DP}_N(q; n, k, t)$, we have $\text{WF}_N \ge \max(N, \text{WF}_1/N)$ and it follows that $\text{WF}_\infty \ge \sqrt{\text{WF}_1}$. The unlimited DOOM problem cannot be easy if the corresponding Decoding Problem is hard.

## 2.3 Generalized Ternary ($U|U + V$) Code

We consider integers $n, k, k_U, k_V$ with $n$ even such that $n > k > 0$, $k = k_U + k_V$, $0 < k_U < n/2$, and $0 < k_V < n/2$. Let **a**, **b**, **c**, **d** denote vectors in $\mathbf{F}_3^{n/2}$ such that

$$ \forall i, 0 \le i < n/2, \begin{cases} a_ic_i \neq 0 \\ a_id_i - b_ic_i \neq 0 \end{cases} \qquad (1) $$

Let $\mathbf{H}_U \in \mathbf{F}_3^{(\frac{n}{2}-k_U) \times \frac{n}{2}}$ and $\mathbf{H}_V \in \mathbf{F}_3^{(\frac{n}{2}-k_V) \times \frac{n}{2}}$ denote parity check matrices of the ternary linear codes $U$ and $V$ of length $n/2$ and dimension respectively $k_U$ and $k_V$.
**Problem 1 (Decoding Problem – DP(q; n, k, t)).** A finite field $\mathbf{F}_q$ and three integers $n, k, t$ such that $n > k > 0$ and $0 \le t \le n$.

**Instance:** $(\mathbf{H}, \mathbf{s}) \in \mathbf{F}_q^{(n-k) \times n} \times \mathbf{F}_q^{n-k}$

**Solution:** $\mathbf{e} \in \mathbf{F}_q^n$ such that $|\mathbf{e}| = t$ and $\mathbf{e}\mathbf{H}^\top = \mathbf{s}$.

We denote $\text{Dec}(q; \mathbf{H}, \mathbf{s}, t)$ an instance of the above problem and also, for convenience, the set of its solutions.

The problem $\text{DP}(q; n, k, t)$ is hard if solving $\text{Dec}(q; \mathbf{H}, \mathbf{s}, t)$ is hard on average with $\mathbf{H}$ uniformly distributed in $\mathbf{F}_q^{(n-k) \times n}$ and $\mathbf{s} = \mathbf{x}\mathbf{H}^\top$ with $\mathbf{x}$ uniformly distributed in $\mathcal{E}_{q;n,t}$, the set of words of weight $t$. When the cardinality of $\mathcal{E}_{q;n,t}$ is (sufficiently) larger than $q^{n-k}$, this is the same as having $\mathbf{s}$ uniformly distributed $\mathbf{F}_q^{n-k}$, see for instance [14, §2.5].

In practice, when $k/n$ and $t/n$ are positive constants, the best known algorithms have an average complexity exponential in $n$ when $t < \frac{q-1}{q}(n-k)$ or $t > k + \frac{q-1}{q}(n-k)$ and polynomial in $n$ when $\frac{q-1}{q}(n-k) \le t \le k + \frac{q-1}{q}(n-k)$.

**Codeword Finding.** Finding codewords of given weight correspond to instances of DP with a zero syndrome $\mathbf{s}$. This problem is also hard and, in practice and in the general case, solvers are the same as for DP.

**Decoding One Out of Many.** The variant of the decoding problem with multiple instances is relevant for the security of code-based signature schemes. This problem was considered in the binary case in [21, 28].

**Problem 2 (DOOM Problem – $\text{DP}_N(q; n, k, t)$).** A finite $\mathbf{F}_q$ field and three integers $n, k, t$ such that $n > k > 0$ and $0 \le t \le n$. A number $N > 0$ of instances.

**Instance:** $(\mathbf{H}, \mathbf{s}_1, \dots, \mathbf{s}_N) \in \mathbf{F}_q^{(n-k) \times n} \times (\mathbf{F}_q^{n-k})^N$

**Solution:** $\mathbf{e} \in \mathbf{F}_q^n$ such that $|\mathbf{e}| = t$ and $\mathbf{e}\mathbf{H}^\top \subset \{\mathbf{s}_1, \dots, \mathbf{s}_N\}$.

By extension, we denote $\text{DP}_\infty(q; n, k, t)$ the unlimited DOOM problem in which the solver is free to decide the value of $N$. If we denote $\text{WF}_N$ the average computational effort for solving $\text{DP}_N(q; n, k, t)$, we have $\text{WF}_N \ge \max(N, \text{WF}_1/N)$ and it follows that $\text{WF}_\infty \ge \sqrt{\text{WF}_1}$. The unlimited DOOM problem cannot be easy if the corresponding Decoding Problem is hard.

## 2.3 Generalized Ternary ($U|U+V$) Code

We consider integers $n, k, k_U, k_V$ with $n$ even such that $n > k > 0$, $k = k_U + k_V$, $0 < k_U < n/2$, and $0 < k_V < n/2$. Let **a**, **b**, **c**, **d** denote vectors in $\mathbf{F}_3^{n/2}$ such that

$$ \forall i, 0 \le i < n/2, \begin{cases} a_ic_i \neq 0 \\ a_id_i - b_ic_i \neq 0 \end{cases} \qquad (1) $$

Let $\mathbf{H}_U \in \mathbf{F}_3^{(\frac{n}{2}-k_U) \times \frac{n}{2}}$ and $\mathbf{H}_V \in \mathbf{F}_3^{(\frac{n}{2}-k_V) \times \frac{n}{2}}$ denote parity check matrices of the ternary linear codes $U$ and $V$ of length $n/2$ and dimension respectively $k_U$ and $k_V$.
$k_V$. The generalized ternary $(U|U+V)$ code $\mathcal{C}$ associated to $(\mathbf{H}_U, \mathbf{H}_V, \mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d})$ admits the following parity check matrix

$$ \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{a} \star \mathbf{H}_V \end{array} \right) \in \mathbf{F}_3^{(n-k) \times n}. \qquad (2) $$

**Dual Code.** If $\mathcal{C}$ is a generalized ternary $(U|U+V)$ code $\mathcal{C}$ associated to $(\mathbf{H}_U, \mathbf{H}_V, \mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d})$, then its dual is also a generalized $(U|U+V)$ code, associated to $(\mathbf{G}_V, \mathbf{G}_U, -\mathbf{c}, \mathbf{d}, \mathbf{a}, -\mathbf{b})$ where $\mathbf{G}_V$ and $\mathbf{G}_U$ are generator matrices of $V$ and $U$, that is, equivalently, parity check matrices of the dual codes $V^\perp$ and $U^\perp$.

**Decoder for Large Weights.** A probabilistic decoding procedure for $\mathcal{C}$ is described in [15]:

$$ \Phi_{C,w}: \mathbf{F}_3^{n-k} \to \mathbf{F}_3^n \\ s \mapsto e \quad \text{such that } e\mathbf{H}^\top = s, |e| = w. \qquad (3) $$

It makes use of the $(U|U+V)$ structure and runs in polynomial time for some weight $w > k + \frac{2}{3}(n-k)$ such that the decoding problem DP(3; $n, k, w$) is hard.

## 2.4 The Wave Signature Scheme

1. Main parameters: code-length $n$, dimension $k$, error weight $w$,

2. Public Key: $\mathbf{H}_{\text{pub}} \in \mathbf{F}_3^{(n-k) \times n}$,

3. Signature: $\mathbf{e} \in \mathbf{F}_3^n$ such that $|\mathbf{e}| = w$ and $\mathbf{e}\mathbf{H}_{\text{pub}}^\top = \text{Hash}(\text{Message}) \in \mathbf{F}_3^{(n-k)}$.

The matrix $\mathbf{H}_{\text{pub}}$ is the reduced row echelon form of the parity check matrix of a generalized ternary $(U|U+V)$ code $\mathcal{C}$ of length $n$ and dimension $k$, randomly permuted by $\pi \in S_n$. The secret key is a decoding procedure, $\Psi: \mathbf{F}_3^{n-k} \to \mathbf{F}_3^n$, to solve $\text{Dec}(\mathbf{H}_{\text{pub}}, \mathbf{s}, w)$ which easily derives from $\Phi_{C,w}$, see (3), and the permutation $\pi$. It involves the parameters $k_U, k_V$ for the $(U|U+V)$ structure, see §2.3, and $g$, called the *gap*, which is used by the decoder. We will refer to the integers $(k_U, k_V, g)$ as the secondary parameters, they are public but are only used for signing.

4. The secondary parameters $(k_U, k_V, g)$ verify

$$ k_U = g + \frac{3}{2}w - n, k_V = k - k_U \text{ and } 0 \le g \le \frac{\lambda}{\log_2 3} \qquad (4) $$

where $\lambda$ is the security parameter<fnref n="1" />.

An additional condition is required to build a secure signature scheme: essentially the distribution of $\Psi(\mathbf{s})$, or equivalently of $\Phi_{C,w}(\mathbf{s})$, must be uniform over $\mathcal{E}_{3;n,w}$ when the input $\mathbf{s}$ is uniformly distributed over $\mathbf{F}_3^{n-k}$. This involves a choice of

<footnote n="1">¹ e.g. $\lambda = 128$ corresponds to a scheme about as secure as AES-128</footnote>
$k_V$. The generalized ternary $(U|U+V)$ code $\mathcal{C}$ associated to $(\mathbf{H}_U, \mathbf{H}_V, \mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d})$ admits the following parity check matrix

$$ \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{a} \star \mathbf{H}_V \end{array} \right) \in \mathbf{F}_3^{(n-k) \times n}. \qquad (2) $$

**Dual Code.** If $\mathcal{C}$ is a generalized ternary $(U|U+V)$ code $\mathcal{C}$ associated to $(\mathbf{H}_U, \mathbf{H}_V, \mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d})$, then its dual is also a generalized $(U|U+V)$ code, associated to $(\mathbf{G}_V, \mathbf{G}_U, -\mathbf{c}, \mathbf{d}, \mathbf{a}, -\mathbf{b})$ where $\mathbf{G}_V$ and $\mathbf{G}_U$ are generator matrices of $V$ and $U$, that is, equivalently, parity check matrices of the dual codes $V^\perp$ and $U^\perp$.

**Decoder for Large Weights.** A probabilistic decoding procedure for $\mathcal{C}$ is described in [15]:

$$ \Phi_{C,w}: \mathbf{F}_3^{n-k} \to \mathbf{F}_3^n \\ s \mapsto e \quad \text{such that } e\mathbf{H}^\top = s, |e| = w. \qquad (3) $$

It makes use of the $(U|U+V)$ structure and runs in polynomial time for some weight $w > k + \frac{2}{3}(n-k)$ such that the decoding problem DP(3; n, k, w) is hard.

## 2.4 The Wave Signature Scheme

1. Main parameters: code-length $n$, dimension $k$, error weight $w$,

2. Public Key: $\mathbf{H}_{\text{pub}} \in \mathbf{F}_3^{(n-k) \times n}$,

3. Signature: $\mathbf{e} \in \mathbf{F}_3^n$ such that $|\mathbf{e}| = w$ and $\mathbf{e}\mathbf{H}_{\text{pub}}^\top = \text{Hash}(\text{Message}) \in \mathbf{F}_3^{(n-k)}$.

The matrix $\mathbf{H}_{\text{pub}}$ is the reduced row echelon form of the parity check matrix of a generalized ternary $(U|U+V)$ code $\mathcal{C}$ of length $n$ and dimension $k$, randomly permuted by $\pi \in S_n$. The secret key is a decoding procedure, $\Psi: \mathbf{F}_3^{n-k} \to \mathbf{F}_3^n$, to solve $\text{Dec}(\mathbf{H}_{\text{pub}}, \mathbf{s}, w)$ which easily derives from $\Phi_{C,w}$, see (3), and the permutation $\pi$. It involves the parameters $k_U, k_V$ for the $(U|U+V)$ structure, see §2.3, and $g$, called the *gap*, which is used by the decoder. We will refer to the integers $(k_U, k_V, g)$ as the secondary parameters, they are public but are only used for signing.

4. The secondary parameters $(k_U, k_V, g)$ verify

$$ k_U = g + \frac{3}{2}w - n, k_V = k - k_U \text{ and } 0 \le g \le \frac{\lambda}{\log_2 3} \qquad (4) $$

where $\lambda$ is the security parameter<fnref n="1" />.

An additional condition is required to build a secure signature scheme: essentially the distribution of $\Psi(\mathbf{s})$, or equivalently of $\Phi_{C,w}(\mathbf{s})$, must be uniform over $\mathcal{E}_{3;n,w}$ when the input $\mathbf{s}$ is uniformly distributed over $\mathbf{F}_3^{n-k}$. This involves a choice of

<footnote n="1">¹ e.g. $\lambda = 128$ corresponds to a scheme about as secure as AES-128</footnote>
internal distributions and possibly some rejection sampling. It is shown in [15] that with a gap $g = \lambda/\log_2 3$ it is possible to implement the decoder so that the statistical distance between the distribution of its output and the uniform distribution over $\mathcal{E}_{3;n,w}$ do not exceed $2^{-\lambda}$.

Depending on the adversarial model and on the security assumptions, the value of the gap $g$ might be lower than $\lambda/\log_2 3$ without reducing the computational security. We will consider various scenarios for the value of $g$ ranging from 0 to $\lambda/\log_2 3$ and examine how they impact the scheme parameters. This is discussed further in §4.3.

**Wave Security Reduction.** With the above notations, and assuming that the decoder's output is properly distributed, the Wave signature scheme is EUF-CMA secure under the following assumptions:

1. The unlimited DOOM problem $DP_{\infty}(3; n, k, w)$ is hard.

2. Permuted generalized ternary $(U|U+V)$ codes of parameters $(n, k_U, k_V)$ are computationally indistinguishable from random.

## 2.5 Weight Distribution and $(U|U+V)$-Specific Codewords.

Let $\mathcal{C}$ denote a ternary generalized $(U|U+V)$ code, presumably used as an instance of Wave, associated to $(H_U, H_V, \mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d})$. We examine below how its weight distribution differs from that of a random code. We denote $U$ and $V$ the codes of respective parity check matrices $H_U$ and $H_V$. We call respectively type-$U$ and type-$V$ codewords, the elements of the following subcodes of $\mathcal{C}$

$$ \mathcal{U}(\mathcal{C}) = \{(\mathbf{a} \star \mathbf{u}, \mathbf{c} \star \mathbf{u}) \mid \mathbf{u} \in U\}, $$

$$ \mathcal{V}(\mathcal{C}) = \{(\mathbf{b} \star \mathbf{v}, \mathbf{d} \star \mathbf{v}) \mid \mathbf{v} \in V\}. $$

We refer to $\mathbf{u}$ and $\mathbf{v}$ above as the component words. Except for the contribution of the type-$U$ and type-$V$ codewords, the weight distribution of $\mathcal{C}$ is as for a random ternary linear $[n, k]$ code, see [13] for precise statements. We partition type-$U$ and type-$V$ codewords according to the Hamming weight of their component words and define

$$ \mathcal{U}(\mathcal{C}, j) = \{(\mathbf{a} \star \mathbf{u}, \mathbf{c} \star \mathbf{u}) \mid \mathbf{u} \in U, |\mathbf{u}| = j\}, $$

$$ \mathcal{V}(\mathcal{C}, j) = \{(\mathbf{b} \star \mathbf{v}, \mathbf{d} \star \mathbf{v}) \mid \mathbf{v} \in V, |\mathbf{v}| = j\}, $$

whose respective expected cardinalities are

$$ \mathbb{E}[|\mathcal{U}(\mathcal{C}, j)|] = W_j(U) = \frac{\binom{n/2}{j} 2^j}{3^{n/2-k_U}} \quad \text{and} \quad \mathbb{E}[|\mathcal{V}(\mathcal{C}, j)|] = W_j(V) = \frac{\binom{n/2}{j} 2^j}{3^{n/2-k_V}}. $$

The words of $\mathcal{U}(\mathcal{C}, j)$ all have a Hamming weight $t = 2j$ while the words of $\mathcal{V}(\mathcal{C}, j)$ have a Hamming weight $j \le t \le 2j$ depending on the intersection of
internal distributions and possibly some rejection sampling. It is shown in [15] that with a gap $g = \lambda/\log_2 3$ it is possible to implement the decoder so that the statistical distance between the distribution of its output and the uniform distribution over $\mathcal{E}_{3;n,w}$ do not exceed $2^{-\lambda}$.

Depending on the adversarial model and on the security assumptions, the value of the gap $g$ might be lower than $\lambda/\log_2 3$ without reducing the computational security. We will consider various scenarios for the value of $g$ ranging from 0 to $\lambda/\log_2 3$ and examine how they impact the scheme parameters. This is discussed further in §4.3.

**Wave Security Reduction.** With the above notations, and assuming that the decoder's output is properly distributed, the Wave signature scheme is EUF-CMA secure under the following assumptions:

1. The unlimited DOOM problem $DP_\infty(3; n, k, w)$ is hard.

2. Permuted generalized ternary $(U|U+V)$ codes of parameters $(n, k_U, k_V)$ are computationally indistinguishable from random.

## 2.5 Weight Distribution and $(U|U+V)$-Specific Codewords.

Let $\mathcal{C}$ denote a ternary generalized $(U|U+V)$ code, presumably used as an instance of Wave, associated to $(H_U, H_V, a, b, c, d)$. We examine below how its weight distribution differs from that of a random code. We denote $U$ and $V$ the codes of respective parity check matrices $H_U$ and $H_V$. We call respectively type-$U$ and type-$V$ codewords, the elements of the following subcodes of $\mathcal{C}$

$$ \mathcal{U}(\mathcal{C}) = \{(\mathbf{a} \star \mathbf{u}, \mathbf{c} \star \mathbf{u}) \mid \mathbf{u} \in U\}, $$

$$ \mathcal{V}(\mathcal{C}) = \{(\mathbf{b} \star \mathbf{v}, \mathbf{d} \star \mathbf{v}) \mid \mathbf{v} \in V\}. $$

We refer to $\mathbf{u}$ and $\mathbf{v}$ above as the component words. Except for the contribution of the type-$U$ and type-$V$ codewords, the weight distribution of $\mathcal{C}$ is as for a random ternary linear $[n, k]$ code, see [13] for precise statements. We partition type-$U$ and type-$V$ codewords according to the Hamming weight of their component words and define

$$ \mathcal{U}(\mathcal{C}, j) = \{(\mathbf{a} \star \mathbf{u}, \mathbf{c} \star \mathbf{u}) \mid \mathbf{u} \in U, |\mathbf{u}| = j\}, $$

$$ \mathcal{V}(\mathcal{C}, j) = \{(\mathbf{b} \star \mathbf{v}, \mathbf{d} \star \mathbf{v}) \mid \mathbf{v} \in V, |\mathbf{v}| = j\}, $$

whose respective expected cardinalities are

$$ \mathbb{E}[|\mathcal{U}(\mathcal{C}, j)|] = W_j(U) = \frac{\binom{n/2}{j} 2^j}{3^{n/2-k_U}} \quad \text{and} \quad \mathbb{E}[|\mathcal{V}(\mathcal{C}, j)|] = W_j(V) = \frac{\binom{n/2}{j} 2^j}{3^{n/2-k_V}}. $$

The words of $\mathcal{U}(\mathcal{C}, j)$ all have a Hamming weight $t = 2j$ while the words of $\mathcal{V}(\mathcal{C}, j)$ have a Hamming weight $j \le t \le 2j$ depending on the intersection of
the component word support with the supports of **b** and **d**. If (**a**, **b**, **c**, **d**) are uniformly distributed with the condition (1), then, on average, three quarters of the $b_i$ and $d_i$ are non zero. So the typical weight of a word of $V(C, j)$ is $t = 3j/2$.

Codewords of type-*U* or type-*V* are very few, less than $3^{k_U} + 3^{k_V}$ among $3^k = 3^{k_U+k_V}$ codewords. However, for a particular weight *t*, it may happen that most codewords of weight *t* of type-*U* or type-*V*. For typical Wave parameters it may happen, see Figure 1, that, either for small or for large values of *t*, type-*U* codewords dominate. We also observe in Figure 1 that the type-*V* codewords never dominate, regardless of the weight. This also holds for other possible choices of code parameters $k_U, k_V$ for Wave.

<figure><img src="image_1.png" /><figcaption>**Fig. 1.** (Expected) Number of codewords of weight *t* in *C* (black), of type-*U* (blue), or type-*V* (red), for Wave parameters $k_U = 0.693 \cdot \frac{n}{2}$, $k_V = 0.307 \cdot \frac{n}{2}$, $k = \frac{n}{2}$ and $w = 0.894 \cdot n$</figcaption></figure>

*Example:* Lets consider words of weight $t = 0.209 \cdot n$ in a ternary ($U|U+V$) code $C$ of length $n$, dimension $k = 0.5 \cdot n$, and $k_U = 0.693 \cdot \frac{n}{2}$ (the vertical line in Figure 1). We expect to find $2^{0.231 \cdot n}$ words of weight $t/2$ in a random ternary linear $[n/2, k_U]$ code (the blue curve) and “only” $2^{0.156 \cdot n}$ in a random ternary linear $[n, k]$ code (the black curve). From [13], the weight of codewords which are not of type-*U* or type-*V* is distributed as for a random code, so, if one can somehow sample a (random) word of weight $t = 0.209 \cdot n$ in *C* as above, it will almost certainly be a type-*U* codeword.
the component word support with the supports of **b** and **d**. If (**a**, **b**, **c**, **d**) are uniformly distributed with the condition (1), then, on average, three quarters of the $b_i$ and $d_i$ are non zero. So the typical weight of a word of $V(C, j)$ is $t = 3j/2$.

Codewords of type-*U* or type-*V* are very few, less than $3^{k_U} + 3^{k_V}$ among $3^k = 3^{k_U+k_V}$ codewords. However, for a particular weight *t*, it may happen that most codewords of weight *t* of type-*U* or type-*V*. For typical Wave parameters it may happen, see Figure 1, that, either for small or for large values of *t*, type-*U* codewords dominate. We also observe in Figure 1 that the type-*V* codewords never dominate, regardless of the weight. This also holds for other possible choices of code parameters $k_U, k_V$ for Wave.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** (Expected) Number of codewords of weight *t* in *C* (black), of type-*U* (blue), or type-*V* (red), for Wave parameters $k_U = 0.693 \cdot \frac{n}{2}$, $k_V = 0.307 \cdot \frac{n}{2}$, $k = \frac{n}{2}$ and $w = 0.894 \cdot n$</figcaption></figure>

*Example:* Lets consider words of weight $t = 0.209 \cdot n$ in a ternary ($U|U+V$) code $C$ of length $n$, dimension $k = 0.5 \cdot n$, and $k_U = 0.693 \cdot \frac{n}{2}$ (the vertical line in Figure 1). We expect to find $2^{0.231 \cdot n}$ words of weight $t/2$ in a random ternary linear $[n/2, k_U]$ code (the blue curve) and “only” $2^{0.156 \cdot n}$ in a random ternary linear $[n, k]$ code (the black curve). From [13], the weight of codewords which are not of type-*U* or type-*V* is distributed as for a random code, so, if one can somehow sample a (random) word of weight $t = 0.209 \cdot n$ in *C* as above, it will almost certainly be a type-*U* codeword.
## 3 q-ary Information Set Decoding (ISD)

Information Set Decoding was first introduced by Prange in 1962 [27] and is one of the main algorithmic techniques to solve the decoding problem. It was later improved in many ways, in particular: birthday paradox [29], representation technique in [23], nearest neighbors in [24]. The current state-of-the-art in the binary case is [5, 6, 9]. Variants using the Generalized Birthday Algorithm [31] (GBA) are also of interest. GBA was first used for decoding in [11], and for some regime of parameters it can be efficiently used within ISD. This is the case in particular for the decoding of large weights in the non binary case [7].

Few contributions are available in the q-ary case, let us mention [26, 8, 7]. The interested reader may also refer to [14, Ch. 3] for a comprehensive survey of ISD for any alphabet size. In general the analysis is very similar to the binary case, we briefly revisit that below. Note that, as remarked in [26], there is a factor $\sqrt{q-1}$ to be gained that derives from the linearity of the problem: the identity $e_0H_0^T = s_0$ remains true up to a non-zero factor, and this can be used to speed-up the search. We will ignore this in the sequel as we only consider complexity up to a polynomial factor.

### 3.1 An ISD Framework

We will describe and analyze several ISD variants that fit in the framework described in [18]. This is the case of most known variants, with the notable exception of the latest and best known asymptotic variants [5, 6, 9]. Those variants have not been generalized yet to the non-binary case, and moreover they are not considered as practical. This could change in the future.

The ISD framework we consider here is described as follows. For a choice of parameters $0 \le \ell \le n-k$ and $0 \le p \le t$, solve $\text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$ by repeating:

1. Pick a permutation $\sigma$ uniformly in $S_n$ and compute $(\mathbf{H}, \mathbf{H}', \mathbf{s}, \mathbf{s}') \in \mathbf{F}_q^{\ell \times (k+\ell)} \times \mathbf{F}_q^{(n-k-\ell) \times (k+\ell)} \times \mathbf{F}_q^{\ell} \times \mathbf{F}_q^{n-k-\ell}$ such that for some non singular matrix $\mathbf{U} \in \mathbf{F}_q^{(n-k) \times (n-k)}$,

$$ \mathbf{U}\mathbf{H}_0^\sigma = \left( \frac{\text{Id}_{n-k-\ell}}{0} \middle| \frac{\mathbf{H}'}{\mathbf{H}} \right) = \mathbf{U}\mathbf{s}_0^T = \left( \frac{\mathbf{s}'^T}{\mathbf{s}^T} \right). \qquad (5) $$

2. Use a SubISD routine to compute $\mathcal{E}_{\text{isd}} \subset \mathcal{E} = \{\mathbf{e} \in \mathcal{E}_{q;k+\ell,p}, |\mathbf{e}| = p, \mathbf{e}\mathbf{H}^T = \mathbf{s}\}$.

3. For all $\mathbf{e} \in \mathcal{E}_{\text{isd}}$, check $\mathbf{e}_0 = (\mathbf{e}, \mathbf{s}' - \mathbf{e}\mathbf{H}'^T)$.

Variants of ISD differ in the SubISD routine used at the second step. Every $e_0$ of weight $t$ at step 3 is a valid solution, the algorithm may either exit there, or continue until a prescribed number of iterations is executed. ISD algorithms are probabilistic and the successive iterations are independent. We will view the sets $\mathcal{E}$ and $\mathcal{E}_{\text{isd}}$ of step 2 as random variables. For convenience, we denote

$$ \mathcal{F} = \{ (\mathbf{e}, \mathbf{s}' - \mathbf{e}\mathbf{H}'^T)^{-1}, \mathbf{e} \in \mathcal{E} \} \quad \text{and} \quad \mathcal{F}_{\text{isd}} = \{ (\mathbf{e}, \mathbf{s}' - \mathbf{e}\mathbf{H}'^T)^{-1}, \mathbf{e} \in \mathcal{E}_{\text{isd}} \} \subset \mathcal{F}. $$
## 3 q-ary Information Set Decoding (ISD)

Information Set Decoding was first introduced by Prange in 1962 [27] and is one of the main algorithmic techniques to solve the decoding problem. It was later improved in many ways, in particular: birthday paradox [29], representation technique in [23], nearest neighbors in [24]. The current state-of-the-art in the binary case is [5, 6, 9]. Variants using the Generalized Birthday Algorithm [31] (GBA) are also of interest. GBA was first used for decoding in [11], and for some regime of parameters it can be efficiently used within ISD. This is the case in particular for the decoding of large weights in the non binary case [7].

Few contributions are available in the q-ary case, let us mention [26, 8, 7]. The interested reader may also refer to [14, Ch. 3] for a comprehensive survey of ISD for any alphabet size. In general the analysis is very similar to the binary case, we briefly revisit that below. Note that, as remarked in [26], there is a factor $\sqrt{q-1}$ to be gained that derives from the linearity of the problem: the identity $e_0H_0^T = s_0$ remains true up to a non-zero factor, and this can be used to speed-up the search. We will ignore this in the sequel as we only consider complexity up to a polynomial factor.

### 3.1 An ISD Framework

We will describe and analyze several ISD variants that fit in the framework described in [18]. This is the case of most known variants, with the notable exception of the latest and best known asymptotic variants [5, 6, 9]. Those variants have not been generalized yet to the non-binary case, and moreover they are not considered as practical. This could change in the future.

The ISD framework we consider here is described as follows. For a choice of parameters $0 \le \ell \le n-k$ and $0 \le p \le t$, solve $\text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$ by repeating:

1. Pick a permutation $\sigma$ uniformly in $S_n$ and compute $(\mathbf{H}, \mathbf{H}', \mathbf{s}, \mathbf{s}') \in \mathbf{F}_q^{\ell \times (k+\ell)} \times \mathbf{F}_q^{(n-k-\ell) \times (k+\ell)} \times \mathbf{F}_q^{\ell} \times \mathbf{F}_q^{n-k-\ell}$ such that for some non singular matrix $\mathbf{U} \in \mathbf{F}_q^{(n-k) \times (n-k)}$,

$$ \mathbf{U}\mathbf{H}_0^\sigma = \left( \frac{\text{Id}_{n-k-\ell}}{0} \middle| \frac{\mathbf{H}'}{\mathbf{H}} \right) = \mathbf{U}\mathbf{s}_0^T = \left( \frac{\mathbf{s}'^T}{\mathbf{s}^T} \right). \qquad (5) $$

2. Use a SubISD routine to compute $\mathcal{E}_{\text{isd}} \subset \mathcal{E} = \{\mathbf{e} \in \mathcal{E}_{q;k+\ell,p}, |\mathbf{e}| = p, \mathbf{e}\mathbf{H}^T = \mathbf{s}\}$.

3. For all $\mathbf{e} \in \mathcal{E}_{\text{isd}}$, check $\mathbf{e}_0 = (\mathbf{e}, \mathbf{s}' - \mathbf{e}\mathbf{H}'^T)$.

Variants of ISD differ in the SubISD routine used at the second step. Every $e_0$ of weight $t$ at step 3 is a valid solution, the algorithm may either exit there, or continue until a prescribed number of iterations is executed. ISD algorithms are probabilistic and the successive iterations are independent. We will view the sets $\mathcal{E}$ and $\mathcal{E}_{\text{isd}}$ of step 2 as random variables. For convenience, we denote

$$ \mathcal{F} = \{ (\mathbf{e}, \mathbf{s}' - \mathbf{e}\mathbf{H}'^T)^{-1}, \mathbf{e} \in \mathcal{E} \} \quad \text{and} \quad \mathcal{F}_{\text{isd}} = \{ (\mathbf{e}, \mathbf{s}' - \mathbf{e}\mathbf{H}'^T)^{-1}, \mathbf{e} \in \mathcal{E}_{\text{isd}} \} \subset \mathcal{F}. $$
The first set $\mathcal{F}$ above has, a priori, the same size as $\mathcal{E}$ and is the maximal search space for a particular iteration. If $\mathbf{x}$ belongs to $\text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$, then the permutation $\sigma$ is “good for $\mathbf{x}$” if $\mathbf{x} \in \mathcal{F}$. The second set $\mathcal{F}_{\text{isd}}$ is possibly smaller than $\mathcal{F}$ and is the effective search space for a particular iteration and a particular SubISD routine, generally $\mathcal{F}_{\text{isd}}$ is close to $\mathcal{F}$.

Let $\mathcal{A}$ denote a variant of ISD, we define the following three quantities

1. For all $\mathbf{x} \in \mathbf{F}_q^n$ such that $\mathbf{x}\mathbf{H}_0^T = \mathbf{s}_0$, we define the probability

$$ \pi_{\ell,p}(\mathbf{x}) = \Pr(\mathbf{x} \in \mathcal{F}) = \frac{\binom{n-k-\ell}{|\mathbf{x}|-p}\binom{k+\ell}{p}}{\binom{n}{|\mathbf{x}|}}, \quad \pi_{\ell,p}(i) = \frac{\binom{n-k-\ell}{i-p}\binom{k+\ell}{p}}{\binom{n}{i}}. $$

As it only depends of the weight of $\mathbf{x}$ we overload the notation and define $\pi_{\ell,p}(|\mathbf{x}|) = \pi_{\ell,p}(\mathbf{x})$. This quantity is the same for all ISD variants. It is in fact the probability that the permutation $\sigma$ drawn at step 1 properly splits the support of $\mathbf{x}$ with exactly $p$ non-zero coordinates in the $k+\ell$ rightmost coordinates after permutation.

2. For a given SubISD routine at step 2, we define the decimation factor as

$$ \mu_{\mathcal{A}} = \frac{\mathbb{E}[|\mathcal{E}_{\text{isd}}|]}{\mathbb{E}[|\mathcal{E}|]} \le 1. $$

This is the proportion of solutions of the decoding problem $\text{Dec}(\mathbf{H}, \mathbf{s}, p)$ that are discovered on average by the SubISD routine at step 2. The decimation factor is also equal to $\mathbb{E}[|\mathcal{F}_{\text{isd}}|]/\mathbb{E}[|\mathcal{F}|]$ and this quantity is independent of the target weight $t$.

3. The average cost of one iteration is denoted $C_{\mathcal{A}}$. It is also independent of the target weight $t$.

For every particular instance $\mathcal{A}$ of the ISD framework, that is for every choice of $(\ell, p)$ and of the SubISD routine, the computational cost can be estimated, depending on the task that $\mathcal{A}$ should solve (single or multiple targets, see below). The cost will next be minimized over all choices of $(\ell, p)$ and possibly other parameters of the SubISD routine.

**Single Solution.** For any $\mathbf{x} \in \text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$, the probability to discover that particular solution in a particular iteration is

$$ P = \Pr(\mathbf{x} \in \mathcal{F}_{\text{isd}}) = \mu_{\mathcal{A}} \cdot \Pr(\mathbf{x} \in \mathcal{F}) = \mu_{\mathcal{A}} \cdot \pi_{\ell,p}(t) $$

so we expect to make $1/P$ iterations to find $\mathbf{x}$ and the expected computational effort is

$$ \text{WF}_{\mathcal{A}}(n, k, t, 1) = \frac{C_{\mathcal{A}}}{\mu_{\mathcal{A}} \cdot \pi_{\ell,p}(t)} \quad (6) $$

up to a constant factor.
The first set $\mathcal{F}$ above has, a priori, the same size as $\mathcal{E}$ and is the maximal search space for a particular iteration. If $\mathbf{x}$ belongs to $\text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$, then the permutation $\sigma$ is “good for $\mathbf{x}$” if $\mathbf{x} \in \mathcal{F}$. The second set $\mathcal{F}_{\text{isd}}$ is possibly smaller than $\mathcal{F}$ and is the effective search space for a particular iteration and a particular SubISD routine, generally $\mathcal{F}_{\text{isd}}$ is close to $\mathcal{F}$.

Let $\mathcal{A}$ denote a variant of ISD, we define the following three quantities

1. For all $\mathbf{x} \in \mathbf{F}_q^n$ such that $\mathbf{x}\mathbf{H}_0^T = \mathbf{s}_0$, we define the probability

$$ \pi_{\ell,p}(\mathbf{x}) = \Pr(\mathbf{x} \in \mathcal{F}) = \frac{\binom{n-k-\ell}{|\mathbf{x}|-p} \binom{k+\ell}{p}}{\binom{n}{|\mathbf{x}|}}, \quad \pi_{\ell,p}(i) = \frac{\binom{n-k-\ell}{i-p} \binom{k+\ell}{p}}{\binom{n}{i}}. $$

As it only depends of the weight of $\mathbf{x}$ we overload the notation and define $\pi_{\ell,p}(|\mathbf{x}|) = \pi_{\ell,p}(\mathbf{x})$. This quantity is the same for all ISD variants. It is in fact the probability that the permutation $\sigma$ drawn at step 1 properly splits the support of $\mathbf{x}$ with exactly $p$ non-zero coordinates in the $k+\ell$ rightmost coordinates after permutation.

2. For a given SubISD routine at step 2, we define the decimation factor as

$$ \mu_{\mathcal{A}} = \frac{\mathbb{E}[|\mathcal{E}_{\text{isd}}|]}{\mathbb{E}[|\mathcal{E}|]} \le 1. $$

This is the proportion of solutions of the decoding problem $\text{Dec}(\mathbf{H}, \mathbf{s}, p)$ that are discovered on average by the SubISD routine at step 2. The decimation factor is also equal to $\mathbb{E}[|\mathcal{F}_{\text{isd}}|]/\mathbb{E}[|\mathcal{F}|]$ and this quantity is independent of the target weight $t$.

3. The average cost of one iteration is denoted $C_{\mathcal{A}}$. It is also independent of the target weight $t$.

For every particular instance $\mathcal{A}$ of the ISD framework, that is for every choice of $(\ell, p)$ and of the SubISD routine, the computational cost can be estimated, depending on the task that $\mathcal{A}$ should solve (single or multiple targets, see below). The cost will next be minimized over all choices of $(\ell, p)$ and possibly other parameters of the SubISD routine.

**Single Solution.** For any $\mathbf{x} \in \text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$, the probability to discover that particular solution in a particular iteration is

$$ P = \Pr(\mathbf{x} \in \mathcal{F}_{\text{isd}}) = \mu_{\mathcal{A}} \cdot \Pr(\mathbf{x} \in \mathcal{F}) = \mu_{\mathcal{A}} \cdot \pi_{\ell,p}(t) $$

so we expect to make $1/P$ iterations to find $\mathbf{x}$ and the expected computational effort is

$$ \text{WF}_{\mathcal{A}}(n, k, t, 1) = \frac{C_{\mathcal{A}}}{\mu_{\mathcal{A}} \cdot \pi_{\ell,p}(t)} \qquad (6) $$

up to a constant factor.
**Multiple Solutions.** Let $\mathcal{X}$ denote a subset of cardinality $N$ of all solutions of $\text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$. The probability to discover an element of $\mathcal{X}$ in a particular iteration is

$$ P_A(t, N) = \Pr(\mathcal{X} \cap \mathcal{F}_{\text{isd}} \neq \emptyset) \le 1 - \prod_{\mathbf{x} \in \mathcal{X}} (1 - \Pr(\mathbf{x} \in \mathcal{F}_{\text{isd}} \neq \emptyset)) \quad (7) \\ \le 1 - (1 - \mu_A \cdot \pi_{\ell,p}(t))^N \\ \le \min(1, N \cdot \mu_A \cdot \pi_{\ell,p}(t)) $$

so the expected computational effort to find an element of $\mathcal{X}$ is

$$ \text{WF}_{\mathcal{A}}(n, k, t, N) = \frac{C_{\mathcal{A}}}{P_{\mathcal{A}}(t, N)} \ge \frac{C_{\mathcal{A}}}{\min(1, N \cdot \mu_{\mathcal{A}} \cdot \pi_{\ell,p}(t))}. \quad (8) $$

The inequality (7) derives from the union bound. The equality holds when the events "$\mathbf{x} \in \mathcal{F}$" are all independent. In some situation, for instance if $\mathcal{X}$ is a set of type-U codewords as in §2.5, the actual probability might be smaller and the actual computational effort larger.

**Effective Workfactor.** The workfactor formula (6) or (8) depends on the parameters $p$ and $\ell$, and possibly other parameters stemming from the subroutine used in the variant. The effective workfactor corresponds to the choice of parameters that will minimize the formula. The corresponding optimization problem can be difficult and has to be solved for each particular problem, that is for given values of $n$, $k$, $t$, and $N$.

## 3.2 ISD-MMT

The generalization of the MMT algorithm [23] to the $q$-ary case is relatively straightforward. We briefly sketch the algorithm and its analysis in the $q$-ary case, the interested reader may wish to check the relevant literature for a more comprehensive presentation.

We consider the framework of the previous section. After permuting the coordinates and computing a partial Gaussian elimination as in (5), we consider the routine of step 2, which attempts to recover all, or as many as possible, elements of the search space $\mathcal{E} = \{\mathbf{e} \in \mathbf{F}_q^{k+\ell}, |\mathbf{e}| = p, \mathbf{e}\mathbf{H}^T = \mathbf{s}\}$.

We denote $L = \binom{k+\ell}{p} (q-1)^p$ and $L_0 = \binom{(k+\ell)/2}{p/4} (q-1)^{p/4}$. We call syndrome of $\mathbf{y} \in \mathbf{F}_q^{k+\ell}$ the quantity $\mathbf{y}\mathbf{H}^T$. An additional parameter $\ell_2$, $0 \le \ell_2 \le \ell$ is introduced. The routine runs as follows:

1. Build 4 lists of size $L_0$ of words in $\mathbf{F}_q^{k+\ell}$ of weight $p/4$

2. Merge the above lists pairwise to obtain 2 lists of size $L_0^2/q^{\ell_2}$ of words in $\mathbf{F}_q^{k+\ell}$ of weight $p/2$ with a prescribed value on $\ell_2$ coordinates of their syndromes

3. Merge the above 2 lists to obtain a list of size $L_0^4/q^{\ell+\ell_2}$ of words in $\mathbf{F}_q^{k+\ell}$ of weight $p$ with a prescribed value on the other $\ell - \ell_2$ coordinates of their syndromes
**Multiple Solutions.** Let $\mathcal{X}$ denote a subset of cardinality $N$ of all solutions of $\text{Dec}(\mathbf{H}_0, \mathbf{s}_0, t)$. The probability to discover an element of $\mathcal{X}$ in a particular iteration is

$$ P_A(t, N) = \Pr(\mathcal{X} \cap \mathcal{F}_{\text{isd}} \neq \emptyset) \le 1 - \prod_{\mathbf{x} \in \mathcal{X}} (1 - \Pr(\mathbf{x} \in \mathcal{F}_{\text{isd}} \neq \emptyset)) \quad (7) \\ \le 1 - (1 - \mu_A \cdot \pi_{\ell,p}(t))^N \\ \le \min(1, N \cdot \mu_A \cdot \pi_{\ell,p}(t)) $$

so the expected computational effort to find an element of $\mathcal{X}$ is

$$ \text{WF}_{\mathcal{A}}(n, k, t, N) = \frac{C_{\mathcal{A}}}{P_{\mathcal{A}}(t, N)} \ge \frac{C_{\mathcal{A}}}{\min(1, N \cdot \mu_{\mathcal{A}} \cdot \pi_{\ell,p}(t))} \quad (8) $$

The inequality (7) derives from the union bound. The equality holds when the events "$\mathbf{x} \in \mathcal{F}$" are all independent. In some situation, for instance if $\mathcal{X}$ is a set of type-U codewords as in §2.5, the actual probability might be smaller and the actual computational effort larger.

**Effective Workfactor.** The workfactor formula (6) or (8) depends on the parameters $p$ and $\ell$, and possibly other parameters stemming from the subroutine used in the variant. The effective workfactor corresponds to the choice of parameters that will minimize the formula. The corresponding optimization problem can be difficult and has to be solved for each particular problem, that is for given values of $n$, $k$, $t$, and $N$.

## 3.2 ISD-MMT

The generalization of the MMT algorithm [23] to the $q$-ary case is relatively straightforward. We briefly sketch the algorithm and its analysis in the $q$-ary case, the interested reader may wish to check the relevant literature for a more comprehensive presentation.

We consider the framework of the previous section. After permuting the coordinates and computing a partial Gaussian elimination as in (5), we consider the routine of step 2, which attempts to recover all, or as many as possible, elements of the search space $\mathcal{E} = \{\mathbf{e} \in \mathbf{F}_q^{k+\ell}, |\mathbf{e}| = p, \mathbf{e}\mathbf{H}^{\top} = \mathbf{s}\}$.

We denote $L = \binom{k+\ell}{p} (q-1)^p$ and $L_0 = \binom{(k+\ell)/2}{p/4} (q-1)^{p/4}$. We call syndrome of $\mathbf{y} \in \mathbf{F}_q^{k+\ell}$ the quantity $\mathbf{y}\mathbf{H}^{\top}$. An additional parameter $\ell_2$, $0 \le \ell_2 \le \ell$ is introduced. The routine runs as follows:

1. Build 4 lists of size $L_0$ of words in $\mathbf{F}_q^{k+\ell}$ of weight $p/4$

2. Merge the above lists pairwise to obtain 2 lists of size $L_0^2/q^{\ell_2}$ of words in $\mathbf{F}_q^{k+\ell}$ of weight $p/2$ with a prescribed value on $\ell_2$ coordinates of their syndromes

3. Merge the above 2 lists to obtain a list of size $L_0^4/q^{\ell+\ell_2}$ of words in $\mathbf{F}_q^{k+\ell}$ of weight $p$ with a prescribed value on the other $\ell - \ell_2$ coordinates of their syndromes
The cost of this procedure is, up to a constant factor, the maximum of all the above list sizes. The optimal choice of $\ell_2$ is such that $q^{\ell_2} = L/L_0^4$ and $L_0$ is usually negligible for parameters of interest.

Using the fact that $\binom{k+\ell}{p/2}(q-1)^{p/2} = \Omega(\sqrt{p}) \cdot L_0^2$, the iteration cost becomes

$$C_{MMT} = \binom{k+\ell}{p}(q-1)^p \max\left(\frac{1}{\binom{k+\ell}{p/2}(q-1)^{p/2}}, \frac{1}{q^\ell}\right)$$

which is minimal when the two terms in the max are equal. Finally the characteristic quantities of ISD-MMT are

$$C_{MMT} = \binom{k+\ell}{p}(q-1)^p q^{-\ell} \text{ and } \mu_{MMT} = 1 \text{ with } q^{\ell} = \binom{k+\ell}{p/2}(q-1)^{p/2} \quad (9)$$

up to a polynomial factor.

## 3.3 ISD-GBA

Wagner's Generalized Birthday Algorithm (GBA) [31] can be used as SubISD routine. Again, we only briefly sketch the algorithm, the interested reader may refer to [25, 7] for more details. The GBA of order $a$ builds a binary tree, with $2^a$ leaves. Lists attached to siblings are merged and attached to the parent node. The list attached to the root is returned.

1. At level $a$: build $2^a$ lists of $L$ words of weight $p/2^a$ in $F_q^{k+\ell}$

2. At level $i$, $0 \le i < a$: merge pairwise the $2^{i+1}$ lists of level $i+1$ to obtain $2^i$ lists of $L$ words of weight $p/2^i$ in $F_q^{k+\ell}$ with a prescribed value on $\ell/a$ coordinates of their syndromes

3. At level 0: output the final list of $L$ words of weight $p$ with a prescribed syndrome

With the constraint that $L = q^{\ell/a}$ and $L^{2^a} \le \binom{k+\ell}{p}(q-1)^p$. In practice, $a$ should be an integer $\ge 2$, but the algorithm can be smoothed, see [18, 7], and we may consider the real value $a$ such that

$$q^{\ell/a} = \left( \binom{k+\ell}{p} (q-1)^p \right)^{\frac{1}{2^a}}. \quad (10)$$

Even though this value of $a$ does not correspond to an actual GBA tree as above, it provides meaningful bounds. Putting everything together, the characteristic quantities of GBA are the following:

$$C_{GBA} = (2^{a+1} - 1) \cdot q^{\ell/a} \text{ and } \mu_{GBA} = \frac{q^{\frac{a+1}{a}\ell}}{\binom{k+\ell}{p}(q-1)^p} \quad (11)$$

up to a polynomial factor.
The cost of this procedure is, up to a constant factor, the maximum of all the above list sizes. The optimal choice of $\ell_2$ is such that $q^{\ell_2} = L/L_0^4$ and $L_0$ is usually negligible for parameters of interest.

Using the fact that $\binom{k+\ell}{p/2}(q-1)^{p/2} = \Omega(\sqrt{p}) \cdot L_0^2$, the iteration cost becomes

$$C_{MMT} = \binom{k+\ell}{p}(q-1)^p \max\left(\frac{1}{\binom{k+\ell}{p/2}(q-1)^{p/2}}, \frac{1}{q^\ell}\right)$$

which is minimal when the two terms in the max are equal. Finally the characteristic quantities of ISD-MMT are

$$C_{MMT} = \binom{k+\ell}{p}(q-1)^p q^{-\ell} \text{ and } \mu_{MMT} = 1 \text{ with } q^{\ell} = \binom{k+\ell}{p/2}(q-1)^{p/2} \quad (9)$$

up to a polynomial factor.

## 3.3 ISD-GBA

Wagner's Generalized Birthday Algorithm (GBA) [31] can be used as SubISD routine. Again, we only briefly sketch the algorithm, the interested reader may refer to [25, 7] for more details. The GBA of order $a$ builds a binary tree, with $2^a$ leaves. Lists attached to siblings are merged and attached to the parent node. The list attached to the root is returned.

1. At level $a$: build $2^a$ lists of $L$ words of weight $p/2^a$ in $\mathbf{F}_q^{k+\ell}$

2. At level $i$, $0 \le i < a$: merge pairwise the $2^{i+1}$ lists of level $i+1$ to obtain $2^i$ lists of $L$ words of weight $p/2^i$ in $\mathbf{F}_q^{k+\ell}$ with a prescribed value on $\ell/a$ coordinates of their syndromes

3. At level 0: output the final list of $L$ words of weight $p$ with a prescribed syndrome

With the constraint that $L = q^{\ell/a}$ and $L^{2^a} \le \binom{k+\ell}{p}(q-1)^p$. In practice, $a$ should be an integer $\ge 2$, but the algorithm can be smoothed, see [18, 7], and we may consider the real value $a$ such that

$$q^{\ell/a} = \left( \binom{k+\ell}{p} (q-1)^p \right)^{\frac{1}{2^a}}. \quad (10)$$

Even though this value of $a$ does not correspond to an actual GBA tree as above, it provides meaningful bounds. Putting everything together, the characteristic quantities of GBA are the following:

$$C_{GBA} = (2^{a+1} - 1) \cdot q^{\ell/a} \text{ and } \mu_{GBA} = \frac{q^{\frac{a+1}{a}\ell}}{\binom{k+\ell}{p}(q-1)^p} \quad (11)$$

up to a polynomial factor.
**The DOOM Variant.** The DOOM problem, Problem 2, is relevant in the case of the security against forgery of a signature scheme, as the adversary can build any number of messages and be happy to sign only one of them.

The best known way to exploit multiple instance with GBA is to fill one of the $2^a$ lists of level $a$ with target syndromes. The characteristic quantities of GBA-DOOM verify (11), but instead of (10) the optimal order $a$ will be such that

$$q^{\ell/a} = \left( \binom{k+l}{p} (q-1)^p \right)^{\frac{1}{2^a-1}}. \qquad (12)$$

# 4 Best Known Attacks on Wave

We consider an instance of Wave of main parameters $(n, w, k)$, public key $H_{pub} \in F_3^{(n-k) \times n}$, and secondary parameters $(k_U, k_V, g)$. The public code is $C_{pub} = C^\pi = \langle H_{pub} \rangle^\perp$ where $\pi$ is a secret permutation and $C$ is a generalized $(U|U+V)$ code. The type-U and type-V codewords of $C$, denoted $U(C)$ and $V(C)$, are defined in §2.5. To ease the statements we will also call type-U and type-V codewords the elements of $C_{pub}$ which belong to $U(C)^\pi$ and $V(C)^\pi$ respectively.

- **Forgery Attack.** Without knowledge about the secret, the adversary is reduced to solve $DP_\infty(3; n, k, w)$ on average. The target weight $w$ is large, close to the block length $n$. In this regime, the best known attack is Information Set Decoding using the Generalized Birthday Algorithm as subroutine, see [7].

- **Key Attack.** The best known method for recovering the secret key, or at least distinguishing the public key from a random matrix, will consist in exhibiting a type-U codeword in $C_{pub}$ or in $C_{pub}^\perp$.

## 4.1 Forgery Attack

This problem was addressed in [7]. We want to solve the unlimited DOOM problem $DP_\infty(3; n, k, w)$ when $w$ is close to $n$. The workfactor is (larger than)

$$\frac{C_{GBA}}{\min(1, N \cdot \mu_{GBA} \cdot \pi_{\ell,p}(w))}$$

with $N = \binom{n}{w} 2^w / 3^{n-k}$ the expected number of solutions, $C_{GBA}$ and $\mu_{GBA}$ defined in (11), minimized over all choices of $\ell, p, a$ such that (12).

**Optimization.** It is optimal to choose $p = k+l$ in this regime, this was already remarked in [7]. We also notice that the workfactor is minimal when the success probability of an iteration is constant (i.e. one or a small number of iterations is enough). This happens, asymptotically, when $N \cdot \mu_{GBA} \cdot \pi_{\ell,p}(t) = 1$. Finally, the minimal workfactor is $WF_{GBA} = q^{\ell/a}$ when $\ell$ and $a$ verify

$$3^{\ell/a} = 2^{(k+l)/(2^a-1)} = \frac{3^{n-k-l}}{\binom{n-k-l}{w-k-l} 2^{w-k-l}}.$$
**The DOOM Variant.** The DOOM problem, Problem 2, is relevant in the case of the security against forgery of a signature scheme, as the adversary can build any number of messages and be happy to sign only one of them.

The best known way to exploit multiple instance with GBA is to fill one of the $2^a$ lists of level $a$ with target syndromes. The characteristic quantities of GBA-DOOM verify (11), but instead of (10) the optimal order $a$ will be such that

$$q^{\ell/a} = \left( \binom{k+l}{p} (q-1)^p \right)^{\frac{1}{2^a-1}}. \qquad (12)$$

# 4 Best Known Attacks on Wave

We consider an instance of Wave of main parameters $(n, w, k)$, public key $H_{pub} \in F_3^{(n-k) \times n}$, and secondary parameters $(k_U, k_V, g)$. The public code is $C_{pub} = C^\pi = \langle H_{pub} \rangle^\perp$ where $\pi$ is a secret permutation and $C$ is a generalized $(U|U+V)$ code. The type-U and type-V codewords of $C$, denoted $U(C)$ and $V(C)$, are defined in §2.5. To ease the statements we will also call type-U and type-V codewords the elements of $C_{pub}$ which belong to $U(C)^\pi$ and $V(C)^\pi$ respectively.

- **Forgery Attack.** Without knowledge about the secret, the adversary is reduced to solve $DP_\infty(3; n, k, w)$ on average. The target weight $w$ is large, close to the block length $n$. In this regime, the best known attack is Information Set Decoding using the Generalized Birthday Algorithm as subroutine, see [7].

- **Key Attack.** The best known method for recovering the secret key, or at least distinguishing the public key from a random matrix, will consist in exhibiting a type-U codeword in $C_{pub}$ or in $C_{pub}^\perp$.

## 4.1 Forgery Attack

This problem was addressed in [7]. We want to solve the unlimited DOOM problem $DP_\infty(3; n, k, w)$ when $w$ is close to $n$. The workfactor is (larger than)

$$\frac{C_{GBA}}{\min(1, N \cdot \mu_{GBA} \cdot \pi_{\ell,p}(w))}$$

with $N = \binom{n}{w} 2^w / 3^{n-k}$ the expected number of solutions, $C_{GBA}$ and $\mu_{GBA}$ defined in (11), minimized over all choices of $\ell, p, a$ such that (12).

**Optimization.** It is optimal to choose $p = k+l$ in this regime, this was already remarked in [7]. We also notice that the workfactor is minimal when the success probability of an iteration is constant (i.e. one or a small number of iterations is enough). This happens, asymptotically, when $N \cdot \mu_{GBA} \cdot \pi_{\ell,p}(t) = 1$. Finally, the minimal workfactor is $WF_{GBA} = q^{\ell/a}$ when $\ell$ and $a$ verify

$$3^{\ell/a} = 2^{(k+l)/(2^a-1)} = \frac{3^{n-k-l}}{\binom{n-k-l}{w-k-l} 2^{w-k-l}}.$$
## 4.2 Key Attack

The key attack we consider here consists in searching a type-U or a type-V codeword in either the public $[n, k]$ code $C_{pub}$ or its dual. This is done by applying a generic decoding technique (e.g. ISD and variants) for a target error weight $t$ and the zero syndrome.

**Limiting the Codeword Search:**

- We will not consider type-V codewords. In fact, for all Wave parameters of interest, the situation is similar to what we observe in Figure 1, the type-V codewords (red curve) are always dominated by the type-U codewords. So it will always be easier to find a type-U.

- We will not consider type-U codewords of high weight. We observe in Figure 1 that, for large weights, the blue curve of type-U codewords is above the expected number of codewords of that weight, in black. This phenomenon even amplifies when the code rate $k$ decrease. Even though, those words are always harder to find in practice.

Note that to be thorough, the designer must check the above cases a posteriori, which can easily be done when the parameters are known. The purpose of the above limitation is to reduce the parameters selection to a trade-off between the forgery attack of §4.1 and the search of type-U codewords of small weight.

**Finding type-U Codewords of Small Weight.** This search will consist in finding a word of weight $t$, to be determined, in the code $C_{pub}$ or $C_{pub}^{\perp}$. The adversary wins if it was able to obtain at least one type-U codeword of such weight. That is:

- either search a type-U codeword in $C_{pub}$, one among $N_U(t) = \binom{n/2}{t/2} 2^{t/2} / 3^{n/2-k_U}$;

- or search a type-U codeword in $C_{pub}^{\perp}$, one among $N_V(t) = \binom{n/2}{t/2} 2^{t/2} / 3^{k_V}$.

The workfactor is minimized over those two cases and over all possible even values of $t$. The corresponding computational effort when the generic decoding algorithm is ISD-MMT [23] is

$$ \min \left( \min_{t, \ell} (\mathrm{WF}_{\mathrm{MMT}}(n, k, t, N_U(t))), \min_{t, \ell} (\mathrm{WF}_{\mathrm{MMT}}(n, n-k, t, N_V(t))) \right) \quad (13) $$

whose value derives from (8) and (9). The optimization parameters $p$ and $\ell$ are related when the optimum is reached in ISD-MMT, see (9), here we write $p$ as a function of $\ell$, and $\ell$ is used to minimize the expression.

*Remark:* the optimal value of $t$, that is the weight for which it is easiest to find a type-U codeword, is a non trivial trade-off. For instance for $(k/n, w/n) = (0.5, 0.894)$ and $k_U = 0.693 n/2$, the easiest target weight is not, as one could expect, the Gilbert-Varshamov distance $(t/n = 0.081)$ where the blue curve meets the horizontal axis in Figure 1) but is much larger $(t/n = 0.209)$ shown by the small vertical black line in Figure 1).
## 4.2 Key Attack

The key attack we consider here consists in searching a type-U or a type-V codeword in either the public $[n, k]$ code $C_{pub}$ or its dual. This is done by applying a generic decoding technique (e.g. ISD and variants) for a target error weight $t$ and the zero syndrome.

**Limiting the Codeword Search:**

- We will not consider type-V codewords. In fact, for all Wave parameters of interest, the situation is similar to what we observe in Figure 1, the type-V codewords (red curve) are always dominated by the type-U codewords. So it will always be easier to find a type-U.

- We will not consider type-U codewords of high weight. We observe in Figure 1 that, for large weights, the blue curve of type-U codewords is above the expected number of codewords of that weight, in black. This phenomenon even amplifies when the code rate $k$ decrease. Even though, those words are always harder to find in practice.

Note that to be thorough, the designer must check the above cases a posteriori, which can easily be done when the parameters are known. The purpose of the above limitation is to reduce the parameters selection to a trade-off between the forgery attack of §4.1 and the search of type-U codewords of small weight.

**Finding type-U Codewords of Small Weight.** This search will consist in finding a word of weight $t$, to be determined, in the code $C_{pub}$ or $C_{pub}^{\perp}$. The adversary wins if it was able to obtain at least one type-U codeword of such weight. That is:

- either search a type-U codeword in $C_{pub}$, one among $N_U(t) = \binom{n/2}{t/2} 2^{t/2} / 3^{n/2-k_U}$;

- or search a type-U codeword in $C_{pub}^{\perp}$, one among $N_V(t) = \binom{n/2}{t/2} 2^{t/2} / 3^{k_V}$.

The workfactor is minimized over those two cases and over all possible even values of $t$. The corresponding computational effort when the generic decoding algorithm is ISD-MMT [23] is

$$ \min \left( \min_{t, \ell} (\mathrm{WF}_{\mathrm{MMT}}(n, k, t, N_U(t))), \min_{t, \ell} (\mathrm{WF}_{\mathrm{MMT}}(n, n-k, t, N_V(t))) \right) \quad (13) $$

whose value derives from (8) and (9). The optimization parameters $p$ and $\ell$ are related when the optimum is reached in ISD-MMT, see (9), here we write $p$ as a function of $\ell$, and $\ell$ is used to minimize the expression.

*Remark:* the optimal value of $t$, that is the weight for which it is easiest to find a type-U codeword, is a non trivial trade-off. For instance for $(k/n, w/n) = (0.5, 0.894)$ and $k_U = 0.693 n/2$, the easiest target weight is not, as one could expect, the Gilbert-Varshamov distance $(t/n = 0.081)$ where the blue curve meets the horizontal axis in Figure 1) but is much larger $(t/n = 0.209)$ shown by the small vertical black line in Figure 1).
## 4.3 Wave Parameter Selection

We consider here asymptotic estimates. Relative parameters are considered, e.g. $k/n$, $w/n...$, and polynomial factors are not considered. Our purpose is to find the good proportion between the scheme parameters, main and secondary. As the security scales linearly with code-length $n$, the target security is obtained as a final step by scaling $n$.

1. Let $\lambda$ be the target (classical) security or the “number of security bits”, e.g. $\lambda = 128$.

We want that all attacks against the scheme require a computational effort at least equal to $2^{\lambda}$.

2. Select the main parameters $(k, w)$. (guidelines: $0.35 \le k/n \le 0.7$ and $0.85 \le w/n \le 0.95$) The forgery attack requires a computational effort

$$WF_{GBA}(n, k, w) \ge 2^{c \cdot n}$$

where $c$ only depends on $k/n$ and $w/n$.

We may now relate the code-length and the security as we want to reach $c \cdot n = \lambda$ where $\lambda$ is the “number of (classical) security bits”.

3. The secondary parameters $(k_U, k_V)$ derive from the main ones:

$$k_U = g + \frac{3}{2}w - n \text{ and } k_V = k - k_U.$$

4. The gap $g$ is used in [15] to unconditionally ensure a uniformity condition needed to formally reach the EUF-CMA security, its value is $g = \lambda/\log_2 3 = 0.631c \cdot n$ for “$\lambda$ bits of (classical) security”. Using $g = 0$ is probably safe but, at the moment, would require an additional heuristic assumption. We will favor an intermediate value $g = 0.315c \cdot n$ and admit that it corresponds to an adversary limited to $2^{\lambda/2}$ queries to a signing oracle, e.g. a scheme with 128 bits of security with an adversary allowed to at most $2^{64}$ queries to a signing oracle, corresponding to a gap $g \approx 40$.

5. The corresponding computational effort for the key attack derives from (13) and §4.2. If we denote $WF_{key}$ this quantity, the corresponding asymptotic exponent is $c' = \frac{1}{n}\log_2(WF_{key})$ which only depends of the relative value $k/n$ and $k_U/n$. Finally $k_U$ is related to $w$ and to the gap $g$.

*Example:* In Figure 2, we consider $k/n = 0.5$. The asymptotic exponent is given for forgery attack, the increasing curve in black, and for the key attack, the decreasing curves in dotted red, solid blue, dashed green, corresponding to various choices for the gap. The optimal choice will correspond to the curves intersections whose numerical values are given in Table 1.

We observe that, even though the gap does not change the order of magnitude, it has a significant impact on the system parameters. In the sequel we will consider the “half gap” scenario, corresponding to $g = 40$ when the target security is $\lambda = 128$.
## 4.3 Wave Parameter Selection

We consider here asymptotic estimates. Relative parameters are considered, e.g. $k/n$, $w/n...$, and polynomial factors are not considered. Our purpose is to find the good proportion between the scheme parameters, main and secondary. As the security scales linearly with code-length $n$, the target security is obtained as a final step by scaling $n$.

1. Let $\lambda$ be the target (classical) security or the “number of security bits”, e.g. $\lambda = 128$.

We want that all attacks against the scheme require a computational effort at least equal to $2^{\lambda}$.

2. Select the main parameters $(k, w)$. (guidelines: $0.35 \le k/n \le 0.7$ and $0.85 \le w/n \le 0.95$) The forgery attack requires a computational effort

$$WF_{GBA}(n, k, w) \ge 2^{c \cdot n}$$

where $c$ only depends on $k/n$ and $w/n$.

We may now relate the code-length and the security as we want to reach $c \cdot n = \lambda$ where $\lambda$ is the “number of (classical) security bits”.

3. The secondary parameters $(k_U, k_V)$ derive from the main ones:

$$k_U = g + \frac{3}{2}w - n \text{ and } k_V = k - k_U.$$

4. The gap $g$ is used in [15] to unconditionally ensure a uniformity condition needed to formally reach the EUF-CMA security, its value is $g = \lambda/\log_2 3 = 0.631c \cdot n$ for “$\lambda$ bits of (classical) security”. Using $g = 0$ is probably safe but, at the moment, would require an additional heuristic assumption. We will favor an intermediate value $g = 0.315c \cdot n$ and admit that it corresponds to an adversary limited to $2^{\lambda/2}$ queries to a signing oracle, e.g. a scheme with 128 bits of security with an adversary allowed to at most $2^{64}$ queries to a signing oracle, corresponding to a gap $g \approx 40$.

5. The corresponding computational effort for the key attack derives from (13) and §4.2. If we denote $WF_{key}$ this quantity, the corresponding asymptotic exponent is $c' = \frac{1}{n}\log_2(WF_{key})$ which only depends of the relative value $k/n$ and $k_U/n$. Finally $k_U$ is related to $w$ and to the gap $g$.

*Example:* In Figure 2, we consider $k/n = 0.5$. The asymptotic exponent is given for forgery attack, the increasing curve in black, and for the key attack, the decreasing curves in dotted red, solid blue, dashed green, corresponding to various choices for the gap. The optimal choice will correspond to the curves intersections whose numerical values are given in Table 1.

We observe that, even though the gap does not change the order of magnitude, it has a significant impact on the system parameters. In the sequel we will consider the “half gap” scenario, corresponding to $g = 40$ when the target security is $\lambda = 128$.
<figure><img src="image_2.png" /><figcaption>**Fig. 2.** Security Exponent for Best Known Forgery Attacks (black) and Key Attacks (blue) vs. Error Weight for a Code Rate $k = 0.5$</figcaption></figure>

<table><caption>**Table 1.** Wave Parameters vs. Gap for $k = 0.5$</caption><thead><tr><th colspan="2">asymptotic parameters</th><th colspan="6">Wave parameters, λ = 128</th></tr><tr><th></th><th>w/n</th><th>c</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>no gap</td><td>0.89665</td><td>0.0162184</td><td>7904</td><td>3952</td><td>7077</td><td>2763</td><td>1183</td><td>0</td></tr><tr><td>half gap</td><td>0.89412</td><td>0.0150016</td><td>8532</td><td>4266</td><td>7629</td><td>2951</td><td>1315</td><td>40</td></tr><tr><td>full gap</td><td>0.89193</td><td>0.0139887</td><td>9150</td><td>4575</td><td>8161</td><td>3132</td><td>1443</td><td>81</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Security Exponent for Best Known Forgery Attacks (black) and Key Attacks (blue) vs. Error Weight for a Code Rate $k = 0.5$</figcaption></figure>

<table><caption>**Table 1.** Wave Parameters vs. Gap for $k = 0.5$</caption><thead><tr><th colspan="2">asymptotic parameters</th><th colspan="6">Wave parameters, λ = 128</th></tr><tr><th></th><th>w/n</th><th>c</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>no gap</td><td>0.89665</td><td>0.0162184</td><td>7904</td><td>3952</td><td>7077</td><td>2763</td><td>1183</td><td>0</td></tr><tr><td>half gap</td><td>0.89412</td><td>0.0150016</td><td>8532</td><td>4266</td><td>7629</td><td>2951</td><td>1315</td><td>40</td></tr><tr><td>full gap</td><td>0.89193</td><td>0.0139887</td><td>9150</td><td>4575</td><td>8161</td><td>3132</td><td>1443</td><td>81</td></tr></tbody></table>
## 4.4 Sizes

The public key can be provided in systematic form, so its size is equal to $k(n-k) \log_2 3$ bits. The signature is a ternary vector $\mathbf{e}$ of length $n$ and weight $w$. As explained in [2, §2.5], when the public key is in systematic form, it is enough to provide the last $k$ coordinates of $\mathbf{e}$. Moreover those coordinates can be compressed to a size $k \cdot h_3(w/n)$ bits, where $h_3(x) = -x \log_2 x - (1-x) \log_2(1-x) + x$ is the ternary entropy function.

For a security level $\lambda = 128$ and the intermediate gap $g = 40$ we give in Table 2 Wave parameters for a code rate between 0.38 and 0.70. We also give in Figure 3 the signature length and the public key size for the same range of code rates. We observe that if $k/n$ decrease below 0.43 or increases above 0.66 then both the signature length and the key size increase. So the effective range for the code rate is rather narrow. In practice $k = 0.5$ seems to offer a rather good trade-off, the signature length is very close the minimum, 737 bytes for a minimum of 723 bytes, while the public key has a size of 3.6MB, not much larger than the minimal 3.04MB.

<table><caption>**Table 2.** Wave parameters for $(\lambda, g) = 128, 40$</caption><thead><tr><th>$k/n$</th><th>$n$</th><th>$k$</th><th>$w$</th><th>$k_U$</th><th>$k_V$</th><th>signature length (bytes)</th><th>key size (MB)</th></tr></thead><tbody><tr><td>0.38</td><td>10464</td><td>3976</td><td>8918</td><td>2953</td><td>1023</td><td>724</td><td>5.11</td></tr><tr><td>0.41</td><td>9792</td><td>4015</td><td>8454</td><td>2928</td><td>1087</td><td>723</td><td>4.60</td></tr><tr><td>0.44</td><td>9262</td><td>4075</td><td>8095</td><td>2920</td><td>1155</td><td>724</td><td>4.19</td></tr><tr><td>0.47</td><td>8846</td><td>4158</td><td>7822</td><td>2927</td><td>1231</td><td>729</td><td>3.86</td></tr><tr><td>0.50</td><td>8526</td><td>4263</td><td>7623</td><td>2949</td><td>1314</td><td>737</td><td>3.60</td></tr><tr><td>0.53</td><td>8318</td><td>4409</td><td>7516</td><td>2995</td><td>1414</td><td>751</td><td>3.41</td></tr><tr><td>0.56</td><td>8184</td><td>4583</td><td>7469</td><td>3059</td><td>1524</td><td>768</td><td>3.27</td></tr><tr><td>0.59</td><td>8124</td><td>4793</td><td>7485</td><td>3143</td><td>1650</td><td>791</td><td>3.16</td></tr><tr><td>0.62</td><td>8136</td><td>5044</td><td>7564</td><td>3249</td><td>1795</td><td>818</td><td>3.09</td></tr><tr><td>0.65</td><td>8226</td><td>5347</td><td>7713</td><td>3383</td><td>1964</td><td>852</td><td>3.05</td></tr><tr><td>0.68</td><td>8402</td><td>5713</td><td>7942</td><td>3550</td><td>2163</td><td>894</td><td>3.04</td></tr><tr><td>0.70</td><td>8574</td><td>6002</td><td>8146</td><td>3685</td><td>2317</td><td>928</td><td>3.06</td></tr></tbody></table>

## 4.5 Scaling Security

All parameters scale linearly with the security. The signature length also scales linearly, the key size however is quadratic. So Table 2 can be used to deduce parameters offering a higher security level, e.g. $\lambda \in \{192, 256\}$. This scaling will also increase the gap while in some situations, for instance in the NIST call for postquantum primitives, some capabilities of the adversary are limited regardless of the target security. Let us assume then that the adversary is limited to $2^{64}$ calls to a signing oracle and we want to reach security levels 192 or 256. It is possible to do slightly better than just scaling Table 2
## 4.4 Sizes

The public key can be provided in systematic form, so its size is equal to $k(n-k) \log_2 3$ bits. The signature is a ternary vector $\mathbf{e}$ of length $n$ and weight $w$. As explained in [2, §2.5], when the public key is in systematic form, it is enough to provide the last $k$ coordinates of $\mathbf{e}$. Moreover those coordinates can be compressed to a size $k \cdot h_3(w/n)$ bits, where $h_3(x) = -x \log_2 x - (1-x) \log_2(1-x) + x$ is the ternary entropy function.

For a security level $\lambda = 128$ and the intermediate gap $g = 40$ we give in Table 2 Wave parameters for a code rate between 0.38 and 0.70. We also give in Figure 3 the signature length and the public key size for the same range of code rates. We observe that if $k/n$ decrease below 0.43 or increases above 0.66 then both the signature length and the key size increase. So the effective range for the code rate is rather narrow. In practice $k = 0.5$ seems to offer a rather good trade-off, the signature length is very close the minimum, 737 bytes for a minimum of 723 bytes, while the public key has a size of 3.6MB, not much larger than the minimal 3.04MB.

<table><caption>**Table 2.** Wave parameters for $(\lambda, g) = 128, 40$</caption><thead><tr><th>$k/n$</th><th>$n$</th><th>$k$</th><th>$w$</th><th>$k_U$</th><th>$k_V$</th><th>signature length (bytes)</th><th>key size (MB)</th></tr></thead><tbody><tr><td>0.38</td><td>10464</td><td>3976</td><td>8918</td><td>2953</td><td>1023</td><td>724</td><td>5.11</td></tr><tr><td>0.41</td><td>9792</td><td>4015</td><td>8454</td><td>2928</td><td>1087</td><td>723</td><td>4.60</td></tr><tr><td>0.44</td><td>9262</td><td>4075</td><td>8095</td><td>2920</td><td>1155</td><td>724</td><td>4.19</td></tr><tr><td>0.47</td><td>8846</td><td>4158</td><td>7822</td><td>2927</td><td>1231</td><td>729</td><td>3.86</td></tr><tr><td>0.50</td><td>8526</td><td>4263</td><td>7623</td><td>2949</td><td>1314</td><td>737</td><td>3.60</td></tr><tr><td>0.53</td><td>8318</td><td>4409</td><td>7516</td><td>2995</td><td>1414</td><td>751</td><td>3.41</td></tr><tr><td>0.56</td><td>8184</td><td>4583</td><td>7469</td><td>3059</td><td>1524</td><td>768</td><td>3.27</td></tr><tr><td>0.59</td><td>8124</td><td>4793</td><td>7485</td><td>3143</td><td>1650</td><td>791</td><td>3.16</td></tr><tr><td>0.62</td><td>8136</td><td>5044</td><td>7564</td><td>3249</td><td>1795</td><td>818</td><td>3.09</td></tr><tr><td>0.65</td><td>8226</td><td>5347</td><td>7713</td><td>3383</td><td>1964</td><td>852</td><td>3.05</td></tr><tr><td>0.68</td><td>8402</td><td>5713</td><td>7942</td><td>3550</td><td>2163</td><td>894</td><td>3.04</td></tr><tr><td>0.70</td><td>8574</td><td>6002</td><td>8146</td><td>3685</td><td>2317</td><td>928</td><td>3.06</td></tr></tbody></table>

## 4.5 Scaling Security

All parameters scale linearly with the security. The signature length also scales linearly, the key size however is quadratic. So Table 2 can be used to deduce parameters offering a higher security level, e.g. $\lambda \in \{192, 256\}$. This scaling will also increase the gap while in some situations, for instance in the NIST call for postquantum primitives, some capabilities of the adversary are limited regardless of the target security. Let us assume then that the adversary is limited to $2^{64}$ calls to a signing oracle and we want to reach security levels 192 or 256. It is possible to do slightly better than just scaling Table 2
<figure><img src="image_3.png" /><figcaption>**Fig. 3.** Signature Length and Public Key Size vs. Code Rate for a Security $\lambda = 128$ and a Gap $g = 40$</figcaption></figure>

<table><caption>**Table 3.** Scaling Wave Parameters with a Gap $g = 40$</caption><thead><tr><th>λ</th><th>g</th><th>n</th><th>k</th><th>w</th><th>k<sub>U</sub></th><th>k<sub>V</sub></th><th>signature length</th><th>key size</th></tr></thead><tbody><tr><td>128</td><td>40</td><td>8526</td><td>4263</td><td>7623</td><td>2949</td><td>1314</td><td>737 bytes</td><td>3.60 MB</td></tr><tr><td>192</td><td>40</td><td>12476</td><td>6238</td><td>11165</td><td>4311</td><td>1927</td><td>1076 bytes</td><td>7.71 MB</td></tr><tr><td>256</td><td>40</td><td>16424</td><td>8212</td><td>14705</td><td>5673</td><td>2539</td><td>1416 bytes</td><td>13.36 MB</td></tr></tbody></table>
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Signature Length and Public Key Size vs. Code Rate for a Security $\lambda = 128$ and a Gap $g = 40$</figcaption></figure>

<table><caption>**Table 3.** Scaling Wave Parameters with a Gap $g = 40$</caption><thead><tr><th>λ</th><th>g</th><th>n</th><th>k</th><th>w</th><th>k<sub>U</sub></th><th>k<sub>V</sub></th><th>signature length</th><th>key size</th></tr></thead><tbody><tr><td>128</td><td>40</td><td>8526</td><td>4263</td><td>7623</td><td>2949</td><td>1314</td><td>737 bytes</td><td>3.60 MB</td></tr><tr><td>192</td><td>40</td><td>12476</td><td>6238</td><td>11165</td><td>4311</td><td>1927</td><td>1076 bytes</td><td>7.71 MB</td></tr><tr><td>256</td><td>40</td><td>16424</td><td>8212</td><td>14705</td><td>5673</td><td>2539</td><td>1416 bytes</td><td>13.36 MB</td></tr></tbody></table>
## 4.6 Quantum Security

All attacks that are involved in the parameter selection process derive from ISD. So far quantum speedup of ISD variants [3, 22, 10] never managed to reduce the security exponent by more than a factor 2 and thus, from §4.5, scaling the scheme to resist to quantum cryptanalysis will be straightforward.

# 5 Conclusion

Wave is the first scalable hash-and-sign signature scheme based on codes. It enjoys short signature and fast verification, whereas signing time is average, hundreds of milliseconds, and the public key large, several megabytes.

We propose here some practical parameters for the scheme, based on the current knowledge of the underlying hard problems. Our proposed methodology would easily adapt to any evolution of the best known solvers for those problems.

Note that all known attacks eventually require the use of solvers for the generic decoding problem, and even though those solvers are used in unusual regime of parameters, the generic decoding problem has been studied for more than half a century without any significant improvement. For instance, decoding at the Gilbert-Varshamov distance at rate 0.5, i.e. $t = 0.11 \cdot n$ errors in a binary code of length $n$ and dimension $n/2$, features a security exponent of 0.12 with Prange algorithm [27] which only reduces to about 0.09 with today's best known solver [5]. In other words, after sixty years, any code-based scheme corresponding to this regime of parameters, as for the instance the Stern authentication scheme [30] and related signatures, as [16] for instance, need an increase of only 25% of its block size to maintain the same security. Very few problems in public key cryptography can claim such a stability for the computational cost of their best known attacks.

## References

1. Aguilar, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: Proc. IEEE Inf. Theory Workshop-ITW 2011. pp. 648–652. IEEE (Oct 2011)

2. Banegas, G., Debris-Alazard, T., Nedeljkovi, M., Smith, B.: Wavelet: Code-based postquantum signatures with fast verification on microcontrollers. Cryptology ePrint Archive, Report 2021/1432 (2021), https://ia.cr/2021/1432

3. Bernstein, D.J.: Grover vs. McEliece. In: Sendrier, N. (ed.) Post-Quantum Cryptography 2010. LNCS, vol. 6061, pp. 73–80. Springer (2010)

4. Biasse, J., Micheli, G., Persichetti, E., Santini, P.: LESS is more: Code-based signatures without syndromes. In: Nitaj, A., Youssef, A.M. (eds.) Progress in Cryptology - AFRICACRYPT 2020. LNCS, vol. 12174, pp. 45–65. Springer (2020). https://doi.org/10.1007/978-3-030-51938-4_3, https://doi.org/10.1007/978-3-030-51938-4_3

5. Both, L., May, A.: Optimizing BJMM with Nearest Neighbors: Full Decoding in $2^{2/21^n}$ and McEliece Security. In: WCC Workshop on Coding and Cryptography (Sep 2017), http://wcc2017.suai.ru/Proceedings_WCC2017.zip
## 4.6 Quantum Security

All attacks that are involved in the parameter selection process derive from ISD. So far quantum speedup of ISD variants [3, 22, 10] never managed to reduce the security exponent by more than a factor 2 and thus, from §4.5, scaling the scheme to resist to quantum cryptanalysis will be straightforward.

# 5 Conclusion

Wave is the first scalable hash-and-sign signature scheme based on codes. It enjoys short signature and fast verification, whereas signing time is average, hundreds of milliseconds, and the public key large, several megabytes.

We propose here some practical parameters for the scheme, based on the current knowledge of the underlying hard problems. Our proposed methodology would easily adapt to any evolution of the best known solvers for those problems.

Note that all known attacks eventually require the use of solvers for the generic decoding problem, and even though those solvers are used in unusual regime of parameters, the generic decoding problem has been studied for more than half a century without any significant improvement. For instance, decoding at the Gilbert-Varshamov distance at rate 0.5, i.e. $t = 0.11 \cdot n$ errors in a binary code of length $n$ and dimension $n/2$, features a security exponent of 0.12 with Prange algorithm [27] which only reduces to about 0.09 with today's best known solver [5]. In other words, after sixty years, any code-based scheme corresponding to this regime of parameters, as for the instance the Stern authentication scheme [30] and related signatures, as [16] for instance, need an increase of only 25% of its block size to maintain the same security. Very few problems in public key cryptography can claim such a stability for the computational cost of their best known attacks.

## References

1. Aguilar, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: Proc. IEEE Inf. Theory Workshop-ITW 2011. pp. 648–652. IEEE (Oct 2011)

2. Banegas, G., Debris-Alazard, T., Nedeljkovi, M., Smith, B.: Wavelet: Code-based postquantum signatures with fast verification on microcontrollers. Cryptology ePrint Archive, Report 2021/1432 (2021), https://ia.cr/2021/1432

3. Bernstein, D.J.: Grover vs. McEliece. In: Sendrier, N. (ed.) Post-Quantum Cryptography 2010. LNCS, vol. 6061, pp. 73–80. Springer (2010)

4. Biasse, J., Micheli, G., Persichetti, E., Santini, P.: LESS is more: Code-based signatures without syndromes. In: Nitaj, A., Youssef, A.M. (eds.) Progress in Cryptology - AFRICACRYPT 2020. LNCS, vol. 12174, pp. 45–65. Springer (2020). https://doi.org/10.1007/978-3-030-51938-4_3, https://doi.org/10.1007/978-3-030-51938-4_3

5. Both, L., May, A.: Optimizing BJMM with Nearest Neighbors: Full Decoding in $2^{2/21^n}$ and McEliece Security. In: WCC Workshop on Coding and Cryptography (Sep 2017), http://wcc2017.suai.ru/Proceedings_WCC2017.zip
6. Both, L., May, A.: Decoding linear codes with high error rate and its impact for LPN security. In: Lange, T., Steinwandt, R. (eds.) Post-Quantum Cryptography 2018. LNCS, vol. 10786, pp. 25–46. Springer, Fort Lauderdale, FL, USA (Apr 2018). https://doi.org/10.1007/978-3-319-79063-3_2, https://doi.org/10.1007/978-3-319-79063-3_2

7. Bricout, R., Chailloux, A., Debris-Alazard, T., Lequesne, M.: Ternary syndrome decoding with large weights. In: Paterson, K.G., Stebila, D. (eds.) Selected Areas in Cryptography - SAC 2019 - 26th International Conference, Waterloo, ON, Canada, August 12-16, 2019, Revised Selected Papers. Lecture Notes in Computer Science, vol. 11959, pp. 437–466. Springer (2019)

8. Canto Torres, R.: Asymptotic analysis of ISD algorithms for the $q$-ary case. In: Proceedings of the Tenth International Workshop on Coding and Cryptography WCC 2017 (Sep 2017), http://wcc2017.suai.ru/Proceedings_WCC2017.zip

9. Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., Tillich, J.: Statistical decoding 2.0: Reducing decoding to LPN. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology - ASIACRYPT 2022. LNCS, vol. 13794, pp. 477–507. Springer (2022). https://doi.org/10.1007/978-3-031-22972-5_17, https://doi.org/10.1007/978-3-031-22972-5_17

10. Chailloux, A., Debris-Alazard, T., Etinski, S.: Classical and quantum algorithms for generic syndrome decoding problems and applications to the lee metric. In: Cheon, J.H., Tillich, J. (eds.) Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20-22, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12841, pp. 44–62. Springer (2021). https://doi.org/10.1007/978-3-030-81293-5_3, https://doi.org/10.1007/978-3-030-81293-5_3

11. Coron, J.S., Joux, A.: Cryptanalysis of a provably secure cryptographic hash function. IACR Cryptology ePrint Archive, Report 2004/013 (2004), http://eprint.iacr.org/

12. Courtois, N., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: Advances in Cryptology - ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Gold Coast, Australia (2001)

13. Debris-Alazard, T.: Cryptographie fondée sur les codes : nouvelles approches pour constructions et preuves ; contribution en cryptanalyse. Theses, Sorbonne Université (Dec 2019), https://tel.archives-ouvertes.fr/tel-02424234

14. Debris-Alazard, T.: Code-based cryptography: Lecture notes. arXiv:2304.03541 (Apr 2023)

15. Debris-Alazard, T., Sendrier, N., Tillich, J.P.: Wave: A new family of trapdoor one-way preimage sampleable functions based on codes. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology - ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 21–51. Springer, Kobe, Japan (Dec 2019). https://doi.org/10.1007/978-3-030-34578-5_2, https://doi.org/10.1007/978-3-030-34578-5_2

16. Feneuil, T., Joux, A., Rivain, M.: Syndrome decoding in the head: Shorter signatures from zero-knowledge proofs. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology - CRYPTO 2023. LNCS, vol. 13508, pp. 541–572. Springer (2022), https://eprint.iacr.org/2022/188

17. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A. (ed.) Advances in Cryptology - CRYPTO '86. LNCS, vol. 263, pp. 186–194. Springer (1987)

18. Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Matsui, M. (ed.) Advances in Cryptology - ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer (2009)
6. Both, L., May, A.: Decoding linear codes with high error rate and its impact for LPN security. In: Lange, T., Steinwandt, R. (eds.) Post-Quantum Cryptography 2018. LNCS, vol. 10786, pp. 25–46. Springer, Fort Lauderdale, FL, USA (Apr 2018). https://doi.org/10.1007/978-3-319-79063-3_2, https://doi.org/10.1007/978-3-319-79063-3_2

7. Bricout, R., Chailloux, A., Debris-Alazard, T., Lequesne, M.: Ternary syndrome decoding with large weights. In: Paterson, K.G., Stebila, D. (eds.) Selected Areas in Cryptography - SAC 2019 - 26th International Conference, Waterloo, ON, Canada, August 12-16, 2019, Revised Selected Papers. Lecture Notes in Computer Science, vol. 11959, pp. 437–466. Springer (2019)

8. Canto Torres, R.: Asymptotic analysis of ISD algorithms for the $q$-ary case. In: Proceedings of the Tenth International Workshop on Coding and Cryptography WCC 2017 (Sep 2017), http://wcc2017.suai.ru/Proceedings_WCC2017.zip

9. Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., Tillich, J.: Statistical decoding 2.0: Reducing decoding to LPN. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology - ASIACRYPT 2022. LNCS, vol. 13794, pp. 477–507. Springer (2022). https://doi.org/10.1007/978-3-031-22972-5_17, https://doi.org/10.1007/978-3-031-22972-5_17

10. Chailloux, A., Debris-Alazard, T., Etinski, S.: Classical and quantum algorithms for generic syndrome decoding problems and applications to the lee metric. In: Cheon, J.H., Tillich, J. (eds.) Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20-22, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12841, pp. 44–62. Springer (2021). https://doi.org/10.1007/978-3-030-81293-5_3, https://doi.org/10.1007/978-3-030-81293-5_3

11. Coron, J.S., Joux, A.: Cryptanalysis of a provably secure cryptographic hash function. IACR Cryptology ePrint Archive, Report 2004/013 (2004), http://eprint.iacr.org/

12. Courtois, N., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: Advances in Cryptology - ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Gold Coast, Australia (2001)

13. Debris-Alazard, T.: Cryptographie fondée sur les codes : nouvelles approches pour constructions et preuves ; contribution en cryptanalyse. Theses, Sorbonne Université (Dec 2019), https://tel.archives-ouvertes.fr/tel-02424234

14. Debris-Alazard, T.: Code-based cryptography: Lecture notes. arXiv:2304.03541 (Apr 2023)

15. Debris-Alazard, T., Sendrier, N., Tillich, J.P.: Wave: A new family of trapdoor one-way preimage sampleable functions based on codes. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology - ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 21–51. Springer, Kobe, Japan (Dec 2019). https://doi.org/10.1007/978-3-030-34578-5_2, https://doi.org/10.1007/978-3-030-34578-5_2

16. Feneuil, T., Joux, A., Rivain, M.: Syndrome decoding in the head: Shorter signatures from zero-knowledge proofs. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology - CRYPTO 2023. LNCS, vol. 13508, pp. 541–572. Springer (2022), https://eprint.iacr.org/2022/188

17. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A. (ed.) Advances in Cryptology - CRYPTO '86. LNCS, vol. 263, pp. 186–194. Springer (1987)

18. Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Matsui, M. (ed.) Advances in Cryptology - ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer (2009)
19. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the fortieth annual ACM symposium on Theory of computing. pp. 197–206. ACM (2008)

20. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Johnson, D.S., Feige, U. (eds.) STOC '07. pp. 21–30. ACM (2007). https://doi.org/10.1145/1250790.1250794, https://doi.org/10.1145/1250790.1250794

21. Johansson, T., Jönsson, F.: On the complexity of some cryptographic problems based on the general decoding problem. IEEE Trans. Inform. Theory 48(10), 2669–2678 (Oct 2002)

22. Kachigar, G., Tillich, J.P.: Quantum information set decoding algorithms. In: Post-Quantum Cryptography 2017. LNCS, vol. 10346, pp. 69–89. Springer, Utrecht, The Netherlands (Jun 2017)

23. May, A., Meurer, A., Thomae, E.: Decoding random linear codes in $O(2^{0.054n})$. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer (2011)

24. May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer (2015)

25. Minder, L., Sinclair, A.: The extended k-tree algorithm. In: Mathieu, C. (ed.) Proceedings of SODA 2009. pp. 586–595. SIAM (2009)

26. Peters, C.: Information-set decoding for linear codes over $F_q$. In: Post-Quantum Cryptography 2010. LNCS, vol. 6061, pp. 81–94. Springer (2010)

27. Prange, E.: The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory 8(5), 5–9 (1962). https://doi.org/10.1109/TIT.1962.1057777, http://dx.doi.org/10.1109/TIT.1962.1057777

28. Sendrier, N.: Decoding one out of many. In: Post-Quantum Cryptography 2011. LNCS, vol. 7071, pp. 51–67 (2011)

29. Stern, J.: A method for finding codewords of small weight. In: Cohen, G.D., Wolfmann, J. (eds.) Coding Theory and Applications. LNCS, vol. 388, pp. 106–113. Springer (1988)

30. Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D. (ed.) Advances in Cryptology - CRYPTO'93. LNCS, vol. 773, pp. 13–21. Springer (1993)

31. Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) Advances in Cryptology - CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer (2002)
19. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the fortieth annual ACM symposium on Theory of computing. pp. 197–206. ACM (2008)

20. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Johnson, D.S., Feige, U. (eds.) STOC '07. pp. 21–30. ACM (2007). https://doi.org/10.1145/1250790.1250794, https://doi.org/10.1145/1250790.1250794

21. Johansson, T., Jönsson, F.: On the complexity of some cryptographic problems based on the general decoding problem. IEEE Trans. Inform. Theory 48(10), 2669–2678 (Oct 2002)

22. Kachigar, G., Tillich, J.P.: Quantum information set decoding algorithms. In: Post-Quantum Cryptography 2017. LNCS, vol. 10346, pp. 69–89. Springer, Utrecht, The Netherlands (Jun 2017)

23. May, A., Meurer, A., Thomae, E.: Decoding random linear codes in $O(2^{0.054n})$. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer (2011)

24. May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer (2015)

25. Minder, L., Sinclair, A.: The extended k-tree algorithm. In: Mathieu, C. (ed.) Proceedings of SODA 2009. pp. 586–595. SIAM (2009)

26. Peters, C.: Information-set decoding for linear codes over $F_q$. In: Post-Quantum Cryptography 2010. LNCS, vol. 6061, pp. 81–94. Springer (2010)

27. Prange, E.: The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory 8(5), 5–9 (1962). https://doi.org/10.1109/TIT.1962.1057777, http://dx.doi.org/10.1109/TIT.1962.1057777

28. Sendrier, N.: Decoding one out of many. In: Post-Quantum Cryptography 2011. LNCS, vol. 7071, pp. 51–67 (2011)

29. Stern, J.: A method for finding codewords of small weight. In: Cohen, G.D., Wolfmann, J. (eds.) Coding Theory and Applications. LNCS, vol. 388, pp. 106–113. Springer (1988)

30. Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D. (ed.) Advances in Cryptology - CRYPTO'93. LNCS, vol. 773, pp. 13–21. Springer (1993)

31. Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) Advances in Cryptology - CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer (2002)