# Design of a Linear Layer Optimised for Bitsliced 32-bit Implementation

Gaëtan Leurent, Clara Pernot

► To cite this version:

Gaëtan Leurent, Clara Pernot. Design of a Linear Layer Optimised for Bitsliced 32-bit Implementation. IACR Transactions on Symmetric Cryptology, 2024, 2024 (1), pp.441-458. 10.46586/tosc.v2024.i1.441-458 . hal-04925740

HAL Id: hal-04925740

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

Submitted on 2 Feb 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Design of a Linear Layer Optimised for Bitsliced 32-bit Implementation

Gaëtan Leurent and Clara Pernot

Inria, Paris, France

gaetan.leurent@inria.fr, clpernot@laposte.net

**Abstract.** The linear layer of block ciphers plays an important role in their security. In particular, ciphers designed following the wide-trail strategy use the branch number of the linear layer to derive bounds on the probability of linear and differential trails. At FSE 2014, the LS-design construction was introduced as a simple and regular structure to design bitsliced block ciphers. It considers the internal state as a bit matrix, and applies alternatively an identical S-Box on all the columns, and an identical L-Box on all the lines. Security bounds are derived from the branch number of the L-Box.

In this paper, we focus on bitsliced linear layers inspired by the LS-design construction and the Spook AEAD algorithm. We study the construction of bitsliced linear transformations with efficient implementations using XORs and rotations (optimized for bitsliced ciphers implemented on 32-bit processors), and a high branch number. In order to increase the density of the activity patterns, the linear layer is designed on the whole state, rather than using multiple parallel copies of an L-Box.

Our main result is a linear layer for 128-bit ciphers with branch number 21, improving upon the best 32-bit transformation with branch number 12, and the one of Spook with branch number 16.

**Keywords:** Bitsliced cipher · Linear layer · Branch number

## 1 Introduction

Block ciphers are one of the most versatile primitives in symmetric cryptography. In particular, the AES [AES01] is currently used to secure the majority on online communication. Most block ciphers are constructed with linear layers and SBoxes: the linear layer mixes the state to provide diffusion; while the SBoxes apply a non-linear operation in parallel to small chunks of the state to provide confusion. This echoes the confusion and diffusion properties of Shannon [Sha45].

A common strategy to design a block cipher is to alternate substitution layers, linear layers, and key additions. This is denoted SPN, and many common ciphers follow this construction: AES [AES01], PRESENT [BKL$^+$07], Skinny [BJK$^+$16], GIFT [BPP$^+$17], ... In order to evaluate the security of those ciphers against differential and linear cryptanalysis, designers typically show bounds on the number of active SBoxes in a differential or linear trail. Combined with the cryptographic properties of the SBox (differential uniformity and linearity), this implies bounds on the probability (or bias) of linear and differential trails. Over the years, various methods have been proposed to obtain bounds on the number of active SBoxes, such as running Matsui's branch and bound algorithm [Mat95], using the wide-trail strategy [DR01], or modeling the search as a MILP problem.
<figure><img src="image_2.png" /><figcaption>Figure 1: A SPN cipher</figcaption></figure>

## 1.1 Design strategies for SPN ciphers

We consider an SPN cipher with $\ell$ parallel SBoxes, each operating on $s$ bits; the block size is $n = \ell s$ (see Figure 1). In this paper, we denote $\mathbb{B}_s$ the set of all $s$-bit elements: $\mathbb{B}_s = \{0,1\}^s$. The internal state is considered as an element in $\mathbb{B}_s^\ell = (\{0,1\}^s)^\ell$, i.e., a sequence of $\ell$ $s$-bit elements $x = (x_0, x_1, \dots, x_{\ell-1})$. We define the Hamming weight of $x$ as $|x| = \#\{i \in \{0,1,\dots,\ell-1\} : x_i \neq 0\}$ (Hamming weight over $\mathbb{B}_s^\ell$).

The round function iterates three transformations:

**SBox layer:** an invertible SBox $S: \mathbb{B}_s \to \mathbb{B}_s$ is applied in parallel to each state element

$$x_i \leftarrow S(x_i), \forall i$$

**Linear layer:** an invertible linear transformation $\Lambda: \mathbb{B}_s^\ell \to \mathbb{B}_s^\ell$ is applied to the state

$$(x_0, x_1, \dots, x_{\ell-1}) \leftarrow \Lambda(x_0, x_1, \dots, x_{\ell-1})$$

In some ciphers such as the AES, $\Lambda$ is a linear operation over $\mathbb{F}_{2^s}$ (identified with $\mathbb{B}_s$) but we consider a more general definition where $\Lambda$ is only required to be linear over $\mathbb{F}_2$.

**Key addition:** a round key $k \in \mathbb{B}_s^\ell$ is added (XORed) to the state

$$(x_0, x_1, \dots, x_{\ell-1}) \leftarrow (x_0, x_1, \dots, x_{\ell-1}) \oplus k$$

SPN ciphers with a full key addition are usually seen as Markov ciphers [LMM91]. Therefore, we can compute the probability of a differential characteristic (resp. correlation of a linear trail) by multiplying the probability (resp. correlation) of each round. In particular, if we obtain a lower bound on the number of active SBoxes, this translates into an upper bound for the probability of differential characteristics (resp. bias of linear trails).
### 1.1.1 The Wide-Trail Strategy

The wide-trail strategy [DR01] is an important method to design SPN ciphers, used in the AES and some of its predecessors. The focus of the wide-trail strategy is to design a linear layer that guarantees a large number of active SBoxes, and to select SBoxes with good cryptographic properties. When the two are combined, they provide bounds on the probability of differential characteristics (and correlation of linear trails).

The differential branch number of a linear transformation $\Lambda$ is defined as

$$ \mathcal{B}_d(\Lambda) = \min_{x \neq 0} (|\Lambda(x)| + |x|). $$

This is an important security property, measuring the diffusion of a linear layer: any non-trivial differential characteristics in two consecutive rounds has at least $\mathcal{B}_d(\Lambda)$ active SBoxes [DR01, Theorem 1]. Therefore, if the SBox has differential uniformity $\delta$, the probability of any r-round differential trail is at most $(\delta/2^s)^{\mathcal{B}_d \cdot [r/2]}$.

Similarly, the linear branch number is defined as

$$ \mathcal{B}_l(\Lambda) = \min_{x \neq 0} (|\Lambda^\top(x)| + |x|), $$

where $\Lambda^\top$ is the linear transformation whose matrix representation over $\mathbb{F}_2$ is the transpose of the matrix representation of $\Lambda$ (note that we must consider the matrix representation as an $\ell s \times \ell s$ matrix over $\mathbb{F}_2$, not as an $\ell \times \ell$ matrix over $\mathbb{F}_{2^s}$). Any non-trivial linear trail in two consecutive rounds has at least $\mathcal{B}_l(\Lambda)$ active SBoxes. Therefore, if the SBox has linearity $\lambda$, the expected squared correlation of any r-round linear trail is at most $(\lambda^2/2^{2s})^{\mathcal{B}_d \cdot [r/2]}$.

We have $2 \le \mathcal{B}_d(\Lambda) \le \ell + 1$ and $2 \le \mathcal{B}_l(\Lambda) \le \ell + 1$. A linear layer is called an MDS matrix when $\mathcal{B}_d(\Lambda) = \ell + 1$; this condition is equivalent to $\mathcal{B}_l(\Lambda) = \ell + 1$. Besides, when the linear layer is orthogonal (i.e. when $\Lambda^\top = \Lambda^{-1}$), we have $\mathcal{B}_l(\Lambda) = \mathcal{B}_d(\Lambda)$.

