源于密碼學(xué)的組合數(shù)猜想問題中的數(shù)據(jù)特征

鄧宇龍， 張曉朋， 鄭玉軍

( 湖南科技學(xué)院數(shù)學(xué)與計算科學(xué)系 計算數(shù)學(xué)研究所, 湖南 永州 425199 )

0 引言

Tu和Deng[1]提出了源于密碼學(xué)的組合數(shù)猜想：

猜想1設(shè)St,k={(a,b)|a,b∈Z2k-1,a+b≡t(mod 2k-1),w(a)+w(b)≤k-1}, 其中1≤t≤2k-2,k≥2,w(t)是t的Hamming權(quán),則集合St,k的基數(shù)#St,k≤2k-1.

根據(jù)文獻(xiàn)[1]的猜想,Tu和Deng獲得了兩類具有最優(yōu)代數(shù)免疫的Boolean函數(shù)類：一類仍然是Bent函數(shù)類,另一類是具有最優(yōu)代數(shù)次數(shù)和目前所知最好的非線性度(這個結(jié)果優(yōu)于文獻(xiàn)[2]給出的函數(shù)類非線性度)的平衡Boolean函數(shù)類.但是,對于猜想1的證明,文獻(xiàn)[1]僅僅只是給出了transfer-matrix算法,然后利用計算機(jī)輔助,機(jī)械地驗(yàn)證了k≤29的情況，這與猜想1的結(jié)論還有很大的差距.

觀察猜想1中集合St,k的構(gòu)造發(fā)現(xiàn)，b由a唯一確定,因此設(shè)想猜想1的結(jié)論可以通過對整數(shù)a的個數(shù)的計算來獲得.源于這種想法,文獻(xiàn)[3]把a(bǔ)劃分成兩類：第一類為a=0,1,…,t,b=t-a; 第二類為a=t+v,b=2k-1-v,v=1,2,…,2k-t-2.根據(jù)這兩類劃分,文獻(xiàn)[3]證明了當(dāng)t的權(quán)w(t)較小時(w(t)≤3)猜想1的結(jié)論成立，并且還指出a的個數(shù)的統(tǒng)計很大程度依賴于

1 背景知識

引理1[3]w(2k-1-x)=k-w(x), 0≤x≤2k-1; 當(dāng)xi=1時,w(x+2i)≤w(x); 當(dāng)且僅當(dāng)對任意的i,xi+yi≤1時,有w(x+y)≤w(x)+w(y); 以及

w(x)=w(x-1)-i+1,x≡2i(mod 2i+1),i=0,1,2,….

根據(jù)引理1有：

定義1(權(quán)值表構(gòu)造函數(shù)) 設(shè)二進(jìn)長度為k的非負(fù)整數(shù)x,y對應(yīng)的和x+y的取值范圍為0～2k-1,x=0或2i,i=0,1,…,k-1, 0≤y

其中1≤i≤k.由k二進(jìn)表示為(x0x1…xk-1)的x旋轉(zhuǎn)形成的集合為

定義3(反射)k二進(jìn)表示為(x0x1…xk-1)的x的反射γ(x)定義為γ(x)=γ(x0x1…xk-1)=(xk-1xk-2…x0).顯然,w(γ(x))=w(x).

2 算法設(shè)計

本文采用C++語言,通過計算機(jī)算法實(shí)現(xiàn)符合條件的元素個數(shù)的計算.由于要搜尋的元素數(shù)據(jù)量呈2i(1≤i≤k)增加,算法中內(nèi)存空間的分配需求較大，而計算機(jī)配置較低，因此本文只統(tǒng)計了二進(jìn)長度較小的元素個數(shù).算法的實(shí)現(xiàn)由以下兩個步驟完成:

步驟1 權(quán)值表的構(gòu)造.首先,根據(jù)權(quán)值表構(gòu)造函數(shù),由于非負(fù)整數(shù)x的取值設(shè)定為2i(0≤i≤k-1), 因此在循環(huán)控制變量i小于二進(jìn)長度k時,總有w(x)=1.其次,初始化二進(jìn)長度為k的變量x,y=1,y由二進(jìn)長度為k非負(fù)整數(shù)x控制；如果y

步驟2 元素個數(shù)的分類統(tǒng)計.根據(jù)文獻(xiàn)[3],把二進(jìn)長度為k的非負(fù)整數(shù)x劃分成兩類：第一類為x=0,1,…,t,y=t-x; 第二類為x=t+v,y=2k-1-v,v=1,2,…,2k-t-2.首先,初始化循環(huán)控制變量x=0,y=t.如果x≤t, 則計算w(x)+w(y)的值.假設(shè)w(x)+w(y)的值為i, 則有St,i的元素個數(shù)#St,i=#St,i+1； 否則x=x+1,y=y-1, 循環(huán)執(zhí)行得到元素個數(shù)的統(tǒng)計分布表.

3 實(shí)驗(yàn)數(shù)據(jù)分析

本文選取k二進(jìn)長度為5和6的數(shù)據(jù)進(jìn)行分析，實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計如表1和表2所示.注意到1≤t≤2k-2,w(t)是t的Hamming權(quán),w(a)+w(b)是可能的權(quán)值,t與w(a)+w(b)所對應(yīng)的數(shù)字是相應(yīng)的取值個數(shù)統(tǒng)計.

表1 k=5的組合分布情況

表2 k=6的組合分布情況

通過對表1和表2數(shù)據(jù)的分析,可得到Tu-Deng猜想問題中的如下一些數(shù)據(jù)分布特征：

定理2(反射的數(shù)據(jù)特征) 設(shè)γ(t)=t2, 則St2,j=γ(St,j).

證明因?yàn)閠2=γ(t)=γ((a+b)mod (2k-1))=(γ(a)+γ(b))mod (2k-1), 所以

γ(St,j)=γ({(a,b)|(a+b)mod (2k-1)=t且w(a)+w(b)=j})=

{(γ(a),γ(b))|(γ(a)+γ(b))mod (2k-1)=γ(t)且w(γ(a))+w(γ(b))=j}.

注意到γ(t)=t2及w(γ(a))=w(a), 于是有γ(St,j)=St1,j.

參考文獻(xiàn)：

[1] Tu Ziren, Deng Yingpu. A conjecture on binary string and its application on constructing Boolean functions of optimal algebraic immunity[J/OL]. [2013-11-17]. http://eprint.iacr.org/2009/272.pdf.

[2] Carlet Claude, Feng Keqin. An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity[C]//Advances in Cryptology-ASIACRYPT 2008. Springer-Verlag, 2008:425-440.

[3] Thomas W Cusick, Li Yuan, Pantelimon. On a combinatorial conjecture[J/OL]. [2013-11-17]. http://eprint.iacr.org/2009/554.pdf.

[4] Zhang Xiaopeng, Deng Yulong. On a combinatorial conjecture[J]. Journal of Hunan University of Science and Engineering, 2013,34(12):58-61.

[5] Flori Jean Pierre, Randriam Hugues, Cohen Gerard, et al. On a conjecture about binary strings distribution[J/OL]. [2013-11-17]. http://eprint.iacr.org/2010/170.pdf.

[6] Flori Jean Pierre， Randriam Hugues. On the number of carries occurring in an addition mod 2k-1[J]. Citation Information, 2012,12(4):601-647.