CS Paper Radar

Complete characterization of the differential spectrum of a Niho type power function

Nian Li, Xi Xie, Rui Xu, Yi Yu, Xiangyong Zeng

cs.IT ·submitted 2026-08-12 07:52 UTC · v1

Abstract

Power functions with Niho exponents have attracted considerable attention due to their important applications in sequence design, coding theory, and cryptography. This paper investigates the differential properties of Niho type power functions of the form $F(x)=x^{s(2^m-1)+1}$ over $\mathbb{F}_{2^{2m}}$ with $2\leq s\leq 2^m$. We first establish a general characterization of the differential spectrum of $F(x)$ having at most three nonzero values via its Walsh spectrum. Focusing subsequently on the case $s=(2^k+1)^{-1} \pmod{2^m+1}$ where $\gcd(k,m)=e$, we employ a refined analysis of the number of solutions to certain equations over finite fields. Specifically, it is proved that $F(x)$ is locally differentially $2^e$-uniform when $\gcd(2^k-1,2^m+1)=2^e+1$ and locally differentially $(2^{2e}-2^e)$-uniform when $\gcd(2^k-1,2^m+1)=1$, and their differential spectra are completely determined. These results completely characterize the differential properties of this family and yield new infinite families of locally differentially $4$-uniform power functions.

Closest papers

Nearest neighbours by meaning across the whole index.

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.59
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

New Construction of Power Functions with Low c-Differential Uniformity over Finite Fields

cs.IT ·2026-09-19 ·Zhiye Yang, Yan Wang, Keqin Feng
theory similarity 0.59
Abstract

This paper investigates the $c$-differential uniformity of power functions over finite fields, an important class of cryptographic functions with favorable differential properties. Specifically, for finite fields $\mathbb{F}_q$ satisfying $q-1=en$ with $e\ge 3$ and $e\mid n$, we prove that there exists $c\in\mathbb{F}_q\setminus\{0,1,ε,\dots,ε^{e-1}\}$, where $ε$ is an $e$-th primitive root of unity in $\mathbb{F}_q^*$, the constructed power functions $f(x)=x^{ln+1}$ with $1\le l\le e-1$ and $\gcd(l,e)=1$ satisfy the upper bound $Δ(f,c)\le e$, provided that certain cyclotomic conditions hold. We show that our conditions are mild; namely, such power functions can be constructed over infinitely many extension fields $\mathbb{F}_q$ of $\mathbb{F}_p$ for any given $e\ge 3$ and prime $p$ with $p\nmid e$. Furthermore, based on the Weil bound for multiplicative character sums, we prove that the obtained upper bound is tight for sufficiently large $q$, demonstrating the optimality of our results. We also analyze the special case $c=-1$ and derive simplified explicit conditions. In particular, we explicitly characterize the admissible parameters for the case $e=3$ and present concrete function examples for practical validation.

0.25

On the boomerang spectrum of the APN power function $x^{q+2}$ over $\F_{q^2}$

cs.IT math.NT ·2026-11-14 ·Kirpa Garg, Constanza Riera, Pantelimon Stănică
similarity 0.58
Abstract

We study the boomerang spectrum of the almost perfect nonlinear power function $x^{q+2}$ over $\F_{q^2}$, where $q$ is an odd prime power with $q\equiv1\pmod6$. The connection of Pal and Stănică between boomerang entries and $(-1)$-differential entries reduces the problem to counting roots of a single equation. We determine the complete contribution from nonzero parameters in $\F_q$. For parameters outside $\F_q$, we obtain a quintic over $\F_q$ in terms of the parameter's trace and norm, with a separate formula when the trace is zero. We exclude the entry four when $q\equiv1\pmod{12}$ and characterize its occurrence when $q\equiv7\pmod{12}$ through a repeated-root parametrization and a residual cubic. We also evaluate the first nonsubfield moment and an aggregate quadratic-character sum, and prove a Weil bound for each nonzero trace. Explicit secant and residual-cubic formulas express the second, third, and fourth falling-factorial moments as finite sums. Once the size-four frequency is known, these moments recover all remaining frequencies through a nonsingular five-dimensional system. A closed-form evaluation of the nonsubfield distribution remains open.

