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)
PDF
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
2016-03-15: received
Short URL
https://ia.cr/2016/286
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/286}},
      url = {https://eprint.iacr.org/2016/286}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.