Preview

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

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

Алгоритм поиска аффинных аннигиляторов булевой функции

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

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

Аннотация

Задача нахождения аннигиляторов низкой степени для произвольной булевой функции до сих пор не имеет эффективных алгоритмов решения. Настоящая работа посвящена предложенному нами алгоритму поиска аффинных аннигиляторов для произвольной булевой функции. Построение нашего алгоритма мы начинаем с исследования тождества
fg ≡ 0 для произвольной булевой функции f и ее предполагаемого аффинного аннигилятора g . А именно, мы используем разложение по первой переменной функций f и g для перехода к уравнениям с булевыми функциям от меньшего числа переменных. По сути, мы устанавливаем эквивалентность между тождеством fg ≡ 0 для булевых функций от n переменных и системой уравнений, содержащей булевы функции от n-1 переменной.

Алгоритм поиска аффинных аннигиляторов булевой функции f находит все такие аффинные функции g , что fg ≡ 0. Предложенный нами алгоритм основан на сведении задачи нахождения базиса пространства аффинных аннигиляторов для булевой функции от  переменных к той же самой задаче для двух ее подфункций от n-1 переменной. У разработанного нами алгоритма можно выделить следующие преимущества:

  1. Алгоритм способен принимать входную функцию в различных представлениях;
  2. Выходные функции также могут иметь различные представления;
  3. Алгоритм может быть эффективно распараллелен.

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

Об авторах

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

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



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

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



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

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 с.


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


Зеленецкий А.С., Ключарев П.Г. Алгоритм поиска аффинных аннигиляторов булевой функции. Математика и математическое моделирование. 2021;(1):13-26. https://doi.org/10.24108/mathm.0121.0000255

For citation:


Zelenetsky A.S., Klyucharev P.G. Affine Annihilator Finding Algorithm for Boolean Function. Mathematics and Mathematical Modeling. 2021;(1):13-26. (In Russ.) https://doi.org/10.24108/mathm.0121.0000255

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


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


ISSN 2412-5911 (Online)