TOPICS
Search

Almost Perfect Nonlinear Function


An almost perfect nonlinear (APN) function F:GF(2)^n->GF(2)^n is a function for which

 F(x+a)+F(x)=b
(1)

has at most two solutions x for every a!=0 and every b (Nyberg 1994). All additions are in the vector space over the two-element finite field. Solutions occur in pairs x,x+a, so this is the smallest possible differential uniformity. The condition controls differential behavior and differs from the affine approximation measured by Boolean function nonlinearity.

The Dobbertin APN function on L=GF(q^5), where q=2^m and m>=1, is

 F(x)=x^(q^4+q^3+q^2+q-1).
(2)

This family was introduced by Dobbertin (2001). For a,b in L, define its Walsh coefficient by

 W_q(a,b)=sum_(x in L)(-1)^(Tr_(L/GF(2))(aF(x)+bx)).
(3)

Kölsch (2026) determines these coefficients through elliptic-curve point counts and Kloosterman sums. In particular, its linearity, the maximum of |W_q(a,b)| over a!=0 and all b, is exactly

 q^2(q+1).
(4)

The set of absolute Walsh values occurring is

 {q^2(q+1)} union q^2U_m union {q^2j:j positive and odd, j<=2sqrt(q)},
(5)

where U_m={0,2^((m+1)/2)} for odd m and U_m={0,2^(m/2),2^(m/2+1)} for even m. This lists the values, without claiming their multiplicities. For example, at a=b=1 the coefficient is (-1)^(m+1)q^2(q+1). Kölsch (2026) reports that ChatGPT suggested the use of Dwork's rationality theorem in the simplified proof.


See also

Boolean Function Nonlinearity, Finite Field, Linear Code, Walsh Transform

Explore with Wolfram|Alpha

References

Dobbertin, H. "Almost Perfect Nonlinear Power Functions on GF(2^n): A New Case for n Divisible by 5." In Finite Fields and Applications (Ed. D. Jungnickel and H. Niederreiter). Berlin, Germany: Springer-Verlag, pp. 113-121, 2001. https://doi.org/10.1007/978-3-642-56755-1_11.Kölsch, L. "The Walsh Spectrum of the Dobbertin APN Function." 13 Nov 2026. https://arxiv.org/abs/2611.18907v1.Nyberg, K. "Differentially Uniform Mappings for Cryptography." In Advances in Cryptology-EUROCRYPT '93 (Ed. T. Helleseth). Berlin, Germany: Springer-Verlag, pp. 55-64, 1994. https://doi.org/10.1007/3-540-48285-7_6.

Cite this as:

Weisstein, Eric W. "Almost Perfect Nonlinear Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AlmostPerfectNonlinearFunction.html

Subject classifications