Alternatively, the differential branch number can be seen as the minimal distance of the code with codewords $x \parallel \Lambda(x)$ for $x \in \mathbb{B}_s^\ell$. If $\Lambda$ is linear over $\mathbb{F}_{2^s}$, this is a linear code over $\mathbb{F}_{2^s}$ of length $2\ell$ and dimension $\ell$. However, the code is only $\mathbb{F}_{2^s}$-linear in general; as an $\mathbb{F}_{2^s}$-linear code it has length $2n = 2\ell s$ and dimension $n = \ell s$, but the branch number is the minimal distance using the Hamming distance over $\mathbb{B}_s$.

In the AES, the linear layer has branch number 5. This guarantees at least 5 active SBoxes every two rounds. Moreover, the AES has a stronger property, due to the interaction between the MixColumns and ShiftRows operations: any 4-round trail has at least 25 active SBoxes (the square of the branch number). In this work we focus on two-round bounds.<fnref n="1" />

### 1.1.2 Bitsliced Ciphers and LS-Designs

Conceptually, a software implementation of an SPN cipher uses a memory cell for each SBox input ($\ell$ memory units of $s$ bits), so that an SBox application corresponds to a table lookup. Alternatively, SPN ciphers can be implemented in a *bitsliced* way with $s$ memory units of $\ell$ bits: a memory cell gathers bits from each SBox, and the SBox is computed with a series of arithmetic operation (AND, OR, XOR, ...). The CPU arithmetic operations operate in parallel on each bit of a memory cell, so that several SBoxes are computed simultaneously. Bitsliced implementations of AES and DES have been proposed with good performances [Bih97, KS09]. They have the advantage of avoiding table lookups; it is well known that table lookups cause side channels because of memory cache, and this leads to practical attacks [TSS+03].

<footnote n="1">¹Obtaining bounds on more than two rounds would likely require different techniques than considered in this work. As a concrete example, [GLSV15] computes bounds over several rounds in the paragraph “From Involutive to Non-involutive Components”, but their approach will not scale to 32-bit words.</footnote>
In general, a bitsliced implementation requires reorganizing the memory layout. However, some ciphers are designed with a bitsliced operation in mind, and are described with a bitsliced state, such as Noekeon [DPVAR00].

The LS-designs [GLSV15] are a family of ciphers optimized for bitsliced implementation. The state is considered as an $s \times \ell$ matrix of bits; the SBox layer applies the same SBox $S: \mathbb{B}_s \to \mathbb{B}_s$ on each column, and the linear layer applies a fixed LBox $L: \mathbb{B}_\ell \to \mathbb{B}_\ell$ on each line. In practice, each line is stored in an $\ell$-bit register, so that the SBox is implemented as a series of bitsliced operations. The linear layer $\Lambda$ operates independently on each register, applying the same transformation $L: \mathbb{F}_2^\ell \to \mathbb{F}_2^\ell$ on each line (corresponding to a given bit of all SBoxes):

$$ (x_0[j], x_1[j], \dots, x_{\ell-1}[j]) \leftarrow L(x_0[j], x_1[j], \dots, x_{\ell-1}[j]), \forall j < s $$

The branch number of $\Lambda$ (over $\mathbb{F}_{2^s}$) is equal to the branch number of $L$ (over $\mathbb{F}_2$). Simple bounds on the security are derived directly from the properties of the SBox and the branch number.

Two 128-bit ciphers are proposed in [GLSV15], Robin and Fantomas, using $s = 8$ and $\ell = 16$. The linear layer is built from an optimal code over $\mathbb{F}_2$ with length $2\ell = 32$ and dimension $\ell = 16$: the resulting LBox is orthogonal, with distance 8. The linear layer is implemented as a series of table lookups. Since the LBox is linear, table lookups are easy to protect against side-channel using masking.

### 1.1.3 Spook

Spook [BBB$^{+20}$] is an AEAD scheme using primitives that build upon the ideas of LS-designs. In particular, Spook uses a 128-bit tweakable block cipher (Clyde-128) that is strongly inspired by the LS-design construction, with two important differences.

First, the LBox is designed so that it has an efficient implementation using XORs and rotations, rather than using table lookups. The block cipher PRIDE [ADK$^{+14}$] also uses a linear layer optimized for implementation with XORs and rotations, but focuses on more efficient implementations and lower branch number. Clyde-128 uses $s = 4$ and $\ell = 32$ so that a natural implementation uses 32-bit words and is efficient on 32-bit processors.

Second, Clyde-128 differs from LS-designs by using an interleaved LBox operating on two $\ell$-bit registers at once, rather than independently on each register. This enables a larger branch number with a modest increase in implementation cost. In particular the best known linear code with length 64 and dimension 32 has distance 12 [Gra07], but the linear layer of Clyde-128 has branch number 16 (as a reference point, the best known linear code over $\mathbb{F}_4$ with length 64 and dimension 32 has minimal distance 17). The linear layer of Clyde-128 and its inverse have an implementation with just 6 XORs and 6 rotations per word (see Algorithm 4 and 5).

## 1.2 Our Results

In this work we follow the strategy of the Spook linear layer to design an efficient linear layer for 128-bit ciphers with good cryptographic properties. We assume that the cipher uses bitsliced 4-bit SBoxes, and we search for a linear layer with a good implementation on 32-bit processors.

We extend the construction of Spook by considering a linear layer that operates on 3 or 4 words at a time, rather than 2. This presents two difficulties, compared to what was done by the Spook designers: bounding the branch number of such a linear layer requires a lot of computation, and the techniques to obtain an efficient implementation of the inverse are not applicable with those parameters.

Eventually, we manage to build a linear transformation with branch number 21, improving from the branch number 16 used in Spook. Our linear layer is as expensive to
<table><caption>**Table 1:** Linear transformations based on XORs and rotations operating on one to four 32-bit words. $c(L)$ corresponds to the number of XORs per 32-bit word in the implementation we propose.</caption><thead><tr><th>LBox</th><th>w</th><th>Branch number</th><th>c(L)</th><th>c(L<sup>-1</sup>)</th><th>Ref</th></tr></thead><tbody><tr><td>L<sub>32</sub></td><td>1</td><td>12</td><td>5</td><td>5</td><td>[Leu19]</td></tr><tr><td>L<sub>32×2</sub></td><td>2</td><td>16</td><td>6</td><td>6</td><td>[BBB<sup>+</sup>20]</td></tr><tr><td>L<sub>32×3</sub></td><td>3</td><td>19</td><td>6</td><td>13</td><td>Subsection 4.1</td></tr><tr><td>L<sub>32×4</sub></td><td>4</td><td>21</td><td>6</td><td>18</td><td>Subsection 4.2</td></tr></tbody></table>

compute than Spook's in the forward direction, but the inverse is around three times more expensive. The code used to search for LBoxes is available from: https://github.com/Lbox-ToSC/lbox-search.

To compare the efficiency of the different linear transformations, we define the notion of cost $c$, which corresponds to the number of XORs to be performed per 32-bit word. Since our linear transformations alternate XORs and rotations, the actual implementation cost is proportional to the number of XORs.

# 2 Linear Transformations Based on XORs and Rotations

An efficient way to build linear transformations is to use a sequence of XORs and rotations. This has been used as a component in several symmetric ciphers, such as SHA-2 [NIS02], PRIDE [ADK<sup>+</sup>14], Spook [BBB<sup>+</sup>20], or Ascon [DEMS21]. In this paper, we use $\oplus$ to denote XOR, and $\ggg$ (resp. $\lll$) to denote circular rotation to the right (resp. left).

## 2.1 Operating on a Single Word

We first consider a linear transformation operating on a single $\ell$-bit word, i.e. an LBox, implemented as a series of rotations, and XORs. For instance, the SHA-2 $\Sigma_0$ function is defined over 32-bit words as:

$$ \Sigma_0(A) = (A \ggg 2) \oplus (A \ggg 13) \oplus (A \ggg 22) $$

