CS Paper Radar

The APN Property of Two Families of functions over $\F_{2^{n}}$ from the Switching Construction

Chenmiao Shi, Longjiang Qu, Kangquan Li

cs.IT ·submitted 2026-11-03 14:57 UTC · v1
theory

Abstract

Let $m\geq5$ be odd with $3\nmid m$. Helleseth, Ichanska, and Kaleyski \cite{HIK} conjectured that two norm-perturbed Budaghyan--Helleseth--Kaleyski functions $F_2,F_3$ over $\F_{2^{2m}}$ are APN. In this paper, we prove this conjecture. First, by using the basis $(1,β)$ of $\F_{2^{2m}}$ over $\F_{2^m}$, we show that $F_2$ and $F_3$ are EA-equivalent to two functions $\mathcal G_1$ and $\mathcal G_0$, respectively. Their derivatives can be written as two trace equations for a matrix $P\in\mathrm{GL}(2,\F_{2^m})$. We then prove that these two equations have no solution. The proof uses only identities over finite fields, the characteristic polynomial of a $2\times2$ matrix, and elementary properties of Frobenius automorphisms. The repeated-root case and all parity cases are considered separately. It follows that the derivative of each function has kernel of size two in every nonzero direction, and hence both $F_2$ and $F_3$ are APN for every admissible $m$.

Closest papers

Nearest neighbours by meaning across the whole index.

Reduced APN permutations and a disproof of the Galois-ring lifting conjecture

cs.IT math.NT ·2026-08-31 ·Daniele Bartoli, Pantelimon Stanica
similarity 0.66
Abstract

We construct infinite families of reduced almost perfect nonlinear (APN) permutations of $\mathbb{F}_{2^m}$ that admit coefficientwise permutation lifts to $\mathrm{GR}(2^k,m)$ for every $k>1$. These families disprove Conjecture~2 of Rønjom and Sandrib (Cryptogr. Commun., 2026), even for reduced polynomial representatives. For every odd $m\ge5$ with $3\nmid m$, we obtain explicit seven-term polynomials over $\mathbb{F}_2$ with formal derivative identically one. We derive them from a complete criterion for the reduced representative of $A(x)^{2^s+1}$ to have no critical point in $\mathbb{F}_{2^m}$, where $A$ is an invertible linearized polynomial and $\gcd(s,m)=1$. We then apply the cube case to construct a second family of degree $2^{m-1}+2$, whose nonconstant derivatives avoid zero by an explicit trace identity. A fixed parameter in $\mathbb{F}_{32}$ gives this family in every dimension $m=5r$ with $r$ odd, including a degree-$18$ example over $\mathbb{F}_{32}$. Both constructions remain in Gold linear equivalence classes, so liftability of reduced representatives is not invariant under invertible $\mathbb{F}_2$-linear input changes. We obtain the lifting conclusions from the standard Galois-ring permutation criterion. We also verify a degree-$24$ example supplied by Zhang and Haobo, prove a trace-adjoint criterion for reduced quadratic functions, and interpret the derivative condition through ramification at rational points.

0.45

On different notions related to APN mappings

cs.IT math.CO ·2026-09-18 ·René Rodríguez-Aldama, Ajla Šehović, Enes Pasalic, Sadmir Kudin
similarity 0.60
Abstract · 30 pages, 2 figures, 3 tables. Example 3.2 has been added. As a consequence, Conjecture 3.1 was modified and renamed as Open Problem 1. The …

An APN mapping $F:\mathbb{F}_{2^n}\to \mathbb{F}_{2^n}$ is a polynomial characterized by the non-vanishing property on 2-flats. In this work, we analyze notions that are closely related to this property. To understand which $k$-flats of $\mathbb{F}_{2^n}$ remain flats under $F$, we study the $k$-breaking. The function $x^{-1}$ has been studied in the past in this context---we extend this study to general mappings and characterize the 2-breaking of APN functions. Recently, two generalizations of the APN property have been introduced: $k$-strongly non-normality and $k$-th-order sum-freedom. Sum-freedom generalizes the non-vanishing property of APN functions to higher dimensional flats. We provide in-depth observations of the relations between the breaking property, strongly non-normality and sum-freedom. We introduce a fourth concept called $k$-strongly breaking, which implies the breaking property. We derive several structural results for both notions and give a characterization of a subclass of APN functions in terms of the 2-strongly breaking property. We propose a different perspective of the non-vanishing property via a natural character transformation, which is closely related to the sum-of-square indicator of the components of $F$. We derive a precise value for the total sum of the sum-of-square indicators of $F$. With this approach, we provide a simple answer to Open Problem 4 in IEEE Trans. Inf. Theory 52(9): 4160-4170, 2006. Moreover, it allows us to explore balancedness properties of polynomials, one of which characterizes component-wise APNness, for odd $n$, and provides a natural extension to any dimension. We show that Dillon's APN permutation and the Gold functions satisfy a related property, termed $k$-balanced, which is presented under our framework.

