| Using the concept of Boolean functions and combinatorics theory comprehensively, we investigate the construction on annihilators of Boolean functions and the algebraic immunity of symmetric Boolean functions in cryptography:Firstly, we introduce two methods of constructing the annihilators of Boolean functions, Construction I makes annihilators based on the minor term expression of Boolean function, meanwhile we get a way to judge whether a Boolean function has low degree annihilators by feature matrix. In Construction II, we use the subfunctions to construct annihilators, we also apply Construction II to LILI-128 and Toyocrypt, and the attacking complexity is reduced greatly. We study the algebraic immunitiy of (5,1,3,12) rotation symmetric staturated best functions and a type of constructed functions, then we prove that a new class of functions are invariants of algebraic attacks, and this property is generalized in the end.Secondly, we present a construction on symmetric annihilators of symmetric Boolean functions. We find the difference between the minimum annihilator degree md(f) and the minimum symmetric annihilator degree mds(f) is at most 1 under some condition. We also study some properties of elementary symmetric Boolean functions, and we get the upper bound of elementary symmetric Boolean function σd of n-d+1, then we show that if the ANF of symmetric Boolean functions don't have terms σ4k, the algebraic immunity will ≤ 3. Finally, we construct a symmetric Boolean function with higher nonlinearity of 2n-1 - 4, but lower algebraic immunity ≤ 2. |
