Том 28, номер 3, 2021 г., Стр. 49-64

УДК 519.8+518.25
Сутормин И. А.
О нелинейности булевых функций, построенных обобщенной конструкцией Доббертина

Аннотация:
Предложено обобщение конструкции, описанной Доббертином в 1995 г., для сбалансированных булевых функций, обладающих высокой нелинейностью. Исследован спектр Уолша — Адамара предложенных функций. Доказана точная верхняя оценка на спектральный радиус (нижняя оценка нелинейности), и показан способ построения сбалансированной функции от $2n$ переменных со спектральным радиусом, равным $2^n + 2^{k} R$, при помощи сбалансированной функции от $n - k$ переменных со спектральным радиусом, равным $R$.
Библиогр. 20.

Ключевые слова: булева функция, бент-функция, нелинейность, сбалансированность, спектральный радиус.

DOI: 10.33048/daio.2021.28.705

Сутормин Иван Александрович ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: ivan.sutormin@gmail.com

Статья поступила 1 декабря 2020 г.
После доработки — 12 марта 2021 г.
Принята к публикации 15 марта 2021 г.

Литература

[1] Matsui M. Linear cryptanalysis method for DES cipher // Advances in Cryptology — EUROCRYPT’93. Proc. Workshop Theory Appl. Cryptogr. Techniques (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. P. 386–397. (Lect. Notes Comput. Sci.; Vol. 765).

[2] Rothaus O. On «bent» functions // J. Comb. Theory, Ser. A. 1976. Vol. 20, No. 3. P. 300–305.

[3] Tokareva N. N. Bent functions: Results and applications to cryptography. Amsterdam: Acad. Press, 2015. 220 p.

[4] Mesnager S. Binary bent functions: Fundamentals and results. Heidelberg: Springer, 2016. 540 p.

[5] Carlet C. Boolean functions for cryptography and error-correcting codes // Boolean Models and Methods in Mathematics, Computer Science, and Engineering. New York: Camb. Univ. Press, 2010. P. 257–397.

[6] Cusick T., Stanica P. Cryptographic Boolean functions and applications. Amsterdam: Acad. Press, 2009. 248 p.

[7] Логачёв О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012. 584 с.

[8] Schmidt K. Asymptotically optimal Boolean functions // J. Comb. Theory, Ser. A. 2019. Vol. 164. P. 50–59.

[9] Seberry J., Zhang X., Zheng Y. Nonlinearly balanced Boolean functions and their propagation characteristics // Advances in Cryptology — Crypto’93. Proc. 13th Annu. Int. Cryptology Conf. (Santa Barbara, CA, USA, Aug. 22–26, 1993). Heidelberg: Springer, 1994. P. 49–60. (Lect. Notes Comput. Sci.; Vol. 773).

[10] Carlet C. On bent and highly nonlinear balanced/resilient functions and their algebraic immunities // Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Proc. 16th Int. Symp. (Las Vegas, NV, USA, Feb. 20–24, 2006). Heidelberg: Springer, 2006. P. 1–28. (Lect. Notes Comput. Sci.; Vol. 3857).

[11] Wang Q., Tan C. H. Properties of a family of cryptographic Boolean functions // Sequences and Their Applications — SETA 2014. Proc. 8th Int. Conf. (Melbourne, Australia, Nov. 24–28, 2014). Cham: Springer, 2014. P. 34–46. (Lect. Notes Comput. Sci.; Vol. 8865).

[12] Tang D., Maitra S. 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. 2018. Vol. 64, No. 1. P. 393–402.

[13] Kavut S., Maitra S., Tang D. Construction and search of balanced Boolean functions on even number of variables towards excellent autocorrelation pro- file // Des. Codes Cryptogr. 2019. Vol. 87. No. 3. P. 261–276.

[14] Patterson N. J., Wiedemann D. H. The covering radius of the (215, 16) Reed–Muller code is at least 16276 // IEEE Trans. Inf. Theory. 1983. Vol. 29, No. 3. P 354–356.

[15] Dobbertin H. Construction of bent functions and balanced Boolean functions with high nonlinearity // Fast Software Encryption. Proc. 2nd Int. Workshop (Leuven, Belgium, Dec. 14–16, 1994). Heidelberg: Springer, 1995. P. 61–74. (Lect. Notes Comput. Sci.; Vol. 1008).

[16] Fomin D. New classes of 8-bit permutations based on a butterfly structure // Math. Asp. Cryptogr. 2019. Vol. 10, No. 2. P. 169–180.

[17] Kolomeec N. The graph of minimal distances of bent functions and its properties // Des. Codes Cryptogr. 2017. Vol. 85, No. 3. P. 395–410.

[18] Kolomeec N. On properties of a bent function secondary construction // Abs. 5th Int. Workshop Boolean Functions and Their Applications (Loen, Norway, Sept. 15–17, 2020). P. 23–26. Available at https://boolean.w.uib.no/files/2020/09/BFA_2020_abstracts_numbered.pdf (accessed Apr. 28, 2021).

[19] Carlet C. Two new classes of bent functions // Advances in Cryptology — EU?ROCRYPT’93. Proc. Workshop Theory Appl. Cryptogr. Techniques (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. P. 77–101. (Lect. Notes Comput. Sci.; Vol. 765).

[20] Ященко В. В. О критерии распространения для булевых функций и о бент-функциях // Пробл. передачи информации. 1997. Т. 33, вып. 1. С. 75–86.