Invariance of Algebraic Immunity of Vectorial Boolean Functions under Equivalence Relations

摘要

Both of algebraic immunity and equivalence relations are of great cryptographic significance. But there are few researches on the properties of algebraic immunity of vectorial Boolean functions under equivalence relations. This paper defines three new notions, which are degree-rank, basic-algebraic-immunity-rank-set and component-algebraic-immunity-rank-set. This paper proves that the degree-rank of the graph of a function for any degree is Carlet-Charpin-Zinoviev (CCZ) equivalence invariant, the basic-algebraic-immunity-rank-set is affine equivalence invariant and the component-algebraic-immunity-rank-set is also affine equivalence invariant. Based on these analyses, this paper finds that the graph algebraic immunity is CCZ equivalence invariant, both of basic algebraic immunity and component algebraic immunity are affine equivalence invariant. This paper also finds that neither the basic algebraic immunity (basic-algebraic-immunity-rank-set) nor the component algebraic immunity (component-algebraic-immunity-rank-set) is extended affine equivalence invariant. It is also shown that the component algebraic immunity for a permutation is not invariant under inverse transformation. Last but not least, this paper investigates the graph algebraic immunity and the component algebraic immunity of optimal 4-bit permutations of all the affine equivalence classes.