# On Functions of $F\_2^{2t}$ mapping Cosets of $F\_2^{2t*}$ to Cosets of $F\_2^{2t*}$

Jules Baudrin, Anne Canteaut, Léo Perrin

► To cite this version:

Jules Baudrin, Anne Canteaut, Léo Perrin. On Functions of $F\_2^{2t}$ mapping Cosets of $F\_2^{2t*}$ to Cosets of $F\_2^{2t*}$. WCC 2024 - Thirteenth International Workshop on Coding and Cryptography, Daniele Bartoli (University of Perugia, Perugia, Italy); Christina Boura (Université de Versailles, Versailles, France); María Naya-Plasencia (INRIA, Paris, France), Jun 2024, Perugia, Italy. pp.13. hal-04982648

HAL Id: hal-04982648

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

Submitted on 7 Mar 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
# On Functions of $F_{2t}$
mapping Cosets of $F_{2t}^*$ to Cosets of $F_{2t}^*$

Jules Baudrin, Anne Canteaut, and Léo Perrin

Inria, Paris, France

{jules.baudrin, anne.canteaut, leo.perrin}@inria.fr

**Abstract.** The punctured finite field $F_{2t}^*$ can be partitioned into mul-
tiplicative cosets of $F_{2t}^*$. In this paper, we investigate functions mapping
these cosets either to multiplicative cosets of $F_{2t}^*$ or to additive cosets of
$F_{2t}^*$. First, we analyze the “subspace property”, a well-known feature of
the so-called Kim mapping, that corresponds to functions preserving the
partition into multiplicative cosets. As a particular case, we study func-
tions whose restriction to each coset coincides with a power permutation.
Those correspond to a particular case of (generalized) cyclotomic map-
pings. We also identify conditions for such functions to be quadratic and
APN, and we study the structure of their Walsh zeroes. There is only one
function in the literature mapping the partition into multiplicative cosets
to that into additive cosets: the S-box of the last symmetric primitives
standardized in Russia. We shed some more light on its design process,
and we derive, for any $t$, permutations of $F_{2t}$ with a similar structure,
and a linearity smaller than $2^{t+2}$.

**Keywords:** Subspace property · Cyclotomic Mappings · APN · S-box

# 1 Introduction

Finding functions from $F_2^n$ to $F_2^n$ with optimal cryptographic properties is a major open problem when $n$ is even. In this case, even the optimal values for the differential uniformity and for the linearity of a bijective mapping are unknown. For instance, the existence of APN permutations on $F_{2^n}$, when $n$ is even and greater than 6, has been open for 15 years, since an APN permutation for $n=6$ was exhibited by Dillon *et al*. in 2009 [6]. For constructing such functions, a natural idea is to decompose $F_{2^n}$, $n=2t$, into the $(2^t+1)$ multiplicative cosets of $F_{2t}$. This spread is actually used in several constructions, including the bent functions of *partial-spread type* introduced much earlier by Dillon [16].

Our work then focuses on two types of functions: functions $F$ mapping each multiplicative coset $\gamma F_{2t}^*$ to a multiplicative coset $F(\gamma)F_{2t}^*$, and bijections $F$ mapping each multiplicative coset $\gamma F_{2t}^*$, except $F_{2t}^*$, to an additive coset $\alpha + F_{2t}^*$. The first type, studied in Section 2, corresponds to the functions satisfying the *subspace property* defined by Dillon *et al*. [6], and includes the so-called Kim mapping for $n=6$. The second type, studied in Section 3, includes the Sbox of the recent Russian standard primitives Streebog and Kuznyechik [26]. We leave
aside bijections mapping the additive cosets of $\mathbb{F}_{2^t}$ into additive cosets, as those have been studied by several authors, e.g. to design backdoored primitives [25,1].

## 1.1 Preliminaries

For two sets $A$ and $B$, we denote by $A \sqcup B$ the disjoint union of $A$ and $B$. Regarding integers, if $u, v \in \mathbb{Z}$ with $u \le v$, the set $\{u, u+1, \dots, v\}$ is denoted by $[u, v]$. The Hamming weight is denoted by $wt(\cdot)$.

Let $K_0$ be a field of size $q$ and $K_1$ be an extension of $K_0$ of degree $d$. The trace function from $K_1$ to $K_0$ is defined as $\text{Tr}_{K_1/K_0}: x \mapsto \sum_{i=0}^{d-1} x^{q^i}$. Its standard properties can be found for instance in [23, Theorems 2.23 & 2.24 p.56].

Though famous, the Walsh transform has many variants. We use the following one.

**Definition 1 (Walsh coefficients and linearity).** Let $K$ be a field over $\mathbb{F}_2$. Let $F: K \to K$ and $\alpha, \beta \in K$. The $(\alpha, \beta)$-Walsh coefficient of $F$ is defined as:

$$W_{K,F}(\alpha, \beta) := \sum_{x \in K} (-1)^{\text{Tr}_{K/\mathbb{F}_2}(\alpha x + \beta F(x))};$$

and the linearity of $F$ is the maximum $\mathcal{L}(F) := \max_{\alpha \neq 0, \beta \in K} |W_{K,F}(\alpha, \beta)|$.

Let $t \in \mathbb{N} \setminus \{0\}$, $n = 2t$. In the following, we consider only the finite field $\mathbb{F}_{2^n}$ and its subfields. When there is no ambiguity on the cardinality, the field with $2^n$ elements and its subfield with $2^t$ elements are denoted by $\mathbb{L} := \mathbb{F}_{2^n}$, and $\mathbb{F} := \mathbb{F}_{2^t} \subset \mathbb{L}$. We reserve the letter $\lambda$ (resp. $\varphi$) for elements of $\mathbb{L}$ (resp. $\mathbb{F}$).

