Search

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is still unknown. Those of Kasami, Niho and Welch functions are known, but not the precise values of their Walsh transform, with rare exceptions. One promising approach that could lead to the resolution of these problems is to consider alternative representations of the functions in questions. We derive alternative representations for the infinite APN monomial families. We show how the Niho, Welch, and Dobbertin functions can be represented as the composition $x^{i} \circ x^{1/j}$ of two power functions, and prove that our representations are optimal, i.e. no two power functions of lesser algebraic degree can be used to represent the functions in this way. We investigate compositions $x^{i} \circ L \circ x^{1/j}$ for a linear polynomial $L$ , show how the Kasami functions in odd dimension can be expressed in this way with $i=j$ being a Gold exponent and compute all APN functions of this form for $n \le 9$ and for $L$ with binary coefficients, thereby showing that our theoretical constructions exhaust all possible cases. We present observations and data on power functions with exponent $\sum _{i = 1}^{k-1} 2^{2ni} - 1$ which generalize the inverse and Dobbertin families. We present data on the Walsh spectrum of the Dobbertin function for $n \le 35$ , and conjecture its exact form. As an application of our results, we determine the exact values of the Walsh transform of the Kasami function at all points of a special form. Computations performed for $n\leq 21$ show that these points cover about 2/3 of the field. [ABSTRACT FROM AUTHOR]

The binomial $B(x) = x^{3} + \beta x^{36}$ (where $\beta $ is primitive in $\mathbb {F}_{2^{2}}$) 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}}$. [ABSTRACT FROM AUTHOR]

We investigate the differential properties of a vectorial Boolean function $G$ obtained by modifying an APN function $F$. This generalizes previous constructions where a function is modified at a few points. We characterize the APN-ness of $G$ via the derivatives of $F$ , and deduce an algorithm for searching for APN functions whose values differ from those of $F$ only on a given set $U \subseteq \mathbb {F}_{2^{n}}$. We introduce a value $\Pi _{F}$ associated with any $F$ , which is invariant under CCZ-equivalence. We express a lower bound on the distance between a given APN function $F$ and the closest APN function in terms of $\Pi _{F}$. We show how $\Pi _{F}$ can be computed efficiently for $F$ quadratic. We compute $\Pi _{F}$ for all known APN functions over $\mathbb {F}_{2^{n}}$ up to $n \le 8$. This is the first new CCZ-invariant for APN functions to be introduced within the last ten years. We derive a mathematical formula for this lower bound for the Gold function $F(x) = x^{3}$ , and observe that it tends to infinity with $n$. Finally, we describe how to efficiently find all sets $U$ such that, taking $G(x) = F(x) + v$ for $x \in U$ and $G(x) = F(x)$ for $x \notin U$ , $G(x)$ is APN. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over ${\mathbb F}_{2^{9}}$ and includes an example of another APN function $x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$ over ${\mathbb F}_{2^{8}}$ , known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions. [ABSTRACT FROM AUTHOR]

We study the problem of existence of APN functions of algebraic degree n over {\mathbb F}_{2^{n}} . We characterize such functions by means of derivatives and power moments of the Walsh transform. We deduce several non-existence results which imply, in particular, that for most of the known APN functions F over \mathbb F2^{n} the function x^{2^{n}-1}+F(x) is not APN, and changing a value of $F$ in a single point then results in non-APN functions. This leads us to conjectures that an APN function modified in one point cannot remain APN and that there exists no APN function of algebraic degree $n$ . [ABSTRACT FROM AUTHOR]

In this paper, we discover that univariate form of a Niho bent function is a sum of functions having the form of a Leander–Kholosha bent function taken with particular coefficients from \mathbb F2^{n}^{*} for every term. We know that the Niho bent functions are related to o-polynomials. The power terms in the univariate Niho bent function can be derived by working, in a first step, on each monomial of the corresponding o-polynomial separately, and in a second step, adding them to obtain the global expression. This allows, knowing the monomials in an o-polynomial, to obtain the power terms of the polynomial representing corresponding bent function. However, the coefficients are not calculated explicitly. The explicit form is given for the bent functions obtained from quadratic and cubic o-polynomials. We also calculate the algebraic degree of any bent function in the Leander–Kholosha class. [ABSTRACT FROM AUTHOR]

This paper consists of two main contributions. First, the Niho bent function consisting of 2^r exponents (discovered by Leander and Kholosha) is studied. The dual of the function is found and it is shown that this new bent function is not of the Niho type. Second, all known univariate representations of Niho bent functions are analyzed for their relation to the completed Maiorana–McFarland class \cal M. In particular, it is proven that two families do not belong to the completed class \cal M. The latter result gives a positive answer to an open problem whether the class H of bent functions introduced by Dillon in his thesis of 1974 differs from the completed class \cal M. [ABSTRACT FROM PUBLISHER]

A function F from Fpn to itself is planar if for any $a\, \in \,F_{{p^n}}^*$ the function F(x+a)-F(x) is a permutation. CCZ-equivalence is the most general known equivalence relation of functions preserving planar property. This paper considers two possible extensions of CCZ-equivalence for functions over fields of odd characteristics, one proposed by Coulter and Henderson and the other by Budaghyan and Carlet. We show that the second one in fact coincides with CCZ-equivalence, while using the first one we generalize one of the known families of PN functions. In particular, we prove that, for any odd prime p and any positive integers n and m, the indicators of the graphs of functions F and F' from Fpn to Fpm are CCZ-equivalent if and only if F and F′ are CCZ-equivalent. We also prove that, for any odd prime p, CCZ-equivalence of functions from Fpn to Fpm, is strictly more general than EA-equivalence when n ≥ 3 and m is greater or equal to the smallest positive divisor of n different from 1. [ABSTRACT FROM AUTHOR]

