布爾函數全局雪崩特征的兩個新指標*

譙通旭,王 瑛,孫 瑞

(中國電子科技集團公司第三十研究所,四川成都610041)

布爾函數全局雪崩特征的兩個新指標*

譙通旭,王 瑛,孫 瑞

(中國電子科技集團公司第三十研究所,四川成都610041)

ZHANG Xian-Mo和ZHENG Yu-liang提出單個函數f的全局雪崩特征的概念,并且給出單個函數雪崩特征的平方和指標σf與絕對指標Δf的上下界。周宇等將上面的概念作了推廣,提出了兩個函數f和g全局雪崩特征的概念。他們給出了兩個函數全局雪崩特征的平方和指標σf,g與絕對指標Δf,g。進而定義兩個新指標:λf(指g遍歷所有n元布爾函數時,σf,g取得的最小值)和βf(指g遍歷所有n元布爾函數時,Δf,g取得的最小值)。得到了λf的值,給出了λf和βf的上界和下界。

布爾函數 Walsh譜 全局雪崩特征 平方和指標 絕對指標

0 引 言

布爾函數是密碼學中研究的對象之一。人們最先考察關于函數的嚴格雪崩準則[1-2](SAC)和擴散特征[3](PC)。ZHANG Xian-mo和ZHENG Yu-liang推廣了這兩個概念,提出了單個函數全局雪崩特征的概念[4]。它是整體上度量單個布爾函數的擴散特性。它以研究單個函數的自相關為基礎。以兩個函數的互相關為基礎,周宇等提出了兩個布爾函數的全局雪崩特征[5]。并且定義了平方和指標σf,g與絕對指標Δf,g。給定函數f,當g跑遍所有布爾函數時,σf,g有一個最小值λf,它意味著對任意的函數g,σf,g不可能小于這個值。因此,選g的時候,希望σf,g接近λf。同樣,可以定義βf。以后可以看到,任給f,計算λf容易;計算βf通常要困難的多。應該綜合地看待指標λf和βf。即構造f,使得指標λf和βf都較小。

1 準備工作

假定n≥2。為二元域上的n維向量空間。Bn為所有n元布爾函數的集合。設f(x)∈Bn,定義f的Walsh(循環)譜為

這里ωx=ω1x1+ω2x2+…+ωnxn。

能量守恒定理(也稱為Parseval關系)如下:

函數f(x)與g(x)的互相關函數定義為

函數f(x)與g(x)的全局雪崩特征的平方和指標定義為

由文獻[5]的推論2知道

這里G(ω)是函數g的Walsh(循環)譜。

函數f(x)與g(x)的全局雪崩特征的絕對指標定義為

2 全局雪崩特征的兩個新指標

定義1給定函數f∈Bn,定義,這里min表示最小值。

定義2給定函數f∈Bn,定義,這里min表示最小值。

定理1。

證明:對任何g,≥(根據能量守恒定理)。設,令g(x)=ω0x,則G(ω0)=2n;G(ω)=0,對所有ω≠ω0成立。因此,此時·。所以λf=2n·。

推論1①當n為偶數時,0≤λf≤22n。如果有一ω0滿足F(ω0)=0,則λf=0。特別地,如果f為bent函數,則λf=22n。

②當n為奇數時,0≤λf＜22n。

定理20≤βf≤2n-2。

定理3若f是bent函數,則βf=。

實際上,有時有非仿射函數f和g滿足Δf,g=。例如f為二次bent函數,h為二次以上的bent函數。g=f+h。f(x+α)+f+h為bent函數加上一個仿射函數。因此Δf,g=。

定理4λf=0等價于βf=0。

證明:按定義可證。

由定理3和定理4可求出βf,一般情況下求βf很難。λf和βf有時一致。猜測有時不一致。

猜測1存在f和g,滿足λf＜λg,βf＞βg。

可用構造的方式或計算機搜索方式解決此猜測。

在密碼學中,給定函數f,在選g時,盡量使σf,g接近λf,Δf,g接近βf。

3 結 語

提出了全局雪崩特征的兩個新指標。一旦給定f,通過計算它的walsh譜,可以得到σf,g的最小值λf,這與周宇博士的方法(任給定f和g,計算σf,g)不同。在密碼學中,如何使σf,g值小是大家關心的問題。給定f,如何計算指標βf是以后研究的目標。當然,還要綜合考慮其它密碼學指標[6-9]。在這些結論的基礎上,可將單輸出布爾函數推廣為多輸出布爾函數,或將有限域GF(2)推廣為整數模q剩余類環Zq,再重新定義和計算σf,g。

