Application of SAT-Solvers to the Problem of Finding Vectorial Boolean Functions with Required Cryptographic Properties
- 1 November 2022
- journal article
- research article
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 16 (4) , 632-644
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 vector APN function with additional properties. It is based on the idea of representing the unknown vectorial Boolean function as a sum of a known APN function 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 paper can prove the nonexistence of cubic APN functions in dimension 7 representable in the form of the sum described above.
Keywords
This publication has 10 references indexed in Scilit:
- New Instances of Quadratic APN FunctionsIEEE Transactions on Information Theory, 2021
- Checking Reversibility of Boolean Functions2016
- Характеризация почти совершенно нелинейных функций через подфункции2015
- Open Questions on Nonlinearity and on APN Functions2015
- A matrix approach for constructing quadratic APN functionsDesigns, Codes and Cryptography, 2014
- A new almost perfect nonlinear function which is not quadraticAdvances in Mathematics of Communications, 2009
- On the classification of APN functions up to dimension fiveDesigns, Codes and Cryptography, 2008
- GRASP-A new search algorithm for satisfiability2002
- Differentially uniform mappings for cryptography2001
- A machine program for theorem-provingCommunications of the ACM, 1962