betaFeedback

WorksMathematics

The Walsh spectrum of the Dobbertin APN function

Abstract

APN functions yield the best resistance to differential attacks when used as a building block of a block cipher. APN functions induced by monomials over finite fields have received particular interest both for their simplicity and their unique properties. A key property of APN functions is their linearity, which has been determined for all known APN monomials outside of the Dobbertin APN monomials. In this paper, we close this gap and determine the complete Walsh spectrum and in particular the linearity of the Dobbertin APN monomial, answering a problem that has been open for more than 20 years. Using known connections, our result also yields the asymptotically largest Sidon sets in elementary abelian 22-groups constructed so far as well as binary linear codes of minimum distance 55 that are almost optimal.

Introduction

Vectorial Boolean functions play an important role in the design of symmetric cryptosystems, serving as the building blocks of block ciphers. To resist differential attacks, a vectorial Boolean function should have low differential uniformity.

Definition 1.1 (Differential uniformity). A function F ⁣:F2n→F2nF \colon\mathbb{F}_2^n \to\mathbb{F}_2^n has differential uniformity dd, if

d=max⁡a∈F2n∖{0}b∈F2n∣{x ⁣:F(x)+F(x+a)=b}∣.d = \max_{\substack{a \in\mathbb{F}_2^n \setminus\{0\}\\ b \in\mathbb{F}_2^n}} \left|\{x \colon F(x) + F(x+a) = b\}\right|.

A function with differential uniformity 2 is called almost perfect nonlinear (APN).

As the differential uniformity is always even, APN functions F ⁣:F2n→F2nF \colon\mathbb{F}_2^n \to\mathbb{F}_2^n provide optimal resistance against differential attacks. One of the most important properties of vectorial Boolean functions for use in substitution permutation networks (SPNs) is their linearity, which can be defined via the Walsh transform of the function.

Definition 1.2 (Walsh transform and linearity). Let F ⁣:F2n→F2nF \colon\mathbb{F}_2^n \to\mathbb{F}_2^n be a function. We define its Walsh transform

WF(a,b)=∑x∈F2n(−1)⟨a,F(x)⟩+⟨b,x⟩,W_F(a,b) = \sum_{x \in\mathbb{F}_2^n} (-1)^{\langle a,F(x)\rangle+\langle b,x\rangle},

where ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle is an arbitrary non-degenerate inner product. We call the multiset that collects the values WF(a,b)W_F(a,b) for all a∈F2n∖{0}a \in\mathbb{F}_2^n \setminus\{0\}, b∈F2nb \in\mathbb{F}_2^n the Walsh spectrum of FF and the multiset that collects ∣WF(a,b)∣|W_F(a,b)| for all a∈F2n∖{0}a \in\mathbb{F}_2^n \setminus\{0\}, b∈F2nb \in\mathbb{F}_2^n the extended Walsh spectrum of $F. The linearity of FF is then defined as

L(F)=max⁡a∈F2n∖{0}b∈F2n∣WF(a,b)∣.L(F) = \max_{\substack{a \in\mathbb{F}_2^n \setminus\{0\}\\ b \in\mathbb{F}_2^n}} |W_F(a,b)|.

All infinite families of APN functions known so far fall in one of two groups: Either they are quadratic, i.e., of algebraic degree 2. In this case, the theory of quadratic forms immediately implies that the Walsh transform of these functions can only take on 0 or powers of 2. A recent study of the possible Walsh spectra of quadratic APN functions can be found in [1]. The second group of APN families consists of APN functions induced by monomials defined over finite fields, i.e., one identifies F2n\mathbb{F}_2^n with the additive group of the finite field F2n\mathbb{F}_{2^n} and then considers functions of the form x↦xdx \mapsto x^d. A table of all known infinite families of APN exponents (up to CCZ-equivalence, which does not affect the extended Walsh spectrum) can be found in Table 1. As we can see in Table 1, all Walsh spectra of the known APN monomials are known, with the exception of the Dobbertin APN monomials. The main objective of this paper is to fill in this gap. The Dobbertin APN function is a monomial defined on Fq5\mathbb{F}_{q^5} where q=2mq=2^m via Fq(x)=xDqF_q(x)=x^{D_q} where Dq=q4+q3+q2+q−1D_q=q^4+q^3+q^2+q-1.

