# Security Analysis of SDiTH

Kévin Carrier, Jean-Pierre Tillich, Valerian Hatey

► To cite this version:

Kévin Carrier, Jean-Pierre Tillich, Valerian Hatey. Security Analysis of SDiTH. Workshop on Code-Based Cryptography, Nov 2023, Lyon, France. hal-04311262

HAL Id: hal-04311262

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

Submitted on 28 Nov 2023

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Security Analysis of SDiTH

Kévin CARRIER, Jean-Pierre TILLICH and Valerian HATEY

CY Cergy Paris Université
ENSEA (École Nationale Supérieure de l'Électronique et de ses Applications)

20 novembre 2023
1 Security Analysis in NIST specification

2 Correction of the analysis

* First problem

* Second problem

* Third problem

3 Improved attack with projective space
# Syndrom Decoding problem

Let us recall the Syndrome Decoding problem

## Problem (Syndrome Decoding SD(H, s, t))

Given a matrix $H \in \mathbb{F}_q^{(n-k) \times n}$, a syndrome $s \in \mathbb{F}_q^{n-k}$ and a distance $t \in [0, n]$, one wants to find a vector $e \in \mathbb{F}_q^n$ such that $He = s$ and $|e| = t$.
# SDITH security

Based on d-split syndrome decoding problem (a key recovery attack on SDITH is as hard as solving the d-split Syndrome Decoding problem)

## Problem (d-split Syndrome Decoding $SD(d, H, s, t)$)

Given a matrix $H \in \mathbb{F}_q^{(n-k) \times n}$, a syndrome $s \in \mathbb{F}_q^{n-k}$ and a distance $t \in [0, n]$, one wants to find a vector $e = (e_1, \dots, e_d) \in (\mathbb{F}_q^{n/d})^d$ such that $He = s$ and $\forall i \in [1, d]$, $|e_i| = t/d$.

## SDITH framework

Solve the $SD(d, H, s, t)$ problem with :

* a random $H$

* $s$ from an injected solution ($s = He$ such that $|e_i| = t/d$)
# Reduce $SD(d)$ to $SD(1)$?

In the specification, they use [Feneuil, Joux, Rivain, 2022] results to obtain the following bound

## Reduction from $SD(d)$ to $SD(1)$

$$T_{SD(d)} \geq \frac{\binom{n/d}{t/d}^d}{\binom{n}{t}} T_{SD(1)}$$

## Idea:

* Consider an algorithm $\mathcal{A}$ which solves $SD(d)$

* Let $(H, s, t)$ be an instance of $SD(1)$

* Run $\mathcal{A}$ on $(H_\sigma, s_\sigma, t)$ with a random permutation at each step

* There is a probability $\frac{\binom{n/d}{t/d}^d}{\binom{n}{t}}$ of obtaining an instance of $SD(d)$ at each step.

## Problem

This bound is tight only when $t \to 0$ (we will see why)
# How they analyze security

## What algorithm used to solve SD(1)?

* ISDs (Information Set Decoding) as usual

* In the case of SDITH the field size is big $q = 256$ or $q = 251$

* They claim that it is enough to stop at Stern's algorithm [Stern,1989]

* Asymptotically with $n$ and $q$ [May,Meurer,Thomas,2011] and [Becker,Joux,May,Meurer,2012] are equivalent to [Prange,1962] ([Canto Torres,2016])

* But non asymptotically?

## Security assessment in the specification

* Based on Stern algorithm

* They perform non-asymptotic analysis to gain security bits

* They use Peters' tricks [Peters,2010] to optimize the non-asymptotic complexity of Stern
Stern algorithm

Input : $\mathbf{H} \in \mathbb{F}_q^{(n-k) \times n}$, $\mathbf{s} \in \mathbb{F}_q^{n-k}$ and $t \in [0, n]$
Output : $\mathbf{e} \in \mathbb{F}_q^n$ such that $\mathbf{He} = \mathbf{s}$ and $|\mathbf{e}| = t$
Parameters : $p \in [0, \frac{\min(t,k)}{2}]$ and $\ell \in [0, n-k-t+2p]$

Repeat as many time as necessary :

● draw $I \subseteq [1, n]$ of size $k$ uniformly at random

● $J \leftarrow [1, n] \setminus I$

● $\mathbf{P} \leftarrow \mathbf{H}_J^{-1}\mathbf{H}_I$

● $\mathbf{y} \leftarrow \mathbf{H}_J^{-1}\mathbf{s}$

● $\mathbf{P}' \leftarrow$ the $\ell$ first rows of $\mathbf{P}$ and $\mathbf{y}' \leftarrow$ the $\ell$ first positions of $\mathbf{s}$

● Bet that :

● $e_I = (x_1, x_2) \in \mathbb{F}_q^{k/2}$ such that $|x_1| = |x_2| = p$

● $e_J = (0_l, x_3) \in \mathbb{F}_q^l \times \mathbb{F}_q^{n-k-l}$ such that $|x_3| = t - 2p$
How to find e with betting?

With the bet, we have :

$$
\begin{pmatrix} \mathbf{P}'\mathbf{x}_2 \\ \mathbf{x}_3 \end{pmatrix} = \begin{pmatrix} \mathbf{y}' - \mathbf{P}'\mathbf{x}_1 \\ \mathbf{y}'' - \mathbf{P}''(\mathbf{x}_1 + \mathbf{x}_2) \end{pmatrix}
$$

● $\mathcal{L}_1 \leftarrow \{\mathbf{y}' - \mathbf{P}'\mathbf{x}_1 : \mathbf{x}_1 \in \mathbb{F}_q^{\lfloor k/2 \rfloor} \times 0^{k-\lfloor k/2 \rfloor} \text{ and } |\mathbf{x}_1| = p\}$

$\mathcal{L}_2 \leftarrow \{ \mathbf{P}'\mathbf{x}_2 : \mathbf{x}_2 \in 0^{\lfloor k/2 \rfloor} \times \mathbb{F}_q^{k-\lfloor k/2 \rfloor} \text{ and } |\mathbf{x}_2| = p \}$

● For all $(\mathbf{y}' - \mathbf{P}'\mathbf{x}_1, \mathbf{P}'\mathbf{x}_2) \in \mathcal{L}_1 \times \mathcal{L}_2$ such that $\mathbf{y}' - \mathbf{P}'\mathbf{x}_1 = \mathbf{P}'\mathbf{x}_2$

• If $|\mathbf{P}(\mathbf{x}_1 + \mathbf{x}_2) - \mathbf{y}| = t - 2p$, return e, such that

$\bullet e_I \stackrel{\text{def}}{=} \mathbf{x}_1 + \mathbf{x}_2$

• $e_J \stackrel{\text{def}}{=} \mathbf{y} - \mathbf{P}(\mathbf{x}_1 + \mathbf{x}_2)$
Stern complexity

$$T_{\text{SD}(1)} = \left( \frac{T_{\text{Gauss}} + T_{\text{lists}} + T_{\text{checks}}}{(1 - (1 - p_e)^{N_{\text{sol}}})} \right) \log_2(q)$$

* $T_{\text{Gauss}}$: complexity of Gaussian elimination

* $T_{\text{lists}}$: complexity of constructing lists

* $T_{\text{checks}}$: complexity of collision checking

* $p_e$: probability of finding a particular solution

* $N_{\text{sol}}$: expected number of solutions to the problem
Peters trick to construct $\mathcal{L}_1$ and $\mathcal{L}_2$

● $\mathcal{L}_1 = \{\mathbf{P}'\mathbf{x}_1 - \mathbf{y}' : \mathbf{x}_1 \in \mathbb{F}_q^{\lfloor k/2 \rfloor} \text{ and } |\mathbf{x}_1| = p\}$ and

$\mathcal{L}_2 = \{\mathbf{P}'\mathbf{x}_2 : \mathbf{x}_2 \in \mathbb{F}_q^{\lfloor k/2 \rfloor - \lfloor k/2 \rfloor} \times \text{ and } |\mathbf{x}_2| = p\}$

● Choose an enumeration order $\sigma$ on $\{\mathbf{x} \in \mathbb{F}_q^{\lfloor k/2 \rfloor} : |\mathbf{x}| = p\}$ such that $\mathbf{x}_{\sigma(i)}$ and $\mathbf{x}_{\sigma(i+1)}$ differ by 1 on at most two **successive** coordinates depending on the case:

● **On the same support** : $\mathbf{x}_{\sigma(i)} = (\dots, d, \dots, 0) \Rightarrow \mathbf{x}_{\sigma(i+1)} = (\dots, d+1, \dots, 0) \Rightarrow \text{One coordinate}$

● **Change of support** : $\mathbf{x}_{\sigma(i)} = (\dots, q-1, 0, \dots) \Rightarrow \mathbf{x}_{\sigma(i+1)} = (\dots, 0, 1, \dots, 0) \Rightarrow \text{Two successive coordinates}$

● Precompute the sums of two successive columns of $\mathbf{P}'$

● Construct an element of the list $\Rightarrow$ one addition of one column of size $\ell$ (except the first which requires $p-1$ or $p$ addition of columns depending on the list)

$$T_{\text{lists}} = \ell k + \ell(2p-1) + \ell(|\mathcal{L}_1| + |\mathcal{L}_2|) \quad (1.1)$$
Second and third tricks

The second trick comes into collision checking

$$|\mathbf{P}(\mathbf{x}_1 - \mathbf{x}_2) - \mathbf{y}| = t - 2p \qquad (1.2)$$

* Verify that the Hamming weight of a certain vector of length $n-k-\ell$ equals $t-2p$

* Remarks that the vector is actually a random vector when it does not come from a wanted solution

* On the wrong candidates, check the Hamming weight over $\frac{q}{q-1}(t-2p+1)$ positions on average

* Checking on each coordinate for each position : $2p$ additions, $2p \frac{q-2}{q-1}$ multiplications

$$T_{\text{checks}} = \frac{q}{q-1}(t-2p+1)2p \left(1 + \frac{q-2}{q-1}\right) \frac{|\mathcal{L}_1| |\mathcal{L}_2|}{q^\ell}$$

Third trick

The third trick concerns Gaussian elimination but they neglect it because they claim that its cost is negligible
# Their complexity result

Let's summarize their results :

## Complexité

* $L_1 := |\mathcal{L}_1| = \binom{\lfloor \frac{k}{2} \rfloor}{p} (q-1)^p$

* $L_2 := |\mathcal{L}_2| = \binom{k-\lfloor \frac{k}{2} \rfloor}{p} (q-1)^p$

* $T_{\text{Gauss}} = \frac{1}{2}(n-k)^2(n+k)$

* $T_{\text{lists}} = \ell k + \ell(2p-1) + \ell(|\mathcal{L}_1| + |\mathcal{L}_2|)$

* $T_{\text{checks}} = \frac{q}{q-1}(t-2p+1)2p\left(1+\frac{q-2}{q-1}\right) \frac{|\mathcal{L}_1||\mathcal{L}_2|}{q^\ell}$

* $p_e = \frac{L_1 L_2 \binom{n-k-\ell}{t-2p}}{\binom{n}{t}(q-1)^{2p}}$

* $N_{\text{sol}} = 1$
<table><caption>Table – SDITH security in the specification</caption><thead><tr><th rowspan="2">Parameter Sets</th><th rowspan="2">Category</th><th colspan="4">Security Specification</th><th colspan="5">SD Parameters</th></tr><tr><th>p</th><th>l</th><th>T<sub>SD(1)</sub> <sup>(n/d)<sup>d</sup></sup>&frasl;<sub>(t/d)<sup>n</sup></sub></th><th>target</th><th>q</th><th>n</th><th>k</th><th>t</th><th>d</th></tr></thead><tbody><tr><td>SDitH-L1-gf256</td><td>I</td><td>1</td><td>2</td><td>143.46</td><td>143</td><td>256</td><td>230</td><td>126</td><td>79</td><td>1</td></tr><tr><td>SDitH-L1-gf251</td><td>I</td><td>1</td><td>2</td><td>143.45</td><td>143</td><td>251</td><td>230</td><td>126</td><td>79</td><td>1</td></tr><tr><td>SDitH-L3-gf256</td><td>III</td><td>2</td><td>5</td><td>207.67</td><td>207</td><td>256</td><td>352</td><td>193</td><td>120</td><td>2</td></tr><tr><td>SDitH-L3-gf251</td><td>III</td><td>2</td><td>5</td><td>207.61</td><td>207</td><td>251</td><td>352</td><td>193</td><td>120</td><td>2</td></tr><tr><td>SDitH-L5-gf256</td><td>V</td><td>2</td><td>5</td><td>272.35</td><td>272</td><td>256</td><td>480</td><td>278</td><td>150</td><td>2</td></tr><tr><td>SDitH-L5-gf251</td><td>V</td><td>2</td><td>5</td><td>272.29</td><td>272</td><td>251</td><td>480</td><td>278</td><td>150</td><td>2</td></tr></tbody></table>
# The choice of a non-asymptotic analysis

## Advantage

* Bit gain on security

## Inconvenience

* Very accurate calculations ⇒ easy to make mistakes

* We are exposed to more attacks which bring non-asymptotic gains
1. Security Analysis in NIST specification

2. Correction of the analysis

* First problem

* Second problem

* Third problem

3. Improved attack with projective space
They do not take into account the $N_{sol}$ factor

Definition

* Let $N_{sol}(d)$ denote the expected number of solutions of SD(d)

* $d_{GV}(n, k) \stackrel{\text{def}}{=} \inf \left( \left\{ t \in \left\lfloor 0, n - \frac{n}{q} \right\rfloor : \binom{n}{t} (q-1)^t \ge q^{n-k} \right\} \right)$

* With their parameters, they take $t = d_{GV}(n, k)$, they assume that the factor $N_{sol}(1)$ is one (we only have the injected solution)

* It is only true asymptotically with $n$

* With their range of parameters $N_{sol}(1) \in [412, 1056] \Rightarrow$ between 8.7 and 10 bits lost
They consider that Gaussian elimination is negligible

In the case of SDitH-L1-gf256 with $q, n, k, t, d = 256, 230, 126, 79, 1$

Their optimal cases :

* $T_{lists} = 15.974459404437539$

* $T_{checks} = 20.231483911937776$

* $T_{Gauss} : 20.883072906964095$

* $T = 143.4589084369141$

The optimal case if we neglect Gaussian elimination :

* $T_{lists} = 16.559421905158693$

* $T_{checks} = 12.231483911937778$

* $T_{Gauss} : 20.883072906964095$

* $T = 140.4941924784691$

It's the opposite

* The cost of Gaussian elimination is even exactly their dominant term

* We have to consider [Bernstein,Lange,Peters,2008] and [Peters,2010] to improve $T_{Gauss}$
The reduction bound is not tight

They do not take into account $N_{sol}$

* Without $N_{sol}$: $p_e(1) \ge \frac{\binom{n/d}{t/d}}{\binom{n}{t}} p_e(d)$

* With $N_{sol}$: $p_e(1)N_{sol}(1) \ge p_e(d) \frac{\binom{n/d}{t/d}}{\binom{n}{t}} \left(1 + (N_{sol}(d) - 1) \frac{\binom{n}{t}}{\binom{n/d}{t/d}}\right)$

The precise reduction from $SD(d)$ to $SD(1)$ give

1. $N_{sol}(d) = 1 \Rightarrow p_e(1)N_{sol}(1) \ge \frac{\binom{n/d}{t/d}}{\binom{n}{t}} p_e(d)N_{sol}(d)$

2. $N_{sol}(d) \gg 1 \Rightarrow p_e(1)N_{sol}(1) \ge p_e(d)N_{sol}(d)$

$N_{sol}(d) \in [30, 748]$ so we are in the second case giving

$$T_{SD(d)} \ge T_{SD(1)}$$

Consequences

Their bound is therefore optimistic, with the real bound they gain security bits
Stern algorithm adapted to SD(d)

it's interesting to directly solve the problem SD(d) here. We therefore adapt Stern to SD(d)

Principle of adaptation

1. Split the information set I as $I_1 \cup \dots \cup I_d$ where $I_i$ is of size $\frac{k}{d}$ and is randomly chosen in I.

2. Make a bet on each of them.

The fact that

$$T_I(d) \le T_I(1)$$

makes us gain in complexity compared to the theoretical bound.
<table><caption>Table – Correction of the analysis</caption><thead><tr><th rowspan="2">Parameter Sets</th><th colspan="3">Security Specification</th><th colspan="3">Correction</th><th colspan="5">SD Parameters</th></tr><tr><th>p</th><th>l</th><th>T<sub>SD(1)</sub>(n/d)<sup>d</sup>/(n/2)</th><th>p</th><th>l</th><th>T<sub>SD(d)</sub></th><th>q</th><th>n</th><th>k</th><th>t</th><th>d</th></tr></thead><tbody><tr><td>SDitH-L1-gf256</td><td>1</td><td>2</td><td>143.46</td><td>1</td><td>2</td><td>134.61</td><td>256</td><td>230</td><td>126</td><td>79</td><td>1</td></tr><tr><td>SDitH-L1-gf251</td><td>1</td><td>2</td><td>143.45</td><td>1</td><td>2</td><td>133.61</td><td>251</td><td>230</td><td>126</td><td>79</td><td>1</td></tr><tr><td>SDitH-L3-gf256</td><td>2</td><td>5</td><td>207.67</td><td>2</td><td>5</td><td>206.16</td><td>256</td><td>352</td><td>193</td><td>120</td><td>2</td></tr><tr><td>SDitH-L3-gf251</td><td>2</td><td>5</td><td>207.61</td><td>2</td><td>5</td><td>205.02</td><td>251</td><td>352</td><td>193</td><td>120</td><td>2</td></tr><tr><td>SDitH-L5-gf256</td><td>2</td><td>5</td><td>272.35</td><td>2</td><td>5</td><td>271.30</td><td>256</td><td>480</td><td>278</td><td>150</td><td>2</td></tr><tr><td>SDitH-L5-gf251</td><td>2</td><td>5</td><td>272.29</td><td>2</td><td>5</td><td>269.81</td><td>251</td><td>480</td><td>278</td><td>150</td><td>2</td></tr></tbody></table>

Remark

We have not yet corrected the complexity of Gaussian elimination, we have to consider [Bernstein,Lange,Peters,2008] and [Peters,2010]
1 Security Analysis in NIST specification

2 Correction of the analysis

* First problem

* Second problem

* Third problem

3 Improved attack with projective space
Observation

Suppose we are trying to solve the problem SD(1) in the case of a 0 syndrome.

We get a good solution if and only if we find $x_1$ and $x_2$ such that

$$P'x_1 = P'x_2 \text{ and } |P(x_1 - x_2)| = t - 2p \quad (3.1)$$

We calculate $(q-1)$ times too much solution

$(x_1, x_2)$ checks (3.1) $\Leftrightarrow$ for all $\alpha$ non zero $(\alpha x_1, \alpha x_2)$ checks (3.1)

How to exploit that?

Adaptation of Stern's algorithm in projective space

Impact on complexity

We divide the size of the lists by a $(q-1)$ factor $\Rightarrow$ we hope to gain a factor $(q-1)$ on the complexity

What if the syndrome is non-zero?
# Reduction of the Syndrome Decoding problem to the low weight code words search

## The reduction :

We look for e such that $\mathbf{H_e} = s$ and $|e| = t$.

Let $\mathcal{C}$ be the code associated with the parity check matrix $\mathbf{H}$.

* Find $z$ such that $\mathbf{H}_z = s$ ($z = (0, s)$)

* Let $\mathbf{H}_z$ a parity check matrix of the code $\langle \mathcal{C}, z \rangle$.

* Find e such that $\mathbf{H}_e = 0$

## Analysis

The algorithm finds e such that $\mathbf{H_e} = \alpha s$ (for a $\alpha \in \mathbb{F}_q$).
(So just divide by $\alpha$ and we solved the problem)

## Proof on board

### What about the complexity

* The reduction cost almost nothing (a factor $\frac{q}{q-1}$)

* We reduced the problem to dimension $k+1 \Rightarrow$ possible loss
Projective space

For a space $\mathcal{E}$ over $\mathbb{F}_q$

$$ \bullet \quad \forall \mathbf{x}, \mathbf{y} \in \mathcal{E}, \quad \mathbf{x} \sim \mathbf{y} \iff \exists \alpha \in \mathbb{F}_q^*, \mathbf{x} = \alpha \mathbf{y} $$

$$ \bullet \quad [\mathbf{x}] \stackrel{\text{def}}{=} \{\mathbf{y} \in \mathcal{E} : \mathbf{y} \sim \mathbf{x}\} $$

$$ \bullet \quad \mathcal{E}/\sim \stackrel{\text{def}}{=} \{[\mathbf{x}] : \mathbf{x} \in \mathcal{E}\} $$
Choose the right representatives

To exploit the idea, we want to take the lists in projective space to divide their size as well as the number of collisions by $(q-1)$:

$$ \mathcal{L}'_1 = \{[\mathbf{P}'\mathbf{x}_1] : [\mathbf{x}_1] \in \mathbb{F}_q^{\lfloor \frac{k+1}{2} \rfloor} / \sim \text{and } |\mathbf{x}_1| = p\} $$

$$ \mathcal{L}'_2 = \{[\mathbf{P}'\mathbf{x}_2] : [\mathbf{x}_2] \in \mathbb{F}_q^{k+1-\lfloor \frac{k+1}{2} \rfloor} / \sim \text{and } |\mathbf{x}_2| = p\} $$