As $\mathbb{F}^*$ is a subgroup of $\mathbb{L}^*$, we can naturally partition $\mathbb{L}^*$ as an union of cosets that is, $\mathbb{L}^* = \bigcup_{\gamma \in \Gamma} \gamma \mathbb{F}^*$, where $\Gamma$ is any complete system of distinct representatives. In the following, we shorten complete system of distinct representatives into *system of directions* where *direction* refers to the geometrical interpretation of such a partition. We also reserve the notation $\Gamma$ for systems of directions and $\gamma$ for elements of $\Gamma$. By construction, $\Gamma \cap \mathbb{F}^*$ contains a single element, which is denoted by $\gamma^\circ$, that is, $\{\gamma^\circ\} := \Gamma \cap \mathbb{F}^*$. We also define $\Gamma^\circ$ as $\Gamma^\circ := \Gamma \setminus \{\gamma^\circ\}$.

Because $2^t - 1$ and $2^t + 1$ are two coprime divisors of $2^{2t} - 1$, the Chinese Remainder Theorem suggests the subgroup $\mathbb{G}$ of order $2^t + 1$ as a natural system of directions. This choice, known as the *polar coordinate system* or *polar representation* (see for instance [11, page 191]), has especially been studied to design Boolean functions with notable properties [12,13,24,31]. More generally, any set $S$ with $2^t + 1$ elements is a system of directions if and only if it satisfies $\Theta(S) = \mathbb{G}$ where $\Theta: \mathbb{L} \to \mathbb{L}$, $x \mapsto x^{2^t - 1}$. In [19], Göloğlu introduces the trace-0/trace-1 representation which corresponds to $\Gamma = \{1\} \cup \text{Tr}_{\mathbb{L}/\mathbb{F}}^{-1}(\{1\})$.

## 2 Subspace Property and the Kim Mapping

The so-called *Kim mapping* [6] is a quadratic APN function of 6 variables. A remarkable property is that it is CCZ-equivalent to a permutation. The Kim
mapping is defined by $\kappa: \mathbb{F}_{64} \to \mathbb{F}_{64}$ $x \mapsto x^3 + x^{10} + ux^{24}$, where $u$ is a root of the primitive polynomial $X^6 + X^4 + X^3 + X + 1$.

As first introduced and studied in [6], $\kappa$ is particularly structured and interacts with the multiplicative decomposition of $\mathbb{F}_{64}$. This is highlighted by the so-called subspace property defined by Dillon et al. as follows.

**Definition 2 (Subspace property [6]).** $F: \mathbb{L} \to \mathbb{L}$ satisfies the subspace property if, for all $\lambda \in \mathbb{L}$, $F(\lambda\mathbb{F}) = F(\lambda)\mathbb{F}$.

The subspace property exactly corresponds to function mapping each multiplicative coset onto another one. Indeed if $F(\lambda) \in F(\lambda\mathbb{F}) = \gamma\mathbb{F}$, so $\gamma\mathbb{F} = F(\lambda)\mathbb{F}$. The image of any function satisfying the subspace property is then a partial spread since it is a union of multiplicative cosets. When $F$ satisfies the subspace property we introduce, for any $\lambda \neq 0$, the function $F_\lambda: \mathbb{F} \to \mathbb{F}$, $\varphi \mapsto \frac{F(\lambda\varphi)}{F(\lambda)}$. The subspace property is a purely set-theoretic property. Indeed, $F$ satisfies the subspace property if and only if, for any $\lambda \neq 0$, $F_\lambda$ is well-defined and bijective. In the following, we focus on the particular case where any $F_\lambda$ is a power mapping.

## 2.1 Cyclotomic mappings satisfying the subspace property

In previous works, functions whose restriction to each multiplicative coset is a power mapping are called (generalized) cyclotomic mapping.

**Definition 3 ((Generalized) cyclotomic mapping [5]).** Let $\ell | 2^n - 1$ and $G$ be the subgroup of order $|G| = \frac{2^n - 1}{\ell}$ (i.e. of index $\ell$). A generalized cyclotomic mapping of index $\ell$ of $\mathbb{L}$ is a function $F: \mathbb{L} \to \mathbb{L}$ which satisfies:

$$ \forall \lambda \in \mathbb{L}, \exists d_{\lambda} \in \mathbb{N}, \forall x \in G, F(\lambda x) = F(\lambda)x^{d_{\lambda}}. $$

When $G$ is clear from context, we rather call it generalized cyclotomic mapping over $G$. If there exists $d$ such that $d_{\lambda} = d$ for all $\lambda$, such mapping is called cyclotomic mapping [29] of order $d$ over $G$ (or of index $\ell$).

Note that if $F(\lambda) \neq 0$, the value of $d_{\lambda} \mod |G|$ only depends on the coset of $\lambda$. Generalized cyclotomic mappings that satisfy the subspace property can therefore be easily characterized.

**Proposition 1.** A generalized cyclotomic mapping $F: \mathbb{L} \to \mathbb{L}$ over $\mathbb{F}^*$ satisfies the subspace property if and only if for any $\lambda \in \mathbb{L}$, $\gcd(d_{\lambda}, 2^t - 1) = 1$ (where $d_{\lambda}$ are defined as in Definition 3).

**Corollary 1.** Let $F: \mathbb{L} \to \mathbb{L}$ be a generalized cyclotomic mapping that satisfies the subspace property. If $F$ is APN, then all exponents $d_{\lambda}$, $\lambda \neq 0$ defined as in Definition 3 are such that $x \mapsto x^{d_{\lambda}}$ is APN on $\mathbb{F}$. Most notably, no APN generalized cyclotomic mapping that satisfies the subspace property exist when $n$ is a multiple of 4.
The first statement remains true for any function satisfying the subspace property. The second one is an immediate corollary of the inexistence of APN bijective power mappings over $\mathbb{F}_{2^k}$ for even $k$.

