Volume 29, No 4, 2022, P. 38-58

UDC 519.7
A. E. Doronin and K. V. Kalgin
Application of SAT solvers to the problem of finding vector Boolean functions with required cryptographic properties

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.

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

DOI: 10.33048/daio.2022.29.730

Artemy E. Doronin ¹
Konstantin V. Kalgin ^2,3
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
3. Institute of Computational Mathematics and Mathematical Geophysics,
6 Acad. Lavrentyev Avenue, 630090 Novosibirsk, Russia
e-mail: artem96dor@gmail.com, kalginkv@gmail.com

Received December 30, 2021
Revised April 11, 2022
Accepted April 15, 2022

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).