代数免疫度最优的旋转对称布尔函数的构造

《代数免疫度最优的旋转对称布尔函数的构造》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第３４卷第２期国防科技大学学报Ｖｏｌ．３４Ｎｏ．２２０１２年４月ＪＯＵＲＮＡＬＯＦＮＡＴＩＯＮＡＬＵＮＩＶＥＲＳＩＴＹＯＦＤＥＦＥＮＳＥＴＥＣＨＮＯＬＯＧＹＡｐｒ．２０１２代数免疫度最优的旋转对称布尔函数的构造１，２１２李超，薛朝红，付绍静（１．国防科技大学理学院，湖南长沙４１００７３；２．国防科技大学计算机学院，湖南长沙４１００７３）摘要：代数免疫度是布尔函数的一个重要密码学指标，为了抵挡代数攻击，密码算法中所使用的布尔函数应当具有较高的代数免疫度。本文利用“轨道交换”技术，给出了一类具有最优代数免疫度的旋转对称布尔函数的构造，该类函数对于代数攻击具有较强的抵抗能力，同时具有较高的

2、非线性度和最优代数次数。关键词：代数免疫度；旋转对称；非线性度；代数次数中图分类号：ＴＮ９１８１文献标志码：Ａ文章编号：１００１－２４８６（２０１２）０２－００３４－０５ＣｏｎｓｔｒｕｃｔｉｏｎｏｆｒｏｔａｔｉｏｎｓｙｍｍｅｔｒｉｃＢｏｏｌｅａｎｆｕｎｃｔｉｏｎｗｉｔｈｍａｘｉｍｕｍａｌｇｅｂｒａｉｃｉｍｍｕｎｉｔｙ１，２１２ＬＩＣｈａｏ，ＸＵＥＣｈａｏｈｏｎｇ，ＦＵＳｈａｏｊｉｎｇ（１．ＣｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅ，ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ；２．ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ，Ｎａｔ

3、ｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＡｌｇｅｂｒａｉｃＩｍｍｕｎｉｔｙｈａｓｂｅｅｎｃｏｎｓｉｄｅｒｅｄａｓｏｎｅｏｆｓｉｇｎｉｆｉｃａｎｔｃｒｙｐｔｏｇｒａｐｈｉｃｐｒｏｐｅｒｔｉｅｓｆｏｒＢｏｏｌｅａｎｆｕｎｃｔｉｏｎｓ．Ｉｎｏｒｄｅｒｔｏｒｅｓｉｓｔａｌｇｅｂｒａｉｃａｔｔａｃｋ，ｈｉｇｈａｌｇｅｂｒａｉｃｉｍｍｕｎｉｔｙｉｓｎｅｃｅｓｓａｒｙｆｏｒｔｈｏｓｅＢｏｏｌｅａｎｆｕｎｃｔｉｏｎｓｕｓｅｄｉｎｓｙｍｍｅｔｒｉｃｃｉｐｈｅｒａｌｇｏｒｉｔｈｍｓ．Ｂａｓｅｄｏｎ“ｏｒｂｉｔｅｘｃｈ

4、ａｎｇｅ”ｔｅｃｈｎｉｑｕｅ，ｔｈｉｓｒｅｓｅａｒｃｈｐｒｅｓｅｎｔｓａｃｏｎｓｔｒｕｃｔｉｏｎｏｆｒｏｔａｔｉｏｎｓｙｍｍｅｔｒｉｃＢｏｏｌｅａｎｆｕｎｃｔｉｏｎｓｗｉｔｈｔｈｅｍａｘｉｍｕｍａｌｇｅｂｒａｉｃｉｍｍｕｎｉｔｙｏｎｅｖｅｎｎｕｍｂｅｒｏｆｖａｒｉａｂｌｅｓ．Ｔｈｅｓｅｆｕｎｃｔｉｏｎｓｈａｖｅｓｔｒｏｎｇｒｅｓｉｓｔａｎｃｅａｇａｉｎｓｔａｌｇｅｂｒａｉｃａｔｔａｃｋｓ．Ｔｈｅｓｅｆｕｎｃｔｉｏｎｓａｌｓｏｈａｖｅｍｕｃｈｂｅｔｔｅｒｎｏｎｌｉｎｅａｒｉｔｙａｎｄｏｐｔｉｍａｌａｌｇｅｂｒａｉｃｄｅｇｒｅｅ．Ｋｅｙｗｏｒｄｓ：ａｌｇｅｂｒａｉｃｉｍｍｕｎｉｔｙ；ｒｏｔ