Not only does the Kim mapping satisfies the subspace property: it is, above all, a cyclotomic mapping of order 3 over $\mathbb{F}^*$. Indeed, for $\lambda \in \mathbb{L}^*$ and $\varphi \in \mathbb{F}^*$, $\kappa(\lambda\varphi) = \varphi^3(\lambda^3 + \lambda^{10} + u\lambda^{24}) = \kappa(\lambda)\varphi^3$. Because $\gcd(3, |\mathbb{F}^*|) = \gcd(3, 7) = 1$, the subspace property is a consequence of its cyclotomicity.

Cyclotomic mapping over $\mathbb{F}^*$ are of the form $x^d P(x^{2^{i}-1})$ for some polynomial $P$, and as such, they are a particular type of Wan-Lidl polynomials. The latter ones have been studied by several authors but mainly in the bijective case, e.g. [4,15,21,28,30]. Most notably, Chen and Coulter recently investigated their differential uniformity but their results do not provide any relevant information for our parameters in characteristic 2.

Obviously, the polynomial forms of these functions can be easily characterized.

**Proposition 2.** [19, p.264], [29, Lemma 1] Let $\mathbb{G}$ be a subgroup of $\mathbb{L}^*$. Let $F: \mathbb{L} \to \mathbb{L}$, $x \mapsto \sum_{i=0}^{2^d-1} a_i x^i$, where $a_i \in \mathbb{L}$ for any $i$. Then $F$ is a cyclotomic mapping of order $d$ over $\mathbb{G}$ if and only if $a_i \neq 0 \implies i \equiv d \mod |G|$.

Proposition 2 can then be refined to quadratic cyclotomic functions of order $d$ over $\mathbb{F}^*$. In that case $\mathrm{wt}(d) \le 2$, but the case $\mathrm{wt}(d) = 1$ is of low interest since such a cyclotomic mapping cannot be APN. When $\mathrm{wt}(d) = 2$, any such $x^d P(x^{2^{i}-1})$ is linearly-equivalent to $x^{2^{i}+1}Q(x^{2^{i}-1})$ for some $i$ and $Q$. From now on, we therefore only focus on Gold exponents $d = 2^i+1$. This family is described in the following corollary.

**Corollary 2.** [19, p.264] Let $F: \mathbb{L} \to \mathbb{L}$ be a quadratic cyclotomic mapping of order $2^i + 1$ and index $2^t + 1$ where $i < t$. Then its univariate representation contains at most 4 monomials, with exponents $2^i+1, 2^i+2^t, 2^{t+i}+1$ and $2^{t+i}+2^t$.

The family described in Corollary 2 has already attracted attention. For instance, it includes the APN trinomials exhibited by Göloğlu for $n \equiv 0 \mod 4$ in [19], which have been latter proved affine equivalent to the Gold power mapping $x^{2^{t-i}+1}$ [7, Section 4]. Despite a reference to the subspace property in [19], Corollary 1 implies that none of those trinomials satisfy the original subspace property defined in Definition 2. The subspace property as defined in [19] actually corresponds to the definition of cyclotomic mapping with a Gold exponent (that is not necessarily bijective).

Carlet [10, § 3.7] also focuses on a sub-family of the polynomials in Corollary 2, namely those with $\gcd(i, n) = 1$ and such that the coefficient of $x^{2^{i}+1}$ is nonzero. When $i = 1$ (i.e. $d = 3$) and $t > 3$, those functions are called *Kim-type functions* in [14]. APN Kim-type functions have been completely characterized in [22] and proved CCZ-equivalent to a Gold function, $x^3$ or $x^{2^{n/2-1}+1}$ over $\mathbb{L}$ in [14]. But, it is worth noting that the more general case of APN quadratic cyclotomic mappings of order $d = 2^i + 1$, for any $i$ with $\gcd(i, t) = 1$ is still
open. Again, even if the different terminologies used in these works may appear confusing<fnref n="1" />, the functions from [10, § 3.7], and in particular Kim-type functions, only satisfy the original subspace property when $t$ is odd.

According to the authors of [6], the cyclotomicity explains some of the “simplicity” of the Kim function and part of its CCZ-equivalence to a permutation. On the other hand, all power mappings, including the APN Gold function $x \mapsto x^3$ over $\mathbb{F}_{64}$, are obviously cyclotomic mappings (because $(\lambda\varphi)^3 = \lambda^3\varphi^3$) but do not share all the properties of $\kappa$. In the following, we thus continue investigating cyclotomicity, the subspace property and the functions satisfying them.

## 2.2 Properties of the functions satisfying the subspace property

**Proposition 3.** Let $\Gamma$ be a system of directions. Let $F: \mathbb{L} \to \mathbb{L}$ be a function satisfying the subspace property. Let $\alpha, \beta \in \mathbb{L}$, then:

$$W_{\mathbb{L},F}(\alpha, \beta) = -2^t + \sum_{\gamma \in \Gamma} W_{\mathbb{F},F_{\gamma}} (\mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\alpha\gamma), \mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\beta F(\gamma))).$$

The proof is a direct computation.

For any $\lambda \in \mathbb{L}$, the size of the preimage of $\lambda\mathbb{F}$ (divided by $2^t$) is denoted by $N_{F,\lambda} := \frac{|F^{-1}(\lambda\mathbb{F})|}{2^t}$. Given any system of directions $\Gamma$, this quantity is also equal to $N_{F,\lambda} = |\{\gamma \in \Gamma \text{ s.t. } F(\gamma) \in \lambda\mathbb{F}\}|$.