FamilyExponent ddConditionsWalsh valuesReferences
Gold2i+12^i+1gcd⁡(i,n)=1\gcd(i,n)=1{0,±2(n+1)/2}\{0,\pm2^{(n+1)/2}\}, nn odd, {0,±2n/2,±2n/2+1}\{0,\pm2^{n/2},\pm2^{n/2+1}\}, nn even[22, 12, 24]
Kasami22i−2i+12^{2i}-2^i+1gcd⁡(i,n)=1\gcd(i,n)=1{0,±2(n+1)/2}\{0,\pm2^{(n+1)/2}\}, nn odd, {0,±2n/2,±2n/2+1}\{0,\pm2^{n/2},\pm2^{n/2+1}\}, nn even[16, 17, 24]
Welch2t+32^t+3n=2t+1n=2t+1{0,±2(n+1)/2}\{0,\pm2^{(n+1)/2}\}[9, 3]
Niho2t+2t/2−12^t+2^{t/2}-1n=2t+1n=2t+1, tt even{0,±2(n+1)/2}\{0,\pm2^{(n+1)/2}\}[8, 14]
2t+2(3t+1)/2−12^t+2^{(3t+1)/2}-1n=2t+1n=2t+1, tt odd{0,±2(n+1)/2}\{0,\pm2^{(n+1)/2}\}[8, 14]
Inverse2n−22^n-2nn odd4Z∩[1−2n/2+1,1+2n/2+1]4\mathbb{Z}\cap[1-2^{n/2+1},1+2^{n/2+1}][22, 20]
Dobbertin24m+23m+22m+2m−12^{4m}+2^{3m}+2^{2m}+2^m-1n=5mn=5mThis work[10]

Table 1. Known APN power families over F2n\mathbb{F}_{2^n}, n≥3n\geq3, up to CCZ-equivalence.

Up until this work, the only known result on the Walsh spectrum of the Dobbertin APN function is that all values are divisible by q2q^2 but not all values are divisible by any larger power of 22, which was shown in 2000 by Canteaut, Charpin, and Dobbertin [4]. Since then, no progress on determining the Walsh spectra of the Dobbertin APN function has been made.

Notation and statement of major results

Fix q=2mq=2^m with m≥1m\geq1, and put K=FqK=\mathbb{F}_q, L=Fq5L=\mathbb{F}_{q^5}, and Kr=FqrK_r=\mathbb{F}_{q^r}. For a finite field FF of characteristic two, write its canonical additive character as

ψF(z)=(−1)Tr⁡F/F2(z).\psi_F(z)=(-1)^{\operatorname{Tr}_{F/\mathbb{F}_2}(z)}.

This paper is concerned with the Walsh transform of the Dobbertin APN function F:L→LF:L\to L defined via F(x)=xDqF(x)=x^{D_q}, where Dq=q4+q3+q2+q−1D_q=q^4+q^3+q^2+q-1. We denote its Walsh transform as

Wq(a,b)=∑x∈Fq5(−1)Tr⁡Fq5/F2(axDq+bx).W_q(a,b)=\sum_{x\in\mathbb{F}_{q^5}}(-1)^{\operatorname{Tr}_{\mathbb{F}_{q^5}/\mathbb{F}_2}(ax^{D_q}+bx)}.

Note that a simple substitution shows Wq(a,b)=Wq(a/(bDq),1)W_q(a,b)=W_q(a/(b^{D_q}),1) if b≠0b\neq0, so it actually suffices to determine Wq(a,1)W_q(a,1) and Wq(a,0)W_q(a,0). Moreover, we have gcd⁡(Dq,q5−1)=1\gcd(D_q,q^5-1)=1 if q=2mq=2^m with mm odd and gcd⁡(Dq,q5−1)=3\gcd(D_q,q^5-1)=3 if mm is even (this holds generally for all APN exponents as shown by Dobbertin, see [5 Proposition 165]), so we get immediately:

Lemma 2.1. Let q=2mq=2^m. We have for all a≠0a\neq0 that

