Open AccessArticle

A Note on APN Permutations and Their Derivatives

Augustine Musukwa

Department of Mathematics and Statistics, Mzuzu University, P/Bag 201, Mzuzu 2, Malawi

Mathematics 2024, 12(22), 3477; https://doi.org/10.3390/math12223477

Submission received: 5 June 2024 / Revised: 14 August 2024 / Accepted: 19 August 2024 / Published: 7 November 2024

(This article belongs to the Section A: Algebra and Logic)

Download Versions Notes

Abstract

Prior to the discovery of an APN permutation in six dimension it was conjectured that such functions do not exist in even dimension, as none had been found at that time. However, finding APN permutations in even dimension

\geq 8

remains a significant challenge. Understanding and determining more properties of these functions is a crucial approach to discovering them. In this note, we study the properties of vectorial Boolean functions based on the weights of the first-order and second-order derivatives of their components. We show that a function is an APN permutation if and only if the sum of the squares of the weights of the first-order derivatives of its components is exactly

2^{2 n - 1} (2^{n - 1} + 1) (2^{n} - 1)

. Additionally, we determined that the sum of the weights of the second-order derivatives of the components of any vectorial Boolean function is at most

2^{2 n - 1} (2^{n} - 1) (2^{n} - 2)

. This bound is achieved if and only if a function is APN.

Keywords:

Boolean functions; weight; first-order derivatives; second-order derivatives; APN functions; APN permutations

MSC:

06E30; 94A60; 14G50

1. Introduction

The nonlinearity and differential uniformity of a vectorial Boolean function from

F_{2}^{n}

to itself are cryptographic properties used to measure the resistance towards linear and differential attacks, respectively [1]. Almost perfect nonlinear (APN) and almost bent (AB) functions are known to provide optimal resistance against said attacks [2]. The cryptographic properties of these functions have been widely studied, and several approaches have been used to study and characterize them (for example, see [2,3,4,5,6]). Today, many APN functions are known, since several studies have been conducted, particularly on their constructions.

However, despite significant efforts, not much is known about APN permutations in even dimension. The only information currently available is that these functions exist in dimension 6 [7], and it has been shown that they do not exist in dimension 4 [4]. This implies that to find an APN permutation in even dimension

\geq 8

remains a significant challenge. The construction of APN permutations may be challenging due to the limited understanding of their properties and characterizations compared with APN functions. Therefore, it is important to further study the properties and characterizations of APN permutations. In this note, our main focus is providing a special characterization for any APN permutation.

We provide preliminaries in Section 2, and our results are presented in the subsequent sections. Note that our results are connected to those presented in [8]. We claim all the results we have explored by using the weights of the first-order and second-order derivatives of vectorial Boolean functions to characterize APN permutations and APN functions, respectively.

In Section 3, we present our main contribution. We show in Theorem 8 that a function is an APN permutation if and only if the sum of the squares of the weights of the first-order derivatives of its components is exactly

2^{2 n - 1} (2^{n - 1} + 1) (2^{n} - 1)

. In Corollary 5, we show that a function is an APN permutation if and only if the sum of the squares of the weights of components for any first-order derivative at a nonzero element is exactly

2^{2 n - 1} (2^{n - 1} + 1)

. Since finding APN permutations remains a significant challenge, especially in even dimension, this characterization can play an important role in their study.

In Section 4, we show in Proposition 5 that the sum of the weights of the second-order derivatives for any Boolean function is at most

2^{2 n - 1} (2^{n} - 1)

. This bound is met if and only if a function is bent. In Proposition 6, we find the exact quantity for partially bent functions. Additionally, in Theorem 9, we determine that the sum of the weights of the second-order derivatives of the components of any vectorial Boolean function is at most

2^{2 n - 1} (2^{n} - 1) (2^{n} - 2)

. This bound is met if and only if the function is APN. Corollary 6 is a consequence of Theorem 9.

2. Preliminaries

In this section, some definitions and well-known results are presented. The reader is referred to [1,9,10,11,12,13,14,15] for more details.

In this paper, the field of two elements, 0 and 1, is denoted by

F_{2}

, and the vector space of dimension n over

F_{2}

is denoted by

F_{2}^{n}

. We use ordinary addition + instead of XOR ⊕. For any set A, its size is denoted by

| A |

A Boolean function is any function f from

F_{2}^{n}

F_{2}

, and a vectorial Boolean function is any function F from

F_{2}^{n}

F_{2}^{m}

for some positive integers n and m. In this paper, we study vectorial Boolean functions from

F_{2}^{n}

to itself, that is,

n = m

. A Boolean function in algebraic normal form (ANF), which is the n-variable polynomial representation over

F_{2}

, is given by

f (x_{1}, \dots, x_{n}) = \sum_{I \subseteq P} a_{I} (\prod_{i \in I} x_{i}),

where

P = {1, \dots, n}

and

a_{I} \in F_{2}

. The algebraic degree (or simply degree) of f, denoted by

deg (f)

, is

{max}_{I \subseteq P} {| I | ∣ a_{I} \neq 0}

A Boolean function f is called affine if

deg (f) \leq 1

, linear if

deg (f) \leq 1

and

f (0) = 0

and quadratic if

deg (f) = 2

. We denote the set of all affine functions by

A_{n}