Abstract: We present a method for constructing new quadratic APN functions from known ones. Applying this method to the Gold power functions we construct an APN function over . It is proven that for this function is CCZ-inequivalent to the Gold functions, and in the case it is CCZ-inequivalent to any power mapping (and, therefore, to any APN function belonging to one of the families of APN functions known so far). [Copyright &y& Elsevier]

Abstract: We present results related to vectorial plateaued functions and mappings whose derivatives are -to-1 functions. The results in this note generalize facts about almost perfect nonlinear and almost bent functions. We investigate the connection between plateaued and -to-1 functions. We show that functions which are both plateaued and differentially uniform give rise to partial difference sets. [Copyright &y& Elsevier]

This paper introduces the first found infinite classes of almost perfect nonlinear (APN) polynomials which are not Carlet—Charpin—Zinoviev (CCZ)-equivalent to power functions (at least for some values of the number of variables). These are two classes of APN binomials from F2n to F2n (for n divisible by 3, resp., 4). We prove that these functions are extended affine (EA)-inequivalent to any power function and that they are CCZ-inequivalent to the Gold, Kasami, inverse, and Dobbertin functions when n ≥ 12. This means that for n even they are CCZ-inequivalent to any known APN function. In particular, for n = 12, 20, 24, they are therefore CCZ-inequivalent to any power function. [ABSTRACT FROM AUTHOR]

A method for constructing differentially 4-uniform quadratic hexanomials has been recently introduced by J. Dillon. We give various generalizations of this method and we deduce the constructions of new infinite classes of almost perfect nonlinear quadratic trinomials and hexanomials from F22m to F22m. We check for m = 3 that some of these functions are CCZ-inequivalent to power functions. [ABSTRACT FROM AUTHOR]

New infinite classes of almost bent and almost perfect nonlinear polynomials are constructed. It is shown that they are affine inequivalent to any sum of a power function and an affine function. [ABSTRACT FROM AUTHOR]

Boolean functions, and bent functions in particular, are considered up to so-called EA-equivalence, which is the most general known equivalence relation preserving bentness of functions. However, for a special type of bent functions, so-called Niho bent functions there is a more general equivalence relation called o-equivalence which is induced from the equivalence of o-polynomials. In the present work we study, for a given o-polynomial, a general construction which provides all possible o-equivalent Niho bent functions, and we considerably simplify it to a form which excludes EA-equivalent cases. That is, we identify all cases which can potentially lead to pairwise EA-inequivalent Niho bent functions derived from o-equivalence of any given Niho bent function. Furthermore, we determine all pairwise EA-inequivalent Niho bent functions arising from all known o-polynomials via o-equivalence. [ABSTRACT FROM AUTHOR]

This paper is dedicated to a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those CCZ-inequivalent to each other. In particular, we prove that the families of APN trinomials (constructed by Budaghyan and Carlet in 2008) and multinomials (constructed by Bracken et al. 2008) are contained in the APN hexanomial family introduced by Budaghyan and Carlet in 2008. We also prove that a generalization of these trinomial and multinomial families given by Duan et al. (2014) is contained in the family of hexanomials as well. [ABSTRACT FROM AUTHOR]

Cryptographically strong functions used as S-boxes in block cyphers are fundamental for the cypher's security. Their representation as lookup tables is possible for functions of small dimension. For larger dimensions, this is infeasible, especially if resources are limited. An alternative is representing the function as a polynomial over a finite field, and constructing a circuit evaluating this polynomial. We study how the choice of primitive polynomial affects the efficiency of hardware implementations. We take Dillon's permutation on 6 bits (the only known permutation in even dimension from the cryptographically optimal Almost Perfect Nonlinear functions) as a relevant example, and present hardware architectures, polynomial representations and hardware theoretical complexities for all primitive polynomials of degree six. To compare the efficiency, we report on results obtained from FPGA (Field Programmable Gate Array) implementations. To the best of our knowledge, no similar study has been given in the literature. We observe that using the primitive trinomial y 6 + y + 1 reduces the number of 2-input XOR gates up to 11.7% and the number of XOR gates × Delay metrics up to 13.2% with respect to the worst-case implementation. Therefore, the choice of primitive polynomial can profoundly impact the efficiency of such an implementation, and should be carefully considered. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) and almost bent (AB) functions are integral components of modern block ciphers and play a fundamental role in symmetric cryptography. In this paper, we describe a procedure for searching for quadratic APN functions with coefficients in F 2 over the finite field F 2 n and apply this procedure to classify all such functions over F 2 n with n ≤ 9. We discover two new APN functions (which are also AB) over F 2 9 that are CCZ-inequivalent to any known APN function over this field. We also verify that there are no quadratic APN functions with coefficients in F 2 over F 2 n with 6 ≤ n ≤ 8 other than the currently known ones. [ABSTRACT FROM AUTHOR]