Application of SAT solvers to~the~problem of~finding vector Boolean functions with~required~cryptographic properties

A. E. Doronin ; K. V. Kalgin

Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 4, pp. 38-58.

Résumé

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: $\mathbf{G} = \mathbf{F}\oplus \mathbf{c}\cdot g_1 \oplus \mathbf{d}\cdot g_2$, where $\mathbf{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.

Détail

Keywords: SAT-solver, cryptography, Boolean function, APN-function.

Bibliographie

[1] Nyberg K., “Differentially uniform mappings for cryptography”, Proc. Workshop Theory Appl. Cryptogr. Techniques, Advances in Cryptology — EUROCRYPT'93 (Lofthus, Norway, May 23–27, 1993), Lect. Notes Comput. Sci., 765, Springer, Heidelberg, 1994, 55–64 | DOI | MR

[2] M. É. Tuzhilin, “APN functions”, Prikl. Diskretn. Mat., 2009, no. 3, 14–20 (Russian)

[3] Brinkmann M., Leander G., “On the classification of APN functions up to dimension five”, Des. Codes Cryptogr., 49 (2008), 273–288 | DOI | MR

[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), Lect. Notes Comput. Sci., 9061, Springer, Cham, 2015, 83–107 | DOI | MR

[5] Calderini M., Budaghyan L., Carlet C., On known constructions of APN and AB functions and their relation to each other, Cryptol. Archive, Pap. 2020/1444, , Univ. California, San Diego, 2020 (accessed July 21, 2022) eprint.iacr.org/2020/1444 | MR

[6] Yu Y., Wan M., Li Y., “A matrix approach for constructing quadratic APN functions”, Des. Codes Cryptogr., 73 (2014), 587–600 | DOI | MR

[7] Beierle C., Leander G., “New instances of quadratic APN functions”, IEEE Trans. Inf. Theory, 68 (2022), 670–678 | DOI | MR

[8] A. A. Gorodilova, “Characterization of almost perfect nonlinear functions in terms of subfunctions”, Discrete Math. Appl., 26:4 (2016), 193–202 | DOI | MR

[9] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR

[10] Satisfiability: Application and Theory, The international SAT competition web page, , Paderborn, 2022 www.satcompetition.org

[11] Davis M., Logemann G., Loveland D., “A machine program for theorem-proving”, Commun. ACM, 5:7 (1962), 394–397 | DOI | MR

[12] Marques Silva J. P., Sakallah K. A., “GRASP — A new search algorithm for satisfiability” (San Jose, USA, Nov. 10–14, 1996), Proc. 1996 IEEE/ACM Int. Conf. Computer-Aided Design, 1996, 220–227, IEEE Comput. Soc., Washington | MR

[13] Yu. Yu. Ogorodnikov, “A combined attack on the RSA algorithm using the SAT approach”, Din. Sist. Mekh. Mash., 2:1 (2016), 276–284 (Russian)

[14] Schmittner S. E., A SAT-based public key cryptography scheme, Cornell Univ., Ithaca, NY, 2015, arXiv: 1507.08094

[15] Rivest R. L., Adleman L., Dertouzos M. L., “On data banks and privacy homomorphisms”, Foundations of Secure Computation, Academic Press, New York, 1978, 169–179 | MR

[16] Wille R., Lye A., Niemann P., “Checking reversibility of Boolean functions”, Reversible Computation, Proc. 8th Int. Conf. (Bologna, Italy, July 7–8, 2016), Lect. Notes Comput. Sci., 9720, Springer, Cham, 2016, 322–337 | DOI | MR

[17] N. K. Vereshchagin and A. Shen', Lectures on Mathematical Logic and Algorithm Theory, v. 1, The Beginnings of Set Theory, MTsNMO, M., 2012 (Russian)

[18] G. S. Tseitin, “On the complexity of proof in prepositional calculus”, Studies in Constructive Mathematics and Mathematical Logic. II, Zap. Nauchn. Semin. LOMI, 8, Nauka, L., 1968, 234–259 (Russian) | MR

[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), Contemp. Math., 518, AMS, Providence, RI, 2010, 33–42 | DOI | MR

[20] Edel Y., Pott A., “A new almost perfect nonlinear function which is not quadratic”, Adv. Math. Commun., 3 (2015), 59–81 | DOI | MR

[21] Kalgin K. V., Idrisova V. A., The classification of quadratic APN functions in 7 variables, Cryptol. Archive; Pap. 2020/1515, , Univ. California, San Diego, 2020 (accessed July 21, 2022) eprint.iacr.org/2020/1515