一类特殊形状的布尔函数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.