李泉，高光普，刘文芬

(信息工程大学 信息工程学院，河南 郑州 450002)

1 引言

1999年，密码学者Pieprzyk[1]在研究散列算法的快速实现时提出了旋转对称函数的概念。随着文献[2~6]等对旋转对称函数的进一步分析与研究后，发现这一类结构特殊的布尔函数可以具有良好的密码学性质，并且搜索旋转对称函数要比穷尽搜索布尔函数空间的效率要高，所以一直以来不断地通过改良搜索旋转对称函数空间的方法寻找密码学性质优良的布尔函数。2006年，密码学者Kavut和Yücel[4]利用最速下降法在旋转对称函数空间上搜索到的非线性度为241的9元布尔函数，随后Kavut和Yücel[7]又证明了241为9元旋转对称函数所能达到的最高非线性度。为了得到更好的结果，2008年，Kavut和Yücel[8]推广了旋转对称函数的概念，提出了k-阶旋转对称函数，初步搜索出了9元非线性度为242的3-阶旋转对称函数，并且利用该结论证明了9元、11元、13元非线性度大于的布尔函数都是存在的，彻底解决了这个提出近 30年的公开问题。k-阶旋转对称函数比旋转对称函数对布尔函数代数结构的约束更低，所以数量更多，并且已经寻找到了比旋转对称函数密码学性质更为优良的布尔函数。

本文在Kavut和Yücel的基础上研究了k-阶旋转对称函数的性质。首先，证明了k-阶旋转对称函数的 Walsh谱和自相关函数都满足k-阶的旋转对称。分析发现k-阶旋转对称函数的很多性质都可以利用其轨道来刻画，并给出了k-阶旋转对称函数的轨道中的长圈和短圈的计数公式。特……