一類特殊形狀的布爾函數(shù)Walsh譜分解式和自相關(guān)函數(shù)

代浩 卓澤朋

摘要：利用布爾函數(shù)Walsh譜和自相關(guān)函數(shù)的定義與性質(zhì)給出一類布爾函數(shù)Walsh譜分解式之間關(guān)系以及自相關(guān)函數(shù)之間的關(guān)系。分析布爾函數(shù)Walsh譜分解式對于研究密碼函數(shù)的性質(zhì)和構(gòu)造具有重要意義。

關(guān)鍵詞：布爾函數(shù)；walsh譜；自相關(guān)函數(shù)

中圖分類號：TN918.1 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）04-0208-02

Walsh Spectrum Decomposition and Autocorrelation Function of A Class of Boolean Functions of Special Shape

DAI Hao， ZHUO Ze-peng

（School of Mathmatical Science，Huaibei Normal University，Huaibei 235000，China）

Abstract：Through making use of the Walsh spectrum of Boolean function and the definition and properties of Autocorrection function， give the relationship between the decomposition formulas of a class of Boolean functions and Walsh spectra as well as the relationship between autocorreclation functions。The analysis of the Walsh spectra of Boolean functions is of great significance to the study of the properties and construction of cryptographic function.

Key words： Boolean function； Walsh spectrum； Autocorrelation function

在密碼學(xué)中通常會根據(jù)不同的需求來構(gòu)造不同的邏輯函數(shù)。例如，構(gòu)造相關(guān)免疫函數(shù)[1]可抵抗相關(guān)攻擊。Rothaus給出的Bent函數(shù)[2]可抵抗差分攻擊，隨后很多人研究了Bent函數(shù)的性質(zhì)和構(gòu)造[3-7]，進而給出了部分Bent函數(shù)[8]，半Bent函數(shù)[9]以及Plateaued函數(shù)[10-11]等。

研究Walsh譜分解式對于密碼函數(shù)的構(gòu)造具有一定推波助瀾的作用。相關(guān)文獻(xiàn)給出了一類布爾函數(shù)Walsh譜的分解式[12]以及利用Walsh譜分解式給出了多輸出Bent函數(shù)的一種構(gòu)造方法[13]。因此，本文主要利用頻譜理論[14]給出一類特殊形狀的布爾函數(shù)Walsh譜分解式之間的關(guān)系以及自相關(guān)函數(shù)之間的關(guān)系。

1 預(yù)備知識

定義1[15] 一個元布爾函數(shù)可表示為：

定義2[15] 設(shè)是一個元布爾函數(shù)，則的Walsh譜定義為：

定義3[15] 設(shè)是一個元布爾函數(shù)，則的自相關(guān)函數(shù)定義為：

2 主要結(jié)論

下面主要分析一類特殊形狀的布爾函數(shù)Walsh譜性質(zhì)之間關(guān)系和自相關(guān)函數(shù)之間關(guān)系。

定理1 元布爾函數(shù)總可寫成

，

其中均是與無關(guān)的元布爾函數(shù).則

（1） 的Walsh譜和的Walsh譜之間關(guān)系為：

（2） 的自相關(guān)函數(shù)和的自相關(guān)函數(shù)之間關(guān)系為：

①當(dāng)時，

，

②當(dāng)，時，

，

③當(dāng)，時，

，

④當(dāng)，時，

，

其中為與的互相關(guān)。

證明：由于的取值與性質(zhì)無關(guān)，故不妨取為。即

（1） ，

=

=

+

=

（2）

①當(dāng)時，

=

+

=。

②當(dāng)，時。

=

+

令為與的互相關(guān)，則

上式=

=。

同理可得

③當(dāng)，時，

④當(dāng)，時，

為使結(jié)論更加整齊好看，可將函數(shù)定義如下：

推論1 將定理1中函數(shù)定義為

且，，，。

則的Walsh譜和的Walsh譜之間關(guān)系為：

推論 2 將定理1中函數(shù)定義為

且，，，。則的自相關(guān)函數(shù)和的自相關(guān)函數(shù)之間關(guān)系為：

。

。

。

。

為使形式統(tǒng)一，定義，，，，

則

3 結(jié)束語

本文研究了一類特殊形狀的布爾函數(shù)Walsh譜分解式和自相關(guān)特征。并在此基礎(chǔ)上又給定了兩種形式更加整齊統(tǒng)一的兩個推論。然而如何利用其構(gòu)造GAC指標(biāo)較小且其他密碼學(xué)指標(biāo)也較好的布爾函數(shù)將是今后需要進一步研究的問題。

參考文獻(xiàn)：

[1] Siegenthaler T. Correlation-immunity of the combining functions for cryptographic applications [J]. IEEE.Trans. Inform. Theory， 1984，IT-30（5）：776-780.

[2] Rothaus O S. On ‘bent function [J]. Journal of Combinatorial Theory， Ser. A， 1976， 20：300-305.

[3] 楊小龍，胡紅鋼. Bent函數(shù)構(gòu)造方法研究[J].密碼學(xué)報，2015，2（5）：404-438.

[4] 曾祥勇，胡磊. Bent函數(shù)的一種迭代構(gòu)造[J].電子學(xué)報，2010，12（38）：2724-2728.

[5] McFarland R L. A family of difference sets in noncyclic groups[J]. Journal of Combinatorial Theory Series A，1973，15（1）：1-10.

[6] Dillion J.Elementary Hadamard Difference Sets[D]. Baltimore：Univ Maryland，1974.

[7] 常祖領(lǐng)，陳魯生，符方偉. PS類Bent函數(shù)的一種構(gòu)造方法[J].電子學(xué)報，2004，32（10）：1649-1653.

[8] Carlet C. Partially-bent function [J]. Designs Codes and Cryptography， 1993， 3（2）：135-145.

[9] Chee S，Lee S， Kim K. Semi-bent Functions[J]. Designs，Codes and Cryptography，1993，3（2）：135-145.

[10] Carlet， prouff E， On plateaued functions and their constructions [J]. IEE. Transactions on Information Theory， 2003， 49（2）：54 -73.

[11] Zheng Y， Zhang X. M. On plateaued Functions [J]. IEE. Transactions on Information Theory， 2001， 47（5）：1215-1223.

[12] 曾本勝，李世取，李坤.一類布爾函數(shù)Walsh譜的分解式及其應(yīng)用[A]. 密碼學(xué)進展-CAINACRYPT98[M]. 北京：科學(xué)出版社，1998.217-220.

[13] 滕吉紅，張文英，劉文芬，等. 密碼函數(shù)的一類遞歸構(gòu)造方法[J].中國工程科學(xué)，2003，5（7）：47-52.

[14] 馮登國. 頻譜理論及其在密碼學(xué)中的應(yīng)用[M]. 北京： 科學(xué)出版社， 2000.

[15] 李世取，曾本勝，廉玉忠，等. 密碼學(xué)中的邏輯函數(shù)[M]. 北京： 北京中軟出版公司， 2003.