Open AccessInvestigation of heuristic search functions for nonlinear substitutions for symmetric cryptography
Author(s) -
Alexandr Kuznetsov,
Nikolay Poluyanenko,
V. A. Katrich,
Serhii Kandii,
Yuliia Zaichenko
Publication year - 2021
Publication title -
radiotekhnika
Language(s) - English
Resource type - Journals
eISSN - 2786-5525
pISSN - 0485-8972
DOI - 10.30837/rt.2021.3.206.05
Subject(s) - heuristic , hill climbing , nonlinear system , cryptography , computer science , mathematical optimization , simulated annealing , cryptanalysis , incremental heuristic search , theoretical computer science , beam search , search algorithm , algorithm , mathematics , physics , quantum mechanics
Nonlinear substitutions (S-boxes) are used in most modern symmetric cryptoalgorithms. They are designed to mix input data and play a significant role in ensuring resistance against known cryptanalytic attacks (differential, linear, algebraic and other cryptanalysis methods). However, random generation of nonlinear substitutions with the desired indicators is an extremely difficult mathematical problem. This article explores the heuristic techniques for S-boxes informed search, in particular, discusses various cost functions used in most of the known algorithms (for example, local search, hill climbing, simulated annealing, genetic search, etc.). The aim of the study is to determine the specific parameters of heuristic functions, which, on the one hand, do not reduce the degree of awareness of the search nodes, and on the other hand, do not require significant computational costs. The article examines the influence of individual parameters on the value of the cost function and complexity of its calculation. It also provides specific recommendations for the formation of parameters for heuristic search for S-boxes, which significantly affect the efficiency of generating nonlinear substitutions for symmetric cryptography.