If there exists a nonzero $\gamma_0 \in \Gamma$ such that $F(\gamma_0) = 0$, then $\gamma_0$ belongs to $\{\gamma \in \Gamma \text{ s.t. } F(\gamma) \in \lambda\mathbb{F}\}$ for all $\lambda \in \mathbb{L}$. It follows that $\sum_{\lambda \in \Gamma} N_{F,\lambda} = 2^t+1+2^t N_{F,0}$. However, the case $N_{F,0} > 0$ is of low interest in our context since any such function has differential uniformity at least $2^t$, because all $(\gamma_0\varphi), \varphi \in \mathbb{F}$ satisfy $F(\gamma_0\varphi + \gamma_0) + F(\gamma_0\varphi) = 0$. This situation occurs for instance when $F$ is defined by the same polynomial as the Kim mapping, $x \mapsto x^3+x^{10}+u'x^{24}$, but when $u'$ is a root of the primitive polynomial $X^6+X^5+X^2+X+1$. Indeed, $F(u'^2) = 0$.

**Proposition 4.** If $F: \mathbb{L} \to \mathbb{L}$ is a function satisfying the subspace property and $\beta \in \mathbb{L}^*$, then $W_{\mathbb{L},F}(0, \beta) = 2^t(N_{F,\beta-1} - 1)$. Most notably, $\mathcal{L}(F) \ge 2^t (\max_{\lambda \in \mathbb{L}^*} (N_{F,\lambda}) - 1)$.

**Proposition 5 (Symmetries of the Walsh coefficients).** Let $F: \mathbb{L} \to \mathbb{L}$. Let $G: \mathbb{F} \to \mathbb{F}$. $F$ satisfies the subspace property with $F_\lambda = G$ for any $\lambda$ if and only if it verifies :

$$\forall \alpha, \beta \in \mathbb{L}, \forall \varphi \in \mathbb{F}^*, \quad W_{\mathbb{L},F}(\alpha, \beta G(\varphi)) = W_{\mathbb{L},F}(\alpha \varphi^{-1}, \beta).$$

Again, the proof is a straight-forward computation. Propositions 4 and 5 respectively explains the first row of Fig. 1, and its the “structured-square” pattern.

<footnote n="1">¹ If they are APN, the functions from [10, § 3.7] are named generalized Kim functions.</footnote>
## 2.3 Quadratic functions satisfying the subspace property

Proposition 4 becomes particularly interesting when looking at quadratic functions. Indeed, when $F$ is quadratic, all its components are plateaued, i.e., there exists $\ell_{\beta} \in \mathbb{N}$ such that for any $\alpha \in \mathbb{L}$, $W_{\mathbb{L},F}(\alpha, \beta) \in \{0, \pm 2^{\ell_{\beta}}\}$. Proposition 4 then provides the linearity of all components $F_{\beta}$ except those such that $N_{F,\beta-1} = 1$. Therefore, it can be refined as follows.

**Corollary 3.** Let $F: \mathbb{L} \to \mathbb{L}$ be a quadratic function satisfying the subspace property, and $\Gamma$ be a system of directions. Then,

$$ \mathcal{L}(F) = \max \left( 2^t \left( \max_{\lambda \in \Gamma} (N_{F,\lambda}) - 1 \right); \max\{\mathcal{L}(F_{\beta}), \beta \in \Gamma \text{ s.t. } N_{F,\beta-1} = 1\} \right). $$

More importantly, we can derive a simple necessary condition for a quadratic function satisfying the subspace property to be APN.

**Theorem 1.** Let $F: \mathbb{L} \to \mathbb{L}$ be a quadratic function satisfying the subspace property. Let $N_i = |\{\gamma \in \Gamma : N_{F,\gamma} = i\}|$ where $\Gamma$ is a system of directions. If $F$ is APN, then $N_0 + N_2 \ge 2(2^t + 1)/3$. Moreover, if $\mathcal{L}(f) = 2^{t+1}$, then $F$ is APN if and only if $N_0 + N_2 = 2(2^t + 1)/3$, which can only occur when $t$ is odd.

*Proof.* As $F$ is quadratic, all its components are plateaued. Moreover, the $\beta$-component is bent if and only if $W_{\mathbb{L},F}(0, \beta) = \pm 2^t$, which equivalently means that $N_{F,\beta-1} \in \{0, 2\}$. The result is then deduced from the fact that, if a function $F$ of $2t$ variables with plateaued components is APN, then it has at least $2(2^t + 1)/3$ bent components. Conversely, if $F$ has $2(2^t + 1)/3$ bent components and $\mathcal{L}(F) = 2^{t+1}$, then $F$ is APN [2, Coro. 3]. □

Most notably, Theorem 1 provides an easy way to check that a given $F$ is not APN by evaluating it at $(2^t+1)$ points only. For instance, if we consider the same polynomial expression as the Kim mapping, $x \mapsto x^3 + x^{10} + u'x^{24}$, with $u'$ a root of any primitive polynomial different from $X^6 + X^4 + X^3 + X + 1$, then we can easily check that $N_0 + N_2 \le 4$, implying that the function is not APN. On the other hand, it is currently not known how to assess in an effective way whether $F$ is a quadratic function satisfying the subspace property. Because of Corollary 2, this technique is however well-suited for quadratic cyclotomic mappings.

For $t=3$, we computationally exhausted all quadratic cyclotomic mappings of order 3 and kept only those for which $N_{F,0} > 0$. Among them, all functions satisfying $N_0 + N_2 \ge 6$ are APN. All the obtained APN functions are CCZ-equivalent either to $\kappa$ or to $x \mapsto x^3$.

## 2.4 Cyclotomic mappings and 3-to-1-ness

A simple particular case is the situation where $N_3 = (2^t + 1)/3$ and $N_0 = 2(2^t + 1)/3$ like in the case of Gold functions $F(x) = x^{2^t+1}$ with $\gcd(\ell, t) = 1$. Indeed, we can directly deduce from Theorem 1 that $F$ is APN. This case has already been studied in a more general context [8,20] since the corresponding functions $F$ are almost 3-to-1, i.e. $F$ is 3-to-1 on $\mathbb{L}^*$. Most notably, the following proposition is a direct consequence of [20].
<figure><img src="image_2.png" /><figcaption>Fig. 1: The Walsh coefficients (LAT) of $κ$ (left) and $x \mapsto x^3$ (right). Dark blue is a low negative value, dark red a high positive value.</figcaption></figure>

**Proposition 6.** Let $F$ be a 3-divisible cyclotomic mapping of order $d$ over $\mathbb{F}^*$ with plateaued components. The following properties are equivalent:

- $F$ is APN

- $F$ is almost 3-to-1 with $F^{-1}(0) = \{0\}$

- $F$ has the Gold-like Walsh spectrum.

## 2.5 Walsh zeroes of functions satisfying the subspace property

A remarkable property of the Kim mapping is that its Walsh zeroes [9], i.e., the set of all $(\alpha, \beta)$ such that $W_κ(\alpha, \beta) = 0$, include two $n$-dimensional subspaces of $\mathbb{F}_2^{2n}$ in direct sum. One of the reasons is the existence of some $(\alpha, \beta)$ such that $W_κ(\alpha\varphi_1, \beta\varphi_2) = 0$ for all $\varphi_1, \varphi_2 \in \mathbb{F}$. Fig. 1 contains a representation of the Walsh coefficients of the Kim mapping where the masks are sorted by cosets. The grey squares on Fig. 1 then correspond to such spaces. The following theorem provides a necessary and sufficient condition for this phenomenon, for the special case of cyclotomic mappings.

**Theorem 2.** Let $F: \mathbb{L} \to \mathbb{L}$ be a cyclotomic mapping of order $d$ over $\mathbb{F}^*$ with $\gcd(d, 2^t - 1) = 1$, $\Gamma$ be a system of directions, $\mathcal{L}(F) \neq 2^{2t}$, and $\alpha, \beta \in \mathbb{L}^*$. Then,

$$W_{\mathbb{L},F}(\alpha\varphi_1, \beta\varphi_2) = 0, \forall \varphi_1, \varphi_2 \in \mathbb{F}^*$$

if and only if $\beta$ is such that $N_{F,\beta-1} = 1$ and $\alpha$ satisfies $\mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\alpha\gamma_0) \neq 0$ and

