DOI: 10.17587/prin.8.76-87

On the Fast Solution of the Jevons Group Action equation on Boolean functions

A. M. Kukartsev, amkukarcev@yandex.ru, A. A. Kuznetsov, kuznetsov@sibsau.ru, Siberian State Aerospace University named after academician M. F. Reshetnev, Krasnoyarsk, 660014, Russian Federation

Corresponding author: Kukartsev Anatolii M., Senior Lecturer, Siberian State Aerospace University named after academician M. F. Reshetnev, Krasnoyarsk, 660014, Russian Federation, e-mail: amkukarcev@yandex.ru

Action of the Jevons group on Boolean functions of n arguments is intransitive and divides the set into orbits of the same cardinalities. In most cases number of elements in the orbit is equal of the group order, i.e. 2ⁿn!. Calculation of the acting group element which links to two functions in the same orbit is a computationally hard mathematical problem. It refers to the problems of classification of Boolean functions relatively to group action. So this action is used as a cryptographic primitive of encryption algorithms that are based on managed operations where a key is an element of the Jevons group and Boolean functions are original encrypted data. We propose an efficient algorithm for computing the acting group element which links (the) two functions. The time complexity of the algorithm is much less than complete enumeration. This algorithm is based on the sequential computation of factors of the acting element written in the canonical form. The presence or absence of a factor in such canonical representation in solution of the equation is determined by frequency characteristics of binary vectors which are equivalent to the unknown Boolean function. We prove the correctness of the algorithm and give the formula for calculating its time complexity. After that an example demonstrates a solution of the equation for Boolean functions of four arguments. We calculate the maximum and minimum theoretical estimates of the time complexity. A number of numerical experiments allowed us to formulate the assumption that complexity of the solution is O(n²) in most cases. Such assessment of complexity is characteristic for equations including Boolean functions with nontrivial inertia subgroup of the Jevons group. For the numerical experiments a spectral analysis method of Boolean functions is developed. Using this method we calculate the minimum, maximum and average estimates of the algorithm complexity for all equations with Boolean functions of four and five arguments with a trivial inertia subgroup of the Jevons group. The results lead to the assumption that the algorithm will be effective for processing of real input data.

Keywords: action on the set, frequency analysis, the Jevons group, Boolean functions, equations of group action on the set Boolean functions

pp. 76–87

For citation:
Kukartsev A. M., Kuznetsov A. A. On the Fast Solution of the Jevons Group Action equation on Boolean functions, Programmnaya Ingeneria, 2017, vol. 8, no. 2, pp. 76—87.

This work was supported by the Grant of Russian Federation President, project nos. MD-3952.2015.9