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

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

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

李雪莲¹,胡予濮²

(1. 西安电子科技大学理学院，陕西西安 710071;
2. 西安电子科技大学计算机网络与信息安全教育部重点实验室，陕西西安 710071)

收稿日期:2008-06-17 出版日期:2009-08-20 发布日期:2009-09-28
通讯作者: 李雪莲
基金资助:
973项目资助(2007CB311201);国家自然科学基金资助(60833008,60803149);广西信息与通信技术重点实验室资助(20902)

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

摘要/Abstract

摘要：

代数免疫度是衡量布尔函数抵抗代数攻击的重要性能指标，具有低代数免疫度的布尔函数是不能抵抗代数攻击的．利用分拆布尔函数的方法证明了如下结论: (1)对于对称布尔函数，即使它们具有高代数免疫度，如果使用不当仍然不能抵抗新型代数攻击; (2)对于由旋转对称函数和低次布尔函数的直和构成的布尔函数即便具有高代数免疫度，如果使用不当，也会受到新型代数攻击．提出的代数攻击需要一段连续的密钥流．

关键词: 流密码, 代数免疫度, 对称布尔函数, 旋转对称布尔函数

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

中图分类号:

TN918.1

李雪莲;胡予濮. 对具有高代数免疫度布尔函数的新型代数攻击[J]. J4, 2009, 36(4): 702-707.

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

参考文献

［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]	牛志华;李政;李哲;辛明军. 2ⁿ周期优秀二元序列生成及其特性分析[J]. J4, 2014, 41(1): 130-134.
[2]	赵永斌;胡予濮;贾艳艳. 一种抵抗能量攻击的线性反馈移位寄存器[J]. J4, 2013, 40(3): 172-179+200.
[3]	杜小妮1;2;陈智雄1;3;陈汝伟1;肖国镇1. 一类新的6次剩余序列的自相关函数 [J]. J4, 2007, 34(4): 642-646.
[4]	杜小妮1;2;陈智雄1;3;陈汝伟1;肖国镇1. 一类新的6次剩余序列的自相关函数 [J]. J4, 2007, 34(4): 642-646.
[5]	闫统江(1;2);范凯(1);杜小妮(1;3);肖国镇(1). 二元W-广义割圆序列的线性复杂度[J]. J4, 2006, 33(4): 617-621.
[6]	牛志华;董庆宽;肖国镇. pⁿ-周期二元序列的线性复杂度与k-错线性复杂度[J]. J4, 2004, 31(4): 622-625.
[7]	王尚平;高虎明;王育民. GF(2)上伪随机序列s∞与-s∞的复杂性分析[J]. J4, 2002, 29(1): 67-71.
[8]	杨礼珍;傅晓彤;肖国镇. 对非线性组合生成器的相关攻击[J]. J4, 2001, 28(5): 566-569.
[9]	许春香;魏仕民;肖国镇. 关于周期序列的线性复杂度[J]. J4, 2001, 28(4): 434-438.
[10]	魏仕民;董庆宽;肖国镇. 确定周期序列k-错线性复杂度的一个快速算法[J]. J4, 2001, 28(4): 421-425.
[11]	胡予濮;白国强;肖国镇. GF(q)上的广义自缩序列[J]. J4, 2001, 28(1): 5-8.
[12]	胡予濮;肖国镇;杨礼珍. 非齐进位模加群及其在密码体制中的应用[J]. J4, 1999, 26(4): 428-431.
[13]	暂时无作者信息. 关于非线性组合序列的稳定性[J]. J4, 1998, 25(1): 0-0.
[14]	暂时无作者信息. 广义e-bent函数[J]. J4, 1997, 24(2): 0-0.
[15]	暂时无作者信息. m阶相关免疫函数的构造与计数[J]. J4, 1997, 24(1): 0-0.