On the equivalence of quadratic APN functions

DOI10.1007/S10623-010-9475-8MaRDI QIDQ648066zbMATH OpenOpenAlexFDO

Authors Carl Bracken, Eimear Byrne, Gary McGuire, Gabriele Nebe

Publication date 22 November 2011

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.1508

almost perfect nonlinear APN automorphism group CCZ-equivalence EA-equivalence Gold function

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Finite fields (field-theoretic aspects) (12E20) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: Establishing the CCZ-equivalence of a pair of APN functions is generally quite difficult. In some cases, when seeking to show that a putative new infinite family of APN functions is CCZ inequivalent to an already known family, we rely on computer calculation for small values of n. In this paper we present a method to prove the inequivalence of quadratic APN functions with the Gold functions. Our main result is that a quadratic function is CCZ-equivalent to an APN Gold function if and only if it is EA-equivalent to that Gold function. As an application of this result, we prove that a trinomial family of APN functions that exist on finite fields of order 2^n where n = 2 mod 4 are CCZ inequivalent to the Gold functions. The proof relies on some knowledge of the automorphism group of a code associated with such a function.

Review text

Let \(L\) be a finite field. A function \(f: L \rightarrow L\) is called \textit{almost perfect nonlinear} (APN) if the equation \(f(x+a)-f(x)=b\) has at most 2 solutions in \(L\), for all \(a,b \in L\), \(a \neq 0\). Two functions \(f,g : L \rightarrow L\) are called \(EA\)-equivalent if there exist affine permutations \(A_1\), \(A_2\) and an affine map \(A\) such that \(g= A_1 \circ f \circ A_2+A\). Furthermore, \(f\), \(g\) are said to be CCZ-equivalent if the graph of one can be obtained from the graph of the other by an affine permutation of the product space. In this paper it is proved that a quadratic function is CCZ-equivalent to the APN Gold function \(x^{2^r+1}\) if and only if it is \(EA\)-equivalent to that Gold function. The proof relies on the study of the automorphism group of a code determines by a quadratic function. Let \(k\) and \(s\) be coprime integers, \(b,c\in \mathbb{F}_{2^{2k}}\), \(c\not \in \mathbb{F}_{2^{k}}\), and \(b\) is a primitive element of \(\mathbb{F}_{2^{2k}}\). Then the polynomials of the form \[ f_s(x) = bx^{2^s+1}+(bx^{2^s+1})^{2^k}+cx^{2^k+1} \] are APN functions. As an application of the main result of the paper it is proved that the above functions are CCZ inequivalent to any Gold function.

Recommendations

Cites work

Cited in

(29)

This page was built for publication: On the equivalence of quadratic APN functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648066)