对具有高代数免疫度布尔函数的新型代数攻击

J4 ›› 2009, Vol. 36 ›› Issue (4): 702-707.

• Original Articles • Previous Articles Next Articles

Algebraic attack on symmetric Boolean functions with a high algebraic immunity

LI Xue-lian¹;HU Yu-pu²

(1. School of Science, Xidian Univ., Xi'an 710071， China;
2. Ministry of Education Key Lab. of Computer Network and Information Security, Xidian Univ., Xi'an 710071， China)

Received:2008-06-17 Online:2009-08-20 Published:2009-09-28
Contact: LI Xue-lian E-mail:xlli@mail.xidian.edu.cn

Abstract

Abstract:

Algebraic immunity is an important index to measure the ability to resist algebraic attacks. If a Boolean function has a low algebraic immunity, then it can not resist the algebraic attack. This paper gives two conclusions on some Boolean functions with a high algebraic immunity, that is, 1) for most of symmetric Boolean functions with a high algebraic immunity, if they are used inappropriately, then the attacker still can launch an efficient algebraic attack; 2)our algebraic attack is still efficient for a more general class of Boolean functions with a high algebraic immunity, which consists of a rotation symmetric Boolean function and a Boolean function with a low degree. Our algebraic attack requires a segment of the consecutive bitstream.

Key words: stream ciphers, algebraic immunity, symmetric Boolean function, rotation symmetric Boolean function

CLC Number:

TN918.1

LI Xue-lian;HU Yu-pu. Algebraic attack on symmetric Boolean functions with a high algebraic immunity[J].J4, 2009, 36(4): 702-707.

References

［1］高军涛，胡予濮，李雪莲. 对自缩序列生成器的错误攻击［J］. 西安电子科技大学学报, 2006, 23(5): 809-813.
Gao Juntao, Hu Yupu, Li Xuelian. Fault Analysis for Self-shrinking Generator［J］. Journal of Xidian University, 2006, 23(5): 809-813.
［2］Courtois N, Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback［C］//Advances in Cryptology-Eurocrypt 2003, LNCS 2656. Berlin: Springer-Verlag, 2003: 345-359.
［3］Li N, Qi W F. Symmetric Boolean Function with Maximum Algebraic Immunity Depending on an Odd Number of Variables ［J］. IEEE Trans on Information Theory, 2006, 52(5): 2271-2273.
［4］Li N, Qu L J, Qi W F. On the Construction of Boolean Functions with Optimal Algebraic Immunity［J］. IEEE Trans on Information Theory, 2008, 54(3): 1330-1334.
［5］Braeken A, Preneel B. On the Algebraic Immunity of Symmetric Boolean Functions［C］//Proc Indocrypt 2005, LNCS 3797. Berlin: Springer-Verlag, 2005: 35-48.
［6］Armknecht F, Krause M. Algebraic Attacks on Combiners with Memory［C］//Advances in Cryptography-Crypto 2003, LNCS 2729. Berlin: Springer-Verlag, 2003: 162-175.
［7］Dalai D K, Maitra S. Reducing the Number of Homogeneous Linear Equations in Finding Annihilators［C］//Sequences and Their Applications-SETA 2006, LNCS 4086. Berlin: Springer-Verlag, 2006: 376-390.
［8］Gupta D K, Maitra K C. Cryptographically Significant Boolean Functions: Construction and Analysis in Terms of Algebraic Immunity［C］//FSE 2005, LNCS 3557. Berlin: Springer-Verlag, 2005: 98-111.
［9］Dalai D K, Maitra S, Sarkar S. Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity ［J］. Design, Codes and Cryptography, 2006, 40(1): 41-58.
［10］Sarkar S, Maitra S. Construction of Rotation Symmetric Boolean Functions on Odd Number of Variables with Maximum Algebraic Immunity［C］//AAECC2007, LNCS 4851. Berlin: Springer-Verlag, 2007: 271-280.
［11］Canteaut A, Videau M. Symmetric Boolean Functions［J］. IEEE Trans on Information Theory, 2005, 51 (8): 2791-2811.
［12］Stanica P, Maitra S. Rotation Symmetric Boolean Functions: Count and Cryptographic Properties ［EB/OL］. ［2007-04-29］. http://dx.doi.org/10.1016/j.dam.

[1]	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.
[2]	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.

Algebraic attack on symmetric Boolean functions with a high algebraic immunity

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Metrics

Comments

Recommended 0