Применение SAT-решателей к задаче поиска векторных булевых функций с требуемыми криптографическими свойствами

Применение SAT-решателей к задаче поиска векторных булевых функций с требуемыми криптографическими свойствами

Доронин А. Е., Калгин К. В.
Дискретный анализ и исследование операций, 29, 4, 38-58 (2022)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2022.29.730

Аннотация:

Представлен подход к решению задачи поиска почти совершенно нелинейной (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.

Литература:
  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 theorem-proving // 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).

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0018).

Доронин Артемий Евгеньевич
  1. Новосибирский гос. университет,
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: artem96dor@gmail.com

Калгин Константин Викторович
  1. Институт математики им. С. Л. Соболева,
    пр. Коптюга, 4, 630090 Новосибирск, Россия
  2. Институт вычислительной математики и математической геофизики,
    пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия

E-mail: kalginkv@gmail.com

Статья поступила 30 декабря 2021 г. 
После доработки — 11 апреля 2022 г. 
Принята к публикации 15 апреля 2022 г.

Abstract:

We propose a method for finding an almost perfect nonlinear (APN) function. It is based on translation into SAT-problem and using SAT-solvers. We construct several formulas defining the conditions for finding an APN-function and introduce two representations of the function: Sparse and dense, which are used to describe the problem of finding one-to-one vectorial Boolean functions and APN-functions. We also propose a new method for finding a vectorial APN-function with additional properties. It is based on the idea of representing an unknown vectorial Boolean function as a sum of known APN-functions and two unknown Boolean functions: $G = F \oplus c \cdot g_1 \oplus d \cdot g_2$, where $F$ is a known APN-function. It is shown that this method is more efficient than the direct construction of APN-function using SAT for dimensions 6 and 7. As a result, the method described in the work can prove the absence of cubic APN-functions in dimension 7 representable in the form of the sum described above. 
Tab. 3, bibliogr. 21.

References:
  1. K. Nyberg, Differentially uniform mappings for cryptography, in Advances in Cryptology — EUROCRYPT’93 (Proc. Workshop Theory Appl. Cryptogr. Techniques, Lofthus, Norway, May 23–27, 1993) (Springer, Heidelberg, 1994), pp. 55–64 (Lect. Notes Comput. Sci., Vol. 765).
     
  2. M. É. Tuzhilin, APN functions, Prikl. Diskretn. Mat., No. 3, 14–20 (2009) [Russian].
     
  3. M. Brinkmann and G. Leander, On the classification of APN functions up to dimension five, Des. Codes Cryptogr. 49, 273–288 (2008).
     
  4. C. Carlet, Open questions on nonlinearity and on APN functions, in Arithmetic of Finite Fields (Rev. Sel. Pap. 5th Int. Workshop., Gebze, Turkey, Sept. 27–28, 2014) (Springer, Cham, 2015), pp. 83–107 (Lect. Notes Comput. Sci., Vol. 9061).
     
  5. M. Calderini, L. Budaghyan, and C. Carlet, On known constructions of APN and AB functions and their relation to each other (Univ. California, San Diego, 2020) (Cryptol. ePrint Archive, Pap. 2020/1444). Available at eprint.iacr.org/2020/1444 (accessed July 21, 2022).
     
  6. Y. Yu, M. Wan, and Y. Li, A matrix approach for constructing quadratic APN functions, Des. Codes Cryptogr. 73, 587–600 (2014).
     
  7. C. Beierle and G. Leander, New instances of quadratic APN functions, IEEE Trans. Inf. Theory 68, 670–678 (2022).
     
  8. A. A. Gorodilova, Characterization of almost perfect nonlinear functions in terms of subfunctions Diskretn. Mat. 27 (3), 3–16 (2015) [Russian] [Discrete Math. Appl. 26 (4), 193–202 (2016)].
     
  9. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  10. The international SAT competition web page (Satisfiability: Application and Theory, Paderborn, 2022). Available at www.satcompetition.org.
     
  11. M. Davis, G. Logemann, and D. Loveland, A machine program for theorem-proving, Commun. ACM 5 (7), 394–397 (1962).
     
  12. J. P. Marques Silva and K. A. Sakallah, GRASP — A new search algorithm for satisfiability, in Proc. 1996 IEEE/ACM Int. Conf. Computer-Aided Design, San Jose, USA, Nov. 10–14, 1996 (IEEE Comput. Soc., Washington, 1996), pp. 220–227.
     
  13. Yu. Yu. Ogorodnikov, A combined attack on the RSA algorithm using the SAT approach, Din. Sist. Mekh. Mash. 2 (1), 276–284 (2016) [Russian].
     
  14. S. E. Schmittner, A SAT-based public key cryptography scheme (Cornell Univ., Ithaca, NY, 2015) (Cornell Univ. Libr. e-Print Archive; arXiv:1507.08094).
     
  15. R. L. Rivest, L. Adleman, and M. L. Dertouzos, On data banks and privacy homomorphisms, in Foundations of Secure Computation (Academic Press, New York, 1978), pp. 169–179.
     
  16. R. Wille, A. Lye, and P. Niemann, Checking reversibility of Boolean functions, in Reversible Computation (Proc. 8th Int. Conf., Bologna, Italy, July 7–8, 2016) (Springer, Cham, 2016), pp. 322–337 (Lect. Notes Comput. Sci., Vol. 9720).
     
  17. N. K. Vereshchagin and A. Shen’, Lectures on Mathematical Logic and Algorithm Theory. Part 1. The Beginnings of Set Theory (MTsNMO, Moscow, 2012) [Russian].
     
  18. G. S. Tseitin, On the complexity of proof in prepositional calculus in Studies in Constructive Mathematics and Mathematical Logic. II (Zap. Nauchn. Semin. LOMI, Vol. 8) (Nauka, Leningrad, 1968), pp. 234–259 [Russian].
     
  19. K. A. Browning, J. F. Dillon, M. T. McQuistan, and A. J. Wolfe, An APN permutation in dimension six, in Finite Fields: Theory and Applications (Proc. 9th Int. Conf., Dublin, Ireland, July 13–17, 2009) (AMS, Providence, RI, 2010), pp. 33–42 (Contemp. Math., Vol. 518).
     
  20. Y. Edel and A. Pott, A new almost perfect nonlinear function which is not quadratic, Adv. Math. Commun. 3, 59–81 (2015).
     
  21. K. V. Kalgin and V. A. Idrisova, The classification of quadratic APN functions in 7 variables (Univ. California, San Diego, 2020) (Cryptol. ePrint Archive; Pap. 2020/1515). Available at eprint.iacr.org/2020/1515 (accessed July 21, 2022).