. The weight of a Boolean function f is defined as

wt (f) = | {x \in F^{n} ∣ f (x) = 1} |

, and f is balanced if

wt (f) = 2^{n - 1}

. The distance between two Boolean functions f and g is defined as

d (f, g) = wt (f + g)

, and the nonlinearity of f is defined as

N (f) = {min}_{α \in A_{n}} d (f, α)

A vectorial Boolean function F from

F_{2}^{n}

to itself can be denoted by

F = (f_{1}, \dots, f_{n})

, where

f_{1}, \dots, f_{n}

are Boolean functions called coordinate functions. The functions

λ \cdot F

, with

λ \in F_{2}^{n} ∖ {0}

and "·" denoting dot product, are called components of F, and they are denoted by

F_{λ}

. A vectorial Boolean function F is a permutation if and only if all its components are balanced. The degree of F is given by

deg (F) = {max}_{λ \in F_{2}^{n} ∖ {0}} deg (F_{λ})

The Walsh transform of a Boolean function f is defined as the function

W_{f}

from

F^{n}

Z

given by

W_{f} (a) = \sum_{x \in F_{2}^{n}} {(- 1)}^{f (x) + a \cdot x},

for all

a \in F_{2}^{n}

. A set of

W_{f} (a)

, for all

a \in F_{2}^{n}

, is called Walsh spectrum. We define

F (f)

F (f) = W_{f} (0) = \sum_{x \in F_{2}^{n}} {(- 1)}^{f (x)} = 2^{n} - 2 wt (f) .

That is,

F (f)

is the Walsh transform of f in zero. Notice that f is balanced if and only if

F (f) = 0

The nonlinearity of a function f can also be defined as

\begin{matrix} N (f) = 2^{n - 1} - \frac{1}{2} max_{a \in F_{2}^{n}} | W_{f} (a) | . \end{matrix}

(1)

The nonlinearity of a vectorial Boolean function F is defined as

N (F) = min_{λ \in F_{2}^{n} ∖ {0}} N (F_{λ}) .

For every Boolean function f, with n even,

N (f) \leq 2^{n - 1} - 2^{\frac{n}{2} - 1}

, and f is said to be bent if and only if the equality holds. The lowest possible value for

{max}_{a \in F_{2}^{n}} | W_{f} (a) |

2^{\frac{n}{2}}

, and this bound is achieved only for bent functions. For n odd, a Boolean function f is called semi-bent if

N (f) = 2^{n - 1} - 2^{\frac{n - 1}{2}}

. Semi-bent functions can also be defined in even dimension. For n even, a function f is semi-bent if

N (f) = 2^{n - 1} - 2^{\frac{n}{2}}

. A vectorial Boolean function F in odd dimension is called almost bent (AB) if all its components are semi-bent.

A Boolean function f on n variables is called plateaued if its Walsh spectrum is either

{\pm 2^{n / 2}}

(this happens only when n is even, and in this case, f is bent) or

{0, \pm μ}

for some integer

μ

(see [16]). The order of a plateaued function f on n variables is defined as the even integer r,

0 \leq r \leq n

, such that all nonzero values of

W_{f}^{2} (a)

, with

a \in F_{2}^{n}

, are

2^{2 n - r}

(see [11,16]).

We define the first-order derivative of f at

a \in F_{2}^{n}

D_{a} f (x) = f (x + a) + f (x)

, and the second-order derivative of f at a and b is defined as

D_{b} D_{a} f (x) = f (x) + f (x + a) + f (x + b) + f (x + a + b)

[12]. An element

a \in F_{2}^{n}

is called a linear structure of f if

D_{a} f

is constant. The set of all linear structures of f is denoted by

V (f)

. It is well-known that

V (f)

is a vector space. Next, we state the result (without proof), which indicates that every first-order derivative of bent functions at a nonzero element is balanced.

Theorem 1.

A Boolean function f on n variables is bent if and only if

D_{a} f

is balanced for any nonzero

a \in F^{n}

We next define some equivalence which will help us to understand more about quadratic Boolean functions. The two Boolean functions

f, g : F_{2}^{n} \to F_{2}

are said to be affine equivalent if there exists an affinity

φ : F_{2}^{n} \to F_{2}^{n}

such that

f = g \circ φ

. This relation is denoted by

\sim_{A}

and written as

f \sim_{A} g

. The defined equivalence classifies the quadratic functions as stated in the following.

Theorem 2

([17]). Let f be a quadratic Boolean function on n variables. Then, the following apply:

(i): $f \sim_{A} x_{1} x_{2} + \dots + x_{2 k - 1} x_{2 k} + x_{2 k + 1}$ , with $k \leq ⌊ \frac{n - 1}{2} ⌋$ , if f is balanced;
(ii): $f \sim_{A} x_{1} x_{2} + \dots + x_{2 k - 1} x_{2 k} + c$ , with $k \leq ⌊ \frac{n}{2} ⌋$ and $c \in F_{2}$ , if f is unbalanced.

The weight of any unbalanced quadratic Boolean function f is related to the dimension of

V (f)

. We state this well-known result in the following.

Theorem 3

([17]). Let f be any unbalanced quadratic Boolean function on n variables. Then,

wt (f) = 2^{n - 1} \pm 2^{\frac{n + k}{2} - 1},

where

k = V (f)

