×

A new characterization of almost bent functions. (English) Zbl 1004.94019

Knudsen, Lars (ed.), Fast software encryption. 6th international workshop, FSE ‘99. Rome, Italy, March 24-26, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1636, 186-200 (1999).
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. F. Chabaud and S. Vaudenay, Adv. Cryptology – EUROCRYPT ‘94, Lect. Notes Comput. Sci. 950, 356-365 (1995; Zbl 0879.94023), E. Biham and A. Shamir, J. Cryptology 4, 3-72 (1991; Zbl 0729.68017), and 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 C. Carlet, P. Charpin and 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 Chabaud and 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].

MSC:

94A60 Cryptography
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite