一种计算旋转对称布尔函数的汉明重量和非线性度的新方法

张习勇 祁应红 高光普 李玉娟



一种计算旋转对称布尔函数的汉明重量和非线性度的新方法

张习勇①②④祁应红*①高光普③李玉娟④

①(信息工程大学 郑州 450002)②(数学工程与先进计算国家重点实验室 无锡 214215)③(洛阳外国语学校 洛阳 471003)④(信息保障技术重点实验室 北京 100072)

旋转对称布尔函数是一类重要的密码学函数，研究其重量和非线性度等密码学性质具有很好的理论价值。区别于已有的计算方法，该文利用特定的正规基把这些布尔函数的问题转化为有限域上的指数和问题，得到了和时一些二次旋转对称布尔函数的重量和非线性度的新结果。使用所提的方法，可以计算几乎全部的二次旋转对称布尔函数的重量和非线性度。所提的新方法对于研究一般的旋转对称布尔函数具有一定的参考意义。

密码学；旋转对称布尔函数；非线性度；汉明重量；正规基

1 引言

布尔函数在现代密码学中有着广泛的应用，很多学者致力于其性质和应用的研究。1999年，Pieprzyk等人[1]提出了旋转对称布尔函数的概念，这类布尔函数在输入变量旋转变化时，其函数值保持不变。人们在研究中发现这种类型的布尔函数具有良好的密码学性质，并将其应用于如MD4, MD5, HAVAL等一些摘要算法中。对这种类型的布尔函数的非线性度和汉明重量的研究取得了很好的结果。例如在2002年，Cusick等人[2]研究了一类二次旋转对称布尔函数的快速求值，得到了该类布尔函数的重量，并且给出了当变元个数为偶数时此类函数的非线性度。同时他们通过分析实验数据，提出了一个猜想：旋转对称布尔函数的非线性度和其汉明重量相等。2010年，Ciungu[3]证明了该猜想在变元个数为3的倍数时是成立的，2011年，Zhang等人[4]证明了上述猜想。2012年，Wang等人[5]将此猜想推广到了次数为4的旋转对称布尔函数，证明了的非线性度与其汉明重量相等。

近来，人们分别研究了旋转对称布尔函数的非线性度、重量和其它性质，有些结论可用公式直接表示这两个参数。文献[11]刻画了二次单轨道旋转对称布尔函数的汉明重量和非线性度，文献[12]中给出了一类特殊的二次双轨道旋转对称布尔函数的汉明重量和非线性度，这些结果只能计算极少几类旋转对称布尔函数的情况，而对于一般的情况，这两篇文章中的方法不再适用。本文利用正规基，将布尔函数的问题转化为有限域上的指数和问题，这种新方法可能更适合研究一般的旋转对称布尔函数。

2 预备知识

定义2[13]元旋转对称布尔函数可以用形式表示，其中，称这种表示方法为的简代数正规型。

由定义3与定义4以及线性函数的性质可知：

有限域可以看成其子域上的向量空间，针对不同的用途，人们选用不同的向量空间上的基，如正规基，多项式基等。在上的正规基是形式如的一组元素，选用这样正规基的优点之一是做平方运算不费计算资源(可以忽略不计)。由正规基定理知，对任意的，在中存在一组上的正规基。假设正规元为，则对任意的，存在使得，称为在此基下的坐标。

本文需要关于有限域上具有良好迹正交关系的正规基的一些结果，下面的结论另文给出，也可参见文献[15]。

定理2[14]假设正整数,满足，奇素数(可相同)满足则有，其中为雅可比符号。

定理3[14]令,，记为在中的阶，令。正整数,满足,，则

由定理2知

另一方面

从而

故此时

综上可得

从而可得

表1是利用计算机编程得到的该函数的汉明重量和非线性度，可用例子中得出的公式进行验证。沿用定理4中的符号及。当即，且对定理4中给出的,时，该函数的重量和非线性度的计算有更简单的公式。证明的方法与定理4的证明类似，只需结合文献[14]中定理5.1，在此只给出结论。

表1计算机编程得到的例1的部分结果

910111314151718 224480992403280641612865280130048 2885121056416081921664065280131072

表2计算机编程得到的例2的部分结果

1014182226 4808064130560209510433546240

证毕

5 与已有结论及方法的比较

