一种代数正规形快速变换的零化子算法

Research on finding annihilators of Boolean functions based the algebraic normal form fast transformations

利用布尔函数代数正规形的性质提出一种代数正规形快速变换和计算方法,该方法具有最小的存储空间和很高的计算效率.以此为基础,提出两种计算布尔函数零化子的有效算法:第1种算法可以求出所有n元布尔函数的代数免疫阶数和最低次零化子的代数正规形表达式;第2种算法能够求出任意一个n元平衡布尔函数代数免疫阶数和所有不超过d次的零化子.同已有基于求解线性同余方程组的零化子求解算法相比,该方法可操作性强,能够更加有效地用于评估布尔函数抵抗代数攻击的强度.

The algebraic normal form fast transfermations （ANFFTs） and computing methods are proposed by using the properties of Boolean Function＇s algebraic normal form, which has the smallest memory and higher efficiency. Under the previous assumption, two efficient algorithms for computing the annihilators of Boolean functions are presented. The first algorithm can be used to find the algebraic immunity of Boolean functions on n-variables and the algebraic normal form of the annihilators with the lowest algebraic degree. The second algorithm can be used to compute the algebraic immunity of a balanced Boolean functions on n-variables and its annihilators which have the algebraic degree~ d. Compared with the algorithms for computing the annihilators by solving linear congruential equations, these methods are highly operable and can be used to assess more effectively the resistance of Boolean functions against algebraic attacks.