Another example given in Algorithm 2 reuses internal values.

By construction this type of linear transformation satisfies $L(x \ggg r) = L(x) \ggg r$, $\forall x \forall r$. Therefore, when written in matrix form, we obtain a circulant matrix: each line is a rotation of the previous line. The set of circulant matrices has a strong structure; in particular the product of two circulant matrices is a circulant matrix. A circulant matrix can be identified with a polynomial in $\mathbb{F}_2[X]/(X^\ell + 1)$, by taking the content of the first row as the coefficients; the product of two circulant matrices is the same as the polynomial product in the ring $\mathbb{F}_2[X]/(X^\ell + 1)$. In particular, a polynomial is invertible in the ring if and only if it is relatively prime with $X^\ell + 1$; when $\ell$ is a power of two, we have $X^\ell + 1 = (X + 1)^\ell$ and a polynomial is invertible if and only if the sum of the coefficients is non-zero. Therefore, when $\ell$ is a power of two, a circulant matrix is invertible if and only if the sum of the elements in the first row is non-zero, and its inverse is also a circulant matrix.

The linear code associated to the LBox is a quasi-cyclic (double circulant) code, with one block being the matrix $L$, and one block being the identity. This class of codes is often used in code-based cryptography because they have a compact description, and they include codes with good properties. In our case we are interested in this class because they have an efficient implementation without using lookup tables.
Alternatively, the input of the linear transformation can be considered in interleaved form. The interleaving function $\mathcal{I}$ takes $w$ $\ell$-bit words as input and turns them into a single $w\ell$-bit word by transposing the bits:

$$ \mathcal{I}(x_1, \dots, x_w) = x_1[0]x_2[0]\dots x_w[0] x_1[1]x_2[1]\dots x_w[1] \dots $$

We define the interleaved matrix $\bar{L}$ of a linear transformation $L$ as the matrix such that

$$ \mathcal{I}(L \times (x_1, \dots, x_w)) = \bar{L} \times \mathcal{I}(x_1, \dots, x_w) $$

As a simplification, the designers of Spook [Leu19] focused on a subset of linear transformations where $\bar{L}$ is a circulant $w\ell \times w\ell$ matrix. This is a subset of the block-circulant linear transformations, because an implementation of $\bar{L}$ using rotations and XORs on one $w\ell$-bit register can be rewritten as an implementation using rotations and XOR on $w$ $\ell$-bit registers, using the following properties:

$$ \mathcal{I}(x_1, x_2, \dots, x_w) \gg wr = \mathcal{I}(x_1 \gg r, x_2 \gg r, \dots, x_w \gg r) $$

$$ \mathcal{I}(x_1, x_2, \dots, x_w) \gg 1 = \mathcal{I}(x_w \gg 1, x_1, \dots, x_{w-1}) $$

As a concrete example, the Spook LBox is shown in Algorithm 4; it takes two words as input and uses a sequence of rotations and XORs to produce two words of output. It is actually built from the following interleaved implementation (given a 64-bit input $x$):

$$ a \leftarrow x \oplus \text{rot}(x, 24) $$

$$ a \leftarrow a \oplus \text{rot}(a, 6) $$

$$ a \leftarrow a \oplus \text{rot}(x, 34) $$

$$ b \leftarrow a \oplus \text{rot}(a, 62) $$

$$ a \leftarrow a \oplus \text{rot}(b, 51) $$

$$ a \leftarrow a \oplus \text{rot}(b, 30) $$

$$ \text{return } \text{rot}(a, 1) $$

## 2.3 Differential and Linear Branch Numbers

An important property of LBoxes built from a circulant matrix $\bar{L}$ is that the linear and differential branch number are equal.

We use the following notation for a circulant matrix $C$, with $c_0, \dots, c_{w\ell-1} \in \mathbb{B} = \{0, 1\}$:

$$ C = \text{Circ}(c_0, c_1, \dots, c_{w\ell-1}) = \begin{bmatrix} c_0 & c_1 & \dots & c_{w\ell-1} \\ c_{w\ell-1} & c_0 & \dots & c_{w\ell-2} \\ \vdots & \vdots & \ddots & \vdots \\ c_1 & c_2 & \dots & c_0 \end{bmatrix} $$

In particular, we have $C^\top = \text{Circ}(c_0, c_1, \dots, c_{w\ell-1})^\top = \text{Circ}(c_0, c_{w\ell-1}, \dots, c_1)$.

**Case $w = 1$.** We first consider the case $w = 1$. We obtain similar expressions for the differential and linear branch number:

$$ \mathcal{B}_d(C) = \min_{x \neq 0} \left( |\text{Circ}(c_0, c_1, \dots, c_{\ell-1})(x)| + |x| \right) $$

$$ \mathcal{B}_l(C) = \min_{x \neq 0} \left( |\text{Circ}(c_0, c_1, \dots, c_{\ell-1})^\top(x)| + |x| \right) $$

$$ = \min_{x \neq 0} \left( |\text{Circ}(c_0, c_{\ell-1}, \dots, c_1)(x)| + |x| \right) $$

$$ = \min_{x \neq 0} \left( |P(\text{Circ}(c_0, c_1, \dots, c_{\ell-1})(x))| + |x| \right), $$
with $P$ a transformation that permutes its elements:

$$ P: \quad \mathbb{B}^{\ell} \to \mathbb{B}^{\ell} \\ (x_0, x_1, \dots, x_{\ell-1}) \mapsto (x_0, x_{\ell-1}, \dots, x_1) $$

Since the Hamming weight is invariant up to permutation of the elements, we have $|P(x)| = |x|$ and we obtain $\mathcal{B}_d(C) = \mathcal{B}_l(C)$.

**General case.** In general, the linear transformation is defined as $L(x) = \mathcal{I}^{-1}(C(\mathcal{I}(x)))$. We obtain:

$$ \begin{aligned} \mathcal{B}_d(C) &= \min_{x \neq 0} \left( |\mathcal{I}^{-1}(\mathrm{Circ}(c_0, c_1, \dots, c_{w\ell-1})(x))| + |x| \right) \\ \mathcal{B}_l(C) &= \min_{x \neq 0} \left( |\mathcal{I}^{-1}(\mathrm{Circ}(c_0, c_1, \dots, c_{w\ell-1})^{\top}(x))| + |x| \right) \\ &= \min_{x \neq 0} \left( |\mathcal{I}^{-1}(\mathrm{Circ}(c_0, c_{w\ell-1}, \dots, c_1)(x))| + |x| \right) \\ &= \min_{x \neq 0} \left( |\mathcal{I}^{-1}(P(\mathrm{Circ}(c_0, c_1, \dots, c_{w\ell-1})(x)))| + |x| \right), \end{aligned} $$

with $P$ a transformation that permutes its elements:

$$ P: \quad \mathbb{B}^{w\ell} \to \mathbb{B}^{w\ell} \\ (x_0, x_1, \dots, x_{w\ell-1}) \mapsto (x_0, x_{w\ell-1}, \dots, x_1) $$

We observe that $P$ preserves the interleaved Hamming weight over $\mathbb{B}_w^\ell$ by writing it over $\mathbb{B}^{w\ell}$:

$$ \begin{aligned} |x| &= |(x_0, x_1, \dots, x_{w\ell-1})| \\ &= \max(x_0, x_1, \dots, x_{w-1}) + \max(x_w, x_{w+1}, \dots, x_{2w-1}) + \dots \\ |\mathcal{I}^{-1}(x)| &= |\mathcal{I}^{-1}(x_0, x_1, \dots, x_{w\ell-1})| \\ &= \max(x_0, x_\ell, \dots, x_{(w-1)\ell}) + \max(x_1, x_{\ell+1}, \dots, x_{(w-1)\ell+1}) + \dots \\ |\mathcal{I}^{-1}(P(x))| &= |\mathcal{I}^{-1}(x_0, x_{w\ell-1}, \dots, x_1)| \\ &= \max(x_0, x_{(w-1)\ell}, \dots, x_\ell) + \max(x_{w\ell-1}, x_{(w-1)\ell-1}, \dots, x_{w\ell-\ell-1}) + \dots \\ &= |\mathcal{I}^{-1}(x)| \end{aligned} $$