$$\left\{ \frac{\mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\alpha\gamma)}{\mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\beta F(\gamma))^e}, \gamma \in \Gamma \setminus \{\gamma_0\} \right\} = \mathbb{F}$$

where $\gamma_0$ is the unique element in $\Gamma$ such that $\mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\beta F(\gamma_0)) = 0$ and $x \mapsto x^e$ is the inverse of $x \mapsto x^d$ over $\mathbb{F}$.
The proof is omitted due to space limitations. Theorem 2 characterizes these peculiar subspaces among the Walsh zeros. Determining whether other cyclotomic mappings satisfying the subspace property share this property with $\kappa$ now sums up to determining whether the bijectivity of $\frac{\mathrm{Tr}_{L/F}(\alpha\gamma)}{\mathrm{Tr}_{L/F}(\beta F(\gamma))}$ is sporadic or not.

# 3 Additive Subspace Property for Permutations and Streebog Sbox

So far, we only considered multiplicative decompositions of $L^*$. But as $F$ is an additive subgroup of $L$, we can also partition $L$ as $L = \bigcup_{\lambda \in O} \lambda + F$ given any system of representatives $O$. We refer to any $\lambda + F$ as an *affine line* and to such $\lambda$ as its *origin*. Any set $O$ with $2^t$ elements such that $\mathrm{Tr}_{L/F}(O) = F$ is a system of origins; and in particular the subspaces $\lambda F$ with $\lambda \in L \setminus F$.

## 3.1 Additive Subspace Property for Permutations

We now define a family of permutations $\Pi$, which map any multiplicative coset $\gamma F^*$, $\gamma \neq \gamma^\circ$ onto the (punctured) additive coset $G(\gamma) + F^*$. Moreover, the restriction of $\Pi$ to all cosets are the same, up to the additive offset, i.e., all the lines are shuffled the same way. Therefore, this property can be seen as “an additive variant” of the subspace property. However, for $\gamma = \gamma^\circ$, $F^*$ must be mapped onto $O$, if we want to construct a permutation of $L^*$. As we will show later, the functions satisfying this property include, for $n = 8$, the Sbox used in the Russian standard primitives Streebog and Kuznyechik [17,18].

**Definition 4 (ASPP).** A function $\Pi: L \to L$ with $\Pi(0) = 0$ is said to have the additive subspace property for permutations (ASPP) if there exist

- $\Gamma$ a system of directions and $O$ a system of origins, and

- two bijective maps: $G: \Gamma^\circ \to O$, $F: F \to F$ with $F(0) = 0$, such that:

$$ \Pi|_{L \setminus F}: \gamma\varphi \mapsto G(\gamma) + F(\varphi) \text{ and } \Pi(F^*) = O. \quad (1) $$

Such a tuple $(\Gamma^\circ, O, F, G)$ is called an ASPP-decomposition of $\Pi$.

Since only $\Gamma^\circ$ matters in Definition 4 and not $\Gamma$, $\gamma^\circ$ can always be chosen freely.

**Proposition 7.** Any function satisfying the ASPP is bijective.

For any such function, the decomposition is almost unique.

**Definition 5 (Trivially-equivalent decompositions).** Let $\Pi$ be a function satisfying ASPP and $(\Gamma^\circ, O, F, G)$ be a decomposition of $\Pi$. Let $\varphi \in F^*$. Let $\tilde{\Gamma}^\circ := \varphi\Gamma^\circ$, and $\tilde{F}: F \to F$, $\tilde{G}: \tilde{\Gamma}^\circ \to O$ be defined as:

$$ \tilde{F} = F \circ M_\varphi \quad \text{and} \quad \tilde{G} = G \circ M_{\varphi^{-1}}, $$

