COMPUTATIONALLY EFFICIENT METHOD FOR DETERMINING THE AVERAGE LINEAR PROPERTIES OF PSEUDO-DYNAMIC SUBSTITUTIONS

Abstract

Pseudo-dynamic substitutions PD-sbox can become an effective replacement for fixed substitutions
in pseudo-random functions, since they have the positive properties of both fixed substitutions
(low consumption of computational resources) and dynamic substitutions (which can radically complicate
the application of statistical cryptanalysis methods). The problem of active implementation of
pseudo-dynamic substitutions is, inter alia, the absence of a computationally efficient method for
determining the averaged linear properties for the entire set of equivalent substitutions generated
using PD-sbox, while in most cases, only the determination of the maximum values of the prevalence
(bias) bias (α, β) from the ideal value 1/2. To solve this problem, an original method is proposed,
which consists in the fact that the maximum dominance values are calculated only for relatively small
fixed substitutions included in the PD-sbox, and the resulting maximum dominance values are obtained
by iterative calculation using a logical-probabilistic expression for the Exclusive OR operation
-NO (XNOR). The effect of using the proposed method is a dramatic reduction in computational
operations and, accordingly, the possibility of determining on a typical personal computer the maximum
values of the prevalence bias (α, β) for 16-element PD-sboxes consisting of 8-bit fixed substitutions
(which is unattainable when using a trivial method).