Therefore we have $\mathcal{B}_d(L) = \mathcal{B}_l(L)$.

## 2.4 Search for Good LBoxes

In order to find an LBox with a good implementation, the Spook designers ran a search over potential implementations until obtaining an LBox with a good branch number [Leu19], rather than first searching a good matrix and then searching a good implementation of this matrix. The implementation is considered as a sequence of operations $x_i \leftarrow x_{a_i} \oplus \mathrm{rot}(x_{b_i}, r_i)$ (with $a_i, b_i < i$), where the input is $x_0$ and the output is the last computed value. Starting with a fixed number of operations $k$, the search algorithm generates random parameters $(a_i, b_i, r_i)_{i=1}^k$, and evaluates the branch number of the resulting linear transformation. The best linear transformation is kept as the result.

The most computationally intensive part of the search is to evaluate the branch number of a given LBox. Finding the branch number of $L$ is equivalent to finding the value $x \neq 0$ that minimizes $|L(x)| + |x|$. A naive approach does exhaustive search over all possible
$x$; this is practical for a 32-bit linear transformation. An improved variant tries $x$ by increasing weight: if $|L(x)| + |x| \ge b$ for all $x$ with $|x| \le b-2$, then the branch number is at least $b$ (because $L$ is invertible). We define the set $\mathcal{X}_h = \{x \in \mathbb{F}_{2^w}^\ell : |x| \le h\}$ of words of weight at most $h$; in order to show that the branch number is at least $b$, we only have to search over the set $\mathcal{X}_{b-2}$. However, this is not feasible with the Spook parameters: with $\ell = 32$, $w = 2$ and branch number 16, we would have to consider $\mathcal{X}_{14}$ of size $\sum_{h=1}^{14} \binom{32}{h} 3^h \approx 2^{51.4}$.

To further reduce the search space, we observe that if $|L(x)| + |x| \le b$ then $|x| \le b/2$ or $|L(x)| \le b/2$. Therefore, to show that the branch number is at least $b$ it is sufficient to exhaustively search all $x$ in $\mathcal{X}_{\lfloor b/2 \rfloor}$ and in $\{L^{-1}(x) : x \in \mathcal{X}_{\lfloor b/2 \rfloor}\}$. With the Spook parameters, we only have to consider $\mathcal{X}_8$ of size roughly $2^{36.2}$, so that this approach is practical. The algorithm is given as Algorithm 1. Moreover, since $L$ is circulant, we can skip candidates that are equivalent up to rotation. This technique works well for Spook [Leu19], but it does not scale to larger values of $w > 2$.

<caption>**Algorithm 1** Compute the branch number of an LBox</caption>

Input: $L$
$b \leftarrow |L(1)| + 1$
$h \leftarrow 1$
while $h \le b/2$ do
    for $x \in \mathcal{X}_h$ do
        if $|x| + |L(x)| < b$ then
            $b \leftarrow |x| + |L(x)|$
        if $|x| + |L^{-1}(x)| < b$ then
            $b \leftarrow |x| + |L^{-1}(x)|$
        $h \leftarrow h + 1$
    return $b$

## 2.5 Efficient Inverse

In order to use a linear transformation in an SPN cipher, it is useful to also have an efficient implementation of the inverse (this is not always a requirement; for instance the CTR mode of encryption does not use the inverse of the block cipher). When using the approach of the previous section we obtain an LBox with an efficient implementation, but we cannot derive an efficient implementation of $L^{-1}$ from an efficient implementation of $L$.

Instead, the Spook designers ran a birthday search to find two efficient implementations such that the resulting matrices $L$ and $L'$ are each other's inverses. The space of circulant matrices is of size $2^{w\ell}$; $2^{w\ell-1}$ are invertible and after identifying matrices that are rotations of each others there are approximately $2^{w\ell-1}/w\ell$ equivalence classes. Therefore the birthday search is expected to find one matrix with efficient implementation in both directions after trying roughly $2^{w\ell/2}/\sqrt{w\ell}$ random implementations ($2^{29}$ with the Spook parameters). In order to obtain $2^t$ candidates, the complexity is roughly $\sqrt{t} \times 2^{w\ell/2}/\sqrt{w\ell}$. With $\ell = 32$, this approach is feasible for $w \le 2$ but not for $w > 2$.

## 2.6 Known Results

We now summarize the state of the art on efficient LBoxes defined for $\ell = 32$-bit words.

**Operating on 1 word [Leu19].** When operating on one word, there are around $2^{31}/32 = 2^{26}$ invertible circulant matrices up to equivalence by rotation. The branch number of a candidate can be computed with at most $2 \times |\mathcal{X}_6| \approx 2^{21.1}$ operations, assuming it is smaller
than 12. Therefore, it is practical to exhaustively search all circulant matrices, showing that the best possible branch number is 12. This matches the best known linear codes with dimension 32 and length 64.

Moreover, there exist LBoxes in this set with an efficient inverse: Algorithm 2 and 3 give the implementation of an LBox with branch number 12 using 5 rotations and 5 XORs, and its inverse using 6 rotations and 5 XORs.

<caption>**Algorithm 2 L32 LBox**</caption>

**Input:** $x$
$a \leftarrow x \oplus \text{rot}(x, 1)$
$b \leftarrow a \oplus \text{rot}(a, 4)$
$a \leftarrow b \oplus \text{rot}(a, 9)$
$b \leftarrow a \oplus \text{rot}(x, 3)$
**return** $b \oplus \text{rot}(a, 6)$

<caption>**Algorithm 3 L32 LBox inverse**</caption>

**Input:** $x$
$a \leftarrow x \oplus \text{rot}(x, 2)$
$b \leftarrow x \oplus \text{rot}(a, 3)$
$a \leftarrow b \oplus \text{rot}(a, 16)$
$b \leftarrow a \oplus \text{rot}(b, 6)$
**return** $\text{rot}(a, 25) \oplus \text{rot}(b, 15)$

**Operating on 2 words [BBB+20, Leu19].** When operating on two words, exhaustive search is no longer possible. The Spook authors ran a search for random circulant matrices, and the best branch number obtained was 16. They also found an LBox with branch number 16 with efficient implementation and efficient inverse, which is used in Spook; Algorithm 4 gives its implementation using 13 rotations and 12 XORs, while Algorithm 5 gives its inverse using 14 rotations and 12 XORs.

<caption>**Algorithm 4 Spook L-box**</caption>

**Input:** $(x, y)$
$a \leftarrow x \oplus \text{rot}(x, 12)$
$b \leftarrow y \oplus \text{rot}(y, 12)$
$a \leftarrow a \oplus \text{rot}(a, 3)$
$b \leftarrow b \oplus \text{rot}(b, 3)$
$a \leftarrow a \oplus \text{rot}(x, 17)$
$b \leftarrow b \oplus \text{rot}(y, 17)$
$c \leftarrow a \oplus \text{rot}(a, 31)$
$d \leftarrow b \oplus \text{rot}(b, 31)$
$a \leftarrow a \oplus \text{rot}(d, 26)$
$b \leftarrow b \oplus \text{rot}(c, 25)$
$a \leftarrow a \oplus \text{rot}(c, 15)$
$b \leftarrow b \oplus \text{rot}(d, 15)$
$b \leftarrow \text{rot}(b, 1)$
**return** $(b, a)$

<caption>**Algorithm 5 Spook L-box inverse**</caption>

