АЛГОРИТМ ГЕНЕРАЦИИ БЕНТ-ФУНКЦИЙ С ПОМОЩЬЮ ВЕЙВЛЕТ–ПРЕОБРАЗОВАНИЯ

Илья В. Шибакин, Алла Б. Левина

Аннотация


Объект данного исследования – бент-функции (максимально нелинейные булевы функции), а также булевы функции с высокой нелинейностью. Предметом статьи является возможность применения вейвлет преобразования для создания бент-функций. Настоящая работа рассматривает два существующих алгоритма генерации бент-функций, первый из которых использует модификацию таблицы истинности (ТИ) исходной функции, а второй – добавление подходящих слагаемых к алгебраической нормальной форме (АНФ) функции. Для обоих алгоритмов приведены теоретические положения, лежащие в их основе, описание принципа работы, а также их сильные и слабые стороны. Вейвлет-преобразование оказалось возможно применить для создания бент-функций. В работе представлен новый алгоритм генерации бент-функций, основанный на вейвлет-преобразовании и функции следа, выполнена его реализация на C++. Для алгоритма генерации бент-функций, основанного на вейвлет-преобразовании, проведена оценка временных затрат на создание бент-функций от аргументов различной длины, сравнение его с рассмотренными в статье известными алгоритмами (алгоритм, задействующий модификацию таблицы истинности; алгоритм, добавляющий слагаемые в АНФ). Алгоритм, изменяющий ТИ исходной функции, улучшает ее нелинейность, но результат его работы скорее всего не будет бент-функцией, а алгоритм, основанный на вейвлет-преобразовании и функции следа всегда генерирует бент-функции. Скорость генерации функций у алгоритма, добавляющего слагаемые в АНФ высока, но новый алгоритм, задействующий вейвлет-преобразование и функцию следа превосходит его в этом отношении. Генерируемые полученным алгоритмом функции, как и сам алгоритм, могут найти применение в теории кодирования, криптографии.

Ключевые слова


криптография, бент-функции, вейвлет-преобразование, функция следа, генерация бент-функций.

Полный текст:

PDF

Литература


1. Rothaus O. On bent functions. IDA CRD W.P. No.169.1966. DOI: https://doi.org/10.1016/0097-3165(76)90024-8.

2. Dillon J.F. A survey of bent functions. The NSA Technical J. 1972. Special Issue. P. 191–215. URL: https://cryptome.org/2015/11/nsa-survey-of-bent-functions.pdf (дата обращения: 12.05.2025).

3. McFarland R.L. A family of difference sets in non-cyclic groups. J. Combin. Theory. Ser. A. 1973, v. 15, no. 1, p. 1–10. DOI: https://doi.org/10.1016/0097-3165(73)90031-9.

4. Токарева Н.Н. Нелинейные булевы функции: бент-функции и их обобщения. Издательство LAP LAMBERT Academic Publishing (Saarbrucken, Germany), ISBN: 978-3-8433-0904-2. 2011. – 180 с.

5. Левина А.Б., Ряскин Г.А. Сплайн-вейвлетные надежные бент-коды. Научно-технический вестник информационных технологий, механики и оптики. 2021, т. 21, № 6, с. 936–941. DOI: https://doi.org/10.17586/2226-1494-2021-21-6-936-941.

6. Левина А.Б., Ряскин Г.А. Создание надежных кодов на основе бент-функций и вейвлет–преобразований. Научно-технический вестник информационных технологий, механики и оптики. 2018, т. 18, № 6, с. 1008–1015. DOI: https://doi.org/10.17586/2226-1494-2018-18-6-1008-1015.

7. Levina, A.; Ryaskin, G. Robust Code Constructions Based on Bent Functions and Spline Wavelet Decomposition. Mathematics 2022, 10, 3305. DOI: https://doi.org/10.20944/preprints202208.0348.v1.

8. Matsui M. Linear cryptanalysis method for DES cipher. Advances in Cryptology – EUROCRYPT’93. Workshop on the theory and application of cryptographic techniques (Lofthus, Norway. May 23–27, 1993). Proc. Berlin: Springer, 1994, p. 386–397 (Lecture Notes in Comput. Sci. V. 765). DOI: https://doi.org/10.1007/3-540-48285-7_33.

9. Молдовян А.А., Молдовян Н.А., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. СПб.: БХВ-Петербург, 2004. ISBN 5-94157-524-6. URL: https://books.4nmv.ru/books/kriptografiya_ot_primitivov_k_sintezu_algoritmov_3642674.pdf (дата обращения: 12.05.2025).

10. Carlet C., Ding C., Niederreiter H. Authentication schemes from highly nonlinear functions. Designs, Codes and Cryptography. 2006, v. 40, no. 1, p. 71–79. DOI: https://doi.org/10.1007/s10623-005-6407-0.

11. Millan W., Clark A., Dawson E. Smart hill climbing finds better Boolean functions. Workshop
on Selected Areas in Cryptology. 1997. Workshop record. P. 50–63. URL: https://www.researchgate.net/publication/2357166_Smart_Hill_Climbing_Finds_Better_Boolean_Functions (дата обращения: 12.05.2025).

12. Fuller J.E. Analysis of affine equivalent Boolean functions for cryptography. Ph. D. thesis, Queensland University of Technology. Brisbane, Australia. 2003. URL: https://scispace.com/papers/analysis-of-affine-equivalent-boolean-functions-for-5u4cm5dfp0 (дата обращения: 12.05.2025).

13. Grocholewska-Czury lo A. A study of differences between bent functions constructed using Rothaus method and randomly generated bent functions. J. Telecommunications
and Information Technology. 2003, no. 4, p. 19–24. URL: https://www.researchgate.net/publication/239550136_A_study_of_dierences_between_bent_functions_constructed_using_Rothaus_method_and_randomly_generated_bent_functions (дата обращения: 12.05.2025).

14. Демьянович Ю.К., Ходаковский В.А. Введение в теорию вэйвлетов:
учебное пособие. СПб.: Изд-во ПГУПС, 2008. – 50 p. URL: https://dl.libcats.org/genesis/366000/6382fd068c32a25b1a8312a510fa8ec9/_as/[Demyanovich_YU.K.,_Hodakovsky_V.A.]_Vvedenie_v_te(libcats.org).pdf (дата обращения: 12.05.2025).

15. Carlet C. Boolean Functions for Cryptography and Error Correcting Codes. Chapter of the monograph «Boolean Methods and Models», Cambridge Univ. Press (P. Hammer, Y. Crama eds.). URL: https://www.researchgate.net/publication/228720083_Boolean_Functions_for_Cryptography_and_Error_Correcting_Codes (дата обращения: 12.05.2025).




DOI: http://dx.doi.org/10.26583/bit.2025.4.08

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.