Математика и математическое моделирование. 2021; : 13-26
Алгоритм поиска аффинных аннигиляторов булевой функции
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. 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 с.
Mathematics and Mathematical Modeling. 2021; : 13-26
Affine Annihilator Finding Algorithm for Boolean Function
https://doi.org/10.24108/mathm.0121.0000255Abstract
So far, there are no efficient algorithms to solve a problem of finding the low degree annihilators for arbitrary Boolean function. In the paper we present a new algorithm to find affine annihilators for an arbitrary Boolean function. We start with considering the identity fg ≡ 0 or the arbitrary Boolean function f and its possible affine annihilator g. We use a special representation of the Boolean function in sum of its sub-functions to reduce degrees of considering functions in previous identity. As a result, we establish equivalence between the identity fg ≡ 0 for Boolean functions of n variables and the system of Boolean equations of n-1 variable.
An algorithm for finding the affine annihilators for the arbitrary Boolean function f must find all the affine functions g so that fg ≡ 0. Our algorithm is based on reducing the problem of finding the affine annihilators for the Boolean function f of n to the similar problem for its sub-functions of n-1 variable. The presented algorithm has the following advantages:
- An input function can be presented in different ways;
- Output can be also presented in different ways;
- The algorithm can be effectively parallelized.
It should be noted that the result we have obtained is not final and highlights some development directions: first, to study the impact of its input and output on the efficiency of the algorithm of various representations and, second, to use our idea of constructing the algorithm for development of algorithms, which allow finding the 2nd, 3rd, etc. degree annihilators for a specified Boolean function.
References
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. Baev V.V. O nekotorykh algoritmakh postroeniya annigilyatorov nizkoi stepeni dlya Bulevykh funktsii // Diskretnaya matematika. 2006. T. 18. № 3. S. 138-151. DOI: 10.4213/dm66
5. Baev V.V. Usovershenstvovannyi algoritm poiska annigilyatorov nizkoi stepeni dlya mnogochlena Zhegalkina // Diskretnaya matematika. 2007. T. 19. № 4. S. 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. Rezhim dostupa: https://eprint.iacr.org/2004/185.pdf (data obrashcheniya 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. Rezhim dostupa: https://eprint.iacr.org/2007/117.pdf (data obrashcheniya 09.04.2021).
10. Logachev O.A., Sal'nikov A.A., Smyshlyaev S.V., Yashchenko V.V. Bulevy funktsii v teorii kodirovaniya i kriptologii: ucheb. posobie. M.: LENAND, 2015. 573 s.
