最高非线性度旋转对称布尔函数与最优代数免疫函数

doi:10.11896/j.issn.1002-137X.2016.11.045

摘要/Abstract

摘要： 研究了旋转对称布尔函数的最高扩散次数、最高非线性度、代数免疫性和最优代数免疫函数的存在性与构造等问题。利用导数和e-导数证明了非线性度达到最高的旋转对称布尔函数的存在性,并利用导数,由扩散性达到最高n次的Bent函数来验证一类旋转对称Bent函数的存在性。同时证明了1阶代数免疫和2阶以上代数免疫旋转对称布尔函数的存在性。另外,利用旋转对称Bent函数构造了非齐次完全旋转对称最优代数免疫布尔函数以及一类众多的最优代数免疫布尔函数,并证明了这两类函数的存在性。同时,也得到了非齐次完全旋转对称相关免疫布尔函数。

关键词: 旋转对称布尔函数,Bent函数,导数,最优代数免疫函数,相关免疫性

Abstract: In this paper,we studied the cryptographic properties of RSBFs,including the highest number of propagation,the highest nonlinearity and algebraic immunity,and also studied the problems of the existence and the construction of the optimal algebraic immunity function.Using the derivative and the e-derivative of the Boolean functions,we proved that there exist RSBFs whose nonlinearity is the highest,and verified the existence of a type of RSBFs from Bent functions whose propagation reaches n degree.Moreover,we also proved the existence of RSBFs with algebraic immunity by one-order or higher than two-order.We constructed inhomogeneous complete RSBFs with the optimal algebraic immunity and a large number of the optimal algebraic immunity Boolean functions from rotation symmetric Bent functions,and proved the existence of the two types of functions.Meanwhile,we also obtained inhomogeneous complete RSBFs with correlation immunity.

Key words: RSBFs,Bent function,Derivative,Optimal algebraic immunity function,Correlation immunity

黄景廉,王卓. 最高非线性度旋转对称布尔函数与最优代数免疫函数[J]. 计算机科学, 2016, 43(11): 230-233. https://doi.org/10.11896/j.issn.1002-137X.2016.11.045

HUANG Jing-lian and WANG Zhuo. Highest Nonlinearity Rotation Symmetric Boolean Functions and Optimal Algebraic Immunity Function[J]. Computer Science, 2016, 43(11): 230-233. https://doi.org/10.11896/j.issn.1002-137X.2016.11.045

参考文献

[1] Courtois N,Meier W.Algebraic attacks on stream ciphers withlinear feedback[C]∥Advances in Cryptology-EUROCRYPT 2003.Warsaw,Poland,2003,LNCS,2656:345-359
[2] Carlet C,Zeng X Y.Further properties of several classes ofBoolean functions with optimum algebraic immunity[J].Designs,Codes and Cryptography,2009,52(3):303-338
[3] Carlet C.A method of construction of balanced functions withoptimum algebraic immunity[C]∥Proceedings of the First International Workshop on Coding and Cryptography.Fujian,2007:25-43
[4] Li Y,Yang M,Kan H B.Constructing and counting Booleanfunctions on even variables with maximum algebraic immunity[J].IEICE Transactions on Fundamentals,2010,93-A(3):640-643
[5] Rizomiliotis P.On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation[J].IEEE Transactions on Information Theory,2010,56(8):4014-4024
[6] Tu Z R,Deng Y P.A class of 1-resilient function with high nonlinearity and algebraic immunity[R].Ryptography ePrint Archive,Report 2010,2010/179
[7] Wang Q,Peng J,Kan H,et al.Constructions of cryptographically significant Boolean functions using primitive polynomials[J].IEEE Transactions on Information Theory,2010,56(6):3048-3053
[8] Li C L,Zhang H G,Zeng X Y,et al.The lower bound on the second-order nonlinearity for a class of Bent functions[J].Chinese Journal of Computers,2012,35(8):1588-1593(in Chinese) 李春雷,张焕国,曾祥勇,等.一类Bent函数的二阶非线性度下界[J].计算机学报,2012,5(8):1588-1593
[9] Sarkar S,Gangopadhyay S.On the second order nonlinearity of a cubic Maiorana-McFarland Bent Functions[J].International Journal of Foundations of Computer Science,2010,21(3):243-254
[10] Su S H,Tang X H.Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity[J].Designs,Codes and Cryptography,2014,71(2):183-199
[11] Chen Y D,Zhang Y N,Tian W.Construction of Even-variableRotation Symmetric Boolean Functions with Optimal Algebraic Immunity[J].Journal of Cryptologic Research,2014,1(5):437-448(in Chinese) 陈银冬,张亚楠,田威.具有最优代数免疫度的偶数元旋转对称布尔函数的构造[J].密码学报,2014,1(5):437-448
[12] Sarkar S,Maitra S.Construction of rotation symmetric Boolean functions with optimal algebraic immunity[J].Computation Systems,2009,12(3):267-284
[13] Fu S,Qu L,Li C,et al.Balanced rotation symmetric Boolean functions with maximum algebraic immunity[J].IET Information Security,2011,5(2):93-99
[14] Dong D S,Li C,Qu L J,et al.Rotation symmetric Boolean functions in even-variable maximum algebraic immunity[J].Journal of National University of Defense Technology,2012,34(4):85-89(in Chinese) 董德帅,李超,屈龙江,等.偶变元MAI 旋转对称布尔函数[J].国防科技大学学报,2012,34(4):85-89
[15] Rothaus O S.On bent functions[J].Journal of CombinatorialTheory,Series A,1976,20:300-305
[16] 温巧燕,钮心忻,杨义先.现代密码学中的布尔函数[M].北京:科学出版社,2000
[17] Li W,Wang Z,Huang J.The e-derivative of boolean functions and its application in the fault detection and cryptographic system[J].Kybernetes,2011,40(5/6):905-911
[18] Huang J L,Wang Z.The relationship between correlation im-mune and weight of H Boolean function[J].Journal on Communications,2012,33(2):110-118(in Chinese) 黄景廉,王卓.H布尔函数的相关免疫性与重量的关系[J].通信学报,2012,33(2):110-118
[19] Zhao M L.Method of detecting special logic function based on Boolean e-derivative[J].Journal of Zhejiang University (Science Edition),2014,41(4):424-426(in Chinese) 赵美玲.基于布尔e导数的特殊逻辑函数检测方法[J].浙江大学学报(理学版),2014,41(4):424-426

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed