几类高非线性度密码函数的构造

doi:10.19665/j.issn1001-2400.20230416

摘要/Abstract

摘要：

布尔函数在密码学中有着重要应用。Bent函数作为非线性度最大的布尔函数一直是对称密码学的热点研究对象。从频谱的角度来看,bent函数在Walsh-Hadamard变换下具有均匀频谱。Negabent函数是bent函数的推广,它在nega-Hadamard 变换下具有均匀频谱。广义negabent函数是指在广义nega-Hadamard变换下具有均匀频谱的函数。Bent函数自1976年被提出以来,人们对其进行了广泛和深入的研究。然而,对于negabent函数和广义negabent函数的相关研究则较少。文中分析了广义negabent函数和广义bent-negabent函数的性质,并构造出一系列广义negabent函数、广义bent-negabent函数和广义semibent-negabent函数。首先,通过分析广义布尔函数的nega-互相关函数与广义nega-Hadamard变换之间的关系,提出一个广义negabent函数的判据。基于该判据,构造了一类广义negabent函数。其次,利用直和构造给出了两类形如f(x)=c₁f₁(x⁽¹⁾)+c₂f₂(x⁽²⁾)+…+c_rf_r(x⁽^r⁾)的广义negabent函数。最后,利用直和构造得到了几类Z₈上的广义bent-negabent函数和广义semibent-negabent函数。文中提出了一些广义negabent函数构造的新方法,丰富了广义negabent函数的结果。

关键词: 布尔函数, 广义negabent函数, 广义bent函数, nega-Hadamard, bent-negabent函数

Abstract:

Boolean functions have important applications in cryptography.Bent functions have been a hot research topic in symmetric cryptography as Boolean functions have maximum nonlinearity.From the perspective of spectrum,bent functions have a flat spectrum under the Walsh-Hadamard transform.Negabent functions are a class of generalized bent functions,which have a uniform spectrum under the nega-Hadamard transform.A generalized negabent function is a function with a uniform spectrum under the generalized nega-Hadamard transform.Bent functions has been extensively studied since its introduction in 1976.However,there are few research on negabent functions and generalized negabent functions.In this paper,the properties of generalized negabent functions and generalized bent-negabent functions are analyzed.Several classes of generalized negabent functions,generalized bent-negabent functions,and generalized semibent-negabent functions are constructed.First,by analyzing a link between the nega-crosscorrelation of generalized Boolean function and the generalized nega-Hadamard transformation,a criterion for generalized negabent functions is presented.Based on this criterion,a class of generalized negabent functions is constructed.Secondly,two classes of generalized negabent functions of the form f(x)=c₁f₁(x⁽¹⁾)+c₂f₂(x⁽²⁾)+…+c_rf_r(x⁽^r⁾) are constructed by using the direct sum construction.Finally,generalized bent-negabent functions and generalized semibent-negabent functions over Z₈ are obtained by using the direct sum construction.Some new methods for constructing generalized negabent functions are given in this paper,which will enrich the results of negabent functions.

Key words: Boolean function, generalized negabent function, generalized bent function, nega-Hadamard, bent-negabent function

中图分类号:

TN918.1

刘欢, 伍高飞. 几类高非线性度密码函数的构造[J]. 西安电子科技大学学报, 2023, 50(6): 237-250.

LIU Huan, WU Gaofei. Several classes of cryptographic Boolean functions with high nonlinearity[J]. Journal of Xidian University, 2023, 50(6): 237-250.

图/表 1

参考文献 34

[1]	ROTHAUS O S. On “Bent” Functions[J]. Journal of Combinatorial Theory,Series A, 1976, 20(3):300-305. doi: 10.1016/0097-3165(76)90024-8
[2]	PARKER M G, POTT A. On Boolean Functions Which Are Bent and Negabent[M]. Heidelberg: Springer, 2007:9-23.
[3]	何业锋, 马文平. 一类具有高非线性度的密码函数[J]. 西安电子科技大学学报, 2010, 37(6):1107-1110.
	HE Yefeng, MA Wenping. One Class of Highly Nonlinear Cryptographic Functions[J]. Journal of Xidian University, 2010, 37(6):1107-1110.
