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

Standard

Application of SAT-Solvers to the Problem of Finding Vectorial Boolean Functions with Required Cryptographic Properties. / Doronin, A. E.; Kalgin, K. V.

In: Journal of Applied and Industrial Mathematics, Vol. 16, No. 4, 2022, p. 632-644.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{a8f38ba7f9f44a1c81e3231b6c0a58e6,

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

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.",

keywords = "APN function, Boolean function, SAT-solver, cryptography",

author = "Doronin, {A. E.} and Kalgin, {K. V.}",

note = "Публикация для корректировки.",

year = "2022",

doi = "10.1134/S1990478922040056",

language = "English",

volume = "16",

pages = "632--644",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "4",

}

RIS

TY - JOUR

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

AU - Doronin, A. E.

AU - Kalgin, K. V.

N1 - Публикация для корректировки.

PY - 2022

Y1 - 2022

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

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

KW - APN function

KW - Boolean function

KW - SAT-solver

KW - cryptography

UR - https://www.mendeley.com/catalogue/d37ccdb1-2aca-3549-8d29-be676c3e2d51/

U2 - 10.1134/S1990478922040056

DO - 10.1134/S1990478922040056

M3 - Article

VL - 16

SP - 632

EP - 644

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 4

ER -

ID: 55697477