Application of SAT-Solvers to the Problem of Finding Vectorial Boolean Functions with Required Cryptographic Properties

被引：0
作者：
Doronin A.E. [1 ]
Kalgin K.V. [2 ,3 ]
机构：
[1] Novosibirsk State University, Novosibirsk
[2] Sobolev Institute of Mathematics, Siberian Branch, Russian Academy ofSciences, Novosibirsk
[3] Institute of Computational Mathematics and Mathematical Geophysics, SiberianBranch,Russian Academy of Sciences, Novosibirsk
来源：
Journal of Applied and Industrial Mathematics | 2022年 / 16卷 / 04期
关键词：
APN function; Boolean function; cryptography; SAT-solver;
D O I：
10.1134/S1990478922040056
中图分类号：
学科分类号：
摘要：
Abstract: We propose a method for finding an almost perfect nonlinear (APN) function. It is basedon translation into SAT-problem and using SAT-solvers. We construct several formulas definingthe 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 Booleanfunctions and APN functions. We also propose a new method for finding a vector APN functionwith additional properties. It is based on the idea of representing the unknown vectorial Booleanfunction as a sum of a known APN function and two unknown Boolean functions,(Formula presented.), where F is a known APN function. It is shown that this method is more efficient thanthe direct construction of APN function using SAT for dimensions 6 and 7. As a result, themethod described in the paper can prove the nonexistence of cubic APN functions in dimension 7representable in the form of the sum described above. © 2022, Pleiades Publishing, Ltd.
引用
收藏
页码：632 / 644
页数：12
相关论文
共 21 条
  • [1] Nyberg K., Differentially uniform mappings for cryptography,” in Adv. Cryptol.—EUROCRYPT’93, Proc. Workshop Theory Appl. Cryptogr, 765, pp. 55-64, (1994)
  • [2] Tuzhilin M.E., APN functions, Prikl. Diskr. Mat., 3, pp. 14-20, (2009)
  • [3] Brinkmann M., Leander G., On the classification of APN functions up to dimension five, Des. Codes Cryptogr., 49, pp. 273-288, (2008)
  • [4] Carlet C., Open questions on nonlinearity and on APN functions,” in Arithmetic of Finite Fields, Rev. Sel. Pap. 5Th Int. Workshop, 9061, pp. 83-107, (2015)
  • [5] Calderini M., Budaghyan L., Carlet C., On Known Constructions of APN and AB Functions and Their Relation to Each Other (Univ. California, San Diego, 2020, Cryptol. Eprint Archive, pp. 2020-1444
  • [6] Yu Y., Wan M., Li Y., A matrix approach for constructing quadratic APN functions, Des. Codes Cryptogr., 73, pp. 587-600, (2014)
  • [7] Beierle C., Leander G., New instances of quadratic APN functions, IEEE Trans. Inf. Theory., 68, pp. 670-678, (2022)
  • [8] Gorodilova A.A., Characterization of almost perfect nonlinear functions in terms of subfunctions, Diskr. Mat., 27, 3, pp. 3-16, (2015)
  • [9] Garey M., Johnson D., Computers and Intractability: Guide to the Theory of NP-Completeness, (1979)
  • [10] The International SAT Competition Web Page. Paderborn: Satisfiability: Application and Theory, (2022)
123