Abstract. The properties of k-dimensional approximations of Boolean functions are analyzed. One of the main results is a theorem that specifies the structure of k-dimensional functions of degree d within the distance of більше 2^n–d (1–ε), ε ∈ (0,1), from a specified n-variable function, 1 ≤d ≤k ≤n, ε ∈ (0,1). This theorem significantly improves Gopalan’s result and notably increases the efficiency of his algorithm for finding all of the mentioned k-dimensional Boolean functions.

Keywords: correlation cryptanalysis, degenerate Boolean function, k-dimensional function, Walsh–Hadamard transform, finding k-dimensional approximations of Boolean functions.