目前对于二次旋转对称布尔函数的重量和非线性度的研究结果有限，原因之一是没有一般性的办法来解决这类二次函数的指数和的计算问题，如上述两文中的方法只能适用于上述两文中的特殊的二次旋转对称布尔函数。本文使用的方法与上述两个文献中使用的方法不同，将二次旋转对称布尔函数的重量和非线性度的问题转化为有限域上单变元函数的指数和计算问题，最终求取了时任意的二次旋转对称布尔函数的重量和非线性度，同时对时的特殊类型的旋转对称布尔函数重量和非线性度进行了刻画。当时，文献[11]的结论是本文定理4的特殊情形，而文献[12]的结论是本文例1的特殊情形。相比于已有的方法，本文的这种利用特殊的正规基的方法更有一般性，能计算大部分二次旋转对称布尔函数的非线性度，且计算非线性度时，主要运算之一是求取特殊的具有指定正交关系的正规基(参见文献[16]等，可知有时(如)是线性运算)。本文方法对研究一般的高次旋转对称布尔函数也有一定的参考意义。

[1] Pieprzyk J and Qu C X. Fast hashing and rotation-symmetric functions[J]., 1999, 5(1): 20-31.

[3] Ciungu L C. Cryptographic Boolean functions: Thus-Morse sequences, weight and nonlinearity[D]. [Ph.D. dissertation], University at Buffalo, 2010.

[4] Zhang X, Guo H, Feng R,.. Proof of a conjecture about rotation symmetric functions[J]., 2011, 311(14): 1281-1289.

[5] Wang B, Zhang X, and Chen W. The hamming weight and nonlinearity of a type of rotation symmetric Boolean function [J].,, 2012, 55(4): 613-626.

[6] Cusick T W. Finding Hamming weights without looking at truth tables[J]., 2013, 5(1): 7-18.

[7] Brown A and Cusick T W. Equivalence classes for cubic rotation symmetric functions[J]., 2013, 5(2): 85-118.

[8] KV L, Sethumadhavan M, and Cusick T W. Counting rotation symmetric functions using Polya’s theorem[J]., 2014, 169: 162-167.

[9] Cusick T W and Cheon Y. Affine equivalence for cubic rotation symmetric Boolean functions with=variables[J]., 2014, 327: 51-61.

[10] Cusick T W and Cheon Y. Affine equivalence of quartic homogeneous rotation symmetric Boolean functions[J]., 2014, 259: 192-211.

[11] Kim H, Park S M, and Hahn S G. On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2[J]., 2009, 157(2): 428-432.

[12] Liu H. On the weight and nonlinearity of quadratic rotation symmetric function with two MRS functions[J]., 2013, 16(1): 12-19.

[14] Hou X D. Explicit evaluation of certain exponential sums of binary quadratic functions[J]., 2007, 13(4): 843-868.

[15] Weinberger M J and Lempel A. Factorization of symmetric circulant matrices in finite fields[J]., 1990, 28(3): 271-285.

[16] Zhang X, Cao X, and Feng R. A method of evaluation of exponential sum of binary quadratic functions[J]., 2012, 18(6): 1089-1103.

A New Method for Evaluation of Hamming Weight and Nonlinearity of Rotation-symmetric Boolean Functions

Zhang Xi-yong①②④Qi Ying-hong①Gao Guang-pu③Li Yu-juan④

①(,450002,)②(,214215,)③(,471003,)④(,100072,)

Rotation-symmetric Boolean function is a class of Boolean functions with good cryptographic properties, and researches on its weight and nonlinearity cryptographic properties have good theoretical value. Different from the conventional calculation method, in this paper, these problems are converted to the evaluation of exponential sum on finite fields with a specific normal basis. Some new results about the weight and nonlinearity of some rotation-symmetric Boolean functions of degree 2 withandare obtained. Using the proposed method, the weight and nonlinearity of almost all Rotation-symmetric Boolean functions of degree 2 can be evaluated. This new method is also interesting for studies on the other Boolean functions.

Cryptography; Rotation-symmetric Boolean functions; Nonlinearity; Hamming weight; Normal bases

TN918

A

1009-5896(2015)11-2691-06

10.11999/JEIT 150164

2015-01-29；改回日期：2015-06-11；

2015-07-27

祁应红 yinghong_qi@163.com

国家自然科学基金(61402522, 60803154, 61572027)；数学工程与先进计算国家重点实验室课题；信息保障技术重点实验室开放基金(KJ-13-108)

The National Natural Science Foundation of China (61402522, 60803154, 61572027); Project of State Key Lab of Mathematical Engineering and Advanced Computing; Open Foundation of Science and Technology on Information Assurance Laboratory (KJ-13-108)

张习勇：男，1975年生，副教授，研究方向为编码密码学.

祁应红：男，1986年生，硕士生，研究方向为编码密码学.

高光普：男，1984年生，讲师，研究方向为对称密码设计与分析.