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.

Key words： 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