We next define a nonlinearity measure for vectorial Boolean functions. Let F be a vectorial Boolean function F from

F_{2}^{n}

to itself and

a, b \in F_{2}^{n}

. Define

δ_{F} (a, b) = | {x \in F_{2}^{n} ∣ D_{a} F (x) = b} | .

The differential uniformity of F is defined as

δ (F) = max_{a \neq 0, b \in F_{2}^{n}} δ_{F} (a, b)

and always satisfies

δ (F) \geq 2

. A function with

δ (F) = 2

is called almost perfect nonlinear (APN).

Next, we present some two well-known results which characterize APN functions.

Theorem 4

([2]). Let F be a function from

F_{2}^{n}

into itself. Then,

\sum_{λ \neq 0, a \in F_{2}^{n}} F^{2} (D_{a} F_{λ}) \geq 2^{2 n + 1} (2^{n} - 1) .

Moreover, the equality holds if and only if F is APN.

Theorem 5

([2]). Let F be a function from

F_{2}^{n}

into

F_{2}^{n}

. Then, for any nonzero

a \in F_{2}^{n}

, we have

\sum_{λ \in F_{2}^{n}} F^{2} (D_{a} F_{λ}) \geq 2^{2 n + 1} .

Moreover, F is APN if and only if the equality holds for all nonzero

a \in F_{2}^{n}

The result we state in the following proposition can be used along with the characterizations given above to check whether a given function is an APN permutation or not.

Proposition 1

([2]). Let F be a function from

F_{2}^{n}

to itself with components

F_{λ}

λ \in F_{2}^{n} ∖ {0}

. Then, F is a permutation if and only if, for all

a \in F_{2}^{n} ∖ {0}

, we have

\sum_{λ \in F_{2}^{n} ∖ {0}} F (D_{a} F_{λ}) = - 2^{n} .

3. On the First-Order Derivatives of APN Permutations

In this section, we give our results which link APN permutations to the squares of weights of the first-order derivatives of their components. We first show the connection between the weight of a Boolean function and the sum of the weight of its first-order derivatives. For a given Boolean function f, we know from [9] that

\begin{matrix} F^{2} (f) = \sum_{a \in F_{2}^{n}} F (D_{a} f) . \end{matrix}

(2)

We use relation (2) to deduce the following.

Proposition 2.

For any Boolean function f on n variables, we have

wt (f) = 2^{n - 1} \pm \frac{1}{2} \sqrt{2^{2 n} - 2 \sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f)} .

Proof.

From the relation

F^{2} (f) = \sum_{a \in F_{2}^{n}} F (D_{a} f)

, we obtain the following:

\begin{matrix} | F (f) | = \sqrt{\sum_{a \in F_{2}^{n}} F (D_{a} f)} . \end{matrix}

(3)

Since

F (f) = 2^{n} - 2 wt (f)

, then (3) becomes

\begin{matrix} | 2^{n} - 2 wt (f) | = \sqrt{\sum_{a \in F_{2}^{n}} (2^{n} - 2 wt (D_{a} f))} . \end{matrix}

(4)

wt (f) \leq 2^{n - 1}

, then

| 2^{n} - 2 wt (f) | = 2^{n} - 2 wt (f)

. So, (4) becomes

\begin{matrix} wt (f) & = 2^{n - 1} - \frac{1}{2} \sqrt{\sum_{a \in F_{2}^{n}} (2^{n} - 2 wt (D_{a} f))} = 2^{n - 1} - \frac{1}{2} \sqrt{2^{2 n} - 2 \sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f)} . \end{matrix}

wt (f) > 2^{n - 1}

, then

| 2^{n} - 2 wt (f) | = 2 w (f) - 2^{n}

. So, (4) becomes

\begin{matrix} wt (f) & = 2^{n - 1} + \frac{1}{2} \sqrt{2^{2 n} - 2 \sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f)} . \end{matrix}

□

By using Proposition 2, we can write the sum of the weight of the first-order derivatives of a Boolean function f in terms of the weight of f as in the following.

Corollary 1.

Let f be a Boolean function on n variables. Then, we have

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = 2 wt (f) [2^{n} - wt (f)] .

Remark 1.

Observe that we can also use relation (2) to write the total weight of the first-order derivatives of a Boolean function f in terms of

F^{2} (f)

as follows:

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = 2^{2 n - 1} - \frac{1}{2} F^{2} (f) .

Recall that

F (f) = 0

if and only if f is balanced. So, we can use Remark 1 and the fact that

0 \leq F^{2} (f) \leq 2^{2 n}

to deduce the following.

Corollary 2.

For any Boolean function f on n variables, we have

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) \leq 2^{2 n - 1} .

Moreover, the equality holds if and only if f is balanced.

The sum of the weight for the first-order derivatives of any quadratic Boolean function is given in the following.

Corollary 3.