We must take precautions

* A collision of equivalence classes does not necessarily induce a collision
  $[\mathbf{P}'\mathbf{x}_1] = [\mathbf{P}'\mathbf{x}_2] \Leftrightarrow \mathbf{P}'\mathbf{x}_1 = \mathbf{P}'\mathbf{x}_2$

* Only a proportion of $\frac{1}{q-1}$ of the pairs $(x'_1, x'_2) \in ([\mathbf{x}_1], [\mathbf{x}_2])$ induce a collision

* We cannot do a naive search for such a couple otherwise we lose the gain of the factor $(q-1)$
The solution

We build good representatives who induce a collision

Particular representative

For all $[\mathbf{x}] \in \mathbb{F}_q^{\frac{k+1}{2}}/\sim$ we define $\bar{\mathbf{x}}$ as the unique representative of $[\mathbf{x}]$ such that :

* If $\mathbf{P}'\mathbf{x} = \mathbf{0}$ : the first non-zero symbol of $\bar{\mathbf{x}}$ is 1

* If $\mathbf{P}'\mathbf{x} \neq \mathbf{0}$ : the first non-zero symbol of $\mathbf{P}'\bar{\mathbf{x}}$ is 1

We now have the desired property

Property

$$[\mathbf{P}'\mathbf{x}_1] = [\mathbf{P}'\mathbf{x}_2] \Leftrightarrow \mathbf{P}'\overline{\mathbf{x}_1} = \mathbf{P}'\overline{\mathbf{x}_2}$$
The algorithm