**Input:** $(x, y)$
$a \leftarrow x \oplus \text{rot}(x, 25)$
$b \leftarrow y \oplus \text{rot}(y, 25)$
$c \leftarrow x \oplus \text{rot}(a, 31)$
$d \leftarrow y \oplus \text{rot}(b, 31)$
$c \leftarrow c \oplus \text{rot}(a, 20)$
$d \leftarrow d \oplus \text{rot}(b, 20)$
$a \leftarrow c \oplus \text{rot}(c, 31)$
$b \leftarrow d \oplus \text{rot}(d, 31)$
$c \leftarrow c \oplus \text{rot}(b, 26)$
$d \leftarrow d \oplus \text{rot}(a, 25)$
$a \leftarrow a \oplus \text{rot}(c, 17)$
$b \leftarrow b \oplus \text{rot}(d, 17)$
$a \leftarrow \text{rot}(a, 15)$
$b \leftarrow \text{rot}(b, 16)$
**return** $(b, a)$

# 3 Search for New Linear Transformations

In this work, we consider linear transformations with $l = 32$ for efficiency reasons, and we attempt to design linear transformations operating on more than 2 words at a time ($w > 2$). This should increase the branch number that we can achieve, but there are two issues that make the previous methods inapplicable:

* The algorithm to compute the branch number described in Section 2.4 is not applicable to $w > 2$;
* The birthday search described in Section 2.5 to find a matrix with efficient implementation and efficient inverse is not applicable to $w > 2$.

## 3.1 Computing the Branch Number Efficiently

As mentioned above, computing the branch number of an LBox is equivalent to computing the minimal distance of a linear code. In particular, we observe that the algorithm described in Section 2.4 is actually the classical Brouwer-Zimmermann [Zim96, BBF+06] minimum distance algorithm, applied to the code generated by $I \parallel \bar{L}$. As far as we know this is the best deterministic algorithm to compute the branch number of an arbitrary linear code, but coding theory offers probabilistic algorithms that are more efficient.

### 3.1.1 Information Set Decoding Algorithm

To efficiently compute the branch number, we use tools from coding theory. More specifically, we use an Information Set Decoding (ISD) algorithm [Pra62] to find a non-zero codeword with the lowest possible weight.

This is an iterative algorithm which, given a matrix, a weight $w$, a number of iterations $t$, and a parameter $d$, returns a codeword of weight $w$ if it finds one.

**Case $w = 1$.** We first describe how the algorithm in the case $w = 1$, so that the code is linear over the field $\mathbb{F}_2$ and the weight is the standard Hamming weight. The code has dimension $\ell$ and length $2\ell$, and is given as a $\ell \times 2\ell$ generating matrix.

We assume that there is a word $W$ of weight $w$ in the code. Each iteration tries to find such a word, and succeeds with some probability $p$. Each iteration works as follows. First, starting from the matrix $\bar{L}$, a random permutation of the columns is performed, and a Gaussian reduction is performed. After the permutation, the $\ell$ columns on the left are called an information set.

We hope that $W$ has weight exactly 1 in the information set. This happens with probability:

$$p = \frac{\binom{\ell}{w-1} \times \binom{\ell}{1}}{\binom{2\ell}{w}}$$

In this case, $W$ is one of the rows of the matrix, if the matrix is in row echelon form.

We have a good probability to find $W$ after $1/p$ iterations: after $(1/p) \times \epsilon$ iterations, we find it with probability $1 - (1-p)^{(1/p) \times \epsilon} \approx 1 - e^{-\epsilon}$.

Knowing that the complexity of this algorithm is dominated by the Gaussian elimination, we consider combinations of $d$ rows. We therefore increase the probability of finding a word of weight $w$ if one exists. This succeeds if $W$ has weight lower or equal than $d$ in the information set. The success probability is:

$$p = \sum_{j=1}^{d} \frac{\binom{\ell}{w-j} \times \binom{\ell}{j}}{\binom{2\ell}{w}}$$

**General case.** When $w > 1$, we consider a code defined by $2^{w\ell}$ basis vectors in $\mathbb{F}_w^{2\ell}$, given a $w\ell \times 2w\ell$ matrix. The code is linear over $\mathbb{F}_2$ but the Hamming weight is defined over $w$-bit words. Therefore, we don't process columns and rows directly, but packets of $w$ columns and $w$ rows:

* instead of randomly permuting the columns, we need to swap packets of $w$ columns, because this permutation corresponds to the selection of an information set, which is defined in association with the Hamming weight.
* instead of enumerating rows in the binary case, i.e., scanning all rows of weight 1 on the information set, here we have to scan all words of weight 1 in the information set: the $2^w - 1$ words with weight 1 on the first packet of $w$ columns, the $2^w - 1$ words with weight 1 on the second packet of $w$ columns, ... In the case $d = 1$, there will therefore be $\ell \times (2^w - 1)$ elements to enumerate.

**Algorithm 6 Information Set Decoding Algorithm to compute the distance of a linear code**

**Input:** $C$: linear code,
$d$: maximum number of rows to XOR to verify weight,
$t$: number of iterations,
**w:** the desired weight.
**for** $i = 1, \dots, t$ **do**
&emsp;&emsp;$C \leftarrow$ Random\_permutation\_of\_columns ($C$)
&emsp;&emsp;$C \leftarrow$ Gaussian\_elimination ($C$)
&emsp;&emsp;**for** all combination $x$ of at most $d$ rows **do**
&emsp;&emsp;&emsp;**if** $|x| < w$ **then**
&emsp;&emsp;&emsp;&emsp;**return** $x$
&emsp;&emsp;**return** False

## 3.2 Best Distance Obtained

First, we looked for the branch number achievable for random circulant matrices: for 3 32-bit words, after $2^{27}$ tests, the best branch number we obtained is 19, which is achieved by 7% of random circulant matrices. For 4 32-bit words, after $2^{18}$ tests, the maximum we obtained is 21, and it is reached by 42% of the random circulant matrices. In the next section, we look for linear transformations with efficient implementation (based on XOR and rotations, as described above) that reach those maximums.

## 3.3 Implementing the Inverse

**Simultaneous Search of $L$ and $L^{-1}$**. As explained in Section 2.5, the strategy used to find linear transformations that can be implemented as well as their inverses using a sequence of operations $x_i \leftarrow x_{a_i} \oplus \text{rot}(x_{b_i}, r_i)$ is impractical for 3 or more words. So we use another strategy: we generate matrices using a sequence of operations $x_i \leftarrow x_{a_i} \oplus \text{rot}(x_{b_i}, r_i)$, and then, for candidates with a high branch number, we look for an efficient implementation of their inverse. This implementation of the inverse will be less efficient than those proposed above, but nonetheless more efficient than a naive implementation.

**Heuristic Search of Good Implementation.** In this section, we describe how to build an implementation of the inverse from its matrix description. We use the notation $|x|_2$ to denote the binary Hamming weight (as opposed to the Hamming weight $|x|$ over $\mathbb{B}_w$). A naive implementation of an LBox $L$ requires $|L(1)|_2$ rotations and $|L(1)|_2 - 1$ XORs, but we can use heuristics to find a more efficient implementation.

Since we work with circulant matrices, we only consider the $wl$-bit word corresponding to the first row of the matrix. Our approach is to start with the target $L(1)$ and to decompose it into several words. For simplicity, we only count the number of XORs in an implementation. We start with the following decomposition:

$$x = a \oplus (a \gg r) \oplus b.$$ Given a target $x$, we iterate over all $r$ ($1 \le r < wl$) and we construct a value $a$ to obtain a small value $|a|_2 + |b|_2$ with $b = x \oplus a \oplus (a \gg r)$.
A good candidate is $z = x \wedge (x \ll r)$; when $z$ and $z \gg r$ are disjoint we take $a = z$ and obtain $|b|_2 = |x|_2 - 2|a|_2$ with $|a|_2 + |b|_2$ minimal. In general, we use a greedy algorithm to iteratively build $a$.