Let f be any quadratic Boolean function on n variables. Then,

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = \{\begin{matrix} 2^{2 n - 1} & if f is balanced \\ 2^{2 n - 1} - 2^{n + k - 1} & otherwise, \end{matrix}

where

k = V (f)

Proof.

If f is balanced, then by Corollary 2, we have

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = 2^{2 n - 1}

. Suppose that f is unbalanced. Then, by Theorem 3, we know that

wt (f) = 2^{n - 1} \pm 2^{\frac{n + k}{2} - 1}

, where

k = V (f)

. By taking

wt (f) = 2^{n - 1} - 2^{\frac{n + k}{2} - 1}

and applying Corollary 1, we have

\begin{matrix} \sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) & = 2 (2^{n - 1} - 2^{\frac{n + k}{2} - 1}) (2^{n} - 2^{n - 1} + 2^{\frac{n + k}{2} - 1}) \\ = 2 (2^{n - 1} - 2^{\frac{n + k}{2} - 1}) (2^{n - 1} + 2^{\frac{n + k}{2} - 1}) \\ = 2 (2^{2 n - 2} - 2^{n + k - 2}) = 2^{2 n - 1} - 2^{n + k - 1} . \end{matrix}

Using

wt (f) = 2^{n - 1} + 2^{\frac{n + k}{2} - 1}

yields the same result. □

Since

D_{a} f

is balanced for all nonzero

a \in F_{2}^{n}

if and only if f is bent, then the following result is immediate.

Corollary 4.

Let f be a bent Boolean function on n variables, with n even. Then,

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = 2^{n - 1} (2^{n} - 1) = 2^{2 n - 1} - 2^{n - 1} .

Note that Corollaries 2 and 3 can also be found in [13]. We claim the results in the remainder of this section and also the next section.

A Boolean function f is partially bent if there exists a linear subspace E of

F_{2}^{n}

such that the restriction of f to E is affine and the restriction of f to any complementary subspace

E^{'}

of E (where

E \oplus E^{'} = F_{2}^{n}

) is bent. It is shown in [4] that in fact

E = V (f)

. In [18], it is proved that the weight for unbalanced partially bent function is given by

2^{n - 1} \pm 2^{n - 1 - h}

, where

dim V (f) = n - 2 h

and

h \leq n / 2

Theorem 6.

For any partially bent Boolean function f on n variables, we have

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = \{\begin{matrix} 2^{2 n - 1} & if f is balanced \\ 2^{2 n - 1} - 2^{2 n - 2 h - 1} & otherwise, \end{matrix}

where

dim V (f) = n - 2 h

and

h \leq n / 2

Proof.

If f is balanced, then by Corollary 2, we have

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = 2^{2 n - 1}

. Now, suppose that f is unbalanced. Recall that

wt (f) = 2^{n - 1} \pm 2^{n - 1 - h}

, where

dim V (f) = n - 2 h

. By taking

wt (f) = 2^{n - 1} + 2^{n - 1 - h}

and applying Corollary 1, we have

\begin{matrix} \sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) & = 2 (2^{n - 1} + 2^{n - 1 - h}) (2^{n} - 2^{n - 1} - 2^{n - 1 - h}) \\ = 2 (2^{n - 1} + 2^{n - 1 - h}) (2^{n - 1} - 2^{n - 1 - h}) \\ = 2 (2^{2 n - 2} - 2^{2 n - 2 - 2 h}) = 2^{2 n - 1} - 2^{2 n - 1 - 2 h} . \end{matrix}

Using

wt (f) = 2^{n - 1} - 2^{n - 1 - h}

yields the same result. □

Proposition 3.

Let f be a plateaued function of order r on n variables. Then, we have

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = \{\begin{matrix} 2^{2 n - 1} & if f is balanced \\ 2^{2 n - 1} - 2^{2 n - r - 1} & otherwise . \end{matrix}

Proof.

If f is balanced, we have

F^{2} (f) = 0

and if f is not balanced, then

F^{2} (f)

is a nonzero positive integer, and we deduce from the definition of a plateaued function of order r that it must be

F^{2} (f) = 2^{2 n - r}

. By applying Remark 1, the result follows. □

Theorem 7.

Let F be a vectorial Boolean function from

F_{2}^{n}

to itself. Then,

\sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) \leq 2^{2 n - 1} (2^{n} - 1) .

Moreover, the equality holds if and only if F is a permutation.

Proof.

By Corollary 2, for any function F from

F_{2}^{n}

to itself, we can deduce that we have

\sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) \leq 2^{2 n - 1} (2^{n} - 1) .

Since all the components

F_{λ}

λ \in F_{2}^{n} ∖ {0}

, of a permutation F are balanced, then it follows that the equality holds if and only if F is a permutation. □

Remark 2.

Observe that if F is an AB function or APN permutation from

F_{2}^{n}

to itself, then we can use Theorem 7 to conclude that the sum of the weight for all the first-order derivatives of its components must be equal to

2^{2 n - 1} (2^{n} - 1)

. A computer check shows that Dillon’s APN permutation in dimension 6 is equal to

2^{11} (2^{6} - 1) = 129,024

Remark 3.

Notice that from Theorem 7, we can deduce that for any non-bijective APN function F from

F_{2}^{n}

to itself, we have

\sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) < 2^{2 n - 1} (2^{n} - 1) .

Proposition 4.

Let n be even and let Q be a quadratic APN function from

F_{2}^{n}

to itself, with bent and unbalanced semi-bent components only. Then, we have

\sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) = 2^{n - 1} (2^{n} - 1) (2^{n} - 2) .

Proof.

From Theorem 1,

D_{a} f

is balanced for all

a \in F_{2}^{n} ∖ {0}

if and only if f is bent. We know that for any unbalanced quadratic function f,

