Construction of balanced Boolean functions with high nonlinearity, good local and global avalanche characteristics

Abstract

Boolean functions possessing multiple cryptographic criteria play an important role in the design of symmetric cryptosystems. The following criteria for cryptographic Boolean functions are often considered:high nonlinearity, balancedness, strict avalanche criterion, and global avalanche characteristics. The trade-off among these criteria is a difficult problem and has attracted many researchers. In this paper, two construction methods are provided to obtain balanced Boolean functions with high nonlinearity. Besides, the constructed functions satisfy strict avalanche criterion and have good global avalanche characteristics property. The algebraic immunity of the constructed functions is also considered.

Keywords

Boolean function / cryptography / nonlinearity / strict avalanche criterion (SAC) / global avalanche characteristics

References

[1] Canteaut A, Carlet C, Charpin P, Fontaine C. Propagation characteristics and correlation immunity of highly nonlinear Boolean functions. In: Advances in Cryptology—EUROCRYPT 2000. Lecture Notes in Computer Science, Vol 1807. Berlin: Springer-Verlag, 2000, 507–522

[2] Carlet C. Partially bent functions. Des Codes Cryptogr, 1993, 3: 135–145

[3] Khoo K, Gong G. New constructions for resilient and highly nonlinear Boolean functions. ACISP, 2003, 498–509

[4] Khoo K, Gong G. New construction for balanced Boolean functions with very high nonlinearity. IEICE Transactions, 2007, 90-A(1): 29–35

[5] Maitra S. High nonlinear balanced Boolean functions with good local and global avalanche characteristics. Inform Process Lett, 2002, 83: 281–286

[6] Meier W, Pasalic E, Carlet C. Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology—EUROCRYPT 2004. Lecture Notes in Computer Science, Vol 3027. Berlin: Springer-Verlag, 2004, 474–491

[7] Rothaus O S. On bent function. J Combin Theory Ser A, 1976, 20: 300–305

[8] Stǎnicǎ P, Sung S H. Improving the nonlinearity of certain balanced Boolean functions with good local and global avalanche characteristics. Inform Process Lett, 2001, 79: 167–172

[9] Stǎnicǎ P, Sung S H. Boolean functions with five controllable cryptographic properties. Des Codes Cryptogr, 2004, 31(2): 147–157

[10] Sun Y, Li L Y, Yang B. Constructions of balanced functions with high nonlinearity. Int J Comput Math, 2013, 90(9): 1832–1839

[11] Tang D, Zhang W G, Tang X H. Construction of balanced Boolean functions with high nonlinearity and good autocorrelation properties. Des Codes Cryptogr, 2013, 67: 77–91

[12] Webster A F, Tavares S E. On the design of S-box. In: Advances in Cryptology—CRYPTO’85. Lecture Notes in Computer Science, Vol 218. Berlin: Springer-Verlag, 1986 ,523 –524

[13] 13. Zeng X Y ,Hu L .A Composition Construction of Bent-Like Boolean Functions from Quadratic Polynomials. IACR Cryptology ePrint Archive, 2003, 204

[14] Zhang F R, Hu Y P ,Jia Y ,Xie M .New constructions of balanced boolean functions with high nonlinearity and optimal algebraic degree. Int J Comput Math, 2012, 89(10): 1319–1331

[15] Zhang W G, Pasalic E. Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes. IEEE Trans Inform Theory, 2014, 60(3): 1638–1651

[16] Zhang W G, Pasalic E. Generalized Maiorana-McFarland construction of resilient Boolean functions with high nonlinearity and good algebraic properties. IEEE Trans Inform Theory, 2014, 60(10): 6681–6695

[17] Zhang W G, Pasalic E. Highly nonlinear balanced S-boxes with good differential properties. IEEE Trans Inform Theory, 2014, 60(12): 7970–7979

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

[19] Zhang X M, Zheng Y L. GAC—the criterion for global avalanche characteristics of cryptographic functions. J Universal Comput Science, 1995, 1(5): 320–337

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg