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.展开更多
In this paper, we study Boolean functions of an odd number of variables with maximum algebraic immunity. We identify three classes of such functions, and give some necessary conditions of such functions, which help to...In this paper, we study Boolean functions of an odd number of variables with maximum algebraic immunity. We identify three classes of such functions, and give some necessary conditions of such functions, which help to examine whether a Boolean function of an odd number of variables has the maximum algebraic immunity. Further, some necessary conditions for such functions to have also higher nonlinearity are proposed, and a class of these functions are also obtained. Finally, we present a sufficient and necessary condition for Boolean functions of an odd number of variables to achieve maximum algebraic immunity and to be also 1-resilient.展开更多
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.展开更多
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].展开更多
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.
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.展开更多
基金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.
基金the National Natural Science Foundation of China (Grant No. 60673081)the "863" project (Grant No. 2006AA01Z417)
文摘In this paper, we study Boolean functions of an odd number of variables with maximum algebraic immunity. We identify three classes of such functions, and give some necessary conditions of such functions, which help to examine whether a Boolean function of an odd number of variables has the maximum algebraic immunity. Further, some necessary conditions for such functions to have also higher nonlinearity are proposed, and a class of these functions are also obtained. Finally, we present a sufficient and necessary condition for Boolean functions of an odd number of variables to achieve maximum algebraic immunity and to be also 1-resilient.
基金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 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 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 ( 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.