D_{a} f

is balanced for all

a \in F^{n} ∖ V (f)

, and

D_{α} f = 0

for all

α \in V (f)

. For semi-bent, we know that

dim V (f) = 2

, i.e.,

| V (f) | = 4

. Thus, for each bent, the sum of the weight for its first-order derivatives must be

2^{n - 1} (2^{n} - 1)

(see Corollary 4), and for each semi-bent, the sum of the weight of its first-order derivatives must be

2^{n - 1} (2^{n} - 4)

. For any quadratic APN function with bent and semi-bent components, there are exactly

2 / 3 (2^{n} - 1)

bent components and

(2^{n} - 1) / 3

semi-bent components (see [12]). So, the sum of the weight of all the first-order derivatives of components of Q must be

\begin{matrix} \sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} Q_{λ}) & = \frac{2}{3} (2^{n} - 1) 2^{n - 1} (2^{n} - 1) + \frac{1}{3} (2^{n} - 1) 2^{n - 1} (2^{n} - 4) \\ = 2^{n - 1} (2^{n} - 1) (\frac{2}{3} (2^{n} - 1) + \frac{1}{3} (2^{n} - 4)) \\ = 2^{n - 1} (2^{n} - 1) (\frac{2 (2^{n} - 1) + (2^{n} - 1) - 3}{3}) \\ = 2^{n - 1} (2^{n} - 1) (\frac{3 (2^{n} - 1) - 3}{3}) \\ = 2^{n - 1} (2^{n} - 1) (2^{n} - 2) . \end{matrix}

□

Remark 4.

A computer check shows that the sum of weights of the first-order derivatives of components of the Gold APN power functions in dimensions 4, 6 and 8 satisfy Proposition 4. Interestingly, non-quadratic APN power functions such as Kasami functions of dimensions 6 and 8 also have the sum of the weights that satisfy Proposition 4. Could this be true in general? However, this is not true for some APN non-power functions which have more bent components than APN power functions. We used a computer to check the Dillon’s quadratic APN function and another quadratic APN function in dimension 6 (found in [12]), which have more bent components than APN power functions, and their sum of the weights were found to be 126,784 and 127,424, respectively.

Now, we present a result that characterizes APN permutations by the sum of the squares of the weights of all the first-order derivatives of their components.

Theorem 8.

Let F be a permutation from

F_{2}^{n}

to itself. Then,

\sum_{λ, a \in F_{2}^{n} ∖ {0}} {[wt (D_{a} F_{λ})]}^{2} \geq 2^{2 n - 1} (2^{n - 1} + 1) (2^{n} - 1) .

Moreover, the equality holds if and only if F is an APN permutation.

Proof.

We have the following:

\begin{matrix} \sum_{λ \neq 0, a \in F_{2}^{n}} F^{2} (D_{a} F_{λ}) & = \sum_{λ \neq 0, a \in F_{2}^{n}} {[2^{n} - 2 wt (D_{a} F_{λ})]}^{2} \\ = \sum_{λ \neq 0, a \in F_{2}^{n}} [2^{2 n} - 4 \cdot 2^{n} wt (D_{a} F_{λ}) + 4 {[wt (D_{a} F_{λ})]}^{2}] \\ = 2^{3 n} (2^{n} - 1) - 4 \cdot 2^{n} \sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) + 4 \sum_{λ, a \in F_{2}^{n} ∖ {0}} {[wt (D_{a} F_{λ})]}^{2} . \end{matrix}

(5)

So, by Equation (5) and Theorem 4, we obtain

\begin{matrix} 2^{3 n} (2^{n} - 1) - 4 \cdot 2^{n} \sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) + 4 \sum_{λ, a \in F_{2}^{n} ∖ {0}} {[wt (D_{a} F_{λ})]}^{2} \geq 2^{2 n + 1} (2^{n} - 1) \\ \sum_{λ, a \in F_{2}^{n} ∖ {0}} {[wt (D_{a} F_{λ})]}^{2} \geq 2^{2 n - 1} (2^{n} - 1) - 2^{3 n - 2} (2^{n} - 1) + 2^{n} \sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) . \end{matrix}

(6)

Since, by Theorem 7,

\sum_{λ, a \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) = 2^{2 n - 1} (2^{n} - 1)

holds if and only if F is a permutation, then relation (6) becomes

\begin{matrix} \sum_{λ, a \in F_{2}^{n} ∖ {0}} {[wt (D_{a} F_{λ})]}^{2} \geq 2^{2 n - 1} (2^{n} - 1) (2^{n - 1} + 1) . \end{matrix}

(7)

Since Theorems 4 and 7 have been used to deduce relation (7), then we can conclude that the equality in this relation holds if and only if F is an APN permutation. □

Observe that the proof of the preceding theorem relied on Theorem 4 even though the theorem itself cannot be used to determine whether the function is an APN permutation or not. Similarly, the following corollary characterizes APN permutations, and its proof largely depends on Theorem 5, which only determines if the function is APN but does not check its bijectivity.

Corollary 5.

Let F be a permutation from

F_{2}^{n}

to itself. Then, for all

a \in F_{2}^{n} ∖ {0}

, we have

\sum_{λ \in F_{2}^{n} ∖ {0}} {[wt (D_{a} F_{λ})]}^{2} \geq 2^{2 n - 1} (2^{n - 1} + 1) .