The only things that change with the classic Stern algorithm are the following :

$$
\mathcal{L}'_1 \leftarrow \left\{ \mathbf{P}'\overline{\mathbf{x}_1} : [\mathbf{x}_1] \in \left( \mathbb{F}_q^{\lceil \frac{k+1}{2} \rceil} \times 0^{k+1-\lceil \frac{k+1}{2} \rceil} \right) / \sim \text{ and } |\mathbf{x}_1| = p \right\}
$$

$$
\mathcal{L}'_2 \leftarrow \left\{ \mathbf{P}'\overline{\mathbf{x}_2} : [\mathbf{x}_2] \in \left( 0^{\lceil \frac{k+1}{2} \rceil} \times \mathbb{F}_q^{k+1-\lceil \frac{k+1}{2} \rceil} \right) / \sim \text{ and } |\mathbf{x}_2| = p \right\}
$$

The collision checking is done with (x1, x2)

The possible losses on the theoretical gain of the factor (q - 1) :

problem one

We must adapt Peters' tips to our new algorithm $\Rightarrow$ potential losses

problem two

We go from dimension $k$ to dimension $(k+1) \Rightarrow$ potential losses
Adaptation of tricks

The tricks on list construction :

* Use as before an enumeration order on $\{\hat{x} \in \mathbb{F}_q^{(k+1)/2} : \hat{x} = (0, \dots, 0, 1, \dots) \text{ and } |\hat{x}| = p\}$ to compute $P'\hat{x}$ in one addition of one columns by elements.

