一種計(jì)算旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的漢明重量和非線性度的新方法

張習(xí)勇 祁應(yīng)紅 高光普 李玉娟

?

一種計(jì)算旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的漢明重量和非線性度的新方法

張習(xí)勇①②④祁應(yīng)紅*①高光普③李玉娟④

①(信息工程大學(xué) 鄭州 450002)②(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室 無(wú)錫 214215)③(洛陽(yáng)外國(guó)語(yǔ)學(xué)校 洛陽(yáng) 471003)④(信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室 北京 100072)

旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)是一類(lèi)重要的密碼學(xué)函數(shù)，研究其重量和非線性度等密碼學(xué)性質(zhì)具有很好的理論價(jià)值。區(qū)別于已有的計(jì)算方法，該文利用特定的正規(guī)基把這些布爾函數(shù)的問(wèn)題轉(zhuǎn)化為有限域上的指數(shù)和問(wèn)題，得到了和時(shí)一些二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的重量和非線性度的新結(jié)果。使用所提的方法，可以計(jì)算幾乎全部的二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的重量和非線性度。所提的新方法對(duì)于研究一般的旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)具有一定的參考意義。

密碼學(xué)；旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)；非線性度；漢明重量；正規(guī)基

1 引言

布爾函數(shù)在現(xiàn)代密碼學(xué)中有著廣泛的應(yīng)用，很多學(xué)者致力于其性質(zhì)和應(yīng)用的研究。1999年，Pieprzyk等人[1]提出了旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的概念，這類(lèi)布爾函數(shù)在輸入變量旋轉(zhuǎn)變化時(shí)，其函數(shù)值保持不變。人們?cè)谘芯恐邪l(fā)現(xiàn)這種類(lèi)型的布爾函數(shù)具有良好的密碼學(xué)性質(zhì)，并將其應(yīng)用于如MD4, MD5, HAVAL等一些摘要算法中。對(duì)這種類(lèi)型的布爾函數(shù)的非線性度和漢明重量的研究取得了很好的結(jié)果。例如在2002年，Cusick等人[2]研究了一類(lèi)二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的快速求值，得到了該類(lèi)布爾函數(shù)的重量，并且給出了當(dāng)變?cè)獋€(gè)數(shù)為偶數(shù)時(shí)此類(lèi)函數(shù)的非線性度。同時(shí)他們通過(guò)分析實(shí)驗(yàn)數(shù)據(jù)，提出了一個(gè)猜想：旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的非線性度和其漢明重量相等。2010年，Ciungu[3]證明了該猜想在變?cè)獋€(gè)數(shù)為3的倍數(shù)時(shí)是成立的，2011年，Zhang等人[4]證明了上述猜想。2012年，Wang等人[5]將此猜想推廣到了次數(shù)為4的旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)，證明了的非線性度與其漢明重量相等。

近來(lái)，人們分別研究了旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的非線性度、重量和其它性質(zhì)，有些結(jié)論可用公式直接表示這兩個(gè)參數(shù)。文獻(xiàn)[11]刻畫(huà)了二次單軌道旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的漢明重量和非線性度，文獻(xiàn)[12]中給出了一類(lèi)特殊的二次雙軌道旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的漢明重量和非線性度，這些結(jié)果只能計(jì)算極少幾類(lèi)旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的情況，而對(duì)于一般的情況，這兩篇文章中的方法不再適用。本文利用正規(guī)基，將布爾函數(shù)的問(wèn)題轉(zhuǎn)化為有限域上的指數(shù)和問(wèn)題，這種新方法可能更適合研究一般的旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)。

2 預(yù)備知識(shí)

定義2[13]元旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)可以用形式表示，其中，稱(chēng)這種表示方法為的簡(jiǎn)代數(shù)正規(guī)型。

由定義3與定義4以及線性函數(shù)的性質(zhì)可知：

