Construction On Annihilators Of Boolean Functions And Analysis Of Algebraic Immunity Of Symmetric Boolean Functions

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 2^n-1 - 4, but lower algebraic immunity ≤ 2.