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

J4 ›› 2009, Vol. 36 ›› Issue (5): 890-895.

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

刘福运;肖鸿;肖国镇

(西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071)

收稿日期:2009-02-09 出版日期:2009-10-20 发布日期:2009-11-30
通讯作者: 刘福运
基金资助:
国家自然科学基金资助(60603010);国家“973”项目资助(2007CB311201);国家自然科学基金资助(60673068)

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

LIU Fu-yun;XIAO Hong;XIAO Guo-zhen

(State Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an 710071， China)

Received:2009-02-09 Online:2009-10-20 Published:2009-11-30
Contact: LIU Fu-yun

摘要/Abstract

摘要：

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

关键词: 代数攻击, 布尔函数, 代数正规形快速变换, 零化子, 代数免疫

Abstract:

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.

Key words: algebraic attacks;Boolean functions;algebraic normal form fast transformations;annihilators;algebraic immunity

中图分类号:

TN918.1

刘福运;肖鸿;肖国镇. 一种代数正规形快速变换的零化子算法[J]. J4, 2009, 36(5): 890-895.

LIU Fu-yun;XIAO Hong;XIAO Guo-zhen. Research on finding annihilators of Boolean functions based the algebraic normal form fast transformations[J]. J4, 2009, 36(5): 890-895.

参考文献

［1］Courtois N, Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback［C］//Advances in Cryptology-EUROCRYPT 2003, Number 2656 in Lecture Notes in Computer Science. Berlin: Springer Verlag, 2003: 345-359.
［2］Carlet C, Dalai D, Gupta K, et al. Algebraic Immunity for Cryptographically Significant Boolean Functions: Analysis and Construction［J］. IEEE Trans on Information Theory, 2006, 52(7): 3105-3121.
［3］Armknecht F. Improving Fast Algebraic Attacks［C］//FSE 2004, Number 3017 in Lecture Notes in Computer Science. Berlin: Springer Verlag, 2004: 65-82.
［4］Braeken A, Lano J, Preneel B. Evaluating the Resistance of Filtersand Combiners Against Fast Algebraic Attacks［EB/OL］. ［2008-12-20］. http://eprint.iacr.org, 2005/276
［5］Sun Bin, Qu Longjiang, Li Chao. New Cryptanalysi of Block Cipher with Low Algebraic Degree［C］//FSE 2009, Lecture Notes in Computer Science. Berlin: Springer Verlag, 2009: 183-195.
［6］Albrecht M, Cid C. Algebraic Techniques in Differential Cryptanalysi［C］//FSE 2009, Lecture Notes in Computer Science. Berlin: Springer Verlag, 2009: 196-210.
［7］陈杰, 胡予濮, 韦永壮. 一种快速构造降次函数的新算法［J］. 西安电子科技大学学报, 2005, 32(5): 790-793.
Chen Jie, Hu Yupu, Wei Yongzhuang. A New Algorithm for Constructing Depressed Functions［J］.Journal of Xidian University, 2005, 32(5): 790-793.
［8］Qu L J, Li C, Feng K Q. A Note Symmetric Boolean Functions with Maximum Algebraic Immunity on Odd Number of Variables［J］. IEEE Trans on Information Theory, 2007, 53(8): 2908-2910.
［9］Dalai D K, Maitra S. Reducing the Number of Homogeneous Linear Equations in Finding Annihilators［C］//Sequences and Their Applications—SETA2006, LNCS, 4086. Heidelberg: Springer, 2006: 376-390.
［10］Armknecht F, Carlet C, Gaborit P, et al. Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks［C］//The Proceedings of EUROCRYPT 2006, LNCS 3029. Berlin: Springer, 2006: 274-290.
［11］Armknecht F. On the Existence of Low-degree Equations for Algebraic Attacks［EB/OL］. ［2008-12-20］. http://eprint.iacr.org, 2004/185.

[1]	冯登国. 浅析Xiao-Massey定理的意义和作用[J]. 西安电子科技大学学报, 2021, 48(1): 7-13.
[2]	周宇,陈智雄,卓泽朋,杜小妮. (n,m)函数抗差分功耗攻击指标的研究综述[J]. 西安电子科技大学学报, 2021, 48(1): 50-60.
[3]	张冬阳;张建奇. 面向三角靶标的人眼对比度阈值特性实验表征[J]. 西安电子科技大学学报, 2016, 43(6): 91-96.
[4]	赵永斌;胡予濮;贾艳艳. 一种抵抗能量攻击的线性反馈移位寄存器[J]. J4, 2013, 40(3): 172-179+200.
[5]	何业锋;马文平. 一类具有高非线性度的密码函数[J]. J4, 2010, 37(6): 1107-1110.
[6]	李雪莲;胡予濮. 对具有高代数免疫度布尔函数的新型代数攻击[J]. J4, 2009, 36(4): 702-707.
[7]	陈杰;胡予濮;韦永壮. 一种快速构造降次函数的新算法[J]. J4, 2005, 32(5): 790-793.
[8]	刘景伟;韦宝典;吕继强;王新梅. AES S盒的密码特性分析[J]. J4, 2004, 31(2): 255-259.
[9]	郑连清1;张串绒1;2;董庆宽2;傅晓彤2;肖国镇2. 布尔函数非线性度界的问题[J]. J4, 2003, 30(2): 281-283.
[10]	谷大武;李继红;肖国镇. 基于正形置换的密码函数的构造[J]. J4, 1999, 26(1): 0-0.
[11]	暂时无作者信息. m阶相关免疫函数的构造与计数[J]. J4, 1997, 24(1): 0-0.