On cross-correlation indicators of an S-box

Abstract

Substitution boxes (S-boxes) are often used as the most important nonlinear components in many symmetric encryption algorithms. The cryptographic properties of an S-box directly affect the security of the whole cipher system. Recently, generalized global avalanche characteristics (GGAC) were introduced to measure the correlation between two arbitrary Boolean functions. In this paper, to better evaluate the security of an S-box, we present two cross-correlation indicators for it. In addition, by studying the related properties of the cross-correlation between two balanced Boolean functions, we propose the lower bounds on the sum-of-squares indicator related to GGAC for two balanced functions and also for an S-box.

Keywords

cryptography / Boolean functions / substitution boxes / balancedness / generalized global avalanche characteristics / cross-correlation

References

[1] Zhang W G, Xiao G Z. Constructions of almost optimal resilient Boolean functions on large even number of variables. IEEE Transactions on Information Theory, 2009, 55(12): 5822–5831

[2] Webster A F, Tavares S E. On the design of S-boxes. In: Proceedings of CRYPTO’85. 1986, 523–534

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

[4] Preneel B, Govaerts R, Vandewalle J. Boolean functions satisfying higher order propagation criteria. In: Proceedings of 1991 Workshop on the Theory and Application of Cryptographic Techniques. 1991, 141–152

[5] Zhang X M, Zheng Y L. GAC - the criterion for global avalanche characteristics of cryptographic functions. Journal of Universal Computer Science, 1995, 1(5): 316–333

[6] Shannon C E. Communication theory of secrecy systems. Bell System Technical Journal, 1949, 28(4): 656–715

[7] Sarkar P, Maitra S. Cross-correlation analysis of cryptographically useful Boolean functions and S-boxes. Theory of Computing Systems, 2002, 35(3): 39–57

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

[9] Leander G, Poschmann A. On the classification of 4-bit S-boxes. In: Proceedings of 1st International Workshop on Arithmetic of Finite Fields. 2007, 159–176

[10] Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 1991, 4(1): 3–72

[11] Matsui M. Linear cryptanalysis method for DES cipher. In: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques. 1994, 396–397

[12] Gligoroski D, Moe M E G. On deviations of the AES S-box when represented as vector valued Boolean function. International Journal of Computer Science and Network Security, 2007, 7(4): 156–163

[13] Gao S, Ma W P, Guo N, Chen Q L. Design of cross-correlation test algorithm on S-box. Geomatics and Information Science of Wuhan University, 2010, 35(5): 558–561

[14] Mister S, Adams C. Practical S-box design. In: Proceedings of the 3rd Annual Workshop on Selected Areas in Cryptography. 1996, 1–17

[15] Nyberg K. Perfect nonlinear S-boxes. In: Proceedings of 10th Annual International Conference on Theory and Application of Cryptographic. 1991, 378–385

[16] Porwik P. The spectral test of Boolean function linearity. Journal of Applied Mathematics and Computer Science, 2003, 13(4): 567–575

[17] National Bureau of Standards. Data encryption standard (DES). Federal Information Processing Standard, 1977

[18] Daemen J, Rijmen V. The block cipher Rijndael. http://www.nist.gov/aes

[19] Johansson T, Pasalic E. A construction of resilient functions with high nonlinearity. IEEE Transactions on Information Theory, 2003, 49(2): 494–501

[20] Zhang M, Chan A. Maximum correlation analysis of nonlinear S-boxes in stream ciphers. In: Proceedings of 20th Annual International Cryptology Conference on Advances in Cryptology. 2000, 501–514

Acknowledgements

This work was supported by the National Science Foundation of China (Grant Nos. 60773002, 61072140, 61003299), the 111 Project (B08038), the Doctoral Program Foundation of Institutions of Higher Education of China (2010020311000 3), and the Fundamental Research Funds for the Central Universities (JY10000901034). The authors would like to thank the anonymous reviewers and editors for their valuable comments and suggestions that greatly improve the technical quality of this paper.

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg