RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2013 Volume 4, Issue 1, Pages 59–76 (Mi mvk73)

This article is cited in 5 papers

Analysis of the spectrum of random symmetric Boolean functions

G. I. Ivchenkoa, Yu. I. Medvedevb, V. A. Mironovaa

a NRU Higher School of Economics, Moscow
b Academy of Cryptography of the Russian Federation, Moscow

Abstract: General probabilistic model of a random symmetric Boolean function of $n$ variables is proposed. The characteristic function of the Walsh spectrum of a random symmetric Boolean function is defined; exact and asymptotic distributions of some spectrum characteristics as $n\to\infty$ are obtained in the case of the parametric measure. The basic properties of the Krawtchouk's polynomials (which are used in proofs) are reviewed.

Key words: symmetric Boolean function, Walsh transform, spectrum of function, characteristic function, parametric measure, Krawtchouk's polynomials, Krawtchouk matrix, spectrum characteristics, limit theorems.

UDC: 519.212.2

Received 20.IV.2012

DOI: 10.4213/mvk73



© Steklov Math. Inst. of RAS, 2024