* Normalize $P'\hat{x}$ by its first non-zero coordinate to get $P'\bar{x}$ (We lose a factor of 2 here on the trick)

$$T'_{\text{lists}} \approx \frac{2}{q} T_{\text{lists}}$$

The second trick on collision checking :

We just need to normalize $\hat{x}$ on collisions to get $\bar{x}$ which takes $2p$ operations per collisions (negligible). We can then apply the trick as before.

$$T'_{\text{checks}} \approx \frac{1}{q} T_{\text{checks}}$$
# The real gain

For the other complexity values, we have :

* $T'_{\text{Gauss}} \approx T_{\text{Gauss}}$

* $N'_{\text{sol}} \approx N_{\text{sol}}$

* $p'_{e} \approx p_{e}/4$ ($\frac{\binom{n-k-1-\ell}{t-2p}}{\binom{n-k-\ell}{t-2p}} \approx \frac{1}{4}$ for the range of parameters)

## Expected gain

* We lose 2 bits due to the transition from dimension $k$ to dimension $k + 1$.

* We lose 1 bit if $T'_{\text{lists}}$ control $T'_{\text{checks}}$

* We should have an additional gain between 5 and 6 bits with the projections

## Remark

We can adapt the Stern projectif algorithm to the problem $\text{SD}(d)$ as previously
<table><caption>Table – SDITH security with our results</caption><thead><tr><th rowspan="2"></th><th colspan="3">Security Specification</th><th colspan="3">Correction</th><th colspan="3">d-split-Stern-proj</th><th colspan="4">SD Parameters</th></tr><tr><th>p</th><th>l</th><th>T<sub>SD(1)</sub>(<sup>n/d</sup>/<sub>t/d</sub>)</th><th>p</th><th>l</th><th>T<sub>SD(d)</sub></th><th>p</th><th>l</th><th>T<sub>SD(d)</sub></th><th>q</th><th>n</th><th>k</th><th>t</th><th>d</th></tr></thead><tbody><tr><td>L1-gf256</td><td>1</td><td>2</td><td>143.46</td><td>1</td><td>2</td><td>134.61</td><td>2</td><td>4</td><td>130.07</td><td>256</td><td>230</td><td>126</td><td>79</td><td>1</td></tr><tr><td>L1-gf251</td><td>1</td><td>2</td><td>143.45</td><td>1</td><td>2</td><td>133.91</td><td>2</td><td>4</td><td>129.36</td><td>251</td><td>230</td><td>126</td><td>79</td><td>1</td></tr><tr><td>L3-gf256</td><td>2</td><td>5</td><td>207.67</td><td>2</td><td>5</td><td>206.16</td><td>2</td><td>4</td><td>200.73</td><td>256</td><td>352</td><td>193</td><td>120</td><td>2</td></tr><tr><td>L3-gf251</td><td>2</td><td>5</td><td>207.61</td><td>2</td><td>5</td><td>205.02</td><td>2</td><td>4</td><td>199.65</td><td>251</td><td>352</td><td>193</td><td>120</td><td>2</td></tr><tr><td>L5-gf256</td><td>2</td><td>5</td><td>272.35</td><td>2</td><td>5</td><td>271.30</td><td>2</td><td>4</td><td>266.77</td><td>256</td><td>480</td><td>278</td><td>150</td><td>2</td></tr><tr><td>L5-gf251</td><td>2</td><td>5</td><td>272.29</td><td>2</td><td>5</td><td>269.81</td><td>2</td><td>4</td><td>265.35</td><td>251</td><td>480</td><td>278</td><td>150</td><td>2</td></tr></tbody></table>
<table><caption>Table – Bit gain on security</caption><thead><tr><th rowspan="2">Parameter Sets</th><th colspan="3">Gains</th></tr><tr><th>Gain-Correction</th><th>Gain-proj</th><th>Total Gain</th></tr></thead><tbody><tr><td>SDitH-L1-gf256</td><td>8.84</td><td>4.54</td><td>13.39</td></tr><tr><td>SDitH-L1-gf251</td><td>9.54</td><td>4.54</td><td>14.09</td></tr><tr><td>SDitH-L3-gf256</td><td>1.51</td><td>5.43</td><td>6.94</td></tr><tr><td>SDitH-L3-gf251</td><td>2.59</td><td>5.36</td><td>7.96</td></tr><tr><td>SDitH-L5-gf256</td><td>1.04</td><td>4.53</td><td>5.57</td></tr><tr><td>SDitH-L5-gf251</td><td>2.48</td><td>4.46</td><td>6.94</td></tr></tbody></table>

The loss of 0.5 bits on the expected results is linked to the fact that the Gaussian elimination is not negligible.
Work in coming

* Improvement of $T_{Gauss}$ with [Bernstein,Lange,Peters,2008] and [Peters,2010]

* Apply the adaptation of projective spaces to [Dumer,1991] to see if we obtain a gain

* Try to generalize the idea to the Grassmannian (generalization of projective spaces with several dimensions)