Spectral Moment of Order Four and the Uniqueness of the CCZ class of Dublin APN Permutation

Valérie Gillot, Philippe Langevin, Abdoulaye Lo · 2025

Read Spectral Moment of Order Four and the Uniqueness of the CCZ class of Dublin APN Permutation by Valérie Gillot, Philippe Langevin, Abdoulaye Lo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12853.txt.

Introduction

Certain Boolean functions resist every linear attack so well that cryptographers prize them, and one famous example may stand alone in its class. Valérie Gillot, Philippe Langevin, and Abdoulaye Lo test that uniqueness in this 2025 note. The functions act on six bits and are called APN, for almost perfect nonlinear. The note attacks the search through a classification of smaller Boolean functions. A spectral moment of order four supplies a new fingerprint for sorting candidates. The Dublin permutation, a celebrated APN example, is the uniqueness candidate in question.

Catalog record

CREATORValérie Gillot, Philippe Langevin, Abdoulaye Lo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-12853

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Spectral Moment of Order Four and the Uniqueness of the CCZ class of Dublin APN Permutation Valérie Gillot, Philippe Langevin, Abdoulaye Lo Abstract 1. Introduction At Finite Field conference FQ9 in Dublin, K. A. Browning, J. F. Dillon, M. T. McQuistan, and A. J. Wolfe offered to us very good news : the discovery of an apn permutation in dimension six [ 3 ] , we will refer to this as ”Dublin permutation”, or ccz -class of Dublin. Since this announcement of their ”update”, numerous attempts have been made to find a new apn permutation in even dimension, unfortunately, no new such permutations have been found! Thanks to the article [ 5 ] , we now have a list of 14 ccz -classes of 6-bit apn functions with representatives of degree less than or equal to 3. The two numerical searches in dimension 6, the classification of cubic apn functions [ 7 ] and the search for apn permutations [ 2 ] suggest that there is no other ccz -class in dimension 6 . However, the lack of theoretical results leaves open the possibility of unknown sporadic classes, hidden within the complexity of the combinatorial of the problem. In order to eventually uncover a novelty in dimension 6, one must search among functions of degree greater than or equal to 4, probably equal. In this talk, we address the question of the existence of an apn function of degree 4 having a special structure based on observations of the decomposition of the 14 known ccz -classes [ 4 ] . More precisely, 12 of the 14 known ccz -classes contain at least one class composed of vectorial functions such that the set of fourth-order spectral moments of the components has exactly two distinct values. We present a procedure to classify 6 bits apn quartics sharing this regularity. To achieve this, we introduce a new algorithm to test the existence of an APN extension of a given (m,m-2) -function. Our talk also provides specific results on APN-functions based on the classification of 6-bits Boolean functions. The technical details are developped in the following sections. 2. Boolean and vectorial function Let {\mathbb{F}}_{2} be the finite field of order 2 . Let m be a positive integer. We denote B(m) the set of Boolean functions f\colon{\mathbb{F}}^{m}_{2}\rightarrow{\mathbb{F}}_{2} . Every Boolean function has a unique algebraic reduced representation: (1) f(x_{1},x_{2},\ldots,x_{m})=f(x)=\sum_{S\subseteq\{1,2,\ldots,m\}}a_{S}X_{S},\quad a_{S}\in{\mathbb{F}}_{2},\ {X_{S}=\prod_{s\in S}x_{s}}. The degree of f is the maximal cardinality of S with a_{S}=1 in the algebraic form. In this paper, we conventionally fix the degree of the null function to zero. To classify Boolean functions, one introduces two definitions of equivalency, for f,g\in B(m) , f and g are affine equivalent (equivalent) if there exist an affine permutation A of {\mathbb{F}}^{m}_{2} such that (f\circ A)(x)=g(x) or g(x)+1 ; f and g are extended affine equivalent ( ea -equivalent) if there exist an affine permutation A of {\mathbb{F}}^{m}_{2} and an affine Boolean function \ell such that g(x)=(f\circ A)(x)+\ell(x) . The Walsh coefficient of f\in B(m) at a\in{\mathbb{F}}^{m}_{2} is {{\widehat{f}(a)}}=\sum_{x\in{\mathbb{F}}^{m}_{2}}(-1)^{f(x)+a.x}, the multiset of Walsh coefficients is called the Walsh spectrum . Let q=2^{m} , the Walsh coefficients satisfy Parseval’s identity : (2) \sum_{a\in{\mathbb{F}}^{m}_{2}}{{{\widehat{f}(a)}}}^{2}=q^{2} The spectral moment of order r is the integer : (3) {\kappa_{r}(f)}=\frac{1}{q^{2}}\sum_{a\in{\mathbb{F}}^{m}_{2}}{{\widehat{f}(a)}}^{r}. It is an ea -invariant when r is even and we normalize the 4th-order spectral moment : (4) \kappa(f)=\frac{1}{q}{\kappa_{4}(f)}=\frac{1}{q^{3}}\sum_{a\in{\mathbb{F}}^{m}_{2}}{{{\widehat{f}(a)}}}^{4} The multiset \mathfrak{w}(f):=\{\!\!\{|{{{\widehat{f}(a)}}}|\mid a\in{\mathbb{F}}^{m}_{2}\}\!\!\} of absolute value of Walsh coefficients of f , is an ea -invariant . The set \mathcal{Q} of quadratic forms of rank 2 is the set of homogeneous polynomial of degree 2 that are ea -equivalent to x_{1}x_{2} . The set \mathcal{Q} is invariant under the action of the group of affine permutations. Based on \mathcal{Q} and the previous invariant \mathfrak{w} , we define an other ea -invariant \mathfrak{J} on B(m) , the multiset : \mathfrak{J}(f)=\{\!\!\{\mathfrak{w}(f+g)\mid g\in\mathcal{Q}\}\!\!\} . A bent function is a Boolean function f whose Walsh transform has constant absolute value. Bent functions exist only for even m , and satisfy : (5) \forall a\in{\mathbb{F}}^{m}_{2},\quad|{{\widehat{f}(a)}}|=\sqrt{q}=2^{m/2}\Longleftrightarrow\kappa(f)=1 Two complementary notions are defined from the Walsh coefficients of a Boolean function f the linearity {\rm l}{\,(f)} and the non-linearity {\rm nl}{\,(f)} with their bound : {\rm l}{\,(f)}:=\max_{a\in{\mathbb{F}}^{m}_{2}}|{{\widehat{f}(a)}}|\geq 2^{m/2}\qquad{\rm nl}{\,(f)}:=2^{m-1}-\frac{1}{2}\max_{a\in{\mathbb{F}}^{m}_{2}}|{{\widehat{f}(a)}}|\leq 2^{m-1}-2^{m/2-1} Bent functions have a maximal non-linearity and achieve the upper bound of non-linearity 2^{m-1}-2^{m/2-1} . The auto-correlation of a Boolean function f is defined for t\in{\mathbb{F}}^{m}_{2} by : (6) f\times f(t)=\sum_{x+y=t}(-1)^{f(x)+f(y)}=\frac{1}{q}\sum_{a\in{\mathbb{F}}^{m}_{2}}{{\widehat{f}(a)}}^{2}(-1)^{a.t} A vectorial (m,n) -function is a mapping from {\mathbb{F}}^{m}_{2} into {\mathbb{F}}^{n}_{2} , it is defined by n coordinate Boolean functions f_{i}=e_{i}.F(x) such that F(x)=\big(f_{1}(x),f_{2}(x),\ldots,f_{n}(x)\big) with (e_{i})_{1\leq i\leq n} being canonical basis of {\mathbb{F}}^{n}_{2} . For any b\in{\mathbb{F}}^{n}_{2} , the Boolean function x\mapsto F_{b}(x)=b.F(x) is a component of F , the space {\langle F\rangle} of the components is generated by the coordinates of F . The degree of a vectorial function is the maximum among the degrees of its Boolean components. Most concepts introduced earlier for Boolean functions can be extended to vectorial functions. We define equivalency of vectorial functions, for F and G two (m,n) -functions, F and G are affine equivalent (equivalent) if there exist an affine (m,m) -permutation A , an affine (n,n) -permutation B such that G(x)=(B\circ F\circ A)(x) ; F and G are extended affine equivalent ( ea -equivalent) if there exist an affine (m,m) -permutation A , an affine (n,n) -permutation B and an affine (m,n) -function C such that G(x)=(B\circ F\circ A)(x)+C(x) ; F and G are ccz -equivalent if there exists an affine permutation \mathcal{A} on {\mathbb{F}}^{m}_{2}\times{\mathbb{F}}^{n}_{2} such that \mathcal{A}(\Gamma(F))=\Gamma(G) where \Gamma(F)=\{(x,F(x))\mid x\in{\mathbb{F}}^{m}_{2}\} (resp. \Gamma(G) ) is the graph of F (resp. G ). Lemma 1 . The multiset {\mathfrak{J}}^{\prime}(F)=\{\!\!\{\mathfrak{J}(f)\mid f\in{\langle F\rangle}\}\!\!\} is an ea -invariant. The Walsh coefficient of a (m,n) -Function F at (a,b)\in{\mathbb{F}}^{m}_{2}\times{\mathbb{F}}^{n}_{2} is Walsh coefficient of its component F_{b} : {{\widehat{F}(a,b)}}={{\widehat{F_{b}}(a)}}=\sum_{x\in{\mathbb{F}}^{m}_{2}}(-1)^{F_{b}(x)+a.x}, the linearity and non-linearity of a (m,n) -function F are respectively the maximum of linearity among its components and the minimum non-linearity among its components : {\rm l}{\,(F)}:=\max_{a\in{\mathbb{F}}^{m}_{2},b\in{\mathbb{F}}^{n}_{2}\setminus\{0\}}|{{\widehat{F_{b}}(a)}}|\qquad{\rm nl}{\,(F)}:=2^{m-1}-\frac{1}{2}\max_{a\in{\mathbb{F}}^{m}_{2},b\in{\mathbb{F}}^{n}_{2}\setminus\{0\}}|{{\widehat{F_{b}}(a)}}| A (m,n) -function is bent if all its non-zero components are bent. It exists iff m is even and n\leq m/2 . For m=2k and n>k , an (m,n) -function F is called (m,n) - mnbc function see [ 1 ] , if it has the maximum number of bent components 2^{n}-2^{n-k} . We consider the system of two equations and r variables in {\mathbb{F}}^{m}_{2} : (7) x_{1}+x_{2}+\cdots+x_{r}=0,\quad\text{and}\quad F(x_{1})+F(x_{2})+\cdots+F(x_{r})=0. We propose to denote by N_{r}(F) the number of solutions, and T_{r}(F) the number of solutions where x_{1} , x_{2} , …, x_{r} are not all distincts. Let us denote (8) Q_{r}(F):=\frac{1}{r!}(N_{r}(F)-T_{r}(F)) Using the character sum counting method, the number of solutions N_{r}(F) of the above system is \displaystyle N_{r}(F) \displaystyle=\frac{1}{2^{n+m}}\sum_{x_{1},x_{2},\ldots,x_{r}}\sum_{b\in\mathbb{F}_{2}^{n}}(-1)^{b.(F(x_{1})+F(x_{2})+\cdots+F(x_{r}))}\sum_{a\in\mathbb{F}_{2}^{m}}(-1)^{a.(x_{1}+x_{2}+\cdots+x_{r})} \displaystyle=\frac{1}{2^{n+m}}\sum_{b\in\mathbb{F}_{2}^{n}}\sum_{a\in\mathbb{F}_{2}^{m}}{{\widehat{F_{b}}(a)}}^{r} In term of moments of order r by of the components of F : (9) N_{r}(F)=2^{m-n}\sum_{f\in{\langle F\rangle}}{\kappa_{r}(f)}. When we observe the Boolean components space {\langle F\rangle} of a vectorial function F , we are interested on the one hand in the set of their ea -classes C_{F}:=\{\text{{ea}-classes}(f)\mid f\in{\langle F\rangle}\} and on the other hand in the set of all normalised 4th-order spectral moments K_{F}:=\{\kappa(f)\mid f\in{\langle F\rangle}\} . For these two sets, we also study their cardinality and their distribution of values. Note that \sharp K_{F}\leq\sharp

Read the complete text