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

Abstract

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

CLC Number:

TN918.1

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.

References

［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]	LUO Fang;ZHOU Xueguang;OU Qingyu. Cryptanalysis of the LBlock using multiple zero-correlation linear approximations [J]. J4, 2014, 41(5): 173-179.
[2]	LIU Jingmei;WANG Yanli;LIANG Bin;ZHAO Senlin. Attack method against the McEliece cryptosystem based on the correlative quasic-cyclic codes set [J]. J4, 2014, 41(2): 15-19+50.
[3]	ZHAO Yongbin;HU Yupu;JIA Yanyan. New design of LFSR based stream ciphers to resist power attack [J]. J4, 2013, 40(3): 172-179+200.
[4]	SUN Jin;HU Yupu. Fully secure attribute-based broadcast encryption [J]. J4, 2012, 39(4): 23-28+154.
[5]	XIAO Heling;CAI Ning;WANG Xiao. Application of quantum LDPC codes to quantum key distribution [J]. J4, 2012, 39(2): 8-11+23.
[6]	LI Xue-lian;HU Yu-pu. Algebraic attack on symmetric Boolean functions with a high algebraic immunity [J]. J4, 2009, 36(4): 702-707.
[7]	ZHANG Chuan-rong;ZHANG Yu-qing. Provable security signcryption scheme and its hybrid construction [J]. J4, 2009, 36(4): 756-760.
[8]	WANG Xin1;SUN Chen2;WANG Xin-mei1. Equivalent keys of multivariate quadratic public key cryptosystem [J]. J4, 2009, 36(3): 428-432.

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

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 8

Metrics

Comments

Recommended 0