0.34

Quadratic APN Functions of $\mathbb{F}_2^{10}$ with a Self-Equivalence of Prime Order

cs.IT cs.CRmath.CO ·2026-11-13 ·Emanuele Bellini
similarity 0.59
Abstract

Almost perfect nonlinear (APN) functions of $\mathbb{F}_2^n$ have the lowest possible differential uniformity. The only known APN permutation in even dimension, in dimension six, is equivalent to a quadratic APN function with a nontrivial linear self-equivalence; no APN permutation is known for even $n \geq 8$. In a published collection of about 3.8 million quadratic APN classes of dimension eight, at most 0.34% have a nontrivial linear self-equivalence. In dimension ten, the 25 literature classes considered here all have one. We study all quadratic APN functions of $\mathbb{F}_2^{10}$ with such a self-equivalence, which usually confines them to a much smaller linear space. Up to conjugacy and power similarity, self-equivalences of prime order have 299 types. We settle 298 of them. Elementary lemmas exclude 280 types, and exhaustive searches confirm this for 242 of them. The other 18 types are settled by exhaustive searches with exact equivalence certificates. Up to extended affine equivalence, the 298 types contain 29 classes of quadratic APN functions, four of them new. This also classifies the quadratic APN functions with coefficients in a subfield. Exactly 24 classes contain one with coefficients in $\mathbb{F}_4$, and all 3 that contain one with coefficients in $\mathbb{F}_{32}$ are among them. The open type consists of the quadratic canonical triplicate functions. They correspond to maximum additive Hermitian rank-distance codes. Three different searches find only the invariants of 16 classes, all among the 29. We conjecture there are no others. No quadratic APN function in the 298 settled types is Carlet-Charpin-Zinoviev equivalent to a permutation.

0.24

CCZ-Equivalence and Enumeration of Triprojective APN Functions

cs.CR ·2026-08-12 ·Jingchuan Ma, Yanhua Liu, Qiaoyun Huang
similarity 0.59
Abstract · 17 pages

We classify all admissible parameters of the G"ologlu--K"olsch triprojective construction of almost perfect nonlinear (APN) functions up to Carlet--Charpin--Zinoviev (CCZ) equivalence. The construction has three coefficients in $K=\mathbb{F}_{2^m}$ and a Frobenius exponent $k$ coprime to $m$. For every $m>1$, we give a necessary-and-sufficient criterion that includes changes of both the coefficients and the exponent. Each parameter choice determines one of the two irreducible cubic polynomials over $\mathbb{F}_2$. Two functions are equivalent precisely when their exponents and cubics agree, or when the exponents are negatives modulo $m$ and the cubics are reciprocal. When $7\nmid m$, every admissible member is equivalent to a Li--Kaleyski representative: the larger coefficient space adds no CCZ classes. When $7\mid m$, those representatives are inadmissible; we construct replacements and classify the full family. There are exactly $\varphi(m)$ CCZ classes, extending the previously known count for the older subfamilies to all admissible coefficients and all degrees. We also count the parameter triples and compute canonical representatives and explicit equivalence maps in deterministic polynomial time for every degree, including degrees divisible by seven. The proof combines a reduction to classical semilinear conjugacy with an intrinsic recovery of the scalar field from the polar bilinear map. The reduction from arbitrary EL equivalence is algebraic in every degree, including degrees three and six.

0.10

Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions

cs.CR cs.IT ·2026-11-06 ·Emanuele Bellini
similarity 0.59
Abstract

Whether almost perfect nonlinear (APN) permutations exist in even dimension $n\ge 8$ is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet--Charpin--Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary $n$-dimensional subspaces among the zeros of the Walsh transform, which lie in $\mathbb{F}_2^{2n}$. A known necessary condition only uses their projections to $\mathbb{F}_2^n$ and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of $\mathbb{F}_2^n$ and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them $39$ to $55$ times faster than the generic search of the commonly used sboxU library. We then study the functions $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$, which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when $4$ divides $n$. With their result, our computations show that this holds for every even $n\le 24$. In dimension $18$ the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile $25$ classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.

0.61

On APN Functions with Boomerang Uniformity One over $\mathbb F_{3^n}$: Differential and Boomerang Spectra and CCZ-Inequivalence

cs.CR ·2026-09-08 ·Namhun Koo, Soonhak Kwon, Minwoo Ko, Byunguk Kim
theory similarity 0.58
Abstract · 37 pages

