Abstract. A theorem that improves a previously known upper bound for the relative distance between a Boolean function of n variables and the set of k-dimensional functions, k < n , is proved. The proof is based on the Bonami–Beckner inequality.

Keywords: correlation cryptanalysis, k-dimensional Boolean function, bent function, Walsh–Hadamard transform, Bonami–Beckner inequality.