摘要
布尔函数在密码系统中有着非常重要的应用,密码系统中的很多问题都可以转化成布尔函数相关密码学性质的研究。本论文主要研究了初等对称布尔函数的平衡性问题、奇变元对称布尔函数的代数免疫度、两种Partial Spread Bent函数的表达式及自对偶情况、Neagbent函数的一些性质以及Bent-Negabent函数的构造。
首先,根据Cusick、Li和Stanica等人的工作,本文进一步研究了他们提出的初等对称布尔函数平衡性问题的猜想。利用初等对称布尔函数的分解,得到了该猜想在大多数情况下都是成立的,并且本文的结果覆盖了几乎所有的已知结果,分析方法也很简单。
其次考虑了奇变元对称布尔函数代数免疫度次优的情况。利用权重支集这个工具并结合对称布尔函数零化子的特点,给出了2m+3个变元的对称布尔函数代数免疫度次优的充要条件;并通过布尔函数的分解与级联,利用偶变元对称布尔函数代数免疫度的一些结果,得到了奇变元对称布尔函数代数免疫度次优或最优的必要条件以及一些奇变元代数免疫度次优或最优的对称布尔函数类。
接着介绍了与Regular Spread相近的两种Spread:Andre Spread和Albert Spread,并分析了由这两种Spread定义的Partial Spread Bent函数的函数表达式、对偶函数的表达式以及自对偶的充要条件。
最后,本文讨论了Negabent函数的一些性质及Bent-Negabent函数的构造问题。通过分析Nega-Hadamard变换和Walsh-Hadamard变换之间的关系,给出了任意变元的布尔函数是Negabent的充要条件,确定了Negabent函数的Nega谱值分布情况,并介绍了一种构造n元Bent-Negabent函数的方法。这种构造方法可以得到任意指定代数次数的Bent-Negabent函数,这表明n元Bent-Negabent函数的代数次数的最大值为n/2,因此解决了关于Bent-Negabent函数代数次数的最大值及构造具有高代数次数的Bent-Negabent的公开问题。
Boolean functions are frequently used in the design of stream ciphers, block ciphers, error correcting codes and Hash functions. One of the most vital roles in cryptography of Boolean functions is to be used as filter and combination generators of stream ciphers based on linear feedback shift registers. In order to resist different kinds of attacks, Boolean functions used in cipher systems must satisfy some properties, such as balancedness, high nonlinearity, high algebraic degree, and high order of algebraic immunity. In this thesis, we mainly focus on the study of Boolean functions in four topics:the balancedness of elementary symmetric Boolean functions, the algebraic immunity of symmetric Boolean functions on odd variables, the representation and the self-duality of some partial spread Bent functions, the properties of Negabent functions and the construction of Bent-Negabent functions.
Firstly, according to the work given by Cusick, Li and Stanica, we will further investi-gate the conjecture about the balancedness of elementary symmetric Boolean functions. By decomposing elementary symmetric Boolean functions, we prove that the conjecture holds in most cases. Our results cover most of the known results, and the method is much simpler than the known methods.
Secondly, we will study the algebraic immunity of symmetric Boolean functions on odd variables. Using the tool of weight support, we give the necessary and sufficient conditions for2m+3variables symmetric Boolean functions to achieve suboptimal algebraic immunity. According to the concatenation of Boolean functions and the known results about symmetric Boolean functions with high algebraic immunity on even number of variables, we obtain some necessary conditions for symmetric Boolean functions with suboptimal algebraic immunity on odd variables and construct some classes of symmetric Boolean functions with suboptimal algebraic immunity on odd variables.
Next, we will consider the properties of partial spread Bent functions. We introduce two kinds of partial spread Bent functions:Andre partial spread Bent functions and Albert partial spread Bent functions, which are similar with the classic partial spread Bent functions--PSap. We give the representations of these Bent functions and their dual functions, and the necessary and sufficient conditions for these Bent functions to be self-dual.
Finally, we will analyze the properties of Negabent functions and the construction of Bent-Negabent functions. We present necessary and sufficient conditions for a Boolean func- tion to be a negabent function for both an even and an odd number of variables, which demon-strates the relationship between negabent functions and bent functions. By using these neces-sary and sufficient conditions for Boolean functions to be negabent, we obtain that the nega spectrum of a negabent function has at most4values. We determine the nega spectrum dis-tribution of negabent functions. Further, we provide a method to construct bent-negabent functions in n variables (n even) of algebraic degree ranging from2ton/2, which implies that the maximum algebraic degree of an n-variable bent-negabent function is equal ton/2. Thus, we answer two open problems proposed by Parker and Pott and by Stanica et al. respectively.
引文
[1]C. Shannon. A Mathematical Theory of Communication. Bell System Technical Jour-nal.1948,27:379-423 and 623-656
[2]C. Shannon. Communication Theory of Secrecy System. Bell System Technical Jour-nal.1949,28(4):656-715
[3]NBS. Date Encryption Standard. FIPS PUB 46, National Bureau of Standards. Wash-ington D.C.,1977
[4]W. Diffie, M. Hellman. New Direction in Cryptography. IEEE Transactions on Infor-mation Theory.1976,22:644-654
[5]R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystem. Comm. ACM.1978,21(2):120-126
[6]NIST. Advanced Encryption Standard-aes. http://csrc.nist.gov/archive/aes/index2.html, 2001
[7]冯登国,裴定一.密码学导引.北京:科学出版社,1999:56-99
[8]A. Menezes, P. Oorschot, S. Vanstone. Handbook of Applied Cryptography. USA: CRC Press,2001:63-297
[9]O. Goldreich. Foundations of Cryptography. British:Cambridge University Press, 2001:89-201
[10]D. Stinson. Cryptography Theory and Practice. Second Edition edn. USA:CRC Press, 2002:56-385
[11]S. Galbraith. Mathematics of Public Key Cryptography. Cambridge University Press, 2012
[12]H. Katzan. The Standard Data Encryption Algorithm. Petrocell:Books Inc.,1977
[13]X. Lai, J. Massey. A Proposal for a New Block Encryption Standard. Cryptology-Eurocrypt 1990.1991:389-404
[14]X. Lai. On the Design and Security of Block Ciphers. ETH Series in Information Proccessing.1992:9752
[15]R. Rivest. The RC5 Encryption Algorithm. Workshop on Cryptographic Algorithms 1994.1995:86-96
[16]B. J. Kaliski, Y. Yin. On Differential and Linear Cryptanalysis of RC5 Encryption Algorithm. Cryptology-Crypto 1995.1995:171-184
[17]R. Rivest, M. Robshaw, Y. Yin. RC6 as the AES. AES Candidate Conference 2000. 2001:337-342
[18]E. Biham, R. Anderson, K. Serpent. A New Block Cipher Proposal. Fast Software Encryption 1998.1998:222-238
[19]R. Rueppel. Analysis and Design of Stream Ciphers.1986:37-189
[20]C. Ding, G. Xiao, W. Shan. The Stability Theory of Stream Ciphers.1991:78-137
[21]Estream. The Ecrypt Stream Cipher Project, http://www.ecrypt.eu.org/stream/,2008
[22]T. E. Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory.1985,31(4):469-472
[23]R. Gold. Maximal Recursive Sequences with 3-valued Recursive Cross-Correlation Functions. IEEE Transactions on Information Theory.1968,14:154-156
[24]L. Welch. Lower Bounds on the Maximum Cross-Correlation of Signals. IEEE Trans-actions on Information Theory.1974,20:397-399
[25]J. Olsen, R. Scholtz, L. Welch. Bent Function Sequences. IEEE Transactions on Infor-mation Theory.1982,28:858-864
[26]P. Kumar, R. Scholtz, L. Welch. Generalized Bent Functions and Their Properties. Combinatory Theory Series A.1985,40(1):90-107
[27]J. No, P. Kumar. A New Family of Binary Pseudorandom Sequences Having Optimal Periodic Correlation Properties and Large Linear Span. IEEE Transactions on Informa-tion Theory.1989,35(2):371-379
[28]A. Klapper.d-form Sequences:Families of Sequences with Low Correlation Values and Large Linear Spans. IEEE Transactions on Information Theory.1995,41(2):423-431
[29]A. Klapper. Large Families of Sequences with Near-optimal Correlations and Large Linear Span. IEEE Transactions on Information Theory.1996,42(4):1241-1248
[30]X. Zeng, Q. Liu, L. Hu. Generalized Kasami Sequences:The Large Set. IEEE Trans-actions on Information Theory.2007,53(7):2587-2598
[31]R. Rueppel, O. Staffelbach. Products of Linear Recurring Sequences with Maximum Complexity. IEEE Transactions on Information Theory.1987,33(1):124-131
[32]X. Lai. Higher Order Derivatives and Differential Cryptanalysis. Symposium on Com-munication, Coding and Cryptography 1994.1994
[33]L. Knudsen. Truncated and Higher Order Differentials. Lecture Notes in Computer Science 1008.1995:196-211
[34]O. Rothaus. On Bent Functions. Journal of Combinational Theory, Ser. A.1976, 20:300-305
[35]F. MacWilliams, N. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company,1977:125-154
[36]C. Carlet. Two Classes of Bent Functions. Cryptology-Eurocrypt 1993.1994:77-101
[37]N. Courtois, J. Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. Cryptology-Asiacrypt 2002.2002:267-287
[38]N. Courtois, W. Meier. Algebraic Attacks on Stream Ciphers with Linear Feedback. Cryptology-Eurocrypt 2003.2003:345-359
[39]N. Courtois. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. Cryptology-Crypto 2003.2003:176-194
[40]F. Armknecht. Improving Fast Algebraic Attacks. Fast Software Encryption 2004. 2004:65-82
[41]J. Cho, J. Pieprzyk. Algebraic Attacks on SOBER-t32 and SOBER-128. Fast Software Encryption 2004.2004:49-64
[42]D. Lee, J. Kim, J. Hong, et al. Algebraic Attacks on Summation Generators. Fast Software Encryption 2004.2004:34-48
[43]C. Carlet, D. Dalai, K. Gupta, et al. Cryptographically Significant Boolean Func-tions:Analysis and Construction. IEEE Transactions on Information Theory.2006, 52(7):3105-3121
[44]F. Armknecht, C. Carlet, P. Gaborit, et al. Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks. EUROCRYPT 2006.2006:147-164
[45]T. Siegenthaler. Correlation-immunity of Nonlinear Combining Functions for Crypto-graphic Applications. IEEE Transactions on Information Theory.1984,30:776-780
[46]A. Webster, S. Tavares. On the Design of S-boxes. Cryptology-Crypto 1985.1986:523-534
[47]S. Lloyd. Characterising and Counting Functions Satisfying the Strict Avalanche Cri-terion of Order(n-3). The Second IMA Confference on Cryptography and Coding 1989.1992:165-172
[48]R. Forre. The Strict Avalanche Criterion:Spectras Properties of Boolean Functions and an Extended Definition. Cryptology-Crypto 1988.1990:450-468
[49]B. Preneel, W. Vanleekwijk, L. V. Linden, et al. Propagation Characteristics of Boolean Functions. Cryptology-Eurocrypt 1990.1991:161-173
[50]B. Prencecl, R. Govaerts, J. Vandewalle. Boolean Functions Satisfying Higher Order Propagation Criteria. Cryptology-Eurocrypt 1991.1991:141-152
[51]C. Carlet. Partially Bent Functions. Designs, Codes and Cryptography.1993,3(2):135-145
[52]W. Cusick. Boolean Functions Satisfying a Higher Order Strict Avalanche Criterion. Cryptology-Eurocrypt 1993.1994:86-95
[53]M. Lobanov. Exact Relation between Nonlinearity and Algebraic Immunity. Discrete Mathematics and Applications.2006,16(5):453-460
[54]C. Carlet. On the Higher Order Nonlinearities of Algebraic Immune Functions. Cryptology-CRYPTO 2006.2006:584-601
[55]M. Lobanov. Exact Relations between Nonlinearity and Algebraic Immunity. Journal of Applied and Industrial Mathematics.2009,3(3):367-376
[56]P. Savicky. On the Bent Boolean Functions Which Are Symmetric. Europ. J. Comb. 1994,15:407-410
[57]S. Maitra, P. Sarkar. Maximum Nonlinearity of Symmetric Boolean Functions on Odd Number of Variables. IEEE Transactions on Information Theory.2002,48(9):2626-2630
[58]C. Carlet. On the Degree, Nonlinearity, Algebraic Thickness and Nonormality of Boolean Function, with Developments on Symmetric Functions. IEEE Transactions on Information Theory.2004,50(9):2178-2185
[59]C. Carlet. Boolean Functions for Cryptography and Error Correcting Codes. Cambridge University Press,2010:257-397
[60]T. Cusick, L. Yuan. k-th Order Symmetric Sac Boolean Functions and Bisecting Bino-mial Coefficients. Discr. Appl. Math.2005,149:73-86
[61]C. J. Mitchell. Enumerating Boolean Functions of Cryptographic Significance. J. Cryp-tol.1990,2(3):155-170
[62]Y. X. Yang, B. Guo. Further Enumerating Boolean Functions of Cryptographic Signif-icance. J. Cryptol.1995,8(3):115-122
[63]P. Sarkar, S. Maitra. Balancedness and Correlation Immunity of Symmetric Boolean Functions. Proceedings of the R.C. Bose Centenary Symposium on Discrete Mathe-matics and Applications.2003:176-181
[64]A. Canteaut, M. Videau. Symmetric Boolean Functions. IEEE Transactions on Infor-mation Theory.2005,51(8):2791-2811
[65]T. Cusick, Y. Li, P. Stanica. Balanced Symmetric Boolean Functions Over GF(p). IEEE Transactions on Information Theory.2008,54(3):1304-1307
[66]T. Cusick, Y. Li, P. Stanica. On a Conjecture for Balanced Symmetric Boolean Func-tions. J. Math. Crypt.2009,3(4):273-290
[67]G. Gao, W. Liu, X. Zhang. The Degree of Balanced Elementray Symmetric Boolean Functions of 4k+3 Variables. IEEE Transactions on Information Theory.2011, 57(7):4822-4825
[68]F. Castro, L. Medina. Linear Recurrences and Asymptotic Behavior of Exponential Sums of Symmetric Boolean Functions. The Electronic Journal of Combinatorics. 2011,18(2):8
[69]Y. Guo, G. Gao, Y. Zhao. Recent Results on Balanced Symmetric Boolean Functions. http://eprint.iacr.org/2012/093
[70]Z. Ou, Y. Zhao. Unbalanced Elementary Symmetric Boolean Functions with the Degree d and wt(d)> 3. http://eprint.iacr.org/2012/101
[71]A. Braeken, B. Preneel. On the Algebraic Immunity of Symmetric Boolean Functions. Cryptology-Indocrypt 2005.2005:35-48
[72]D. Dalai, K. Gupta, S. Maitra. Cryptographically Significant Boolean Functions:Con-struction and Analysis in Terms of Algebraic Immunity. Workshop on Fast Software Encryption 2005.2005:98-111
[73]D. Dalai, S. Maitra, S. Sarkar. Basic Theory in Construction and Analysis of Boolean Functions of Variables with Maximum Algebraic Immunity. Designs, Codes and Cryp-tography.2006,40(1):41-58
[74]N. Li, W. Qi. Construction and Analysis of Boolean Functions of 2t+1 Variables with Maximum Algebraic Immunity. Cryptology-ASIACRYPT 2006. Berlin,2006:84-98
[75]N. Li, W. Qi. Symmetric Boolean Functions Depending on an Odd Number of Variables with Maximum Algebraic Immunity. IEEE Transactions on Information Theory.2006, 52(5):2271-2273
[76]L. Qu, C. Li, K. Feng. A Note on Symmetric Boolean Functions with Maximum Al-gebraic Immunity in Odd Number of Variables. IEEE Transactions on Information Theory.2007,53(8):2908-2910
[77]Q. Liao, F. Liu, K. Feng. On (2m+1)variable Symmetric Boolean Functions with Submaximum Algebraic Immunity 2m-1. Sci. China, Ser. A.2009,52(1):17-28
[78]L. Qu, K. Feng, F. Liu, et al. Constructing Symmetric Boolean Functions with Maximum Algebraic Immunity. IEEE Transactions on Information Theory.2009, 55(5):2406-2412
[79]L. Qu, C. Li. On the 2m-variable Symmetric Boolean Functions with Maximum Alge-braic Immunity. Sci. China Ser. F.2008,51:120-127
[80]J. Peng, Q. Wu, H. Kan. On Symmetric Boolean Functions with High Algebraic Immu-nity on Even Number of Variables. IEEE Transactions on Information Theory.2011, 57(10):7205-7220
[81]H. Wang, J. Peng, Y. Li, et al. On 2k-variable Symmetric Boolean Functions with Maximum Algebraic Immunity k. IEEE Transactions on Information Theory.2012, 58(8):5612-5624
[82]F. Liu, K. Feng. Efficient Computation of Algebraic Immunity of Symmetric Boolean Functions. Lecture Notes in Computer Science.2007,4484:318-329
[83]F. Liu, K. Feng. On the 2m-variable Symmetric Boolean Functions with Maximum Algebraic Immunity 2m-1. Workshop on Coding and Cryptography 2007
[84]廖群英,冯克勤,刘峰.具有最优代数免疫度的2m个变量的对称boolean函数.中国科学:数学.2010,40(10):929-942
[85]R. McFarland. A Family of Noncyclic Difference Sets. Journal of Comb. Theory, Ser. A.1973,15:1-10
[86]J. Dillon. Elementary Hadamard Difference Sets. Ph.D. Thesis. Univ. of Maryland, 1974
[87]A. Youssef, G. Gong. Hyper-bent Functions. Crypology-Eurocrypt 2001.2001:406-419
[88]G. Leander. Monomial Bent Functions. IEEE Transactions on Information Theory. 2006,52(2):738-743
[89]T. Neumann. Bent Functions. Diploma Thesis. University of Kaiserslautern,2006
[90]P. Charpin, G. Gong. Hyperbent Functions, Kloosterman Sums and Dickson Polyno-mials. IEEE Transactions on Information Theory.2008,54(9):4230-4238
[91]S. Mesnager. Bent and Hyper-Bent Functions in Polynomial Form and Their Link with some Exponential Sums and Dickson Polynomials. IEEE Transactions on Information Theory.2011,57(9):5996-6009
[92]S. Mesnager. A New Class of Bent and Hyper-bent Boolean Functions in Polynomial Forms. Design, Codes and Cryptography.2011,59:265-279
[93]J.-P. Flori, S. Mesnager. Dickson Polynomial, Hyperelliptic Curves and Hyper-Bent Functions. Sequences and Their Applications-SETA 2012.2012:40-52
[94]Z. Tu, Y. Deng. A Conjecture on Binary String and its Applications on Constructing Boolean Functions of Optimal Algebraic Immunity. Design, Codes and Cryptography. 2011,60(1):1-14
[95]Z. Tu, Y. Deng. Boolean Functions with All Main Cryptographic Properties. Cryptology ePrint Archive.2010:2010/518
[96]N. Tokareva. Generalizations of Bent Functions:A Survey. Journal of Applied and Industrial Mathematics.2011,5(1):110-129
[97]M. Parker. The Constabent Properties of Golay-Davis-Jedwab Sequences. IEEE Inter-national Symposium on Information Theory 2000
[98]C. Riera, M. Parker. Generalized Bent Criteria for Boolean Functions (I). IEEE Trans-actions on Information Theory.2006,52(9):4142-4159
[99]M. Parker, A. Pott. On Boolean Functions Which Are Bent and Negabent. Lecture Notes in Computer Science.2007,4893:9-23
[100]K.-U. Schmidt, M. Parker, A. Pott. Negabent Functions in the Maiorana-Mcfarland Class. Sequences and Their Applications-SETA 2008.2008:390-402
[101]S. Sarkar. On the Symmetric Negabent Boolean Functions. Indocrypt 2009.2009:136-143
[102]P. Stanica, S. Gangopadhyay, A. Chaturvedi, et al. Nega-Hadamard Transform, Bent and Negabent Functions. Sequences and Their Applications-SETA 2010.2010:359-372
[103]P. Stanica, S. Gangopadhyay, A. Chaturvedi, et al. Investigations on Bent and Negabent Functions via the Nega-Hadamard Transform. IEEE Transactions on Information The-ory.2012,58(6):4064-4072
[104]S. Sarkar. Characterizing Negabent Boolean Functions over Finite Fields. Sequences and Their Applications-SETA 2012.2012:77-88
[105]N. Tokareva. Bent Functions:Results and Applications. A Survey. Applied Discrete Mathematics.2009,2(1):15-37
[106]A. Ambrosimov. Properties of the Bent Functions of q-ary Logic Over Finite Fields. Discrete Math.1994,6(3):50-60
[107]O. Logachev, A. Salnikov, V. Yashchenko. Bent Functions on a Finite Abelian Group. Discrete Math. Appl.1997,7(6):547-564
[108]G. Gong, S. W. Golomb. Transform Domain Analysis of DES. IEEE Transactions on Information Theory.1999,45(6):2065-2073
[109]C. Carlet, C. Ding. Highly Nonlinear Mappings. Journal of Complexity.2004,20(2-3):205-244
[110]L. Poinsot, S. Harari. Generalized Boolean Bent Functions. Cryptology-Indocrypt 2004.2005:107-119
[111]L. Poinsot. Multidimensional Bent Functions. GESTS Intern. Transactions on Comput. Sci. Eng.2005,18(1):185-195
[112]K.-U. Schmidt. Quaternary Constant-Amplitude Codes for Multicode CDMA. IEEE International Symposium on Information Theory-ISIT 2007.2007:2781-2785
[113]W. Meier, E. Pasalic, C. Carlet. Algebraic Attacks and Decomposition of Boolean Functions. Cryptology-Eurocrypt 2004.2004:474-491
[114]E. Hansen. A Table of Series and Products. Prentice-Hall, Englewood Cliffs,1975
[115]D. Hughes, F. Piper. Projective Planes. Springer-Verlag,1973:187-191
[116]A. Albert. On Nonassociative Division Algebras. TAMS.1952,72:296-309
[117]A. Albert. On the Collineation Groups Associated with Twisted Fields.1958/1959 Calcutta Math. Soc. Golden Jubilee Commemoration Part 11:485-497
[118]A. Albert. Finite Division Algebras and Finite Planes. AMS Proc. Sympos. Appl. Math. 1960,10:53-70
[119]L. Dickson. History of the Theory of Numbers, Volume II. Chelsea Publishing Com-pagny,1919
[120]Y. Laigle-Chapuy. Permutation Polynomials and Applications to Coding Theory. Finite Fields Appl.2007,13:58-70
[121]H. Niederreiter, K. Robinson. Complete Mappings of Finite Fields. J. Austral. Math. Soc. Ser. A.1982,33:197-212