Moreover, the equality holds if and only if F is an APN permutation.

Proof.

By Proposition 1, we can deduce that F is permutation if and only if, for any nonzero

a \in F_{2}^{n}

\begin{matrix} - 2^{n} = \sum_{λ \in F_{2}^{n} ∖ {0}} F (D_{a} F_{λ}) = \sum_{λ \in F_{2}^{n} ∖ {0}} [2^{n} - 2 wt (D_{a} F_{λ})] = 2^{n} (2^{n} - 1) - 2 \sum_{λ \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) \\ ⟺ \sum_{λ \in F_{2}^{n} ∖ {0}} wt (D_{a} F_{λ}) = 2^{2 n - 1} . \end{matrix}

(8)

By Theorem 5 and Relation 8, we can deduce that for any nonzero

a \in F_{2}^{n}

, we have

\begin{matrix} 2^{2 n + 1} & \leq \sum_{λ \in F_{2}^{n}} F^{2} (D_{a} F_{λ}) = \sum_{λ \in F_{2}^{n}} {[2^{n} - 2 wt (D_{a} F_{λ})]}^{2} \\ = 2^{3 n} - 4 \cdot 2^{n} \sum_{λ \in F_{2}^{n}} wt (D_{a} F_{λ}) + 4 \sum_{λ \in F_{2}^{n}} {[wt (D_{a} F_{λ})]}^{2} \\ = 2^{3 n} - 4 \cdot 2^{n} (2^{2 n - 1}) + 4 \sum_{λ \in F_{2}^{n}} {[wt (D_{a} F_{λ})]}^{2} \end{matrix}

from which we conclude that

\sum_{λ \in F_{2}^{n} ∖ {0}} {[wt (D_{a} F_{λ})]}^{2} \geq 2^{2 n - 1} (2^{n - 1} + 1)

and the equality holds if and only if F is an APN permutation. □

Remark 5.

A computer check shows that the results in Theorem 8 and Corollary 5 hold for Dillon’s APN permutation in dimension 6. However, the result can never hold for non-bijective APN functions, and in their case, the values are not unique. For example, we used a computer to check the sum of squares of the weights of the first-order derivatives of the components of the Dillon’s quadratic APN function and another quadratic APN function in dimension 6 (found in [12]; they have more bent components than APN power functions), and the values were 4,114,432 and 4,241,408, respectively.

4. On the Weight of the Second-Order Derivatives of APN Functions

In this section, we use the sum of weights of the second-order derivatives of (vectorial) Boolean functions to characterize APN functions and other functions.

We first exhibit the relationship between the weights of the first-order derivatives and the weights of the second-order derivatives. By Corollary 1, we can deduce that for any

a \in F_{2}^{n}

, we have

\sum_{b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} f) = 2 wt (D_{a} f) [2^{n} - wt (D_{a} f)] = 2^{n + 1} wt (D_{a} f) - 2 {[wt (D_{a} f)]}^{2}

, from which we obtain

\begin{matrix} \sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} f) = 2^{n + 1} \sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) - 2 \sum_{a \in F_{2}^{n} ∖ {0}} {[wt (D_{a} f)]}^{2} . \end{matrix}

(9)

From Corollary 2, we know that

\sum_{a \in F_{2}^{n} ∖ {0}} wt (D_{a} f) = 2^{2 n - 1}

if and only if f is balanced. So, it implies that Equation (9) becomes

\begin{matrix} \sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} f) = 2^{3 n} - 2 \sum_{a \in F_{2}^{n} ∖ {0}} {[wt (D_{a} f)]}^{2} \end{matrix}

(10)

if and only if f is balanced.

By Remark 1, for any

a \in F_{2}^{n}

, we have

\sum_{b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} f) = 2^{2 n - 1} - \frac{1}{2} F^{2} (D_{a} f)

, from which we obtain

\begin{matrix} \sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} f) = 2^{2 n - 1} (2^{n} - 1) - \frac{1}{2} \sum_{a \in F_{2}^{n} ∖ {0}} F^{2} (D_{a} f) . \end{matrix}

(11)

Observe that

\sum_{a \in F_{2}^{n} ∖ {0}} F^{2} (D_{a} f) = 0

if and only if

D_{a} f

is balanced for all

a \in F_{2}^{n} ∖ {0}

if and only if f is bent. Hence, the result that follows can be deduced from relation (11).

Proposition 5.

Let f be a Boolean function on n variables. Then, we have

\sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} f) \leq 2^{2 n - 1} (2^{n} - 1) .

Moreover, the equality holds if and only if f is bent.

Next, we find the sum of the weights of the second-order derivatives of a partially bent function.

Proposition 6.

For any partially bent function f on n variables, we have

\sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} f) = 2^{2 n - 1} (2^{n} - 2^{n - 2 h}),

where

dim V (f) = n - 2 h

h \leq n / 2

Proof.

Observe that for all

α \in V (f)

, we have

D_{α} f = c

, with

c \in F_{2}

, and

D_{a} f

is balanced for all

a \in F^{n} ∖ V (f)

. We saw in a previous section that

dim V (f) = n - 2 h

. So, we have

| F_{2}^{n} ∖ V (f) | = 2^{n} - 2^{n - 2 h}