where $M_\varphi$ (resp. $M_{\varphi^{-1}}$) denotes the multiplication-by-$\varphi$ (resp by $\varphi^{-1}$) mapping. Then, the tuple $(\tilde{\Gamma}^\circ, O, \tilde{F}, \tilde{G})$ is an ASPP-decomposition of $\Pi$. $(\Gamma^\circ, O, F, G)$ and $(\tilde{\Gamma}^\circ, O, \tilde{F}, \tilde{G})$ are called trivially-equivalent.
**Proposition 8 (Uniqueness of the decomposition).** Let $\Pi$ be a function satisfying the ASPP. Then all decompositions of $\Pi$ are trivially equivalent.

It is worth noting that, while the subspace property was independent of the choice of $\Gamma$, this is not the case for the ASPP.

## 3.2 Streebog/Kuznyechik S-box

The S-box used by the last two Russian standards, Streebog and Kuznyechik, is defined for $n = 8$, i.e., $\mathbb{L} = \mathbb{F}_{256}$ and $\mathbb{F} = \mathbb{F}_{16}$. It is specified [17,18] as a look-up table of integers ranging from 0 to 255. In order to rather study a function $F: \mathbb{L} \to \mathbb{L}$, identification between $\mathbb{L}$ and $[0, 255]$ must be specified, as two different identifications gives two functions over $\mathbb{L}$ with a priori different properties.

The latest study [26] on the S-box points out a representation of $\mathbb{F}_{256}$ that we will also be using: $\mathbb{F}_{256} \simeq \mathbb{F}_2[X]/(X^8+X^4+X^3+X^2+1)$. Identification between 8-bit words, integers of $[0, 255]$ and polynomials of degree at most 7 is done canonically: $\sum_{i=0}^{7} b_i 2^i \simeq \sum_{i=0}^{7} b_i X^i \simeq (b_7, \dots, b_0)$. Finally, we denote $\Lambda: \mathbb{L} \to [0, 255]$ the isomorphism built from these relations. Through $\Lambda$, $\mathbb{L}$ inherits from the ordering of integers.

In the following, we consider the bijective S-box $\pi: \mathbb{L} \to \mathbb{L}$ defined as $\pi = \Lambda^{-1} \circ \text{LUT} \circ \Lambda$ where LUT is the look-up table given as specifications [17,18]. The previous studies [26,27,3] of $\pi$ show how much it interacts with both additive and multiplicative decompositions. We continue along this line of work by studying its normalized form $\pi_0 := \pi + \pi(0)$, which acts as a permutation of $\mathbb{L}^*$.

The TK-log decomposition of $\pi$ [26] can be restated by the fact that $\pi_0$ satisfies the ASPP. The decomposition of $\pi$ is therefore unique and partially exhibited in [26]. Indeed, Perrin shows that the multiplicative coordinates correspond to the decomposition $\Gamma \times \mathbb{F}^*$ where $\Gamma = \{a^i, i \in [0, 16]\}$ and $a$ is a well-chosen root of the polynomial defining $\mathbb{L}$, namely $a := \Lambda(2)$ as $2 \simeq X$. In other words, $a$ is the class of $X$. Instead of $\Gamma$, we observe that $a^{17} \{a^{-i}, i \in [1, 16]\} = \Gamma^\circ$ and use the associated trivially-equivalent decomposition to describe some properties of $\pi_0$ that can be easily verified.

**Proposition 9.** Let $b = a^{-1}$. Let $(\Gamma^\circ, \mathcal{O}, F, G)$ be the ASPP-decomposition of $\pi_0$ with $\Gamma = \{b^i, i \in [0, 16]\} = \{1\} \cup \Gamma^\circ$. Let $G^\circ := \pi_0|_{\mathbb{F}}$.

1. Let $\lambda \in \mathbb{L}$, and $\mathcal{O} \cap (\lambda+\mathbb{L}) = \{o_\lambda\}$. Then $\forall \varphi \in \mathbb{F}$, $\Lambda(o_\lambda) \le \Lambda(\lambda+\varphi)$, meaning that the origin chosen for each affine line is the smallest possible one.

2. Let $\mathbb{F}$ be enumerated in increasing order as $\mathbb{F} = \{\varphi_0, \varphi_1, \dots, \varphi_{15}\}$. Let $i \in [0, 16]$, $j \in [0, 14]$. Then:

$$ \mathrm{Tr}_{\mathbb{L}/\mathbb{F}} \circ \pi_0(b^{i+17j}) = \begin{cases} \mathrm{Tr}_{\mathbb{L}/\mathbb{F}} \circ G(b^i) = \varphi_{i-1} & \text{if } i \neq 0 \\ \mathrm{Tr}_{\mathbb{L}/\mathbb{F}} \circ G^\circ(b^{17j}) = \varphi_{j+1} & \text{if } i = 0, \end{cases} \quad (2) $$

and $\mathrm{Tr}_{\mathbb{L}/\mathbb{F}} \circ G^\circ(0) = 0 = \varphi_0$. In other words, enumerating both coordinates of preimages by increasing powers results in enumerating the origins of the images by increasing traces.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Graphical representation of the values of Tr$_{L/F}$ ◦ π$_{0}$ (b$^{i+17j}$). The first column corresponds to i = 0, i.e., to Tr$_{L/F}$ ◦ π$_{0}$ (F).</figcaption></figure>

As pointed out in [26], O is even more structured as it is an F$_{2}$-vectorial subspace of dimension 4. This structure is in line with Proposition 9. Indeed, a natural way to obtain a system of origins is to complete any basis of F, B$_{0}$ , into a basis of L, B$_{0}$ ∪ B$_{1}$ . Then, O = 〈 B$_{1}$ 〉 is a system of origins that is also an F$_{2}$ - subspace. The most natural algorithm to do so is to exhaust L \ F while keeping the first four vectors which make the rank grow. This procedure leads to the described system of origins. Regarding π$_{0}$ , F is the least understood building- block. It remains an open question to determine whether a simple and natural description of F exists or not.