有限域可以看成其子域上的向量空間，針對(duì)不同的用途，人們選用不同的向量空間上的基，如正規(guī)基，多項(xiàng)式基等。在上的正規(guī)基是形式如的一組元素，選用這樣正規(guī)基的優(yōu)點(diǎn)之一是做平方運(yùn)算不費(fèi)計(jì)算資源(可以忽略不計(jì))。由正規(guī)基定理知，對(duì)任意的，在中存在一組上的正規(guī)基。假設(shè)正規(guī)元為，則對(duì)任意的，存在使得，稱(chēng)為在此基下的坐標(biāo)。

本文需要關(guān)于有限域上具有良好跡正交關(guān)系的正規(guī)基的一些結(jié)果，下面的結(jié)論另文給出，也可參見(jiàn)文獻(xiàn)[15]。

定理2[14]假設(shè)正整數(shù),滿(mǎn)足，奇素?cái)?shù)(可相同)滿(mǎn)足則有，其中為雅可比符號(hào)。

定理3[14]令,，記為在中的階，令。正整數(shù),滿(mǎn)足,，則

由定理2知

另一方面

從而

故此時(shí)

綜上可得

從而可得

表1是利用計(jì)算機(jī)編程得到的該函數(shù)的漢明重量和非線性度，可用例子中得出的公式進(jìn)行驗(yàn)證。沿用定理4中的符號(hào)及。當(dāng)即，且對(duì)定理4中給出的,時(shí)，該函數(shù)的重量和非線性度的計(jì)算有更簡(jiǎn)單的公式。證明的方法與定理4的證明類(lèi)似，只需結(jié)合文獻(xiàn)[14]中定理5.1，在此只給出結(jié)論。

表1計(jì)算機(jī)編程得到的例1的部分結(jié)果

910111314151718 224480992403280641612865280130048 2885121056416081921664065280131072

表2計(jì)算機(jī)編程得到的例2的部分結(jié)果

1014182226 4808064130560209510433546240

證畢

5 與已有結(jié)論及方法的比較

目前對(duì)于二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的重量和非線性度的研究結(jié)果有限，原因之一是沒(méi)有一般性的辦法來(lái)解決這類(lèi)二次函數(shù)的指數(shù)和的計(jì)算問(wèn)題，如上述兩文中的方法只能適用于上述兩文中的特殊的二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)。本文使用的方法與上述兩個(gè)文獻(xiàn)中使用的方法不同，將二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的重量和非線性度的問(wèn)題轉(zhuǎn)化為有限域上單變?cè)瘮?shù)的指數(shù)和計(jì)算問(wèn)題，最終求取了時(shí)任意的二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的重量和非線性度，同時(shí)對(duì)時(shí)的特殊類(lèi)型的旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)重量和非線性度進(jìn)行了刻畫(huà)。當(dāng)時(shí)，文獻(xiàn)[11]的結(jié)論是本文定理4的特殊情形，而文獻(xiàn)[12]的結(jié)論是本文例1的特殊情形。相比于已有的方法，本文的這種利用特殊的正規(guī)基的方法更有一般性，能計(jì)算大部分二次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)的非線性度，且計(jì)算非線性度時(shí)，主要運(yùn)算之一是求取特殊的具有指定正交關(guān)系的正規(guī)基(參見(jiàn)文獻(xiàn)[16]等，可知有時(shí)(如)是線性運(yùn)算)。本文方法對(duì)研究一般的高次旋轉(zhuǎn)對(duì)稱(chēng)布爾函數(shù)也有一定的參考意義。

[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

祁應(yīng)紅 yinghong_qi@163.com

國(guó)家自然科學(xué)基金(61402522, 60803154, 61572027)；數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室課題；信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(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)

張習(xí)勇：男，1975年生，副教授，研究方向?yàn)榫幋a密碼學(xué).

祁應(yīng)紅：男，1986年生，碩士生，研究方向?yàn)榫幋a密碼學(xué).

高光普：男，1984年生，講師，研究方向?yàn)閷?duì)稱(chēng)密碼設(shè)計(jì)與分析.