. Since

D_{a} f

is balanced, then by Corollary 2, we can deduce that

\sum_{b \in F^{n} ∖ {0}} wt (D_{b} D_{a} f) = 2^{2 n - 1}

, and since

D_{α} f

is constant, then clearly, we have

\sum_{b \in F^{n} ∖ {0}} wt (D_{b} D_{α} f) = 0

. Therefore, it follows that

\begin{matrix} \sum_{a, b \in F^{n} ∖ {0}} wt (D_{b} D_{a} f) & = \sum_{a \in F^{n} ∖ V (f)} \sum_{b \in F^{n} ∖ {0}} wt (D_{b} D_{a} f) + \sum_{α \in V (f)} \sum_{b \in F^{n} ∖ {0}} wt (D_{b} D_{α} f) \\ = (2^{n} - 2^{n - 2 h}) 2^{2 n - 1} + 2^{n - 2 h} (0) = 2^{2 n - 1} (2^{n} - 2^{n - 2 h}) . \end{matrix}

□

Next, we give a characterization of APN functions that is based on the sum of the weights of all the second-order derivatives of their components, and it is deduced from Theorem 4. This result simply gives a different perspective on how we can view APN functions, but it is not any better than Theorem 4, as they both just determine that a function is APN but cannot be used to check bijectivity.

Theorem 9.

Let F be a function from

F_{2}^{n}

to itself. Then,

\sum_{λ, b, a \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) \leq 2^{2 n - 1} (2^{n} - 1) (2^{n} - 2) .

Moreover, the equality holds if and only if F is APN.

Proof.

By Relation (11), for any

λ \in F_{2}^{n} ∖ {0}

, we obtain

\sum_{a \in F_{2}^{n} ∖ {0}} F^{2} (D_{a} F_{λ}) = 2^{2 n} (2^{n} - 1) - 2 \sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ})

from which we deduce the following:

\begin{matrix} \sum_{a \in F_{2}^{n}} F^{2} (D_{a} F_{λ}) & = \sum_{a \in F_{2}^{n} ∖ {0}} F^{2} (D_{a} F_{λ}) + 2^{2 n} = 2^{2 n} (2^{n} - 1) - 2 \sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) + 2^{2 n} \\ = 2^{3 n} - 2 \sum_{a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) . \end{matrix}

(12)

By using relation (12), we have

\begin{matrix} \sum_{λ \neq 0, a \in F_{2}^{n}} F^{2} (D_{a} F_{λ}) & = 2^{3 n} (2^{n} - 1) - 2 \sum_{λ, a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) . \end{matrix}

(13)

By applying Theorem 4, relation (13) becomes

\begin{matrix} 2^{3 n} (2^{n} - 1) - 2 \sum_{λ, a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) \geq 2^{2 n + 1} (2^{n} - 1), \end{matrix}

(14)

and the equality holds if and only if F is APN. Relation (14) is then reduced to

\sum_{λ, a, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) \leq 2^{2 n - 1} (2^{n} - 1) (2^{n} - 2)

and the equality holds if and only if F is APN. □

Corollary 6.

Let F be a function from

F_{2}^{n}

into

F_{2}^{n}

. Then, for any nonzero

a \in F_{2}^{n}

, we have

\sum_{λ, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) \leq 2^{2 n - 1} (2^{n} - 2) .

Moreover, F is APN if and only if the equality holds for all nonzero a in

F_{2}^{n}

Proof.

By applying relation (2), for any

a \in F_{2}^{n}

, we have the following:

\begin{matrix} \sum_{λ \in F_{2}^{n}} F^{2} (D_{a} F_{λ}) & = \sum_{λ, b \in F_{2}^{n}} F (D_{b} D_{a} F_{λ}) \\ = \sum_{λ, b \in F_{2}^{n}} [2^{n} - 2 wt (D_{b} D_{a} F_{λ})] \\ = 2^{3 n} - 2 \sum_{λ, b \in F_{2}^{n}} wt (D_{b} D_{a} F_{λ}) \\ = 2^{3 n} - 2 \sum_{λ, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) . \end{matrix}

(15)

By applying Theorem 5 and Equation (15), we deduce the following:

\sum_{λ, b \in F_{2}^{n} ∖ {0}} wt (D_{b} D_{a} F_{λ}) \leq 2^{2 n - 1} (2^{n} - 2) .

□

It is evident from Theorem 7 that the sum of the weights of the first-order derivatives of the components of APN permutations is different from that of non-bijective APN functions. However, it is not the case for the sum of the weights of the second-order derivatives of components for both bijective and non-bijective APN functions, since it is clear from Theorem 9 that the sum is the same.

5. Conclusions

In this note, we explored the use of the weights of the first-order and second-order derivatives of vectorial Boolean functions to characterize APN permutations and APN functions, respectively. We demonstrated that a function is an APN permutation if and only if the sum of the squares of the weights of the first-order derivatives of its components is exactly

2^{2 n - 1} (2^{n - 1} + 1) (2^{n} - 1)

. Consequently, it was shown that a function is an APN permutation if and only if the sum of the squares of the weights of components for any first-order derivative at a nonzero element is exactly

2^{2 n - 1} (2^{n - 1} + 1)

. Additionally, we showed that the sum of the weights of the second-order derivatives for any Boolean function is at most