5、ａｔｉｏｎｓｙｍｍｅｔｒｉｃ；ｎｏｎｌｉｎｅａｒｉｔｙ；ａｌｇｅｂｒａｉｃｄｅｇｒｅｅ代数攻击的提出和发展被认为是近年来密码ｘｉ＋ｋ，如果ｉ＋ｋ≤ｎ，ｋρｎ（ｘｉ）＝{分析技术最重要的突破之一，代数免疫度也成为ｘ，其他．ｉ＋ｋ－ｎ衡量密码函数安全性的一个重要指标，如何构造ｋｎρｎ的定义可以推广到向量ｘ＝（ｘ１，ｘ２，…，ｘｎ）∈Ｆ２代数免疫度最优的函数（简称ＭＡＩ函数）已经成ｋｋｋｋ［１－９］上，ρｎ（ｘ１，ｘ２，…，ｘｎ）＝（ρｎ（ｘ１），ρｎ（ｘ２），…，ρｎ为近年来研究的一个重点问题。旋转对称布（ｘｎ））．尔函数（简称ＲｏｔＳ函数）由于其良好的结构特性，在密码学中有着广泛的应用，

6、因而构造代数免疫定义１如果对于任意的ｘ＝（ｘ１，ｘ２，…，ｘｎ）ｎ度最优且具有其他良好密码学性质的ＲｏｔＳ函数∈Ｆ２，以及０≤ｋ≤ｎ－１，都有ｋ具有重要意义。文献［１０］给出了一种代数免疫ｆ（ρｎ（ｘ１，ｘ２，…，ｘｎ））＝ｆ（ｘ１，ｘ２，…，ｘｎ）度最优的ＲｏｔＳ函数的构造方法，本文利用“轨道则称ｆ（ｘ１，ｘ２，…，ｘｎ）为旋转对称布尔函数。交换”技术，构造了一类代数免疫度最优的ＲｏｔＳ记Ｇ（ｘ，ｘ，…，ｘ）＝｛ρｋ（ｘ，ｘ，…，ｘ）ｎ１２ｎｎ１２ｎ函数，并给出了所构造函数的非线性度下界，与文０≤ｋ≤ｎ－１}，即（ｘ１，ｘ２，…，ｘｎ）在ρｎ作用下的献［１０］中结果相比，构造函数的非

7、线性度得到了ｎ轨道。显然Ｆ２中的所有向量被分为不同的轨道，一定提升，同时代数次数达到最优。如果Ｇｎ（ｘ１，ｘ２，…，ｘｎ）＝ｔ，称Ｇｎ（ｘ１，ｘ２，…，ｘｎ）１预备知识是一个ｔ－轨道，容易验证ｔ是ｎ的一个因子。对于ｘｉ∈Ｆ２（１≤ｉ≤ｎ），以及０≤ｋ≤ｎ－１，记ｘ珋＝（ｘ１＋１，ｘ２＋１，…，ｘｎ＋１），易知Ｇｎ（ｘ珋）定义＝Ｇｎ（ｘ），Ｇｎ（ｘ）称为轨道Ｇｎ（ｘ）的共轭轨道。如果Ｇｎ（ｘ）＝Ｇｎ（ｘ珋），则称Ｇｎ（ｘ）为自共轭轨道。收稿日期