Let $q=3^n$, where $n>1$ is odd, and let $g:\Fq\to\Fq$ be a perfect nonlinear (PN) function represented by a Dembowski--Ostrom (DO) polynomial. Put $τ=g(1)$, let $ε$ be the indicator of $\Fthree^*$, and, for $c\in\Fq$, define $\widetilde G_c(x):=g(x+c)+τε(x)$. We prove that every $\widetilde G_c$ is APN and has boomerang uniformity either one or two. More precisely, \[ β_{\widetilde G_c}=1 \quad\Longleftrightarrow\quad c\in\mathcal C_g :=\{c\in\Fq\setminus\Fthree:g(c)+τ\notin g(\Fq)\}, \qquad |\mathcal C_g|=\frac{q-3}{2}, \] whereas $β_{\widetilde G_c}=2$ for the remaining $(q+3)/2$ parameters. We determine the common differential spectrum and complete boomerang spectra of all the functions $\widetilde G_c$. Since boomerang uniformity one is the least possible for an APN function over a finite field of odd characteristic, this gives, to the best of our knowledge, the first general construction yielding infinite families of APN functions attaining this optimum. This common differential spectrum rules out CCZ equivalence with every power function and every Ness--Helleseth-type binomial. We also prove that CCZ equivalence between sign-switches of DO PN functions forces EA equivalence between the original PN functions. Using the orders of the nuclei of the associated presemifields, we exhibit, for infinitely many odd $n$, three pairwise CCZ-inequivalent PN functions over $\F_{3^n}$, one from each of the Gold $f_1$, Ding--Yuan $f_3$, and Bierbrauer $f_5$ families. Consequently, over each such field, our construction produces three pairwise CCZ-inequivalent APN functions with boomerang uniformity one. The smallest extension degree obtained in this way is $n=45$.

0.53

New Classes of CCZ-Inequivalent APN Functions with Boomerang Uniformity One in Odd Characteristic: Differential and Boomerang Spectra

cs.IT cs.CR ·2026-11-07 ·Namhun Koo, Soonhak Kwon
similarity 0.58
Abstract

Let $q=p^n>3$ be an odd prime power and let $g:\F_q\to\F_q$ be an even perfect nonlinear (PN) function with $g(0)=0$. We construct almost perfect nonlinear (APN) functions $G_{λ,M}(x)=g(x)+M(x)+λ(x^{q-1}-1)$, where $λ\in\F_q^*$, $-λ\notin g(\F_q)$, and $M$ is an $\F_p$-linearized permutation polynomial. These one-point modifications of $g+M$ have boomerang uniformity one, the smallest possible value for APN functions in odd characteristic. We give complete differential and boomerang spectrum formulas and obtain closed-form evaluations for selected constructions based on Coulter--Matthews monomials and Dembowski--Ostrom polynomials. For $q>7$, comparison of differential spectra establishes CCZ-inequivalence to all APN monomial families listed in the paper and every APN binomial in the original Ness--Helleseth family or its extension by Zeng et al. We characterize CCZ-equivalence within our construction, showing that any two linearly inequivalent even PN functions over the same field yield CCZ-inequivalent APN functions. We obtain three pairwise CCZ-inequivalent APN functions with boomerang uniformity one over $\F_{p^{15\ell}}$ for every $\ell\ge1$, six over $\F_{p^{120r}}$ for every $r\ge1$, and unbounded numbers of such classes in characteristic three. We further prove that CCZ-equivalence and EA-equivalence coincide for functions at Hamming distance at most $m$ from a PN function, provided that $m(m+1)<q-q/p$. We also show that all our APN functions have the maximal possible algebraic degree $n(p-1)$. Finally, we exhibit both CCZ-equivalent and CCZ-inequivalent APN pairs with boomerang uniformity one at Hamming distance one.

0.17

A new upper bound for Sidon sets in $\mathbb{F}_2^{4k+3}$

cs.IT math.CO ·2026-09-23 ·Darrion Thornburgh
theory similarity 0.57
Abstract · 7 pages

A subset $S \subseteq \mathbb{F}_2^n$ is called a Sidon set if no four distinct points of $S$ have zero sum. It is shown that if $n \geq 7$ and $n \equiv 3 \mod 4$, then $|S|\leq 2^{\frac{n+1}{2}}-3$. As a consequence, for any even $t \geq 4$, there does not exist a binary linear $[2^t-3,2^t-2t-2,5]$-code, strengthening a nonexistence result of Brouwer and Tolhuizen from 1993. As a second consequence, we also show that for an even integer $n \geq 4$, every almost perfect nonlinear (APN) function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ has nonlinearity at least $3$.

0.21