Cryptology ePrint Archive: Report 2019/994

A new family of APN quadrinomials

Lilya Budaghyan and Tor Helleseth and Nikolay Kaleyski

Abstract: The binomial $B(x) = x^3 + \beta x^{36}$ (where $\beta$ is primitive in $\mathbb{F}_{2^4}$) over $\mathbb{F}_{2^{10}}$ is the first known example of an Almost Perfect Nonlinear (APN) function that is not CCZ-equivalent to a power function, and has remained unclassified into any infinite family of APN functions since its discovery in 2006. We generalize this binomial to an infinite family of APN quadrinomials of the form $x^3 + a (x^{2^i+1})^{2^k} + b x^{3 \cdot 2^m} + c (x^{2^{i+m}+2^m})^{2^k}$ from which $B(x)$ can be obtained by setting $a = \beta$, $b = c = 0$, $i = 3$, $k = 2$. We show that for any dimension $n = 2m$ with $m$ odd and $3 \nmid m$, setting $(a,b,c) = (\beta, \beta^2, 1)$ and $i = m-2$ or $i = (m-2)^{-1} \mod n$ yields an APN function, and verify that for $n = 10$ the quadrinomials obtained in this way for $i = m-2$ and $i = (m-2)^{-1} \mod n$ are CCZ-inequivalent to each other, to $B(x)$, and to any other known APN function over $\mathbb{F}_{2^{10}}$.

Category / Keywords: foundations / Boolean function, APN, differential uniformity

Date: received 2 Sep 2019, last revised 3 Sep 2019

Contact author: nikolay kaleyski at uib no

Available format(s): PDF | BibTeX Citation

Note: Minor update to Table 2 and one paragraph added on F13 before Corollary 1.

Version: 20190905:071817 (All versions of this report)

Short URL: ia.cr/2019/994


[ Cryptology ePrint archive ]