Том 29, номер 4, 2022 г., Стр. 38-58
УДК 519.7
Доронин А. Е., Калгин К. В.
Применение SAT-решателей к задаче поиска векторных булевых функций с требуемыми криптографическими свойствами
Аннотация:
Представлен подход к решению задачи поиска почти совершенно нелинейной (APN) функции, основанный на её сведении к классической задаче выполнимости и использовании SAT-решателей. Описано построение формул, определяющих APN-функцию. Введены два представления функции: разреженное и плотное, в которых описана задача поиска взаимно однозначной векторной булевой функции и APN-функции. Также в работе представлен новый подход к решению задачи построения векторных булевых APN-функций, обладающих дополнительными свойствами. В основе подхода лежит идея представления неизвестной векторной булевой функции в виде суммы известной APN-функции и двух неизвестных булевых функций: $G = F \oplus c \cdot g_1 \oplus d \cdot g_2$, где $F$ — известная APN-функция. Показано, что для функций от $n = 6, 7$ переменных такой подход имеет большую эффективность в сравнении с прямым построением APN-функции при помощи SAT. Как итог, описанным в работе методом удалось показать отсутствие кубических APN-функций от 7 переменных, представимых в виде описанной выше суммы.
Табл. 3, библиогр. 21.
Ключевые слова: SAT-решатель, криптография, булева функция, APN-функция.
DOI: 10.33048/daio.2022.29.730
Доронин Артемий Евгеньевич 1
Калгин Константин Викторович 2,3
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
3. Институт вычислительной математики и математической геофизики,
пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия
е-mail: artem96dor@gmail.com, kalginkv@gmail.com
Статья поступила 30 декабря 2021 г.
После доработки — 11 апреля 2022 г.
Принята к публикации 15 апреля 2022 г.
Литература
[1] Nyberg K. Differentially uniform mappings for cryptography // Advances in Cryptology — EUROCRYPT’93. Proc. Workshop Theory Appl. Cryptogr. Techniques (Lofthus, Norway, May 23–27, 1993). Heidelberg: Springer, 1994. P. 55–64. (Lect. Notes Comput. Sci.; V. 765).
[2] Тужилин М. Э. Почти совершенные нелинейные функции // Прикл. дискрет. математика. 2009. № 3. С. 14–20.
[3] Brinkmann M., Leander G. On the classification of APN functions up to dimension five // Des. Codes Cryptogr. 2008. V. 49. P. 273–288.
[4] Carlet C. Open questions on nonlinearity and on APN functions // Arithmetic of Finite Fields. Rev. Sel. Pap. 5th Int. Workshop. (Gebze, Turkey, Sept. 27–28, 2014). Cham: Springer, 2015. P. 83–107. (Lect. Notes Comput. Sci.; V. 9061).
[5] Calderini M., Budaghyan L., Carlet C. On known constructions of APN and AB functions and their relation to each other. San Diego: Univ. California, 2020. (Cryptol. ePrint Archive; Pap. 2020/1444).
Available at eprint.iacr. org/2020/1444 (accessed July 21, 2022).
[6] Yu Y., Wan M., Li Y. A matrix approach for constructing quadratic APN functions // Des. Codes Cryptogr. 2014. V. 73. P. 587–600.
[7] Beierle C., Leander G. New instances of quadratic APN functions // IEEE Trans. Inf. Theory. 2022. V. 68. P. 670–678.
[8] Городилова A. A. Характеризация почти совершенно нелинейных функций через подфункции // Дискрет. математика. 2015. T. 27, № 3. С. 3–16.
[9] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 420 с.
[10] The international SAT competition web page. Paderborn: Satisfiability: Application and Theory, 2022. Available at www.satcompetition.org.
[11] Davis M., Logemann G., Loveland D. A machine program for theoremproving // Commun. ACM. 1962. V. 5, No. 7. P. 394–397.
[12] Marques Silva J. P., Sakallah K. A. GRASP — A new search algorithm for satisfiability // Proc. 1996 IEEE/ACM Int. Conf. Computer-Aided Design (San Jose, USA, Nov. 10–14, 1996). Washington: IEEE Comput. Soc., 1996. P. 220–227.
[13] Огородников Ю. Ю. Комбинированная атака на алгоритм RSA с использованием SAT-подхода // Динамика систем, механизмов и машин. 2016. Т. 2, № 1. С. 276–284.
[14] Schmittner S. E. A SAT-based public key cryptography scheme. Ithaca, NY: Cornell Univ., 2015. (Cornell Univ. Libr. e-Print Archive; arXiv:1507.08094).
[15] Rivest R. L., Adleman L., Dertouzos M. L. On data banks and privacy homomorphisms // Foundations of Secure Computation. New York: Academic Press, 1978. P. 169–179.
[16] Wille R., Lye A., Niemann P. Checking reversibility of Boolean functions // Reversible Computation. Proc. 8th Int. Conf. (Bologna, Italy, July 7–8, 2016). Cham: Springer, 2016. P. 322–337. (Lect. Notes Comput. Sci.; V. 9720).
[17] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. М.: МЦНМО, 2012. 112 с.
[18] Цейтин Г. С. О сложности вывода в исчислении высказываний // Исследования по конструктивной математике и математической логике. II. Зап. науч. сем. ЛОМИ. Т. 8. Л.: Наука, 1968. С. 234–259.
[19] Browning K. A., Dillon J. F., McQuistan M. T., Wolfe A. J. An APN permutation in dimension six // Finite Fields: Theory and Applications. Proc. 9th Int. Conf. (Dublin, Ireland, July 13–17, 2009). Providence, RI: AMS, 2010. P. 33–42. (Contemp. Math.; V. 518).
[20] Edel Y., Pott A. A new almost perfect nonlinear function which is not quadratic // Adv. Math. Commun. 2015. V. 3. P. 59–81.
[21] Kalgin K. V., Idrisova V. A. The classification of quadratic APN functions in 7 variables. San Diego: Univ. California, 2020. (Cryptol. ePrint Archive; Pap. 2020/1515).
Available at eprint.iacr.org/2020/1515 (accessed July 21, 2022).
