zbMATH — the first resource for mathematics

A theory of highly nonlinear functions. (English) Zbl 1125.94022
Fossorier, Marc (ed.) et al., Applied algebra, algebraic algorithms and error-correcting codes. 16th international symposium, AAECC-16, Las Vegas, NV, USA, February 20–24, 2006. Proceedings. Berlin: Springer (ISBN 3-540-31423-7/pbk). Lecture Notes in Computer Science 3857, 87-100 (2006).
Summary: Highly nonlinear functions are important as sources of low-correlation sequences, high-distance codes and cryptographic primitives, as well as for applications in combinatorics and finite geometry. We argue that the theory of such functions is best seen in terms of splitting factor pairs. This introduces an extra degree of freedom, through the pairing of a normalised function \(\phi : G \rightarrow N\) between groups with a homomorphism \(\rho : G \rightarrow \operatorname{Aut} (N)\).
From this perspective we introduce a new definition of equivalence for functions, relative to \(\rho\), and show it preserves their difference distributions. When \(\rho \equiv 1\) it includes CCZ and generalised linear equivalence, as well as planar and linear equivalence.
More generally, we use splitting factor pairs to relate several important measures of nonlinearity. We propose approaches to both linear approximation theory and bent functions, and to difference distribution theory and perfect nonlinear functions, which encompass the current approaches.
For the entire collection see [Zbl 1097.94001].

94A60 Cryptography
Full Text: DOI