布爾函數(shù)全局雪崩特征的兩個(gè)新指標(biāo)*

譙通旭,王 瑛,孫 瑞

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

布爾函數(shù)全局雪崩特征的兩個(gè)新指標(biāo)*

譙通旭,王 瑛,孫 瑞

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

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

布爾函數(shù) Walsh譜 全局雪崩特征 平方和指標(biāo) 絕對(duì)指標(biāo)

0 引 言

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

1 準(zhǔn)備工作

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

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

能量守恒定理(也稱(chēng)為Parseval關(guān)系)如下:

函數(shù)f(x)與g(x)的互相關(guān)函數(shù)定義為

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

由文獻(xiàn)[5]的推論2知道

這里G(ω)是函數(shù)g的Walsh(循環(huán))譜。

函數(shù)f(x)與g(x)的全局雪崩特征的絕對(duì)指標(biāo)定義為

2 全局雪崩特征的兩個(gè)新指標(biāo)

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

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

定理1。

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

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

②當(dāng)n為奇數(shù)時(shí),0≤λf＜22n。

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

定理3若f是bent函數(shù),則βf=。

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

定理4λf=0等價(jià)于βf=0。

證明:按定義可證。

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

猜測(cè)1存在f和g,滿(mǎn)足λf＜λg,βf＞βg。

可用構(gòu)造的方式或計(jì)算機(jī)搜索方式解決此猜測(cè)。

在密碼學(xué)中,給定函數(shù)f,在選g時(shí),盡量使σf,g接近λf,Δf,g接近βf。

3 結(jié) 語(yǔ)

提出了全局雪崩特征的兩個(gè)新指標(biāo)。一旦給定f,通過(guò)計(jì)算它的walsh譜,可以得到σf,g的最小值λf,這與周宇博士的方法(任給定f和g,計(jì)算σf,g)不同。在密碼學(xué)中,如何使σf,g值小是大家關(guān)心的問(wèn)題。給定f,如何計(jì)算指標(biāo)βf是以后研究的目標(biāo)。當(dāng)然,還要綜合考慮其它密碼學(xué)指標(biāo)[6-9]。在這些結(jié)論的基礎(chǔ)上,可將單輸出布爾函數(shù)推廣為多輸出布爾函數(shù),或?qū)⒂邢抻騁F(2)推廣為整數(shù)模q剩余類(lèi)環(huán)Zq,再重新定義和計(jì)算σ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] 王林,譙通旭,趙偉,等.關(guān)于完全非線性函數(shù)的非線性度的界[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] 譙通旭,祝世雄,王運(yùn)兵,等.單圈T函數(shù)序列與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] 譙通旭,王運(yùn)兵,謝上明,等.具有最大代數(shù)免疫度函數(shù)的研究[J].通信技術(shù),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—),女,碩士,高級(jí)工程師,主要研究方向?yàn)樾畔踩c通信保密;

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

孫 瑞(1982—),男,學(xué)士,工程師,主要研究方向?yàn)槊艽a學(xué)及其應(yīng)用。

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—),男,學(xué)士,高級(jí)工程師,主要研究方向?yàn)槊艽a學(xué);

2014-04-14;

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

國(guó)家自然科學(xué)基金(No.61309034);中國(guó)電子科技集團(tuán)創(chuàng)新人才項(xiàng)目(No.JJQN201332)

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