A new characterization of almost bent functions
A function \(f:{\mathbb F}^m_2\rightarrow{\mathbb F}^m_2\), when used as a round permutation of an iterated block cipher, opposes an optimal resistance to differential or linear attack respectively if \[ \begin{aligned} \delta_f&:=\max_{a\neq 0} \max_b(\# \{ x\in {\mathbb F}^m_2\mid f(x+a)+f(x)=b\}) \quad\text{or}\\ \lambda_f&:=\max_ a\max_b(|\#\{x\in {\mathbb F}^m_2\mid ax+b\cdot f(x)=0\}-2^{m-1}|) \end{aligned} \] (where \(\cdot\) is the usual dot product) are as small as possible [cf. \textit{F. Chabaud} and \textit{S. Vaudenay}, Adv. Cryptology -- EUROCRYPT `94, Lect. Notes Comput. Sci. 950, 356-365 (1995; Zbl 0879.94023), \textit{E. Biham} and \textit{A. Shamir}, J. Cryptology 4, 3-72 (1991; Zbl 0729.68017), and \textit{M. Matsui}, Adv. Cryptology -- EUROCRYPT `93, Lect. Notes Comput. Sci. 765, 386-397 (1994; Zbl 0951.94519)]. \(f\) is called almost perfect nonlinear (APN) if \(\delta_f\) is equal to the lower bound, i.e. \(\delta_f=2\), and \(f\) is called almost bent (AB) if \(\lambda_f\) achieves the lower bound \(\lambda_f=2^{\frac{m-1}{2}}\). Related to \(f\) is the linear binary code \(C_f\) with parity check matrix \[ H_f=\begin{pmatrix} 1&\alpha&\alpha^2&\ldots &\alpha^{2^m-2}\\ f(1)&f(\alpha)&f(\alpha^2)&\ldots& f(\alpha^{2^m-2})\end{pmatrix}. \] It was proved by \textit{C. Carlet, P. Charpin} and \textit{V. Zinoviev} [Des. Codes Cryptography 15, 125-156 (1998; Zbl 0938.94011)] that the nonlinearity of \(f\) corresponds to the minimal distance of the dual of \({\mathcal C}_f\), and it was established by \textit{Chabaud} and \textit{Vaudenay} [loc. cit.] that AB-functions are APN-functions, the converse of which is not true. In the reviewed paper, it is shown that, for an odd \(m\) and a function \(f:{\mathbb F}^m_2\rightarrow {\mathbb F}^m_2\) with \(\lambda_f\neq 2^{m-1}\) the following holds: \(f\) is AB iff 1.) \(f\) is APN and 2.) \({\mathcal C}^{\bot}_f\) is \(2^{\frac{m-1}{2}}\) divisible; (here a binary code is called \(2^{\ell}\) divisible if the weight of any of its codewords is divisible by \(2^{\ell}\)). This enables the authors to exhibit some infinite families of power functions \(f:x\rightarrow x^s\) which are not almost bent. For the entire collection see [Zbl 0917.00016].
- Codes, bent functions and permutations suitable for DES-like cryptosystems
- Topics in Cryptology – CT-RSA 2006
- scientific article; zbMATH DE number 5831605
- On an algorithm generating 2-to-1 APN functions and its applications to ``The big APN problem
- On almost perfect nonlinear permutations
- Codes, graphs, and schemes from nonlinear functions
- Binary quasi-perfect linear codes from APN quadratic functions
- APN polynomials and related codes
- On the dimension of an APN code
- On Almost Perfect Nonlinear Functions Overmmb F₂ⁿ
- Codes, bent functions and permutations suitable for DES-like cryptosystems
- Algebraic construction of near-bent and APN functions
- A new class of \(p\)-ary regular bent functions
- Quadratic almost bent functions -- their partial characterization and design in the spectral domain
- Class of quadratic almost bent functions that is EA-inequivalent to permutations
- scientific article; zbMATH DE number 841853 (Why is no real title available?)
- Algebraic construction of near-bent function with application to cryptography
- scientific article; zbMATH DE number 7301759 (Why is no real title available?)
- Bent and near-bent function construction and 2-error-correcting codes
This page was built for publication: A new characterization of almost bent functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4941812)
