About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 3, 2021, P. 49-64
UDC 519.8+518.25
I. A. Sutormin
On nonlinearity of Boolean functions generated by the generalized Dobbertin construction
Abstract:
We propose a generalization of Dobbertin’s 1995 construction for balanced highly nonlinear Boolean functions. TheWalsh–Hadamard spectrum of the proposed functions is studied. An exact upper bound for the spectral radius (lower bound for nonlinearity) is achieved. We also introduce a method for constructing a balanced function of $2n$ variables and spectral radius $2^n + 2^kR$ using a balanced function of $n - k$ variables and spectral radius $R$.
Bibliogr. 20.
Keywords: boolean function, bent function, nonlinearity, balancedness, spectral radius.
DOI: 10.33048/daio.2021.28.705
Ivan A. Sutormin 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: ivan.sutormin@gmail.com
Received December 1, 2020
Revised March 12, 2021
Accepted March 15, 2021
References
[1] M. Matsui, Linear cryptanalysis method for DES cipher, in Advances in Cryptology — EUROCRYPT’93 (Proc. Workshop Theory Appl. Cryptogr. Techniques, Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 386–397 (Lect. Notes Comput. Sci., Vol. 765).[2] O. Rothaus, On «bent» functions, J. Comb. Theory, Ser. A, 20 (3), 300–305 (1976).
[3] N. N. Tokareva, Bent Functions: Results and Applications to Cryptography (Acad. Press, Amsterdam, 2015).
[4] S. Mesnager, Binary Bent Functions: Fundamentals and Results (Springer, Heidelberg, 2016).
[5] C. Carlet, Boolean functions for cryptography and error-correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Camb. Univ. Press, New York, 2010),
[6] T. Cusick and P. Stanica, Cryptographic Boolean Functions and Applications (Acad. Press, Amsterdam, 2009).
[7] O. A. Logachyov, A. A. Sal’nikov, S. V. Smyshlyaev, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology (MTsNMO, Moscow, 2012) [Russian].
[8] K. Schmidt, Asymptotically optimal Boolean functions, J. Comb. Theory, Ser. A, 164, 50–59 (2019).
[9] J. Seberry, X. Zhang, and Y. Zheng, Nonlinearly balanced Boolean functions and their propagation characteristics, in Advances in Cryptology — Crypto’93 (Proc. 13th Annu. Int. Cryptology Conf., Santa Barbara, CA, USA, Aug. 22–26, 1993) (Springer, Heidelberg, 1994), pp. 49–60 (Lect. Notes Comput.
Sci., Vol. 773).
[10] C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebraic immunities, in Applied Algebra, Algebraic Algorithms and Error- Correcting Codes (Proc. 16th Int. Symp., Las Vegas, NV, USA, Feb. 20–24, 2006) (Springer, Heidelberg, 2006), pp. 1–28 (Lect. Notes Comput. Sci., Vol. 3857).
[11] Q. Wang and C. H. Tan, Properties of a family of cryptographic Boolean functions, in Sequences and Their Applications — SETA 2014 (Proc. 8th Int. Conf., Melbourne, Australia, Nov. 24–28, 2014) (Springer, Cham, 2014), pp. 34–46 (Lect. Notes Comput. Sci., Vol. 8865).
[12] D. Tang and S. Maitra, Construction of $n$-variable ($n \equiv 2$ mod 4) balanced Boolean functions with maximum absolute value in autocorrelation spectra $< 2^{\frac{n}{2}}$, IEEE Trans. Inf. Theory 64 (1), 393–402 (2018).
[13] S. Kavut, S. Maitra, and D. Tang, Construction and search of balanced Boolean functions on even number of variables towards excellent autocorrelation profile, Des. Codes Cryptogr. 87 (3), 261–276 (2019).
[14] N. J. Patterson andD. H. Wiedemann, The covering radius of the (215, 16) Reed–Muller code is at least 16276, IEEE Trans. Inf. Theory 29 (3), 354–356 (1983).
[15] H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in Fast Software Encryption (Proc. 2nd Int. Workshop, Leuven, Belgium, Dec. 14–16, 1994) (Springer, Heidelberg, 1995), pp. 61–74 (Lect. Notes Comput. Sci., Vol. 1008).
[16] D. Fomin, New classes of 8-bit permutations based on a butterfly structure, Math. Asp. Cryptogr. 10 (2), 169–180 (2019).
[17] N. Kolomeec, The graph of minimal distances of bent functions and its properties, Des. Codes Cryptogr. 85 (3), 395–410 (2017).
[18] N. Kolomeec, On properties of a bent function secondary construction, Abs. 5th Int. Workshop Boolean Functions and Their Applications, Loen, Norway, Sept. 15–17, 2020, pp. 23–26. Available at http://boolean.w.uib.no/files/2020/09/BFA_2020_abstracts_numbered.pdf (accessed Apr. 28, 2021).
[19] C. Carlet, Two new classes of bent functions, in Advances in Cryptology — EUROCRYPT’93 (Proc. Workshop Theory Appl. Cryptogr. Techniques, Lofthus, Norway,May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 77–101 (Lect. Notes Comput. Sci., Vol. 765).
[20] V. V. Yashchenko, On the propagation criterion for Boolean functions and on bent functions, Probl. Peredachi Inf. 33 (1), 62–71 (1997) [Russian] [Probl. Inf. Transm. 33 (1), 75–86 (1997)].
