Preview

Математика и математическое моделирование

Расширенный поиск

Булевы функции, имеющие аффинные аннигиляторы

https://doi.org/10.24108/mathm.0620.0000246

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

Аннотация

Настоящая работа посвящена исследованию булевых функций, имеющих аффинные аннигиляторы. Были получены результаты в двух следующих направлениях: оценке количества исследуемых функций и связи коэффициентов Уолша-Адамара произвольной булевой функции с наличием у нее аффинного аннигилятора. Исследованию количества булевых функций с аффинными аннигиляторами посвящен второй раздел настоящей работы. Данная величина была ограничена сверху и снизу. Помимо этого была получена асимптотическая оценка числа булевых функций, имеющих аффинные аннигиляторы. В третьем разделе проводится исследование коэффициентов Уолша-Адамара булевых функций, имеющих аффинные аннигиляторы. Вначале раздела представлен результат, связывающий спектр произвольной булевой функции с ее расстоянием до пространства аннигиляторов произвольной аффинной функцией. Из этого результата была получена зависимость расстояния между произвольной булевой функцией и множеством функций с аффинными аннигиляторами от спектра данной булевой функции. Было получено необходимое и достаточное условие наличия у произвольной булевой функции аффинного аннигилятора. Благодаря полученным зависимостям удалось вывести ограничение на абсолютные значения коэффициентов Уолша-Адамара произвольной булевой функции.

Также был предложен метод анализа булевых уравнений, основанный на сочетании двух известных ранее методах. А именно, на методах анализа булевых уравнений с применением аннигиляторов и с применением линейных статаналогов. Была получена оценка вероятности успешности предложенного метода для анализа булева уравнения с произвольной булевой функцией. Было установлено, что бент-функции являются наиболее устойчивыми к данному методу анализа.

Полученные результаты могут быть использованы для анализа булевых уравнений. Зависимости, полученные в настоящей работе, могут быть использованы, например, для исследований бент-функций и свойства алгебраической иммунности булевой функций.

Об авторах

А. С. Зеленецкий
МГТУ им. Н.Э. Баумана, Москва
Россия

Зеленецкий  Алексей Сергеевич



П. Г. Ключарев
МГТУ им. Н.Э. Баумана, Москва
Россия

Ключарев Петр Георгиевич



Список литературы

1. Courtois N.T., Meier W. Algebraic attacks on stream ciphers with linear feedback // Advances in cryptology – EUROCRYPT 2003: Intern. conf. on the theory and applications of cryptographic techniques (Warszaw, Poland, May 4-8, 2003): Proc. B.: Springer, 2003. Pp. 345-359. DOI: 10.1007/3-540-39200-9_21

2. Meier W., Pasalic E., Carlet C. Algebraic attacks and decomposition of Boolean functions // Advances in cryptology – EUROCRYPT 2004: Intern. conf. on the theory and applications of cryptographic techniques (Interlaken, Switzerland, May 2-6, 2004): Proc. B.: Springer, 2004. Pp. 474-491. DOI: 10.1007/978-3-540-24676-3_28

3. Courtois N. Fast algebraic attacks on stream ciphers with linear feedback // Advances in cryptology – CRYPTO 2003: 23rd Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 17-21, 2003): Proc. B.: Springer, 2003. Pp. 176-194. DOI: 10-1007/978-3-540-45146-4_11

4. Баев В.В. О некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций // Дискретная математика. 2006. Т. 18. № 3. С. 138-151. DOI: 10.4213/dm66

5. Баев В.В. Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина // Дискретная математика. 2007. Т. 19. № 4. С. 132-138. DOI: 10.4213/dm982

6. Armknecht F. On the existence of low-degree equations for algebraic attacks // Cryptology ePrint Archive: Report 2004/185. Режим доступа: https://eprint.iacr.org/2004/185.pdf (дата обращения 09.04.2021).

7. Dalai D.K., Gupta K.C., Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions // Progress in cryptology - INDOCRYPT 2004: 5th intern. conf. on cryptology in India (Chennai, India, December 20-22, 2004): Proc. B.: Springer, 2005. Pp. 92-106. DOI: 10.1007/978-3-540-30556-9_9

8. Carlet C. On the higher order nonlinearities of algebraic immune functions // Advances in cryptology - CRYPTO 2006: 26th Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 20-24, 2006): Proc. B.: Springer, 2006. Pp. 584-601. DOI: 10.1007/11818175_35

9. Mesnager S. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity // Cryptology ePrint Archive: Report 2007/117. Режим доступа: https://eprint.iacr.org/2007/117.pdf (дата обращения 09.04.2021).

10. Логачев О.А., Сальников А.А., Смышляев С.В., Ященко В.В. Булевы функции в теории кодирования и криптологии: учеб. пособие. М.: ЛЕНАНД, 2015. 573 с.


Для цитирования:


Зеленецкий А.С., Ключарев П.Г. Булевы функции, имеющие аффинные аннигиляторы. Математика и математическое моделирование. 2020;(6):1-12. https://doi.org/10.24108/mathm.0620.0000246

For citation:


Zelenetsky A.S., Klyucharev P.G. Boolean Functions with Affine Annihilators. Mathematics and Mathematical Modeling. 2020;(6):1-12. (In Russ.) https://doi.org/10.24108/mathm.0620.0000246

Просмотров: 98


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)