三类布尔函数的相关函数研究

2014-06-02卓泽朋崇金凤

计算机工程 2014年3期

关键词：下界雪崩布尔

卓泽朋，崇金凤，王慧

三类布尔函数的相关函数研究

卓泽朋，崇金凤，王慧

(淮北师范大学数学科学学院，安徽淮北 235000)

布尔函数；Bent函数；自相关函数；非线性度；全局雪崩准则；绝对值指标

1 概述

Bent函数[1]是非线性度达到最大的一类布尔函数，在密码设计和通信领域有着广泛应用。但该类函数也有弱点，如没有弹性，只能是偶数维的函数。为了弥补Bent函数的不足，又相继提出了部分Bent函数[2]、半-Bent函数[3]和Plateaued函数[4]等。严格雪崩准则(Strict Avalanche Criterion, SAC)[5]和扩散准则(Propagation Criterion, PC)[6]研究的是布尔函数与其移位布尔函数的相关程度，但它们只对某些点的自相关值有要求，而对其他点不加限制，这会导致布尔函数安全的局部性。为了克服这方面的缺点和不足，文献[7]提出布尔函数的全局雪崩准则(Global Avalanche Criterion, GAC)，并引入与之相关的2个指标：绝对值指标和平方和指标，研究表明，这2个指标越小，布尔函数的GAC越好，Bent函数恰好能达到这2个指标的下界。GAC从全局出发，对所有点提出了要求，使人们对SAC和PC有了进一步思考[7-8]。文献[9]讨论2个布尔函数间的GAC，将一个布尔函数的GAC推广到2个不同布尔函数之间，得到2个不同布尔函数GAC的上下界，对文献[7]中的结果进行了推广。在文献[10-12]中，研究了任意4个布尔函数的互相关函数间满足的一个等式，利用该等式得到很多结论。

2 预备知识

首先给出一些符号说明：

从互相关函数的定义很容易得到：

Bent函数恰好能达到这2个指标的下界，这2个指标越小，布尔函数的GAC越好。

3 三类布尔函数的相关函数

由自相关函数的定义得到：

结论得证。

布尔函数的相关函数能刻画布尔函数的扩散特征和线性结构特征，在布尔函数的性质研究中发挥着重要作用，利用互相关函数的定义得到：

证明：根据互相关函数的定义，有：

结论得证。

注：在定理2中：

在文献[22]中，利用此等式给出了任意三次布尔函数的自相关函数平方的上界，借助该上界进一步研究了多类重要的迹函数表示的三次布尔函数的平方和指标与绝对值指标的上下界问题。将该上界叙述如下：

所以：

因此，根据引理得到：

4 结束语

[1] Rothaus O S. On “Bent” Functions[J]. Journal of Combina- torial Theory, Series A, 1976, 20(3): 300-305.

[2] Carlet C. Partially-bent Functions[C]//Proc. of Cryptology- CRYPTO’93. Berlin, Germany: Springer-Verlag, 1993: 280- 291.

[3] Chee S, Lee S, Kim K. Semi-bent Functions[J]. Designs, Codes and Cryptography, 1993, 3(2): 135-145.

[4] Zheng Yuliang, Zhang Xianmo. On Plateaued Functions[J]. IEEE Transactions on Information Theory, 2001, 47(5): 1215-1223.

[5] Webster A F, Tavares S E. On the Design of S-boxes[C]//Proc. of CRYPTO’85. London, UK: Spinger-Verlag, 1985: 523-534.

[6] Preneel B, Leekwijck W V. Propagation Characteristics of Boolean Functions[C]//Proc. of EUROCRYPT’90. Berlin, Germany: Springer-Verlag, 1990: 161-173.

[7] Zhang Xianmo. GAC——The Criterion for Global Avalanche Characteristics of Cryptographic Functions[J]. Journal of Universal Computer Science, 1995, 1(5): 315-333.

[8] 崇金凤, 卓泽朋. 满足p次扩散准则的弹性函数的全局雪崩特征[J]. 计算机应用研究, 2011, 28(3): 1142-1144.

[9] Zhou Yu, Xie Min, Xiao Guozhen. On the Global Avalanche Characteristics Between Two Boolean Functions and the Higher Order Nonlinearity[J]. Information Sciences, 2010, 180(2): 256-265.

[10] Zhuo Zepeng, Zhang Weiguo, Xiao Guozhen, et al. On Correlation Properties of Boolean Functions[J]. Chinese Journal of Electronics, 2011, 20(1): 143-146.

[11] Zhuo Zepeng. On Cross-correlation Properties of Boolean Functions[J]. International Journal of Computer Mathematics, 2011, 88(10): 2035-2041.

[12] 卓泽朋. 密码学中布尔函数的性质和构造[D]. 西安: 西安电子科技大学, 2012.

[13] Sun Guanghong, Wu Chuankun. The Lower Bounds on the Second Order Nonlinearity of Three Classes of Boolean Functions with High Nonlinearity[J]. Information Sciences, 2009, 179(3): 267-278.

[14] Gangopadhyay S, Sarkar S, Telang R. On the Lower Bounds of the Second Order Nonlinearities of Some Boolean Functions[J]. Information Sciences, 2010, 180(2): 266-273.

[15] 李雪莲, 胡予濮, 高军涛. Bent函数和半-bent函数的二阶非线性度下界[J]. 电子与信息学报, 2010, 32(10): 2521-2525.

[16] 卓泽朋, 魏仕民, 崇金凤, 等. 一类三次Bent函数的二阶非线性度[J]. 武汉大学学报: 理学版, 2013, 59(1): 82-86.

[17] 徐媛, 崇金凤, 卓泽朋. 一类Bent函数的二阶非线性度[J]. 计算机应用研究, 2011, 28(7): 2687-2689.

[18] Charpin P, Pasalic E, Tavernier C. On Bent and Semi-bent Quadratic Boolean Functions[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4286-4298.

[19] Khoo K, Gong Guang. A New Family of Gold-like Sequences[C]//Proc. of International Conference on Sequences, Subsequences, and Consequences. Berlin, Germany: Springer- Verlag, 2002.

[20]Khoo K, Gong Guang, Stinson D R. A New Characterization of Semi-bent and Bent Functions on Finite Fields[J]. Designs, Codes and Cryptography, 2006, 38(2): 279-295.

[21]Carlet C. Recursive Lower Bounds on the Nonlinearity Profile of Boolean Functions and Their Applications[J]. IEEE Transactions on Information Theory, 2008, 54(3): 1262-1272.

[22] Singh D, Bhaintwal M. Additive Autocorrelation of Some Classes of Cubic Semi-bent Boolean Functions[EB/OL]. (2012-02-15). http://eprint.iacr.org/2012.127.pdf.

[23] Canteaut A, Charpin P, Kyureghyan G M. A New Class of Monomial Bent Functions[J]. Finite Fields and Their Applications, 2008, 14(1): 221-241.

[24] Canteaut A, Charpin P. Decomposing Bent Functions[J]. IEEE Transactions on Information Theory, 2003, 49(8): 2004-2019.

编辑陆燕菲

Research on Correlation Function for Three Classes of Boolean Functions

ZHUO Ze-peng, CHONG Jin-feng, WANG Hui

(School of Mathematical Science, Huaibei Normal University, Huaibei 235000, China)