On designated-weight Boolean functions with highest algebraic immunity  

作　　者：LIU MeiCheng1,3, DU YuSong2, PEI DingYi2 & LIN DongDai1 1The State Key Laboratory of Information Security, Institute of Software of Chinese Academy of Sciences, Beijing 100190, China 2College of Mathematics and Information Sciences, Guangzhou University, Guangzhou 510006, China 3Graduate University of Chinese Academy of Sciences, Beijing 100049, China 

出　　处：《Science China Mathematics》2010年第11期2847-2854,共8页中国科学：数学（英文版）

基　　金：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.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.

关 键 词：CRYPTOGRAPHY BOOLEAN function ALGEBRAIC IMMUNITY ALGEBRAIC degree NONLINEARITY 

分 类 号：O153.2[理学—数学]