We can implement $a$ and $b$ naively, and we obtain an implementation of $x$ with cost $(|a|_2 - 1) + (|b|_2 - 1) + 2$; most of the time this is smaller than the cost of a naive implementation ($|x|_2 - 1$). We can often further reduce the cost of the implementation by recursively decomposing $a$ and $b$.

More generally, we build a recursive algorithm to find an implementation of a vector of target values $(x_0, \dots, x_v)$. At each step, we apply several heuristics to attempt to decompose elements of the vector. We start the algorithm with the vector $(L(1))$, and eventually we implement the final vector naively and reconstruct the target by inverting the decomposition operations.

We consider the following decompositions:

$x_i = a \oplus (a \gg r) \oplus b$. We exhaustively consider all $x_i$'s (and $r$) and use the same decomposition as above. This reduces the implementation cost if $|a|_2 + |b|_2 < |x_i|_2$. The new vector to decompose is $(x_0, \dots, x_{i-1}, x_{i+1}, \dots, x_v, a, b)$.

$x_i = a \oplus (x_j \gg r)$. We exhaustively consider all pairs $(x_i, x_j)$ and all values $r$, and define $a = x_i \oplus x_j \gg r$. If $|a|_2 + 1 < |x_i|_2$ this reduces the implementation cost. The new vector to decompose is $(x_0, \dots, x_{i-1}, x_{i+1}, \dots, x_v, a)$.

$x_i = a \oplus b, x_j = (a \gg r) \oplus c$. We exhaustively consider all pairs $(x_i, x_j)$ and all values $r$, and define $a = x_i \wedge (x_j \ll r)$, $b = x_i \oplus a$, $c = x_j \oplus (a \gg r)$. We have $|b|_2 = |x_i|_2 - |a|_2$ and $|c|_2 = |x_j|_2 - |a|_2$, so that this reduces the implementation cost when $|a|_2 > 1$.

The new vector to decompose is $(x_0, \dots, x_{i-1}, x_{i+1}, \dots, x_{j-1}, x_{j+1}, \dots, x_v, a, b)$.

When several decompositions are possible, we try various heuristics to select a decomposition, from a simple greedy heuristic to more advanced heuristics (with a recursive call to the greedy heuristic) to get a more accurate estimate of the cost of the new vector.

We also considered a decomposition that adds an arbitrary bit to one of the objectives; this random noise generally increases the implementation cost but it can sometimes simplify a later decomposition.

# 4 Results

Using the new described methods, we managed to obtain matrices with efficient implementations that meet the best distances obtained with random circulant matrices for 3 and 4 words.

## 4.1 Considering 3 Words

We first consider a linear layer operating on three 32-bit words, to be used for a cipher with a 96-bit or 192-bit internal state. We found an LBox operating on three 32-bit words with branch number 19 and an efficient implementation (18 rotations and 18 XORs). It matches the best branch number observed with random circulant matrices, and the number of XORs per 32-bit word is 6, as in Spook. The implementation of the inverse has been found using the strategy described in Section 3.3: it has 42 rotations and 39 XORs. The implementations of the linear transformation and its inverse are given in algorithms 7 and 9. This candidate was tested with $2^{20}$ iterations of the information set decoding algorithm 6 with $\mathbf{w} = 18$ and $d = 3$. Each iteration costs $\binom{32}{3} \times 7^3 + \binom{32}{2} \times 7^2 + 32 \times 7 \approx 2^{20.7}$, and
the probability of finding a word of weight 18 at each iteration is $2^{-10.17}$. By repeating $2^{20}$ times, the probability of failing to find this word is $e^{-2^{20-10.17}} \approx 2^{-1313}$ if it exists.

## 4.2 Considering 4 Words

Next, we consider a linear layer operating on four 32-bit words, to be used for a cipher with a 128-bit internal state (our main target), or a 256-bit internal state. We found an LBox operating on four 32-bit words with branch number 21 and an efficient implementation (24 rotations and 24 XORs). It matches the best branch number observed with random circulant matrices, and the number of XORs per 32-bit word is 6, as in Spook. The implementation of the inverse has been found using the strategy described in Section 3.3: it has 76 rotations and 72 XORs. The implementations of the linear transformation and its inverse are given in algorithms 8 and 10. This candidate was tested with $2^{25}$ iterations of the information set decoding algorithm 6 with $w = 20$ and $d = 2$. Each iteration costs $(\binom{32}{2} \times 15^2 + 32 \times 15) \approx 2^{16.8}$, and the probability of finding a word of weight 20 at each iteration is $2^{-16.29}$. By repeating $2^{25}$ times, the probability of failing to find this word is $e^{-2^{25-16.29}} \approx 2^{-604}$ if it exists.

<caption>Algorithm 7 $L_{32 \times 3}$ LBox</caption>

Input: $(x, y, z)$
    $a \leftarrow x \oplus \text{rot}(y, 17)$
    $b \leftarrow y \oplus \text{rot}(z, 17)$
    $c \leftarrow z \oplus \text{rot}(x, 18)$
    $d \leftarrow a \oplus \text{rot}(c, 30)$
    $e \leftarrow b \oplus \text{rot}(a, 31)$
    $c \leftarrow c \oplus \text{rot}(b, 31)$
    $a \leftarrow d \oplus \text{rot}(x, 21)$
    $b \leftarrow e \oplus \text{rot}(y, 21)$
    $f \leftarrow c \oplus \text{rot}(z, 21)$
    $d \leftarrow d \oplus \text{rot}(b, 30)$
    $e \leftarrow e \oplus \text{rot}(f, 30)$
    $c \leftarrow c \oplus \text{rot}(a, 31)$
    $a \leftarrow d \oplus \text{rot}(c, 23)$
    $b \leftarrow e \oplus \text{rot}(d, 24)$
    $f \leftarrow c \oplus \text{rot}(e, 24)$
    $a \leftarrow a \oplus \text{rot}(d, 26)$
    $b \leftarrow b \oplus \text{rot}(e, 26)$
    $c \leftarrow f \oplus \text{rot}(c, 26)$
    \textbf{return} $(a, b, c)$

<caption>Algorithm 8 $L_{32 \times 4}$ LBox</caption>

Input: $(x, y, z, t)$
    $a \leftarrow x \oplus \text{rot}(y, 19) \oplus \text{rot}(t, 24)$
    $b \leftarrow y \oplus \text{rot}(z, 19) \oplus \text{rot}(x, 25)$
    $c \leftarrow z \oplus \text{rot}(t, 19) \oplus \text{rot}(y, 25)$
    $d \leftarrow t \oplus \text{rot}(x, 20) \oplus \text{rot}(z, 25)$
    $e \leftarrow a \oplus \text{rot}(c, 2)$
    $f \leftarrow b \oplus \text{rot}(d, 2)$
    $g \leftarrow c \oplus \text{rot}(a, 3)$
    $h \leftarrow d \oplus \text{rot}(b, 3)$
    $i \leftarrow e \oplus \text{rot}(h, 8)$
    $j \leftarrow f \oplus \text{rot}(e, 9)$
    $k \leftarrow g \oplus \text{rot}(f, 9)$
    $l \leftarrow h \oplus \text{rot}(g, 9)$
    $e \leftarrow i \oplus \text{rot}(d, 30)$
    $f \leftarrow j \oplus \text{rot}(a, 31)$
    $g \leftarrow k \oplus \text{rot}(b, 31)$
    $h \leftarrow l \oplus \text{rot}(c, 31)$
    $a \leftarrow e \oplus \text{rot}(k, 3)$
    $b \leftarrow f \oplus \text{rot}(l, 3)$
    $c \leftarrow g \oplus \text{rot}(i, 4)$
    $d \leftarrow h \oplus \text{rot}(j, 4)$
    \textbf{return} $(a, b, c, d)$

