一類特殊形狀的布爾函數Walsh譜分解式和自相關函數

代浩 卓澤朋

摘要：利用布爾函數Walsh譜和自相關函數的定義與性質給出一類布爾函數Walsh譜分解式之間關系以及自相關函數之間的關系。分析布爾函數Walsh譜分解式對于研究密碼函數的性質和構造具有重要意義。

關鍵詞：布爾函數；walsh譜；自相關函數

中圖分類號：TN918.1 文獻標識碼：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

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

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

1 預備知識

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

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

定義3[15] 設是一個元布爾函數，則的自相關函數定義為：

2 主要結論

下面主要分析一類特殊形狀的布爾函數Walsh譜性質之間關系和自相關函數之間關系。

定理1 元布爾函數總可寫成

，

其中均是與無關的元布爾函數.則

（1） 的Walsh譜和的Walsh譜之間關系為：

（2） 的自相關函數和的自相關函數之間關系為：

①當時，

，

②當，時，

，

③當，時，

，

④當，時，

，

其中為與的互相關。

證明：由于的取值與性質無關，故不妨取為。即

（1） ，

=

=

+

=

（2）

①當時，

=

+

=。

②當，時。

=

+

令為與的互相關，則

上式=

=。

同理可得

③當，時，

④當，時，

為使結論更加整齊好看，可將函數定義如下：

推論1 將定理1中函數定義為

且，，，。

則的Walsh譜和的Walsh譜之間關系為：

推論 2 將定理1中函數定義為

且，，，。則的自相關函數和的自相關函數之間關系為：

。

。

。

。

為使形式統一，定義，，，，

則

3 結束語

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

參考文獻：

[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函數構造方法研究[J].密碼學報，2015，2（5）：404-438.

[4] 曾祥勇，胡磊. Bent函數的一種迭代構造[J].電子學報，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] 常祖領，陳魯生，符方偉. PS類Bent函數的一種構造方法[J].電子學報，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] 曾本勝，李世取，李坤.一類布爾函數Walsh譜的分解式及其應用[A]. 密碼學進展-CAINACRYPT98[M]. 北京：科學出版社，1998.217-220.

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

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

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