Fast Algebraic Immunity Of Rotationally Symmetric Boolean Functions

Modern Cryptography can be classified as Asymmetric Cryptography and Symmetric Cryptography according to their keys, and Symmetric Cryptography can be classified as block cyphers and stream cyphers. This paper will discuss the property of the nonlinear part of stream cyphers——Boolean functions. Boolean functions is the key component of stream cyphers, which means, their cryptographic properties will directly influence the security of the whole cypher system. In order to judge the safety of Boolean functions, lots of Boolean functions’ properties are introduced and researched recently. Algebraic Immunity and Fast Algebraic Immunity are proposed to measure the capability of Boolean functions being against Algebraic Attacks and Fast Algebraic Attacks. If the Algebraic Immunity of an n-variable Boolean function achieves optimum [n/2] and its Fast Algebraic Immunity achieves optimum n, we call it an AAR (Algebraic Attack Resistant) function. According to the definitions of Algebraic Immunity and Fast Algebraic Immunity, AAR functions will have the best abilities to be against Algebraic Attacks and Fast Algebraic Attacks. However, AAR is hard to achieve. Rotation Symmetric Boolean functions are a class of Boolean functions which have simple structures and some interesting properties, they are concerned and researched widely. It is significant to research the properties of Rotation Symmetric Boolean functions. In this paper, we researched the Algebraic Normal Form and Simple Algebraic Normal Form, and we get conclusions that, several classes of Rotation Symmetric Boolean functions cannot achieve the optimum Fast Algebraic Immunity, which means, they are not AAR functions. This conclusion has important implications for both research and application of Boolean functions and stream cyphers.