卓澤朋，崇金鳳，王 慧

?

三類布爾函數(shù)的相關(guān)函數(shù)研究

卓澤朋，崇金鳳，王 慧

(淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000)

布爾函數(shù)；Bent函數(shù)；自相關(guān)函數(shù)；非線性度；全局雪崩準(zhǔn)則；絕對(duì)值指標(biāo)

1 概述

Bent函數(shù)[1]是非線性度達(dá)到最大的一類布爾函數(shù)，在密碼設(shè)計(jì)和通信領(lǐng)域有著廣泛應(yīng)用。但該類函數(shù)也有弱點(diǎn)，如沒有彈性，只能是偶數(shù)維的函數(shù)。為了彌補(bǔ)Bent函數(shù)的不足，又相繼提出了部分Bent函數(shù)[2]、半-Bent函數(shù)[3]和Plateaued函數(shù)[4]等。嚴(yán)格雪崩準(zhǔn)則(Strict Avalanche Criterion, SAC)[5]和擴(kuò)散準(zhǔn)則(Propagation Criterion, PC)[6]研究的是布爾函數(shù)與其移位布爾函數(shù)的相關(guān)程度，但它們只對(duì)某些點(diǎn)的自相關(guān)值有要求，而對(duì)其他點(diǎn)不加限制，這會(huì)導(dǎo)致布爾函數(shù)安全的局部性。為了克服這方面的缺點(diǎn)和不足，文獻(xiàn)[7]提出布爾函數(shù)的全局雪崩準(zhǔn)則(Global Avalanche Criterion, GAC)，并引入與之相關(guān)的2個(gè)指標(biāo)：絕對(duì)值指標(biāo)和平方和指標(biāo)，研究表明，這2個(gè)指標(biāo)越小，布爾函數(shù)的GAC越好，Bent函數(shù)恰好能達(dá)到這2個(gè)指標(biāo)的下界。GAC從全局出發(fā)，對(duì)所有點(diǎn)提出了要求，使人們對(duì)SAC和PC有了進(jìn)一步思考[7-8]。文獻(xiàn)[9]討論2個(gè)布爾函數(shù)間的GAC，將一個(gè)布爾函數(shù)的GAC推廣到2個(gè)不同布爾函數(shù)之間，得到2個(gè)不同布爾函數(shù)GAC的上下界，對(duì)文獻(xiàn)[7]中的結(jié)果進(jìn)行了推廣。在文獻(xiàn)[10-12]中，研究了任意4個(gè)布爾函數(shù)的互相關(guān)函數(shù)間滿足的一個(gè)等式，利用該等式得到很多結(jié)論。

2 預(yù)備知識(shí)

首先給出一些符號(hào)說明：

從互相關(guān)函數(shù)的定義很容易得到：

Bent函數(shù)恰好能達(dá)到這2個(gè)指標(biāo)的下界，這2個(gè)指標(biāo)越小，布爾函數(shù)的GAC越好。

3 三類布爾函數(shù)的相關(guān)函數(shù)

由自相關(guān)函數(shù)的定義得到：

結(jié)論得證。

布爾函數(shù)的相關(guān)函數(shù)能刻畫布爾函數(shù)的擴(kuò)散特征和線性結(jié)構(gòu)特征，在布爾函數(shù)的性質(zhì)研究中發(fā)揮著重要作用，利用互相關(guān)函數(shù)的定義得到：

證明：根據(jù)互相關(guān)函數(shù)的定義，有：

結(jié)論得證。

注：在定理2中：

在文獻(xiàn)[22]中，利用此等式給出了任意三次布爾函數(shù)的自相關(guān)函數(shù)平方的上界，借助該上界進(jìn)一步研究了多類重要的跡函數(shù)表示的三次布爾函數(shù)的平方和指標(biāo)與絕對(duì)值指標(biāo)的上下界問題。將該上界敘述如下：

所以：

因此，根據(jù)引理得到：

4 結(jié)束語(yǔ)

[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次擴(kuò)散準(zhǔn)則的彈性函數(shù)的全局雪崩特征[J]. 計(jì)算機(jī)應(yīng)用研究, 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] 卓澤朋. 密碼學(xué)中布爾函數(shù)的性質(zhì)和構(gòu)造[D]. 西安: 西安電子科技大學(xué), 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函數(shù)和半-bent函數(shù)的二階非線性度下界[J]. 電子與信息學(xué)報(bào), 2010, 32(10): 2521-2525.

[16] 卓澤朋, 魏仕民, 崇金鳳, 等. 一類三次Bent函數(shù)的二階非線性度[J]. 武漢大學(xué)學(xué)報(bào): 理學(xué)版, 2013, 59(1): 82-86.

[17] 徐 媛, 崇金鳳, 卓澤朋. 一類Bent函數(shù)的二階非線性 度[J]. 計(jì)算機(jī)應(yīng)用研究, 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)

Boolean function; Bent function; auto-correlation function; degree of nonlinearity; Global Avalanche Criterion(GAC);absolute value indicator

1000-3428(2014)03-0180-04

A

TN918.1

安徽省自然科學(xué)基金資助項(xiàng)目(1208085QF119)；安徽高校省級(jí)自然科學(xué)研究基金資助項(xiàng)目(KJ2012Z353, KJ2013Z286)。

卓澤朋(1978－)，男，副教授、博士，主研方向：密碼學(xué)，信息安全；崇金鳳，副教授、碩士；王 慧，講師、碩士。

2013-01-14

2013-03-18 E-mail：zepengzhu@chnu.edu.cn

10.3969/j.issn.1000-3428.2014.03.037