0.23

Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports

cs.IT ·2026-09-18 ·Chen Wang, Xiaoyan Zhang, Chunming Tang, Zhengchun Zhou
hot direction similarity 0.53
Abstract

Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general construction attaining both properties is spectral (Hodžić et al., IEEE Trans. Inf. Theory 65(9): 5865--5879, 2019). In that work, explicit algebraic normal forms are not generally provided, and no general method is established for prescribing a common algebraic degree for all family members. In this paper, we present two new explicit algebraic constructions within a unified framework, one based on linear functions and the other on partially linear functions with bent components. Let $p\geq 2$ and $q\geq 0$ satisfy $q<2^p-p-1$, and set $m=p+q$. Both constructions yield maximum-cardinality families of $2^{q+1}$ $(q+1)$-plateaued Boolean functions with pairwise disjoint Walsh supports. No member admits a nonzero linear structure, and every member has an explicit generalized Maiorana--McFarland representation. The first construction produces functions in $m+p+1$ variables and realizes any prescribed common algebraic degree $3\leq d\leq p+1$, provided that $q<\sum_{i=2}^{d-1}\binom{p}{i}$; its maximum attainable degree $p+1$ is optimal. The second construction produces functions in $n+p+1$ variables, where $n>m$ and $n-m$ is even, and realizes any prescribed common algebraic degree $3\leq d\leq p+(n-m)/2$, provided that $q<\sum_{i=2}^{\min\{d-1,p\}}\binom{p}{i}$; its maximum attainable degree $p+(n-m)/2$ is next-to-optimal.

0.34

The Walsh spectrum of the Dobbertin APN function

cs.IT math.CO ·2026-11-13 ·Lukas Kölsch
similarity 0.53
Abstract · 27 pages

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 $2$-groups constructed so far as well as binary linear codes of minimum distance $5$ that are almost optimal.

0.25

Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

cs.CC math.NT ·2026-11-01 ·Joseph M. Shunia
theory similarity 0.53
Abstract · 12 pages. An earlier version appeared as Revision 2 of ECCC TR23-200: https://eccc.weizmann.ac.il/report/2023/200/#revision2

We give a deterministic polynomial-time primality test whose main verification is the congruence $(1+X)^n=1+X^n$ in $C_n[X]/(X^r-b(Y))$, where $C_n=(\mathbb{Z}/n\mathbb{Z})[Y]/(Φ_r(Y))$. Two identities in the coefficient ring normalize $b$ and ensure compatibility with the main congruence. A finite-field root count and a lattice bound show that an accepted input is a prime power; elementary preprocessing excludes nontrivial perfect powers. We construct $b$ deterministically using Jacobi sums and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner, which extends OpenAI's Hecke zero-free theorem. The total bit complexity is $L^{32+o(1)}$, where $L=\lceil\log_2 n\rceil$, and verification after constructing $b$ costs $L^{6+o(1)}$. More generally, for a fixed real algebraic $1/2\leθ<1$, a common zero-free boundary $\Re s>θ$ for the relevant Dedekind zeta functions gives $L^{\max\{6,(1-θ)^{-1}\}+o(1)}$. This bound reaches $L^{6+o(1)}$ at $θ=5/6$, and hence under GRH. We state a fixed-base modification of Agrawal's conjecture for odd integers passing the base-$2$ Fermat test, using the modulus $X^r-2$ with $r$ the least positive integer not dividing $n(n-1)$.

0.44

Bounds on polynomial approximations of the discrete logarithm function

cs.CC cs.CR ·2026-10-24 ·Swastik Kopparty, Rishabh Kothary, Ashutosh Shankar
publishedtheory similarity 0.52
Abstract

We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, dlog(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.

0.41

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.52
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