[4]	SCHMIDT K U, PARKER M G, POTT A. Negabent Functions in the Maiorana-McFarland Class[C]// Sequences and Their Applications-SETA 2008:5203.Heidelberg:Springer, 2008:390-402.
[5]	GANGOPADHYAY S, CHATURVEDI A. A New Class of Bent-Negabent Boolean Functions[J]. IACR Cryptology ePrint Archive, 2010, 2010:597.
[6]	SU W, POTT A, TANG X. Characterization of Negabent Functions and Construction of Bent-Negabent Functions with Maximum Algebraic Degree[J]. IEEE transactions on information theory, 2013, 59(6):3387-3395. doi: 10.1109/TIT.2013.2245938
[7]	ZHANG F, WEI Y, PASALIC E. Constructions of Bent-Negabent Functions and Their Relation to the Completed Maiorana-McFarland Class[J]. IEEE Transactions on Information Theory, 2015, 61(3):1496-1506. doi: 10.1109/TIT.2015.2393879
[8]	MANDAL B, MAITRA S, STǍNICǍ P. On the Existence and Non-Existence of Some Classes of Bent-Negabent Functions[J]. Applicable Algebra in Engineering Communication and Computing, 2022, 33(3):237-260. doi: 10.1007/s00200-020-00444-w
[9]	PASALIC E, KUDIN S, POLUJAN A, et al. Vectorial Bent-Negabent Functions—Their Constructions and Bounds[J]. IEEE Transactions on Information Theory, 2023, 69(4):2702-2712. doi: 10.1109/TIT.2022.3226571
[10]	STǍNICǍ P. On Weak and Strong 2^k-bent Boolean Functions[J]. IEEE Transactions on Information Theory, 2016, 62(5):2827-2835. doi: 10.1109/TIT.2016.2539971
[11]	TANG C, XIANG C, QI Y, et al. Complete Characterization of Generalized Bent and 2^k-bent Boolean Functions[J]. IEEE Transactions on Information Theory, 2017, 63(7):4668-4674. doi: 10.1109/TIT.2017.2686987
[12]	WANG L, YU L, ZHUO Z. Further Results on 2^k-bent Functions[J]. International Journal of Electronics and Information Engineering, 2021, 13(2):38-46.
[13]	周宇, 陈智雄, 卓泽朋, 等. (n,m)函数抗差分功耗攻击指标的研究综述[J]. 西安电子科技大学学报, 2021, 48(1):50-60.
	ZHOU Yu, CHEN Zhixiong, ZHUO Zepeng, et al. Survey of Results of(n,m)-Functions against Differential Power Attack[J]. Journal of Xidian University, 2021, 48(1):50-60.
[14]	WU G, LI N, ZHANG Y, et al. Several Classes of Negabent Functions over Finite Fields[J]. Science China Information Sciences, 2018, 61(3):1-3.
[15]	ZHOU Y, QU L. Constructions of Negabent Functions over Finite Fields[J]. Cryptography and Communications, 2017, 9(2):165-180. doi: 10.1007/s12095-015-0167-0
[16]	XIE X, LI N, ZENG X Y, et al. Several Classes of Bent Functions over Finite Fields[J]. Designs,Codes and Cryptography, 2022, 91(2):309-332. doi: 10.1007/s10623-022-01109-0
[17]	肖艳. 奇变元semibent-negabent函数的构造[D]. 湖北: 湖北大学, 2017.
[18]	YANG Z Y, KE P H, CHEN Z X. New Secondary Constructions of Generalized Bent Functions[J]. Chinese Journal of Electronics, 2021, 30(6):1022-1029. doi: 10.1049/cje2.v30.6
[19]	MANDAL B, GANGOPADHYAY A K. A Note on Generalization of Bent Boolean Functions[J]. Advances in Mathe-matics of Communications, 2021, 15(2):329.
[20]	CALDERÓN-GÓMEZ J E, MEDINA L A, MOLINA-SALAZAR C. Short Cycle Rotation Boolean Functions:Generators and Count[C]// 2022 Fall Eastern Sectional Meeting.Seoul:AMS, 2022:1-12.
[21]	MEDINA L A, SEPÚLVEDA L B, SERNA-RAPELLO C A. Walsh-Hadamard Transforms of Generalized p-ary Functions and C-finite Sequences[J]. Discrete Applied Mathematics, 2022, 315:86-96. doi: 10.1016/j.dam.2022.03.016
[22]	CHATURVEDI A, GANGOPADHYAY A K. On Generalized Nega-Hadamard Transform[C]// International Conference on Heterogeneous Networking for Quality.Reliability,Security and Robustness:115.Heidelberg:Springer, 2013:771-777.
[23]	KAUR R, SHARMA D. Results on Generalized Negabent Functions[J]. Notes on Number Theory and Discrete Mathematics, 2018, 24(4):38-44. doi: 10.7546/nntdm
[24]	HODŽIĆ S, PASALIC E. Generalized Bent Functions-Some General Construction Methods and Related Necessary and Sufficient Conditions[J]. Cryptography & Communications, 2015, 7(4):469-483.
[25]	郑连清, 张串绒, 董庆宽. 布尔函数非线性度界的问题[J]. 西安电子科技大学学报, 2003(2):281-283.
	ZHENG Lianqing, ZHANG Cuanrong, DONG Qingkuan, et al. Study of Nonlinearity Bounds of Boolean Functions[J]. Journal of Xidian University, 2003(2):281-283.
