Algebraic degenerate approximations of Boolean functions / Alekseychuk A.N., Konyushok S.N. // Cybernetika i sistemny analiz.
Properties of k-dimensional approximations of Boolean functions are investigated. One of main results is the theorem on the structure of k-dimensional functions whose degree equals d and whose distance from a given Boolean function of n variables is no longer than 2 n-d (1-ε), 1 ≤ d ≤ k ≤ n, ε∈ (0, 1) This theorem considerably strengthens the well-known P. Gopalan result and makes it possible to considerably increase the efficiency of his algorithm for constructing all the mentioned k-dimensional Boolean functions.
Refs: 12 titles.
correlation cryptanalysis, degenerate Boolean function, k-dimensional function, Walsh–Hadamard transform, finding k-dimensional approximations of Boolean functions
Institute of Special Communications and Information Protection, National Technical University of Ukraine "Kyiv Polytechnic Institute", Kyiv, Ukraine