The construction of pseurandom 0-1 sequence generators with the property that statistical analysis of the output signal yields no information about the key initially used is a problem of current interest in cryptography. One of the possible solutions is to introduce a combinating Boolean function f(x₁, ..., x_n) that would use several pseudo-random generators as inputs to transform their signals in such a way that the frequency of zeroes in the output matches the frequency of units both for the function and for its subfunctions on at least n-k variables. Such combinating functions are known as order k stable. The present article provides a shrap estimate for the order of stability of quadratic functions in n variables: 𝑘 < ⌊𝑛/2⌋. We also obtain a general representation for all quadratic (𝑛−1)-stable functions on 2n variables up to a permutation of variable indices.

cryptoanalysis, quadratic Boolean functions, combinating Boolean function, pseudorandom sequences

Mathematical problems and theory of numerical methods