Paper 2016/286
On a remarkable property of APN Gold functions
Anastasiya Gorodilova
Abstract
In [13] for a given vectorial Boolean function $F$ from $\mathbb{F}_2^n$ to itself it was defined an associated Boolean function $\gamma_F(a,b)$ in $2n$ variables that takes value~$1$ iff $a\neq{\bf 0}$ and equation $F(x)+F(x+a)=b$ has solutions. In this paper we introduce the notion of differentially equivalent functions as vectorial functions that have equal associated Boolean functions. It is an interesting open problem to describe differential equivalence class of a given APN function. We consider the APN Gold function $F(x)=x^{2^k+1}$, where gcd$(k,n)=1$, and prove that there exist exactly $2^{2n+n/2}$ distinct affine functions $A$ such that $F$ and $F+A$ are differentially equivalent if $n=4t$ for some $t$ and $k = n/2 \pm 1$; otherwise the number of such affine functions is equal to $2^{2n}$. This theoretical result and computer calculations obtained show that APN Gold functions for $k=n/2\pm1$ and $n=4t$ are the only functions (except one function in 6 variables) among all known quadratic APN functions in $2,\ldots,8$ variables that have more than $2^{2n}$ trivial affine functions $A^F_{c,d}(x)=F(x)+F(x+c)+d$, where $c,d\in\mathbb{F}_2^n$, preserving the associated Boolean function when adding to $F$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Boolean functionAlmost perfect nonlinear functionAlmost bent functionCrooked functionDifferential equivalence
 Contact author(s)
 gorodilova @ math nsc ru
 History
 20160315: received
 Short URL
 https://ia.cr/2016/286
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/286, author = {Anastasiya Gorodilova}, title = {On a remarkable property of {APN} Gold functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/286}, year = {2016}, url = {https://eprint.iacr.org/2016/286} }