Proof confirms two function families are secure against specific attacks
The APN Property of Two Families of functions over $\F_{2^{n}}$ from the Switching Construction
Information Theory
Summary
This paper proves a long-standing guess that two special mathematical functions behave very well for cryptography, meaning they resist certain attacks. The authors show these functions have a property called APN, key for protecting data against differential attacks. They do this by translating the problem into a simpler form using matrices and then proving certain equations have no solutions, which guarantees this strong resistance. This confirmation applies to a broad class of inputs, ensuring the functions’ security in many cases.
What this means in practice
- •For cryptographic engineers: Use proven APN function families to design block ciphers with high resistance to differential cryptanalysis.
- •For hardware security teams: Implement these APN functions in hardware to strengthen security modules against side-channel and fault attacks relying on weak functions.
A theory result. No direct application yet.
Authors
Chenmiao Shi, Longjiang Qu, Kangquan Li
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$.