[26]	MEIDL W, POLUJAN A A, POTT A. Linear Codes and Incidence Structures of Bent Functions and Their Generalizations[J]. Discrete Mathematics, 2023, 346(1):113-157.
[27]	MESNAGER S. Several New Infinite Families of Bent Functions and Their Duals[J]. IEEE Transactions on Information Theory, 2014, 60(7):4397-4407. doi: 10.1109/TIT.2014.2320974
[28]	HODŽIĆ S, PASALIC E, WEI Y. A General Framework for Secondary Constructions of Bent and Plateaued Functions[J]. Designs,Codes and Cryptography, 2020, 88(10):2007-2035. doi: 10.1007/s10623-020-00760-9
[29]	CHAABANE S, GHATTASSI A, MENSI K, et al. GIS-Based Multi-Criteria Analysis of an Eco-Innovative APOC Wastewater Treatment and Reuse System for Irrigation Purposes in the Rural Locality of Bent Saidane(NE Tunisia)[J]. Euro-Mediterranean Journal for Environmental Integration, 2022, 7(4):497-510. doi: 10.1007/s41207-022-00329-z
[30]	GADOULEAU M, MARIOT L, PICEK S. Bent Functions in the Partial Spread Class Generated by Linear Recurring Sequences[J]. Designs,Codes and Cryptography, 2022, 91(1):63-82. doi: 10.1007/s10623-022-01097-1
[31]	BAPIĆ A, PASALIC E, ZHANG F R, et al. Constructing New Superclasses of Bent Functions from Known Ones[J]. Cryptography and Communications, 2022, 14(6):1229-1256. doi: 10.1007/s12095-022-00566-7
[32]	冯登国. 浅析Xiao-Massey定理的意义和作用[J]. 西安电子科技大学学报, 2021, 48(1):7-13.
	FENG Dengguo. On the Significance and Function of the Xiao-Massey Theorem[J]. Journal of Xidian University, 2021, 48(1):7-13.
[33]	STǍNICǍ P, GANGOPADHYAY S, CHATURVEDI A, et al. Nega-Hadamard Transform,Bent and Negabent Functions[C]// International Conference on Sequences and Their Applications.Sequences and Their Applications-SETA 2010:6338.Heidelberg:Springer, 2010:359-372.
[34]	CHATURVEDI A, GANGOPADHYAY S, STǍNICǍ P, et al. Investigations on Bent and Negabent Functions via the Nega-Hadamard Transform[J]. IEEE Transactions on Information Theory, 2012, 58(6):4064-4072. doi: 10.1109/TIT.2012.2186785

	构造方法^[23]	条件
f为Z₈上的广义	f(x,y)=4g(x)+(4h(x)+4g(x))y	当g,h为negabent函数
negabent函数	f(x,y)=4g(x)+(4h(x)+2g(x))y	当g,h$\oplus$k为negabent函数且$\mathcal{N}$_h(u)= $\mathcal{N}$_g_$\oplus$_h(u)
f为Z₁₆上的广义	f(x,y)=8g(x)+(8h(x)+8k(x)+8g(x))y	当g,h$\oplus$k为negabent函数
negabent函数	f(x,y)=8g(x)+(8h(x)+8k(x)+4g(x))y	当g,g$\oplus$k,g$\oplus$h$\oplus$k 为negabent函数, 且$\mathcal{N}$_h_$\oplus$_k(u)= $\mathcal{N}$_g_$\oplus$_h_$\oplus$_k(u)
	f(x,y,z)=8g(x)+(8h(x)+4)y+(8k(x)+4)z+ (8l(x)+4)(1+y)(1+z)-4yz	当g$\oplus$l,g$\oplus$k,g$\oplus$h,g$\oplus$h$\oplus$k 为 negabent函数,且$\mathcal{N}$_g_$\oplus$_k(u)= $\mathcal{N}$_g_$\oplus$_h_$\oplus$_k(u)