## 4.3 Results on Smaller Word Sizes

Our technique can easily be applied to smaller word sizes. In Table 2, we list results on 16-bit words and 8-bit words. In particular, with 16-bit words we obtain branch number 14 with 8 words, corresponding to a 128-bit state. With 8-bit words, we obtain branch number 8 with 8 words, corresponding to an almost-MDS diffusion layer.
<table><caption>**Algorithm 9** $L_{32 \times 3}$ LBox inverse</caption><thead><tr><th>Input: (x, y, z)</th><th></th></tr></thead><tbody><tr><td>a ← rot(y, 14) ⊕ rot(y, 26)</td><td>l ← l ⊕ c</td></tr><tr><td>b ← rot(z, 14) ⊕ rot(z, 26)</td><td>g ← g ⊕ rot(e, 26)</td></tr><tr><td>c ← rot(x, 15) ⊕ rot(x, 27)</td><td>h ← h ⊕ rot(f, 26)</td></tr><tr><td>d ← rot(a, 8)</td><td>i ← i ⊕ rot(d, 27)</td></tr><tr><td>e ← rot(b, 8)</td><td>a ← rot(y, 1) ⊕ rot(z, 22)</td></tr><tr><td>f ← rot(c, 8)</td><td>b ← rot(z, 1) ⊕ rot(x, 23)</td></tr><tr><td>a ← a ⊕ rot(a, 1)</td><td>c ← rot(x, 2) ⊕ rot(y, 23)</td></tr><tr><td>b ← b ⊕ rot(b, 1)</td><td>j ← j ⊕ rot(c, 18)</td></tr><tr><td>c ← c ⊕ rot(c, 1)</td><td>k ← k ⊕ rot(a, 19)</td></tr><tr><td>g ← rot(z, 6)</td><td>l ← l ⊕ rot(b, 19)</td></tr><tr><td>h ← rot(x, 7)</td><td>d ← d ⊕ a ⊕ rot(d, 8)</td></tr><tr><td>i ← rot(y, 7)</td><td>e ← e ⊕ b ⊕ rot(e, 8)</td></tr><tr><td>g ← g ⊕ rot(c, 10)</td><td>f ← f ⊕ c ⊕ rot(f, 8)</td></tr><tr><td>h ← h ⊕ rot(a, 11)</td><td>a ← d ⊕ g ⊕ rot(e, 11)</td></tr><tr><td>i ← i ⊕ rot(b, 11)</td><td>b ← e ⊕ h ⊕ rot(f, 11)</td></tr><tr><td>j ← rot(x, 21)</td><td>c ← g ⊕ i ⊕ rot(d, 12)</td></tr><tr><td>k ← rot(y, 21)</td><td>a ← a ⊕ j ⊕ rot(a, 30)</td></tr><tr><td>l ← rot(z, 21)</td><td>b ← b ⊕ k ⊕ rot(b, 30)</td></tr><tr><td>j ← j ⊕ a</td><td>c ← c ⊕ l ⊕ rot(c, 30)</td></tr><tr><td>k ← k ⊕ b</td><td>return (a, b, c)</td></tr></tbody></table>

<table><caption>**Algorithm 10** $L_{32 \times 4}$ LBox inverse</caption><thead><tr><th>Input: (x, y, z, t)</th><th></th></tr></thead><tbody><tr><td>a ← rot(t, 2) ⊕ rot(x, 28)</td><td>e ← e ⊕ rot(q, 12)</td></tr><tr><td>b ← rot(x, 3) ⊕ rot(y, 28)</td><td>f ← f ⊕ rot(r, 12)</td></tr><tr><td>c ← rot(y, 3) ⊕ rot(z, 28)</td><td>g ← g ⊕ rot(s, 12)</td></tr><tr><td>d ← rot(z, 3) ⊕ rot(t, 28)</td><td>h ← h ⊕ rot(u, 12)</td></tr><tr><td>e ← rot(y, 15) ⊕ a</td><td>a ← a ⊕ q ⊕ rot(r, 3)</td></tr><tr><td>f ← rot(z, 15) ⊕ b</td><td>b ← b ⊕ r ⊕ rot(s, 3)</td></tr><tr><td>g ← rot(t, 15) ⊕ c</td><td>c ← c ⊕ s ⊕ rot(u, 3)</td></tr><tr><td>h ← rot(x, 16) ⊕ d</td><td>d ← d ⊕ u ⊕ rot(q, 4)</td></tr><tr><td>a ← rot(y, 25) ⊕ rot(a, 21)</td><td>q ← a ⊕ e ⊕ rot(d, 0)</td></tr><tr><td>b ← rot(z, 25) ⊕ rot(b, 21)</td><td>r ← b ⊕ f ⊕ rot(a, 1)</td></tr><tr><td>c ← rot(t, 25) ⊕ rot(c, 21)</td><td>s ← c ⊕ g ⊕ rot(b, 1)</td></tr><tr><td>d ← rot(x, 26) ⊕ rot(d, 21)</td><td>u ← d ⊕ h ⊕ rot(c, 1)</td></tr><tr><td>i ← rot(x, 9) ⊕ rot(t, 19)</td><td>k ← rot(x, 1) ⊕ rot(t, 26) ⊕ rot(k, 4)</td></tr><tr><td>j ← rot(y, 9) ⊕ rot(x, 20)</td><td>l ← rot(y, 1) ⊕ rot(x, 27) ⊕ rot(l, 4)</td></tr><tr><td>k ← rot(z, 9) ⊕ rot(y, 20)</td><td>i ← rot(z, 1) ⊕ rot(y, 27) ⊕ rot(i, 5)</td></tr><tr><td>l ← rot(t, 9) ⊕ rot(z, 20)</td><td>j ← rot(t, 1) ⊕ rot(z, 27) ⊕ rot(j, 5)</td></tr><tr><td>m ← i ⊕ rot(k, 2) ⊕ rot(e, 7)</td><td>a ← k ⊕ m ⊕ rot(m, 12)</td></tr><tr><td>n ← j ⊕ rot(l, 2) ⊕ rot(f, 7)</td><td>b ← l ⊕ n ⊕ rot(n, 12)</td></tr><tr><td>o ← k ⊕ rot(i, 3) ⊕ rot(g, 7)</td><td>c ← i ⊕ o ⊕ rot(o, 12)</td></tr><tr><td>p ← l ⊕ rot(j, 3) ⊕ rot(h, 7)</td><td>d ← j ⊕ p ⊕ rot(p, 12)</td></tr><tr><td>q ← rot(t, 3) ⊕ rot(y, 7)</td><td>m ← q ⊕ a ⊕ rot(c, 18)</td></tr><tr><td>r ← rot(x, 4) ⊕ rot(z, 7)</td><td>n ← r ⊕ b ⊕ rot(d, 18)</td></tr><tr><td>s ← rot(y, 4) ⊕ rot(t, 7)</td><td>o ← s ⊕ c ⊕ rot(a, 19)</td></tr><tr><td>u ← rot(z, 4) ⊕ rot(x, 8)</td><td>p ← u ⊕ d ⊕ rot(b, 19)</td></tr><tr><td></td><td>return (m, n, o, p)</td></tr></tbody></table>
<table><caption>**Table 2:** Linear transformations based on XORs and rotations operating on 8-bit words and 16-bit words. $c(L)$ is the number of XORs per word.</caption><thead><tr><th>LBox</th><th>ℓ</th><th>w</th><th>β</th><th>c(L)</th></tr></thead><tbody><tr><td>L<sub>8</sub></td><td>8</td><td>1</td><td>4</td><td>2</td></tr><tr><td>L<sub>8×2</sub></td><td>8</td><td>2</td><td>6</td><td>3</td></tr><tr><td>L<sub>8×4</sub></td><td>8</td><td>4</td><td>7</td><td>4</td></tr><tr><td>L<sub>8×6</sub></td><td>8</td><td>6</td><td>7</td><td>4</td></tr><tr><td>L'<sub>8×6</sub></td><td>8</td><td>6</td><td>8</td><td>5</td></tr><tr><td>L<sub>8×8</sub></td><td>8</td><td>8</td><td>8</td><td>4</td></tr></tbody></table>