Wq(a,0)={(−1)m/225m/2,m is even, a is a non-cube,(−1)m/2+125m/2+1,m is even, a is a cube,0,m is odd.W_q(a,0)= \begin{cases} (-1)^{m/2}2^{5m/2}, & m\text{ is even},\ a\text{ is a non-cube},\\ (-1)^{m/2+1}2^{5m/2+1}, & m\text{ is even},\ a\text{ is a cube},\\ 0, & m\text{ is odd}. \end{cases}

Proof. By the consideration above, we have Wq(a,0)=0W_q(a,0)=0 if mm is odd since x↦xqaDx\mapsto x^{q^D_a} permutes LL. If mm is even then Wq(a,0)=WF(a,0)W_q(a,0)=W_F(a,0) where F(x)=x3F(x)=x^3. This cubic sum was determined by Carlitz [6]. □

References

  1. [1]Sophie Hannah Bénéteau, Nicolas Goluboff, Lukas Kölsch, and Divyesh Vaghasiya, On the walsh spectra of quadratic apn functions, IEEE Transactions on Information Theory (2026). (Cited on page 1.)arxiv.org/abs/2510.12008
  2. [2]Lilya Budaghyan, Marco Calderini, Claude Carlet, Diana Davidova, and Nikolay S Kaleyski, On two fundamental problems on apn power functions, IEEE Transactions on Information Theory 68 (2022), no. 5, 3389–3403. (Cited on pages 4 and 6.)DOI
  3. [3]Anne Canteaut, Pascale Charpin, and Hans Dobbertin, Binary m-sequences with three-valued cross-correlation: a proof of Welch’s conjecture, IEEE Transactions on Information Theory 46 (2000), no. 1, 4–8. (Cited on page 2.)
  4. [4]———, Weight divisibility of cyclic codes, highly nonlinear functions on f2m, and crosscorrelation of maximum-length sequences, SIAM Journal on Discrete Mathematics 13 (2000), no. 1, 105–138. (Cited on page 2.)DOI
  5. [5]Claude Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, 2021. (Cited on pages 2 and 9.)DOI
  6. [6]Leonard Carlitz, Explicit evaluation of certain exponential sums, Mathematica Scandinavica 44 (1979), no. 1, 5–16. (Cited on pages 3 and 22.)DOI
  7. [7]Ingo Czerwinski and Alexander Patz, On large Sidon sets, Journal of Combinatorial Theory, Series A 220 (2026), 106129. (Cited on pages 24 and 25.)
  8. [8]Hans Dobbertin, Almost perfect nonlinear power functions on GF(2^n): the Niho case, Information and Computation 151 (1999), no. 1–2, 57–72. (Cited on page 2.)
  9. [9]———, Almost perfect nonlinear power functions on GF(2^n): the Welch case, IEEE Transactions on Information Theory 45 (1999), no. 4, 1271–1275. (Cited on page 2.)DOI
  10. [10]———, Almost perfect nonlinear power functions on GF(2^n): a new case for n divisible by 5, Finite Fields and Applications (Dieter Jungnickel and Harald Niederreiter, eds.), Springer, 2001, pp. 113–121. (Cited on page 2.)DOI
  11. [11]Bernard Dwork, On the rationality of the zeta function of an algebraic variety, American Journal of Mathematics 82 (1960), 631–648. (Cited on page 14.)DOI
  12. [12]Robert Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Transactions on Information Theory 14 (1968), no. 1, 154–156. (Cited on page 2.)DOI
  13. [13]Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, vol. 52, Springer-Verlag, New York, 1977. (Cited on page 21.)
  14. [14]H. D. L. Hollmann and Qing Xiang, A proof of the Welch and Niho conjectures on cross-correlations of binary m-sequences, Finite Fields and Their Applications 7 (2001), no. 2, 253–286. (Cited on page 2.)DOI
  15. [15]Xiang-Dong Hou, Explicit evaluation of certain exponential sums of binary quadratic functions, Finite Fields and Their Applications 13 (2007), no. 4, 843–868. (Cited on page 22.)DOI
  16. [16]H. Janwa and R. M. Wilson, Hyperplane sections of Fermat varieties in P^3 in char. 2 and some applications to cyclic codes, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Gérard Cohen, Teo Mora, and Oscar Moreno, eds.), Lecture Notes in Computer Science, vol. 673, Springer, 1993, pp. 180–194. (Cited on page 2.)DOI
  17. [17]Tadao Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed–Muller codes, Information and Control 18 (1971), no. 4, 369–394. (Cited on page 2.)DOI
  18. [18]Neal Koblitz, p-adic numbers, p-adic analysis, and zeta-functions, 2 ed., Graduate Texts in Mathematics, vol. 58, Springer-Verlag, New York, 1984. (Cited on page 14.)
  19. [19]Gilles Lachaud and Jacques Wolfmann, Sommes de Kloosterman, courbes elliptiques et codes cycliques en caractéristique 2, C. R. Acad. Sci. Paris Sér. I Math. 305 (1987), no. 20, 881–883. (Cited on page 21.)
  20. [20]——— , The weights of the orthogonals of the extended quadratic binary Goppa codes, IEEE Transactions on Information Theory 36 (1990), no. 3, 686–692. (Cited on pages 2 and 23.)DOI
  21. [21]F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, North-Holland Mathematical Library, vol. 16, North-Holland, Amsterdam, 1977. (Cited on page 25.)
  22. [22]Kaisa Nyberg, Differentially uniform mappings for cryptography, Advances in Cryptology—EUROCRYPT ’93 (Tor Helleseth, ed.), Lecture Notes in Computer Science, vol. 765, Springer, 1994, pp. 55–64. (Cited on page 2.)
  23. [23]Joseph H. Silverman, The arithmetic of elliptic curves, 2 ed., Graduate Texts in Mathematics, vol. 106, Springer, New York, 2009. (Cited on page 14.)
  24. [24]Satoshi Yoshiara, Plateaudness of Kasami APN functions, Finite Fields and Their Applications 47 (2017), 11–32. (Cited on page 2.)DOI

Paper details

vlnc:W_vmdfxjbb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT 6

View statement
Looking for related papers…
Contents