3.3 Walsh coefficients of the functions satisfying the ASPP

We now focus on the Walsh coefficients of the functions satisfying the ASPP. The next proposition expresses them in terms of the functions involved in their ASPP-decomposition. Its proof and that of the following corollary are omitted due to space constraints.

Proposition 10. Let Π be a function satisfying the ASPP, (Γ $^{◦}$, O , F, G ) an ASPP-decomposition of Π, and G ◦ = Π$_{|}$$_{F}$ . Let α ∈ L and β ∈ L ∗ be decomposed as β = γ$_{β}$ϕ$_{β}$ with γ$_{β}$ ∈ Γ ◦ ∪ { 1 } , ϕ$_{β}$ ∈ F $^{∗}$. Finally, let G ◦ γ$_{β}$ be the function from F to F defined by x ↦→ Tr$_{L/F}$ ( γ$_{β}$G $^{◦}$( x )). Then W$_{L,}$$_{Π}$ ( α, β ) = S$_{G}$ ◦ + S$_{F}$ where

$$
S_{G^{\circ}} = W_{F, G_{\gamma_{\beta}}^{\circ}} (\mathrm{Tr}_{L/F}(\alpha), \varphi_{\beta}) - W_{F, G_{\gamma_{\beta}}^{\circ}} (0, \varphi_{\beta}) \\
\text{and } S_F = \sum_{\gamma \in \Gamma^{\circ}} (-1)^{\mathrm{Tr}_{L/F}(\beta G(\gamma))} W_{F,F} (\mathrm{Tr}_{L/F}(\alpha\gamma), \mathrm{Tr}_{L/F}(\beta)).
$$

Corollary 4 (Output mask in F $^{∗}$) . Let Π be a function satisfying the ASPP, (Γ $^{◦}$, O , F, G ) be an ASPP-decomposition of Π, and G ◦ = Π$_{|}$$_{F}$ . Let α ∈ L $^{∗}$, and α − 1 be decomposed as α − 1 = ϕ$_{α}$ − $^{1}$γ$_{α}$ − $^{1}$, γ$_{α}$ − 1 ∈ Γ , ϕ$_{α}$ − 1 ∈ F $^{∗}$. Let β ∈ F $^{∗}$. Then

$$
W_{\mathbb{L},\Pi}(\alpha, \beta) = \begin{cases} 0, & \text{if } \alpha \in \mathbb{F}^* \\ W_{\mathbb{F},G_1^\circ}(\mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\alpha), \beta) + 2^t(-1)^{\mathrm{Tr}_{\mathbb{L}/\mathbb{F}}(\beta G(\gamma_{\alpha-1}))}, & \text{if } \alpha \neq \mathbb{F}, \end{cases}
$$
where $G_1^\circ : x \mapsto \text{Tr}_{\mathbb{L}/\mathbb{F}}(G^\circ(x))$.

As an interesting particular case, we can construct functions satisfying the ASPP with remarkable properties such as a linearity which is at most twice the smallest known linearity for an S-box on $\mathbb{L}$.

**Proposition 11.** Let $\Pi$ be a function satisfying the ASPP, with $(\Gamma^\circ, \mathcal{O}, F, G)$ such that $\Gamma^\circ = \mathbb{G} \setminus \{1\}$ and $F = \text{Id}$. Then $\mathcal{L}(F) \le 2^{t+2}$.

We can even build such permutations with $\mathcal{L}(F) \le 3 \times 2^t$: for $n = 8, 10, 12, 14$ and $16$ bits, we obtained linearities equal respectively to 44, 80, 156, 300 and 568.

# 4 Conclusions

Our results show that the functions of $F_{2^2t}$ obtained by mapping the multiplicative cosets of $F_{2t}^*$ into multiplicative or additive cosets of $F_{2t}^*$ have interesting properties, like a low differential uniformity and a low linearity. Most notably, these properties capture some functions with remarkable properties, like the Kim mapping and the Streebog S-box. Our work enlightens for instance the role played by this structure on the fact that the Kim mapping is CCZ-equivalent to a permutation.

*Acknowledgments*. Jules Baudrin is funded by ANR (French National Research Agency) grant ANR-20-CE48-0017 (SELECT). The work of Anne Canteaut is partially supported by ANR grant ANR-21-CE39-0012. The work of Léo Perrin is supported by the European Research Council (ERC, grant agreement no. 101041545 “ReSCALE”).

# References

1. Bannier, A., Bodin, N., Filiol, E.: Partition-based trapdoor ciphers. Cryptology ePrint Archive, Report 2016/493 (2016), https://eprint.iacr.org/2016/493

2. Berger, T.P., Canteaut, A., Charpin, P., Laigle-Chapuy, Y.: On almost perfect nonlinear functions over $F_2^n$. IEEE Transactions on Information Theory 52(9), 4160–4170 (2006)

3. Biryukov, A., Perrin, L., Udovenko, A.: Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 372–402. Springer, Heidelberg, Germany, Vienna, Austria (May 8–12, 2016). https://doi.org/10.1007/978-3-662-49890-3_15

4. Bors, A., Panario, D., Wang, Q.: Functional graphs of generalized cyclotomic mappings of finite fields. arXiv 1108.1873 (2023). https://doi.org/10.48550/arXiv.2304.00181

5. Bors, A., Wang, Q.: Generalized cyclotomic mappings: Switching between polynomial, cyclotomic, and wreath product form. Communications in Mathematical Research 38(2), 246–318 (2022). https://doi.org/10.4208/cmr.2021-0029
6. Browning, K.A., Dillon, J., McQuistan, M.T., Wolfe, A.J.: An APN permutation in dimension six. In: Post-proceedings of the 9-th International Conference on Finite Fields and Their Applications. vol. 518, pp. 33–42. American Mathematical Society (2010)

