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

doi:10.1007/s11464-016-0518-y

Front. Math. China

2016, Vol. 11

Issue (2) : 339-352 https://doi.org/10.1007/s11464-016-0518-y

RESEARCH ARTICLE

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

Luyang LI¹,Yujuan SUN^1,²(

),Weiguo ZHANG^1,²

1. ISN Laboratory, Xidian University, Xi’an 710071, China
2. Science and Technology on Communication Security Laboratory, Chengdu 610041, China

Download: PDF(138 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Issue Date: 18 April 2016

Cite this article:

Luyang LI,Yujuan SUN,Weiguo ZHANG. Construction of balanced Boolean functions with high nonlinearity, good local and global avalanche characteristics[J]. Front. Math. China, 2016, 11(2): 339-352.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-016-0518-y
https://academic.hep.com.cn/fmc/EN/Y2016/V11/I2/339

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 https://doi.org/10.1007/3-540-45539-6_36
2	Carlet C. Partially bent functions. Des Codes Cryptogr, 1993, 3: 135–145 https://doi.org/10.1007/BF01388412
3	Khoo K, Gong G. New constructions for resilient and highly nonlinear Boolean functions. ACISP, 2003, 498–509 https://doi.org/10.1007/3-540-45067-x_43
4	Khoo K, Gong G. New construction for balanced Boolean functions with very high nonlinearity. IEICE Transactions, 2007, 90-A(1): 29–35 https://doi.org/10.1093/ietfec/e90-a.1.29
5	Maitra S. High nonlinear balanced Boolean functions with good local and global avalanche characteristics. Inform Process Lett, 2002, 83: 281–286 https://doi.org/10.1016/S0020-0190(02)00207-7
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 https://doi.org/10.1007/978-3-540-24676-3_28
7	Rothaus O S. On bent function. J Combin Theory Ser A, 1976, 20: 300–305 https://doi.org/10.1016/0097-3165(76)90024-8
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 https://doi.org/10.1016/S0020-0190(00)00221-0
9	Stǎnicǎ P, Sung S H. Boolean functions with five controllable cryptographic properties. Des Codes Cryptogr, 2004, 31(2): 147–157 https://doi.org/10.1023/B:DESI.0000012443.88578.69
10	Sun Y, Li L Y, Yang B. Constructions of balanced functions with high nonlinearity. Int J Comput Math, 2013, 90(9): 1832–1839 https://doi.org/10.1080/00207160.2013.770147
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 https://doi.org/10.1007/s10623-011-9587-9
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 https://doi.org/10.1080/00207160.2012.687726
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 https://doi.org/10.1109/TIT.2014.2300067
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 https://doi.org/10.1109/TIT.2014.2345772
17	Zhang W G, Pasalic E. Highly nonlinear balanced S-boxes with good differential properties. IEEE Trans Inform Theory, 2014, 60(12): 7970–7979 https://doi.org/10.1109/TIT.2014.2360880
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 https://doi.org/10.1109/TIT.2009.2032736
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

[1]	Ze LI. Asymptotic stability of solitons to 1D nonlinear Schrödinger equations in subcritical case[J]. Front. Math. China, 2020, 15(5): 923-957.
[2]	Weiyang WANG, Keqin FENG. Inhomogeneous quantum codes (II): non-additive case[J]. Front Math Chin, 2012, 7(3): 573-586.

Viewed

Full text

Abstract

Cited

Shared

Discussed