<table><thead><tr><th>LBox</th><th>ℓ</th><th>w</th><th>β</th><th>c(L)</th></tr></thead><tbody><tr><td>L<sub>16</sub></td><td>16</td><td>1</td><td>8</td><td>4</td></tr><tr><td>L<sub>16×2</sub></td><td>16</td><td>2</td><td>10</td><td>5</td></tr><tr><td>L<sub>16×4</sub></td><td>16</td><td>4</td><td>12</td><td>5</td></tr><tr><td>L<sub>16×6</sub></td><td>16</td><td>6</td><td>13</td><td>5</td></tr><tr><td>L<sub>16×8</sub></td><td>16</td><td>8</td><td>14</td><td>6</td></tr></tbody></table>

# 5 Conclusion

We obtain a 128-bit linear transformation which is a very good candidate for the linear layer of a bitsliced 128-bit cipher with 32 4-bit SBoxes. It has an efficient implementation as a series of 32-bit XORs and rotations, and a branch number of 21.

As a comparison, our new linear layer has a better branch number than the one used in Spook (with branch number 16), and the implementation in the forward direction has the same efficiency. However, the inverse is about three time more expensive. Using our linear layer in Spook would significantly improve the security margin, with a limited impact on performance (because Spook only requires the inverse for the tag verification).

We obtain this result by designing an LBox operating on all four state words, while Spook uses two copies of an LBox operating on 2 words. We had to solve two problems. Firstly, how to compute efficiently the branch number of a linear transformation? For this, we used tools from coding theory: an Information Set Decoding algorithm is used to compute the branch number of a linear transformation. Secondly, how to find linear transformations with an efficient implementation and/or whose inverse has an efficient implementation? To do this, we proposed linear transformations from sequences of XORs and rotations of 32-bit words.

# References

[ADK<sup>+14</sup>] Martin R. Albrecht, Benedikt Driessen, Elif Bilge Kavun, Gregor Leander, Christof Paar, and Tolga Yalçin. Block ciphers - focus on the linear layer (feat. PRIDE). In Juan A. Garay and Rosario Gennaro, editors, *CRYPTO 2014, Part I*, volume 8616 of LNCS, pages 57–76. Springer, Heidelberg, August 2014.

[AES01] Advanced Encryption Standard (AES). National Institute of Standards and Technology, NIST FIPS PUB 197, U.S. Department of Commerce, November 2001.

[BBB<sup>+20</sup>] Davide Bellizia, Francesco Berti, Olivier Bronchain, Gaëtan Cassiers, Sébastien Duval, Chun Guo, Gregor Leander, Gaëtan Leurent, Itamar Levi, Charles Momin, Olivier Pereira, Thomas Peters, François-Xavier Standaert, Balazs Udvarhelyi, and Friedrich Wiemer. Spook: Sponge-based leakage-resistant authenticated encryption with a masked tweakable block cipher. *IACR Trans. Symm. Cryptol.*, 2020(S1):295–349, 2020.

[BBF<sup>+06</sup>] Anton Betten, Michael Braun, Harald Fripertinger, Adalbert Kerber, Axel Kohnert, and Alfred Wassermann. *Error-correcting linear codes: Classification*
by isometry and applications, volume 18. Springer Science & Business Media, 2006.

[Bih97] Eli Biham. A fast new DES implementation in software. In Eli Biham, editor, *FSE'97*, volume 1267 of LNCS, pages 260-272. Springer, Heidelberg, January 1997.

[BJK$^{+}$16] Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY family of block ciphers and its low-latency variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors, *CRYPTO 2016, Part II*, volume 9815 of LNCS, pages 123-153. Springer, Heidelberg, August 2016.

[BKL$^{+}$07] Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe. PRESENT: An ultra-lightweight block cipher. In Pascal Paillier and Ingrid Verbauwhede, editors, *CHES 2007*, volume 4727 of LNCS, pages 450-466. Springer, Heidelberg, September 2007.

[BPP$^{+}$17] Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present (full version). Cryptology ePrint Archive, Report 2017/760, 2017. https://eprint.iacr.org/2017/760.

[DEMS21] Christoph Dobraunig, Maria Eichlseder, Florian Mendel, and Martin Schläffer. Ascon v1.2: Lightweight authenticated encryption and hashing. *Journal of Cryptology*, 34(3):33, July 2021.

[DPVAR00] Joan Daemen, Michaël Peeters, Gilles Van Assche, and Vincent Rijmen. Nessie proposal: Noekeon. October 2000. http://gro.noekeon.org/Noekeon-spec.pdf.

[DR01] Joan Daemen and Vincent Rijmen. The wide trail design strategy. In Bahram Honary, editor, *8th IMA International Conference on Cryptography and Coding*, volume 2260 of LNCS, pages 222-238. Springer, Heidelberg, December 2001.

[GLSV15] Vincent Grosso, Gaëtan Leurent, François-Xavier Standaert, and Kerem Varici. LS-designs: Bitslice encryption for efficient masked software implementations. In Carlos Cid and Christian Rechberger, editors, *FSE 2014*, volume 8540 of LNCS, pages 18-37. Springer, Heidelberg, March 2015.

[Gra07] Markus Grassl. Bounds on the minimum distance of linear codes and quantum codes. Online available at http://www.codetables.de, 2007. Accessed on 2023-08-07.

[KS09] Emilia Käsper and Peter Schwabe. Faster and timing-attack resistant AES-GCM. In Christophe Clavier and Kris Gaj, editors, *CHES 2009*, volume 5747 of LNCS, pages 1-17. Springer, Heidelberg, September 2009.

[Leu19] Gaëtan Leurent. Efficient linear layers for spook. Slides from the "Spook day" worfkshop, July 2019. https://www.spook.dev/assets/workshop/leurent.pdf.

[LMM91] Xuejia Lai, James L. Massey, and Sean Murphy. Markov ciphers and differential cryptanalysis. In Donald W. Davies, editor, *EUROCRYPT'91*, volume 547 of LNCS, pages 17-38. Springer, Heidelberg, April 1991.
[Mat95] Mitsuru Matsui. On correlation between the order of S-boxes and the strength of DES. In Alfredo De Santis, editor, *EUROCRYPT'94*, volume 950 of LNCS, pages 366-375. Springer, Heidelberg, May 1995.

[NIS02] NIST. Secure hash standard. FIPS 180-2, August 2002.

[Pra62] Eugene Prange. The use of information sets in decoding cyclic codes. *IRE Trans. Inf. Theory*, 8(5):5-9, 1962.

[Sha45] Claude E Shannon. A mathematical theory of cryptography. *Mathematical Theory of Cryptography*, 1945.

[TSS+03] Yukiyasu Tsunoo, Teruo Saito, Tomoyasu Suzaki, Maki Shigeri, and Hiroshi Miyauchi. Cryptanalysis of DES implemented on computers with cache. In Colin D. Walter, Çetin Kaya Koç, and Christof Paar, editors, *CHES 2003*, volume 2779 of LNCS, pages 62-76. Springer, Heidelberg, September 2003.

[Zim96] Karl-Heinz Zimmermann. Integral hecke modules, integral generalized Reed-Muller codes, and linear codes. Technical report, Techn. Univ. Hamburg-Harburg, November 1996.