Математика и математическое моделирование. 2020; : 1-12
Булевы функции, имеющие аффинные аннигиляторы
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 с.
Mathematics and Mathematical Modeling. 2020; : 1-12
Boolean Functions with Affine Annihilators
https://doi.org/10.24108/mathm.0620.0000246Abstract
In the article we study boolean functions with affine annihilators. We have obtained results in both, estimating the number of functions under study and defining the relationship between Walsh-Hadamard coefficients of an arbitrary boolean function and its affine annihilator available. The second section of this article focuses on estimating the number of boolean functions with affine annihilators. The value has top and bottom bound. Besides, we have obtained the asymptotic estimate of the number of boolean functions with affine annihilators. The third section studies the Walsh-Hadamard coefficients of boolean functions with affine annihilators. First, we have derived the dependence of the Walsh-Hadamard coefficient on the distance between an arbitrary boolean function and a vector space of the affine function’s annihilators. Based on this result, we have obtained the dependence of distance between an arbitrary boolean function and a set of functions with affine annihilators on the spectrum of given function. Also we have defined the necessary and sufficient condition for the arbitrary boolean function to be with an affine annihilator available. Using the results obtained we bounded an absolute value of Walsh-Hadamard coefficients.
Also we suggested a method for boolean equations analysis, which is based on two known methods. Namely, we used an analysis using annihilators and an analysis using linear analogs. We have obtained an estimate of the success probability of the suggested method for an arbitrary boolean function. Also we proved that bent functions are the most resistant to this analysis.
The results obtained can be used in analysis of boolean equations. Also obtained dependences can be used, for instance, to study bent functions and algebraic immunity of boolean functions.
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.
