三類布爾函數的相關函數研究

卓澤朋，崇金鳳，王 慧

?

三類布爾函數的相關函數研究

卓澤朋，崇金鳳，王 慧

(淮北師范大學數學科學學院，安徽 淮北 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)

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

安徽省自然科學基金資助項目(1208085QF119)；安徽高校省級自然科學研究基金資助項目(KJ2012Z353, KJ2013Z286)。

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

2013-01-14

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

10.3969/j.issn.1000-3428.2014.03.037