On properties of maximally nonlinear functions of odd number of variables

Oleg A. Logachev, Sergei N. Fedorov, Valeriy V. Yashchenko

Abstract


Boolean functions that are maximally nonlinear, that is, having maximal Hamming distance from the set of affine Boolean functions, are widely used, for  example, in the construction of ciphers, since they increase their security  against  certain cryptanalysis methods. By now, the class of maximally nonlinear Boolean functions of an odd number of variables is not sufficiently studied. There are still no meaningful necessary and sufficient conditions for a function to belong to this class. Studies of algebraic, spectral and combinatorial properties of such functions are far from any systematic generalizations. At the same time, in the case of an even number of variables, the situation is much more  favorable. Studies of the class of corresponding Boolean functions, called bent functions, are very effective. In particular, there is a spectral characterization of this class, the actual value of nonlinearity and methods for constructing such functions are known. The task of obtaining similar knowledge for an odd number of variables is undoubtedly important for possible applications of the Boolean function theory. This work aims, in a sense, to restore balance and partially fills this gap. It is devoted to the development of the mathematical apparatus needed for the study of this problem in geometric interpretation. In addition, new properties of spectral coefficients are obtained in it, a number of properties of bent functions are transferred to the case of an odd number of variables.

Full Text:

PDF (Russian)

References


Logachev O. A., Salnikov A. A., Yashchenko V. V. Boolean functions in coding theory and cryptography. Providence (Rhode Island, USA) : American Mathematical Society, 2011.

Rothaus O. S. On “bent” functions // Journal of Combinatorial Theory, Series A. 1976. Vol. 20, no. 3. P. 300–305.

Tokareva N. N. Bent functions : Results and applications to cryptography. Amsterdam : Academic Press, 2015.

Mykkeltveit J. J. The covering radius of the (128, 8) Reed—Muller code is 56 // IEEE Transactions on Information Theory. 1980. Vol. IT-26, no. 3. P. 359–362.

Brualdi R. A., Litsyn S., Pless V. Covering radius // Handbook of Coding Theory, Volume 1 / Ed. by V. Pless, W. C. Huffman. Amsterdam; New York : Elsevier Science, 1998. P. 755–826.

Logachev O. A., Fedorov S. N., Yashchenko V. V. Boolean functions as points on the hypersphere in the Euclidean space // Discrete Mathematics and Applications. 2019. Vol. 29, no. 2. P. 89–101.

Logachev O. A., Fedorov S. N., Yashchenko V. V. On some invariants under the action of an extension of GA(n, 2) on the set of Boolean functions // Discrete Mathematics and Applications. 2022. Vol. 32, no. 3. P. 177–192.

Logachev O. A., Fedorov S. N., Yashchenko V. V. Pseudo-Boolean functions valued on hypershere // International Journal of Open Information Technologies. 2022. Vol. 10, no. 4. P. 10–14. [in Russian].


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2022

ISSN: 2307-8162