[1] ADAMS C M,TRVARES S E.Generating and Counting Binary Bent Sequences[J].IEEE Transactions on Information Theory,1990,36(05):1170-1173.

[2] WEBSTER A F.Plaintext/Ciphertext Bit Dependencies in Cryptographic System[D].Ontario,Canada:Department of Electrical Engeneering,Queen’s University,1985.

[3] PRENEEL B,LEEKWIJC K,LINDEN LV,et al.Propagation Characteristics of Boolean Functions[C]//Advances in Cryptology-EUROCRYPT’90.Berlin:Springer -Verlag,1991:155-165.

[4] ZHANG X M,ZHENG Y L.GAC-the Criterion for Global Avalanche Characteristics of Cryptographic Functions [J].Journal for Universal Computer Science,1995, 1(05):316-333.

[5] ZHOU Yu,XIE Min,XIAO Guo-zhen.On the Global Avalanche Characteristics between Two Boolean Functions and the Higher Order Nonlinearity[J].Information Sciences,2010,180(02):256-265.

[6] 王林,譙通旭,趙偉,等.關于完全非線性函數的非線性度的界[J].信息安全與通信保密,2011(11):66-67.

WANG Lin,QIAO Tong-xu,ZHAO Wei,et al.On Nonlinearity Bounds of Perfect Nonlinear Functions[J]. Information Security and Communications Privacy,2011 (11):66-67.

[7] 譙通旭,祝世雄,王運兵,等.單圈T函數序列與M序列研究[J].信息安全與通信保密,2013(01):36-39.

QIAO Tong-xu,ZHU Shi-xiong,WANG Yun-bing,et al.Study on Single-Cycle T-Function Sequences and MSequences[J].Information Security and Communications Privacy,2013(01):36-39.

[8] 譙通旭,王運兵,謝上明,等.具有最大代數免疫度函數的研究[J].通信技術,2013,46(11):86-89.

QIAO Tong-xu,WANG Yun-bing,XIE Shang-ming,et al.Study on Functions with Optimum Algebraic Immunity [J].Communications Technology,2013,46(11):86-89.

[9] ZHOU Yu.On the Distribution of Autocorrelation Value of Balanced Boolean Functions[J].Advances in Mathematics of Communications,2013,7(03):335-347.

QIAO Tong-xu(1963—),male,B.Sci., senior engineer,mainly engaged in the research of cryptography.

王 瑛(1971—),女,碩士,高級工程師,主要研究方向為信息安全與通信保密;

WANG Ying(1971—),female,M.Sci.,senior engineer, mainly engaged in the research of information security and communications privacy.

孫 瑞(1982—),男,學士,工程師,主要研究方向為密碼學及其應用。

SUN Rui(1982—),male,B.Sci.,engineer,mainly engaged in the research of cryptography and its applications.

Two New Indicators of Global Avalanche Characteristics between Two Boolean Functions

QIAO Tong-xu,WANG Ying,SUN Rui
(No.30 Institute of CETC,Chengdu Sichun 610041,China)

ZHANG Xian-Mo and ZHENG Yu-liang suggested the notion of global avalanche characteristics of single Boolean functionf,and introduced the sum of squares indicatorσfand the absolute indicator Δf. ZHOU Yu et al.generalized the above notions.The notion of global avalanche characteristics of two Boolean functionfandgis proposed,and the sum of squares indicatorσf,gand absolute indicatorΔf,gof global avalanche characteristics of two Boolean functionfandgare defined.Givenn-variable functionf,λf, which is minimum value ofσf,g,wheregis anyn-variable Boolean function,is defined.βf,which is minimum value of Δf,g,wheregis any n-variable Boolean function,is defined.These are two new indicators.λfis computed.The lower and the upper bounds ofλfandβfare given.

boolean function;walsh spectrum;global avalanche characteristics;sum of squares indicator; absolute indicator

TN918.1

A

1002-0802(2014)06-0651-03

10.3969/j.issn.1002-0802.2014.06.014

譙通旭(1963—),男,學士,高級工程師,主要研究方向為密碼學;

2014-04-14;

2014-05-13 Received date：2014-04-14;Revised date：2014-05-13

國家自然科學基金(No.61309034);中國電子科技集團創新人才項目(No.JJQN201332)

Foundation Item:National Natural Science Foundation of China(No.61309034)and China Electronics Technology Group Corporation Innovative Technology Projects(No.JJQN201332)