2^{2 n - 1} (2^{n} - 1)

. This bound is achieved if and only if the function is bent. Furthermore, we determined that the sum of the weights of the second-order derivatives of the components of any vectorial Boolean function is at most

2^{2 n - 1} (2^{n} - 1) (2^{n} - 2)

. This bound is achieved if and only if a function is APN.

Funding

This publication was possible thanks to the SG-NAPI award supported by the German Ministry of Education and Research, BMBF, through UNESCO-TWAS.

Data Availability Statement

The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding author.

Conflicts of Interest

The authors declare no conflicts of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript; or in the decision to publish the results.

References

Carlet, C. Boolean Functions for Cryptography and Coding Theory; Cambridge University Press: Cambridge, MA, USA, 2021. [Google Scholar]
Berger, T.P.; Canteaut, A.; Charpin, P.; Laigle-Chapuy, Y. On almost Perfect Nonlinear Functions over $F_{2 n}$ . IEEE Trans. Inf. Theory 2006, 52, 4160–4170. [Google Scholar] [CrossRef]
Beth, T.; Ding, C. On almost perfect nonlinear permutations. In Advances in Cryptology—EUROCRYPT ’93; Helleseth, T., Ed.; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 1994; Volume 765, pp. 65–76. [Google Scholar]
Calderini, M.; Sala, M.; Villa, I. A note on APN permutations in even dimension. Finite Fields Their Appl. 2015, 46, 1–6. [Google Scholar] [CrossRef]
Carlet, C. Characterizations of the Differential Uniformity of Vectorial Functions by the Walsh Transform. IEEE Trans. Inf. Theory 2018, 64, 6443–6453. [Google Scholar] [CrossRef]
Carlet, C. Componentwise APNness, Walsh uniformity of APN functions, and cyclic-additive difference sets. Finite Fields Their Appl. 2018, 53, 226–253. [Google Scholar] [CrossRef]
Browning, K.A.; Dillon, J.F.; McQuistan, M.T.; Wolfe, A.J. An APN permutation in dimension six. Finite Fields Appl. 2010, 518, 33–42. [Google Scholar]
Musukwa, A. On APN functions and their derivatives. arXiv 2023, arXiv:2305.00582. [Google Scholar] [CrossRef]
Canteaut, A.; Carlet, C.; Charpin, P.; Fontaine, C. On cryptographic properties of the cosets of R(1,m). IEEE Trans. Inf. Theory 2001, 47, 1494–1513. [Google Scholar] [CrossRef]
Carlet, C. Vectorial Boolean Functions for Cryptography. In Boolean Models and Methods in Mathematics, Computer Science and Engineering; Cambridge University Press: Cambridge, MA, USA, 2010; Volume 2, pp. 398–470. [Google Scholar]
Cusick, T.W.; Stănică, P. Cryptographic Boolean Functions and Applications; Academic Press: San Diego, CA, USA, 2009. [Google Scholar]
Musukwa, A.; Sala, M. On the linear structures of balanced functions and quadratic APN functions. Cryptogr. Commun. 2020, 12, 859–880. [Google Scholar] [CrossRef]
Musukwa, A.; Sala, M. A Note on Vectorial Boolean Functions as Embeddings. arXiv 2024, arXiv:2406.06429. [Google Scholar] [CrossRef]
Musukwa, A.; Sala, M.; Villa, I.; Zaninelli, M. On Second-Order Derivatives of Boolean Functions and Cubic APN Permutations in Even Dimension. Mediterr. J. Math. 2024, 21, 116. [Google Scholar] [CrossRef]
Nyberg, K. Differentially uniform mappings for cryptography. In Advances in Cryptology—EUROCRYPT ’93; Helleseth, T., Ed.; LNCS 765; Springer: Berlin/Heidelberg, Germany, 1994; pp. 55–64. [Google Scholar]
Zheng, Y.; Zhang, X.-M. On plateaued functions. IEEE Trans. Inf. Theory 2001, 47, 1215–1223. [Google Scholar] [CrossRef]
MacWilliams, F.-J.; Sloane, N.-J.-A. The Theory of Error-Correcting Codes; Elsevier: New York, NY, USA, 1977. [Google Scholar]
Carlet, C. Partially-bent functions. Des Codes Crypt 1993, 3, 135–145. [Google Scholar] [CrossRef]

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the author. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Musukwa, A. A Note on APN Permutations and Their Derivatives. Mathematics 2024, 12, 3477. https://doi.org/10.3390/math12223477

AMA Style

Musukwa A. A Note on APN Permutations and Their Derivatives. Mathematics. 2024; 12(22):3477. https://doi.org/10.3390/math12223477

Chicago/Turabian Style

Musukwa, Augustine. 2024. "A Note on APN Permutations and Their Derivatives" Mathematics 12, no. 22: 3477. https://doi.org/10.3390/math12223477

APA Style

Musukwa, A. (2024). A Note on APN Permutations and Their Derivatives. Mathematics, 12(22), 3477. https://doi.org/10.3390/math12223477

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

A Note on APN Permutations and Their Derivatives

Abstract

1. Introduction

2. Preliminaries

3. On the First-Order Derivatives of APN Permutations

4. On the Weight of the Second-Order Derivatives of APN Functions

5. Conclusions

Funding

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI