The autocorrelation distribution of balanced Boolean function

Abstract

The global avalanche characteristics (the sumof- squares indicator and the absolute indicator) measure the overall avalanche characteristics of a cryptographic Boolean function. Sung et al. (1999) gave the lower bound on the sumof- squares indicator for a balanced Boolean function satisfying the propagation criterion with respect to some vectors. In this paper, if balanced Boolean functions satisfy the propagation criterion with respect to some vectors, we give three necessary and sufficient conditions on the auto-correlation distribution of these functions reaching the minimum the bound on the sum-of-squares indicator. And we also find all Boolean functions with 3-variable, 4-variable, and 5-variable reaching the minimum the bound on the sum-of-squares indicator.

Keywords

Boolean functions / auto-correlation distribution / global avalanche characteristics / balanced / propagation criterion

References

[1] Adams C, Tavares S. Generating and counting binary bent sequences. IEEE Transactions on Information Theory, 1990, 36(5): 1170-1173

[2] Webster A F. Plaintext/ciphertext bit dependencies in cryptographic system. Master thesis, Department of Electrical Engineering, Queen’s University, Ontario, Cannada, 1985

[3] Preneel B, Van Leekwijck W, Van Linden L, Govaerts R, Vandewalle J. Propagation characteristics of boolean functions. In: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology. 1991, 161-173

[4] Zhang K, Zheng Y. GAC-the criterion for global avalance characteristics of cryptographic functions. Journal of Universal Computer Science, 1995, 1(5): 320-337

[5] Son J, Lim J, Chee S, Sung S. Global avalanche characteristics and nonlinearity of balanced boolean functions. Information Processing Letters, 1998, 65(3): 139-144

[6] Sung S, Chee S, Park C. Global avalanche characteristics and propagation criterion of balanced boolean functions. Information Processing Letters, 1999, 69(1): 21-24

[7] Charpin P, Pasalic E. On propagation characteristics of resilient functions. In: Proceedings of the 9th Annual International Workshop on Selected Areas in Cryptography. 2002, 175-195

[8] Zhou Y, Xie M, Xiao G. On the global avalanche characteristics between two boolean functions and the higher order nonlinearity. Information Sciences, 2010, 180(2): 256-265

[9] Zhang X, Zheng Y. Characterizing the structures of cryptographic functions satisfying the propagation criterion for almost all vectors. Designs, Codes and Cryptography, 1996, 7(1): 111-134

[10] Carlet C. Partially-bent functions. In: Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology. 1992, 280-291

[11] Meier W, Pasalic E, Carlet C. Algebraic attacks and decomposition of boolean functions. In: Proceedings of Advances in Cryptology- EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques. 2004, 474-491

[12] Zhou Y, Xiao G. On the equal-weight symmetric boolean functions. Frontiers of Computer Science in China, 2009, 3(4): 485-493

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg