To protect against algebraic attacks, a high algebraic immunity is now an important criterion for Boolean functions used in stream ciphers. In this paper, a new method based on a univariate polynomial representation o...To protect against algebraic attacks, a high algebraic immunity is now an important criterion for Boolean functions used in stream ciphers. In this paper, a new method based on a univariate polynomial representation of Boolean functions is proposed. The proposed method is used to constmct Boolean functions with an odd number of variables and with maximum algebraic immunity. We also discuss the nonlinearity of the constructed functions. Moreover, a lower bound is deter- mined for the number of Boolean functions with rmximum algebraic immunity.展开更多
This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in assoc...This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in associative classes. For some n, a part of 1-resilient functions with maximum algebraic immunity constructed in the paper can achieve almost optimal nonlinearity. Apart from their high nonlinearity, the functions reach Siegenthaler＇s upper bound of algebraic degree. Also a class of l-resilient functions on any number n 〉 2 of variables with at least sub-optimal algebraic immunity is provided.展开更多
All (2m +1)-variable symmetric Boolean functions with submaximal algebraic immunity 2m-1 are described and constructed. The total number of such Boolean functions is 32 ·22m-3 +3m-2 · 24 - 2 for m≥2.
The properties of the 2m-variable symmetric Boolean functions with maximum al- gebraic immunity are studied in this paper. Their value vectors, algebraic normal forms, and algebraic degrees and weights are all obtaine...The properties of the 2m-variable symmetric Boolean functions with maximum al- gebraic immunity are studied in this paper. Their value vectors, algebraic normal forms, and algebraic degrees and weights are all obtained. At last, some necessary conditions for a symmetric Boolean function on even number variables to have maximum algebraic immunity are introduced.展开更多
For an odd integer n ≥ 7, this paper presented a class of n-variable rotation symmetric Boolean functions （RSBFs） with optimum algebraic immunity. The nonlinearity of the constructed functions is determined.
Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the m...Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d = n1 +2 their nonlinearities equalthe minimum of ∑d-1 i=0 (ni) and ∑ d-1 i=0 (ni). Lastly, we identify two classes of such functions, one having algebraic degree of n or n-1.展开更多
Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This ...Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of two bits, and then generalizing the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions with maximum algebraic immunity are constructed. Enumeration of such functions is also n given. For a given function p（x） with deg（p（x）） 〈 [n/2], we give a method to construct functions in the form p（x）＋q（x） which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q（x） has degree no less than [n/2].展开更多
Boolean functions with optimal algebraic immunity(OAI functions) are important cryptographic primitives in the design of stream ciphers. During the past decade, a lot of work has been done on constructing such functio...Boolean functions with optimal algebraic immunity(OAI functions) are important cryptographic primitives in the design of stream ciphers. During the past decade, a lot of work has been done on constructing such functions, among which mathematics, especially ?nite ?elds, play an important role. Notably, the approach based on decompositions of additive or multiplicative groups of?nite ?elds turns out to be a very successful one in constructing OAI functions, where some original ideas are contributed by Tu and Deng(2012), Tang, et al.(2017), and Lou, et al.(2015). Motivated by their pioneering work, the authors and their collaborators have done a series of work, obtaining some more general constructions of OAI functions based on decompositions of ?nite ?elds. In this survey article, the authors review our work in this ?eld in the past few years, illustrating the ideas for the step-by-step generalizations of previous constructions and recalling several new observations on a combinatorial conjecture on binary strings known as the Tu-Deng conjecture. In fact, the authors have obtained some variants or more general forms of Tu-Deng conjecture, and the optimal algebraic immunity of certain classes of functions we constructed is based on these conjectures.展开更多
This paper first proposes an infinite class of 2k-variable Boolean functions with high nonlinearity and high algebraic degree. Then an infinite class of balanced Boolean functions are proposed by modifying the above B...This paper first proposes an infinite class of 2k-variable Boolean functions with high nonlinearity and high algebraic degree. Then an infinite class of balanced Boolean functions are proposed by modifying the above Boolean functions. This class of balanced Boolean functions have optimal algebraic degree and high nonlinearity. Both classes have optimal algebraic immunity based on a general combinatorial conjecture.展开更多
Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This ...Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents one main result to find balanced rotation symmetric Boolean functions with maximum algebraic immunity. Through swapping the values of two orbits of rotation class of the majority function, a class of 4k＋l variable Boolean functions with maximum algebraic immu- nity is constructed. The function f（x） we construct always has terms of degree n-2 independence of what ever n is. And the nonlinearity off（x） is relatively good for large n.展开更多
Boolean functions used in a cryptographic system should have high algebraic immunity to resist algebraic attacks. This paper presents a matrix method for constructing balanced Boolean functions achieving maximum algeb...Boolean functions used in a cryptographic system should have high algebraic immunity to resist algebraic attacks. This paper presents a matrix method for constructing balanced Boolean functions achieving maximum algebraic immunity.展开更多
Algebraic immunity is an important cryptographic property of Boolean functions. In this paper, odd-variable balanced Boolean functions with optimal algebraic immunity are obtained by m-sequence and consequently, we ge...Algebraic immunity is an important cryptographic property of Boolean functions. In this paper, odd-variable balanced Boolean functions with optimal algebraic immunity are obtained by m-sequence and consequently, we get bases with special constructions of vector space. Furthermore, through swapping some vectors of these two bases, we establish all kinds of odd-variable balanced Boolean functions with optimal algebraic immunity.展开更多
Tu and Deng proposed a class of bent functions which are of optimal algebraic immunity under the assumption of a combinatorial conjecture.In this paper,the authors compute the dual of the Tu-Deng functions and then sh...Tu and Deng proposed a class of bent functions which are of optimal algebraic immunity under the assumption of a combinatorial conjecture.In this paper,the authors compute the dual of the Tu-Deng functions and then show that they are still of optimal algebraic immunity under the assumption of the same conjecture.For another class of Boolean functions constructed by Tang,et al.which are of optimal algebraic immunity with similar forms to Tu-Deng functions,the authors show that they are not bent functions by using some basic properties of binary complete Kloosterman sums.展开更多
The trace inverse functions Tr(λx^(-1)) over the finite field F_(2~n) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS,RAKAPOSHI,the simple counter stream cipher(SCSC...The trace inverse functions Tr(λx^(-1)) over the finite field F_(2~n) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS,RAKAPOSHI,the simple counter stream cipher(SCSC) presented by Si W and Ding C(2012),etc.In order to evaluate the security of those ciphers in resistance to(fast) algebraic attacks,the authors need to characterize algebraic properties of Tr(λx^(-1)).However,currently only some bounds on algebraic immunity of Tr(λx^(-1)) are given in the public literature,for example,the NGG upper bound and the Bayev lower bound,etc.This paper gives the exact value of the algebraic immunity of Tr(λx^(-1)) over F_(2~n),that is,AI(Tr(λx^(-1))) =[2n^(1/2)]- 2,where n ≥ 2,A ∈ F_(2~n) and λ≠ 0,which shows that Dalai's conjecture on the algebraic immunity of Tr(λx^(-1)) is correct.What is more,the authors demonstrate some weak properties of Tr(λx^(-1)) against fast algebraic attacks.展开更多
Algebraic immunity is an important cryptographic property of Boolean functions. The notion of algebraic immunity of Boolean functions has been generalized in several ways to vector-valued functions over arbitrary fini...Algebraic immunity is an important cryptographic property of Boolean functions. The notion of algebraic immunity of Boolean functions has been generalized in several ways to vector-valued functions over arbitrary finite fields. In this paper, the results of Ref. [25] are generalized to arbitrary finite fields. We obtain vector-valued functions over arbitrary finite fields such that their algebraic immunities can reach the upper bounds. Furthermore, all the component functions, together with their some nonzero linear combinations, of vector-valued Boolean functions achieved by this construction have optimal algebraic immunities simultaneously.展开更多
基金This work was supported by the National Natural Science Foundation of China under Grants No. 61103191, No. 61070215 the Funds of Key Lab of Fujian Province University Network Security and Cryptology under Crant No. 2011003 and the Open Research Fund of State Key Laboratory of Inforrmtion Security.
文摘To protect against algebraic attacks, a high algebraic immunity is now an important criterion for Boolean functions used in stream ciphers. In this paper, a new method based on a univariate polynomial representation of Boolean functions is proposed. The proposed method is used to constmct Boolean functions with an odd number of variables and with maximum algebraic immunity. We also discuss the nonlinearity of the constructed functions. Moreover, a lower bound is deter- mined for the number of Boolean functions with rmximum algebraic immunity.
基金supported by the National Natural Science Foundations of China under Grant Nos. 60903200,61003299
文摘This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in associative classes. For some n, a part of 1-resilient functions with maximum algebraic immunity constructed in the paper can achieve almost optimal nonlinearity. Apart from their high nonlinearity, the functions reach Siegenthaler＇s upper bound of algebraic degree. Also a class of l-resilient functions on any number n 〉 2 of variables with at least sub-optimal algebraic immunity is provided.
基金supported by the Major State Basic Research Development Program of China (Grant No.2004CB3180004)National Natural Science Foundation of China (Grant No. 60433050)
文摘All (2m +1)-variable symmetric Boolean functions with submaximal algebraic immunity 2m-1 are described and constructed. The total number of such Boolean functions is 32 ·22m-3 +3m-2 · 24 - 2 for m≥2.
基金Supported by the National Natural Science Foundation of China(Grant No.60573028)the Open Founds of Key Lab of Fujian Province University Network Security and Cryptology(Grant No. 07A003)the Basic Research Foundation of National University of Defense Technology(Grant No.JC07-02-03)
文摘The properties of the 2m-variable symmetric Boolean functions with maximum al- gebraic immunity are studied in this paper. Their value vectors, algebraic normal forms, and algebraic degrees and weights are all obtained. At last, some necessary conditions for a symmetric Boolean function on even number variables to have maximum algebraic immunity are introduced.
基金Supported by the National Natural Science Foundation of China ( 60603012)the Foundation of Hubei Provincial Department of Education, China (D200610004)
文摘For an odd integer n ≥ 7, this paper presented a class of n-variable rotation symmetric Boolean functions （RSBFs） with optimum algebraic immunity. The nonlinearity of the constructed functions is determined.
基金supported by National Natural Science Foundation of China (Grant Nos.10971246, 60970152)
文摘Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d = n1 +2 their nonlinearities equalthe minimum of ∑d-1 i=0 (ni) and ∑ d-1 i=0 (ni). Lastly, we identify two classes of such functions, one having algebraic degree of n or n-1.
基金Supported by the National Natural Science Foundation of China (Grant No. 60673068)the Natural Science Foundation of Shandong Province (Grant Nos. Y2007G16, Y2008G01)
文摘Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of two bits, and then generalizing the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions with maximum algebraic immunity are constructed. Enumeration of such functions is also n given. For a given function p（x） with deg（p（x）） 〈 [n/2], we give a method to construct functions in the form p（x）＋q（x） which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q（x） has degree no less than [n/2].
基金supported by the National Key Research and Development Program of China under Grant No.2016YFB0800401
文摘Boolean functions with optimal algebraic immunity(OAI functions) are important cryptographic primitives in the design of stream ciphers. During the past decade, a lot of work has been done on constructing such functions, among which mathematics, especially ?nite ?elds, play an important role. Notably, the approach based on decompositions of additive or multiplicative groups of?nite ?elds turns out to be a very successful one in constructing OAI functions, where some original ideas are contributed by Tu and Deng(2012), Tang, et al.(2017), and Lou, et al.(2015). Motivated by their pioneering work, the authors and their collaborators have done a series of work, obtaining some more general constructions of OAI functions based on decompositions of ?nite ?elds. In this survey article, the authors review our work in this ?eld in the past few years, illustrating the ideas for the step-by-step generalizations of previous constructions and recalling several new observations on a combinatorial conjecture on binary strings known as the Tu-Deng conjecture. In fact, the authors have obtained some variants or more general forms of Tu-Deng conjecture, and the optimal algebraic immunity of certain classes of functions we constructed is based on these conjectures.
基金supported by the National Basic Research Program of China under Grant No.2011CB302400
文摘This paper first proposes an infinite class of 2k-variable Boolean functions with high nonlinearity and high algebraic degree. Then an infinite class of balanced Boolean functions are proposed by modifying the above Boolean functions. This class of balanced Boolean functions have optimal algebraic degree and high nonlinearity. Both classes have optimal algebraic immunity based on a general combinatorial conjecture.
基金Supported by the National Natural Science Foundation of China(61272434)the Natural Science Foundation of Shandong Province(ZR 2012FM004,ZR2013FQ021)the Foundation of Science and Technology on Information Assume Laboratory(KJ-13-004)
文摘Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents one main result to find balanced rotation symmetric Boolean functions with maximum algebraic immunity. Through swapping the values of two orbits of rotation class of the majority function, a class of 4k＋l variable Boolean functions with maximum algebraic immu- nity is constructed. The function f（x） we construct always has terms of degree n-2 independence of what ever n is. And the nonlinearity off（x） is relatively good for large n.
基金supported by the National Natural Science Foundation of China under Grant Nos.61070172 and 10990011the Strategic Priority Research Program of Chinese Academy of Sciences under Grant No. XDA06010702the State Key Laboratory of Information Security,Chinese Academy of Sciences
文摘Boolean functions used in a cryptographic system should have high algebraic immunity to resist algebraic attacks. This paper presents a matrix method for constructing balanced Boolean functions achieving maximum algebraic immunity.
基金supported by the National Natural Science Foundation of China (61102093, 61170270, 61121061)The Fundamental Research for the Central Universities (BUPT 2012RC0710)
文摘Algebraic immunity is an important cryptographic property of Boolean functions. In this paper, odd-variable balanced Boolean functions with optimal algebraic immunity are obtained by m-sequence and consequently, we get bases with special constructions of vector space. Furthermore, through swapping some vectors of these two bases, we establish all kinds of odd-variable balanced Boolean functions with optimal algebraic immunity.
基金supported by National Basic Research Program of China under Grant No.2011CB302400
文摘Tu and Deng proposed a class of bent functions which are of optimal algebraic immunity under the assumption of a combinatorial conjecture.In this paper,the authors compute the dual of the Tu-Deng functions and then show that they are still of optimal algebraic immunity under the assumption of the same conjecture.For another class of Boolean functions constructed by Tang,et al.which are of optimal algebraic immunity with similar forms to Tu-Deng functions,the authors show that they are not bent functions by using some basic properties of binary complete Kloosterman sums.
基金supported by the National Natural Science Foundation of China under Grant No.61572491the 973 Program under Grant No.2011CB302401the open project of the SKLOIS in Institute of Information Engineering,Chinese Academy of Sciences under Grant No.2015-MS-03
文摘The trace inverse functions Tr(λx^(-1)) over the finite field F_(2~n) are a class of very important Boolean functions and are used in many stream ciphers such as SFINKS,RAKAPOSHI,the simple counter stream cipher(SCSC) presented by Si W and Ding C(2012),etc.In order to evaluate the security of those ciphers in resistance to(fast) algebraic attacks,the authors need to characterize algebraic properties of Tr(λx^(-1)).However,currently only some bounds on algebraic immunity of Tr(λx^(-1)) are given in the public literature,for example,the NGG upper bound and the Bayev lower bound,etc.This paper gives the exact value of the algebraic immunity of Tr(λx^(-1)) over F_(2~n),that is,AI(Tr(λx^(-1))) =[2n^(1/2)]- 2,where n ≥ 2,A ∈ F_(2~n) and λ≠ 0,which shows that Dalai's conjecture on the algebraic immunity of Tr(λx^(-1)) is correct.What is more,the authors demonstrate some weak properties of Tr(λx^(-1)) against fast algebraic attacks.
基金supported by National Natural Science Foundation of China(60873191,60903152,61003286,60821001)
文摘Algebraic immunity is an important cryptographic property of Boolean functions. The notion of algebraic immunity of Boolean functions has been generalized in several ways to vector-valued functions over arbitrary finite fields. In this paper, the results of Ref. [25] are generalized to arbitrary finite fields. We obtain vector-valued functions over arbitrary finite fields such that their algebraic immunities can reach the upper bounds. Furthermore, all the component functions, together with their some nonzero linear combinations, of vector-valued Boolean functions achieved by this construction have optimal algebraic immunities simultaneously.
