Algebraically degenerate approximations of boolean functions PDF

Автори:A.N. Alekseychuk, S.N. Konyushok

A.N. Alekseychuk, S.N. Konyushok

UDC 519.7

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

Author Affiliations

Institute of Special Communications and Information Protection, National Technical University of Ukraine "Kyiv Polytechnic Institute", Kyiv, Ukraine


1. P. Gopalan, R. O’Donnel, A. Servedio, A. Shpilka, and K. Wimmer, “Testing Fourier dimensionality and sparsity,” SIAM J. on Comput., 40 (4), 1075–1100 (2011). CrossRef

2. P. Gopalan, “A Fourier-analytic approach to Reed-Muller decoding,” in: Proc. Annual IEEE Symp. on Foundation in Computer Science (FOCS 2010), Springer, Berlin (2010), pp. 685–694.

3. R. L. Lechner, “Harmonic analysis of switching functions,” in: Recent Developments in Switching Theory, Academic Press, New–York (1971), pp. 122–228.

4. E. Dawson and C. K. Wu, “Construction of correlation immune Boolean functions,” in: Proc. Inform. and Communicat. Security, Springer, Berlin (1997), pp. 170–180.

5. E. K. Alekseev, “On some measures of nonlinearity for Boolean functions,” Applied Discrete Mathematics, No. 2 (12), 5–16 (2011).

6. J. Daemen, R. Govaerts, and J. Vandewalle, “Resynchronization weakness in synchronous stream ciphers,” in: Advances in Cryptology, Proc. EUROCRYPT’93, Springer, Berlin (1993), pp. 159–167.

7. J. Goliċ and G. Morgari, “On the resynchronization attack,” in: Proc. Fast Software Encryption (FSE’03), Springer, Berlin (2003), pp. 100–110.

8. E. K. Alekseev, “On an attack on a filtering generator with a complication function close to an algebraically degenerate one,” in: Collected Articles of Young Scientists of the Faculty of MVK at the Moscow State University, No. 8 (2011), pp. 114–123.

9. A. Canteaut, “On the correlations between a combining function and function of fewer variables,” in: Proc. 2002 IEEE Inform. Theory Workshop, Springer, Berlin (2002), pp. 78–81.

10. A. N. Alekseychuk and S. N. Konyushok, “An improved test of Boolean functions for
k-dimensionality,” Cybernetics and Systems Analysis, 49, No. 2, 183–190 (2013). CrossRef

11. A. N. Alekseychuk and S. N. Konyushok, “Fast algorithm for reconstruction of high-probable low-dimensional approximations for Boolean functions,” in: Proc. Intern. Conf. on Modern Stochastics: Theory and Applications III, Taras Shevchenko National University of Kyiv (2012), p. 32.

12. O. A. Logachyov, A. A. Salnikov, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology [in Russian], MCCME, Moscow (2004).

Cybernetics and Systems Analysis

November 2014, Volume 50, Issue 6, pp 817-828

Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 3–14, November–December, 2014