7. Budaghyan, L., Helleseth, T., Li, N., Sun, B.: Some results on the known classes of quadratic APN functions. In: Hajji, S.E., Nitaj, A., Souidi, E.M. (eds.) Codes, Cryptology and Information Security - C2SI 2017. Lecture Notes in Computer Science, vol. 10194, pp. 3–16. Springer (2017). https://doi.org/10.1007/978-3-319-55589-8_1

8. Budaghyan, L., Ivkovic, I., Kaleyski, N.: Triplicate functions. Cryptography and Communications 15(1), 35–83 (2023)

9. Canteaut, A., Perrin, L.: On CCZ-equivalence, extended-affine equivalence, and function twisting. Finite Fields and Their Applications 56, 209–246 (2019). https://doi.org/https://doi.org/10.1016/j.ffa.2018.11.008

10. Carlet, C.: Open questions on nonlinearity and on APN functions. In: Koç, Ç.K., Mesnager, S., Savaş, E. (eds.) Arithmetic of Finite Fields. pp. 83–107. Springer International Publishing, Cham (2015)

11. Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press (2021). https://doi.org/10.1017/9781108606806

12. Carlet, C., Feng, K.: An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 425–440. Springer, Heidelberg, Germany, Melbourne, Australia (Dec 7–11, 2008). https://doi.org/10.1007/978-3-540-89255-7_26

13. Carlet, C., Mesnager, S.: A note on semi-bent boolean functions. Cryptology ePrint Archive, Paper 2010/486 (2010), https://eprint.iacr.org/2010/486, https://eprint.iacr.org/2010/486

14. Chase, B., Lisonek, P.: Kim-type APN functions are affine equivalent to Gold functions. Cryptogr. Commun. 13(6), 981–993 (2021). https://doi.org/10.1007/S12095-021-00490-2

15. Chen, L., Coulter, R.S.: Bounds on the differential uniformity of the Wan-Lidl polynomials. Cryptogr. Commun. 15(6), 1069–1085 (2023). https://doi.org/10.1007/S12095-023-00634-6

16. Dillon, J.F.: Elementary Hadamard difference-sets. Ph.D. thesis, University of Maryland, USA (1974)

17. Federal Agency on Technical Regulation and Metrology: Information technology – data security: Hash function. English version available at http://wwwold.tc26.ru/en/standard/gost/GOST_R_34_11-2012_eng.pdf (2012)

18. Federal Agency on Technical Regulation and Metrology: Information technology – data security: Block ciphers. English version available at http://wwwold.tc26.ru/en/standard/gost/GOST_R_34_12_2015_ENG.pdf (2015)

19. Göloğlu, F.: Almost perfect nonlinear trinomials and hexanomials. Finite Fields and Their Applications 33, 258–282 (2015)

20. Kölsch, L., Kripke, B., Kyureghyan, G.M.M.: Image sets of perfectly nonlinear maps. Des. Codes Cryptogr. 91(1), 1–27 (2023). https://doi.org/10.1007/S10623-022-01094-4

21. Laigle-Chapuy, Y.: Permutation polynomials and applications to coding theory. Finite Fields and Their Applications 13(1), 58–70 (2007). https://doi.org/10.1016/J.FFA.2005.08.003
22. Li, K., Li, C., Helleseth, T., Qu, L.: A complete characterization of the APN property of a class of quadrinomials. IEEE Trans. Inf. Theory **67**(11), 7535–7549 (2021). https://doi.org/10.1109/TIT.2021.3102872

23. Lidl, R., Niederreiter, H.: Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20. Cambridge University Press (1997)

24. Lou, Y., Han, H., Tang, C., Xu, M.: Constructing vectorial boolean functions with high algebraic immunity based on group decomposition. Cryptology ePrint Archive, Paper 2012/335 (2012), https://eprint.iacr.org/2012/335, https://eprint.iacr.org/2012/335

25. Paterson, K.G.: Imprimitive permutation groups and trapdoors in iterated block ciphers. In: Knudsen, L.R. (ed.) FSE'99. LNCS, vol. 1636, pp. 201–214. Springer, Heidelberg, Germany, Rome, Italy (Mar 24–26, 1999). https://doi.org/10.1007/3-540-48519-8_15

26. Perrin, L.: Partitions in the S-box of Streebog and Kuznyechik. IACR Trans. Symm. Cryptol. **2019**(1), 302–329 (2019). https://doi.org/10.13154/tosc.v2019.i1.302-329

27. Perrin, L., Udovenko, A.: Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog. IACR Trans. Symm. Cryptol. **2016**(2), 99–124 (2016). https://doi.org/10.13154/tosc.v2016.i2.99-124, https://tosc.iacr.org/index.php/ToSC/article/view/567

28. Wan, D., Lidl, R.: Permutation polynomials of the form $x^r f(x^{(q-1)/d})$ and their group structure. Monatshefte für Mathematik **112**, 149–163 (1991)

29. Wang, Q.: Cyclotomic mapping permutation polynomials over finite fields. In: Golomb, S.W., Gong, G., Helleseth, T., Song, H.Y. (eds.) Sequences, Subsequences, and Consequences. pp. 119–128. Springer Berlin Heidelberg, Berlin, Heidelberg (2007)

30. Wang, Q.: A note on inverses of cyclotomic mapping permutation polynomials over finite fields. Finite Fields and Their Applications **45**, 422–427 (2017). https://doi.org/10.1016/j.ffa.2017.01.006

31. Zheng, J., Wu, B., Chen, Y., Liu, Z.: Constructing 2*m*-variable boolean functions with optimal algebraic immunity based on polar decomposition of $F_{2^m}^*$. arXiv 1304.2946 (2013)