An improved test of boolean functions for k-dimensionality PDF

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

A.N. Alekseychuk, S.N. Konyushok

UDC 621.391:519.2

An improved test of Boolean functions for -dimensionality / Alekseychuk A.N., Konyushok S. N. // Cybernetika i sistemny analiz.

A probabilistic test of Boolean functions for k-dimensionality is constructed. The test has a less time complexity and a smaller first kind error probability (with the same upper bound for the second kind error probability) in comparison with a well-known previously proposed test.

Refs: 9 titles.

Keywords:

testing property of Boolean functions, probabilistic algorithm, k-dimensional function, Walsh–Hadamard transform.

Author Affiliations

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

References

1. P. Gopalan, R. O’Donnell, A. Servedio, et al., “Testing Fourier dimensionality and sparsity,” SIAM J. Comput., 40, No. 4, 1075–1100 (2011). CrossRef

2. O. A. Logachev, A. A. Salnikov, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptography [in Russian], MCCME, Moscow (2012).

3. V.V. Yashchenko, “On the propagation criterion for Boolean functions and on bent functions,” Problemy Peredachi Informatsii, 33, No. 1, 75–86 (1997).

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

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

6. E.K. Alekseev, “On an attack on a filtering generator with a nearly algebraically degenerate function,” in: Proc. 6th Intern. Sci. Conf. on Problems of Security and Antiterrorism, Vol. 2, MCCME, Moscow (2011), pp. 114–123.

7. L.A. Levin, “Randomness and non-determinism,” J. Symbolic Logic, 58, No. 3, 1102–1103 (1993).

8. N. Alon, T. Kaufman, M. Krivelevich, et al., “Testing Reed-Muller codes,” IEEE Trans. Inform. Theory, 51, No. 11, 4032–4039 (2005). CrossRef

9. A. Bhattacharyya, S. Kopparty, G. Schoenebeck, et al., “Optimal testing of Reed-Muller codes,” in: Proc. 51st Ann. IEEE Symp. on Foundations of Comput. Science, Las Vegas (2010), pp. 488–497.

Cybernetics and Systems Analysis

March 2013, Volume 49, Issue 2, pp 183-190

Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 27–35, March–April 2013