 Pure Mathematics 理论数学, 2013, 3, 120-125 http://dx.doi.org/10.12677/pm.2013.32019 Published Online March 2013 (http://www.hanspub.org/journal/pm.html) A Generalization of One Class of Semi-Bent Functions with Polynomial Trace Form Hao Chen, Xiwang Cao College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing Email: chenhao246@sina.cn, xwcao@nuaa.edu.cn Received: Dec. 22nd, 2012; revised: Feb. 5th, 2013; accepted: Feb. 21st, 2013 Abstract: This paper is devoted to generalize a class of semi-Bent functions with even number of variables on the finite filed 2n F . We define the functions 21213 2121211 ,2 ,,, 1111 mn mm r ax s rs nnn abcd gxTrTr bxTrcxTrdx and 21r213 2 ,1 1 mn rn ab fxTraxTr bx , where 2nm with odd, r is a positive integer and m 0,1 4,1 6,3s, and . In the paper [1], S. Mesnager has discussed whether could be semi-Bent function under the situations 4 22 ,, nn aFbFcF 2,dFx2n F , ,,, rs abcd g3r and ,211 m r. In this paper, we will give a further investigation on the function by removing the restrictions on r. We need to note that Kloosterman sums and cubic sums are essential to this paper. , ,, rs abc g, d Keywords: Boolean Functions; Semi-Bent Functions; Walsh-Hadamard Transformation; Kloosterman Sums; Cubic Sums 一类带有多项式迹形式的 Semi-Bent 函数的推广 陈 浩，曹喜望 南京航空航天大学理学院，南京 Email: chenhao246@sina.cn, xwcao@nuaa.edu.cn 收稿日期：2012 年12 月22 日；修回日期：2013 年2月5日；录用日期：2013 年2月21 日 摘 要：本文的主要是对一类已知的 semi-Bent 函数作进一步的推广。首先，我们来定义下列两个位于 有限域上的具有多项式迹形式的布尔函数 21213 2121211 ,2 ,,, 1111 mn mm r s rs nn abcd gxTr axTrbxTr cxTr dx n 及 21 213 2 ,1 1 mn r rn ab fxTraxTr bx ，其中 2nm 且 为奇数，r是一个正整数且m 0,1 4,1 6,3s， 及 。在文献[1]中，S. Mesnager已经讨论了当 或者 时，函数可能成为 semi-Bent 的情形。在本文中，我们将取消对 r的任何的限制条件，进一步的 讨论函数 成为 semi-Bent 函数的条件。在推广结论的过程中，我们要借助于Kloosterman 和以及 Cubic 和这两样工具。 4 22 ,, nn aFbFcF , ,,, rs abcd g , ,,, rs abcd g 22 ,n dFxF 3r ,21 1 m r 关键词：布尔函数；Semi-Bent 函数；Walsh-Hadamard 转换；Kloosterman 和；Cubic 和 Copyright © 2013 Hanspub 120  陈浩，曹喜望 一类带有多项式迹形式的 Semi-Bent 函数的推广 1. 引言 Bent 函数是 Rothus[2]于1976年提出的一类特殊的布尔函数，它满足到所有的仿射函数的汉明距离都等于 12 22 nn 1 ，Bent 函数仅存在于变量个数为偶数的情形。Bent 函数由于其在代数及组合学方面的良好性质以及 在密码和编码理论及序列等方面的多重应用而被广泛研究。Bent函数的定义是比较简单的，但是需要特别强调 的是，在当前的数学水平下想要对它们进行明确的分类是不可行的。因此，想要尽可能多的了解它们，找出构 造方法就显得尤为重要。 Semi-Bent 函数的概念于1994 年由 Chee、Lee及Kim[3]在亚洲的一个重要的密码学会议Asiacrypt上提出。 和Bent 函数一样，semi-Bent函数也由于其拥有的一系列优异的性质而被广泛的研究[4]。但是与 bent函数不同 的是，semi-Bent 函数对于变量个数的奇偶性没有限制。当 取奇数的时候，semi-Bent 函数的 Walsh-Hadamard 转换的值为 或者 n 0 12 2n ；当 取偶数的时候，semi-Bent 函数的 Walsh-Hadamard 转换的值为 或者 n0 22 2n 。 在本文中，我们只研究变量个数为偶数的semi-Bent 函数。Semi-Bent 函数都是平衡函数并且在平衡且达到稳定 的函数中具有极大非线性性[5,6]。读者可以阅读文献[7]去了解平衡布尔函数的更多的性质。迄今为止，几乎所有 的semi-Bent 函数都是由选择合适的 的幂多项式 d 1nd Tr x 导出的[8,9]。 本文的主要结构如下：第二节介绍一下必要的基础知识；第三节明确一些特定的记号以及归纳总结一些基 本定理；在第四节中，我们将对一类含有多项式迹形式的 semi-Bent 函数进行推广。 2. 背景知识简介 令2n F 是含有 个元素的有限域， 2n 2n F 是它的所有非零元素构成的乘法群。在本文中我们主要讨论位于 2n F 或 者是 2n F 的子域上的布尔函数。 2.1. 布尔函数的迹表示 设， 是正整数并且满足整除 时，我们用表示从m nmnn m Tr 2n F 到2m F 的迹函数，即 22 2 , nm n n m Trxx xxxF 特别地，当 时，称为绝对迹函数，它满足性质 1m11 nm m TrTr Trn 。 有限域 2n F 上的每个非零布尔函数 f x都有如下形式的迹表示： 21 12 1, n n n oj j j j f xTraxexx F 1 . 其中，表示从 模的每个分圆陪集中选取一个代表元所形成的整数的集合，表示包含元素 的上 述分圆陪集的大小且 ，e的值为或 。因为布尔函数的迹表示是唯一的，所以它又被称为布尔函数的 多项式形式。 n 22 n 2 j aF oj j oj 01 2.2. Walsh变换，Semi-Bent 函数的定义 定义 2.2.1 有限域2n F 上的布尔函数 f x的Walsh变换定义为 2 12 ˆ,n n n fxF f xTr xF 其中 满足对于 2,1 n x xFx 。 利用 Walsh 变换，我们可以给出 semi-Bent 函数的定义[3,10]。 定义 2.2.2 设 f x是2n F 到2 F 的函数。当 为偶数时，若对于n2n F ，都有 22 ˆ0,2n f ，则称 f x是semi-Bent 函数；当 为奇数时，若对于n2n F 都有 12 ˆ0,2n f ，则也称 f x是semi-Bent Copyright © 2013 Hanspub 121  陈浩，曹喜望 一类带有多项式迹形式的 Semi-Bent 函数的推广 函数。 2.3. 极分解、Kloosterman 和、Cubic 和 设 21 21 m n UxFx ,则 是有限域U2n F 的循环群的一个阶为 2 m1 的子群。根据有限域的知识可知， 2n F 的每一个非零元素 x 都有唯一的分解： x uy，其中 2 ,m uUyF 。 定义 2.3.1 有限域 2n F 上的 Kloosterman 和定义为 2 12 1,m m m mxF K aTraxa x F 0x 其中，当时，我们规定 111 m Tr x 。 Lachaud 和Wolfman 已经计算出了2m F 上的 Kloosterman 和取值范围。 引理 1[11] 对于 ， 2m aF m K a的值 s 满足 21 21 21,2 mm s 1 及 0mod4s。 定义 2.3.2 有限域 2m F 上的 Cubic 和定义为 2 3 14 2 ,, m m m mxF bCabTrax bxaFF , 。 读者可以参考文献[12]去了解更多的关于 Cubic 和的取值问题。 3. 循环群 U上的特征和 在本文中，我们总是假设 为奇数。设2,nmm 是2n F 的一个本原元，则U是由 生成的一个循环 21 m 群并且 21 3 n 是U的一个 3次单位根。设 3 VuuU，则U可以表示为如下形式： 2 0i i UV 。 函数 21 21 23 ,1 1 n m r rn ab fxTrax Trbx ，4 2, n aFbF ，2n x F我们定义如下形式的记号： ,, r rab ab uU f fu ， ,0 r ri ia vV Sf v, 则有 01 2,0,0 r rrr ar uU SSSfu f a i . 当时，记。特别的，对于任意的整数 ，我们有。 1r1 i SSi mod3 r r ii SS 由定理[1,11,13]，我们可以总结出下面的结论。 引理 3 设 是一个正整数且满足 。设 ，则 r ,21 1 m r 2m aF 1) ,0 1 ra m f Ka； 2) 00 1, rmm SS CaaKa 3； 3) 12 1, rr mm SS CaaKa 3。 4. 主要结论 本节中，我们主要讨论 在没有任何限制条件的情形下r ,rab f 的取值情况。 引理 4.1 设为奇数。设2,nmm4 bF ，2m aF 且 是的生成元。如果U ,21 31 m r ，那么 Copyright © 2013 Hanspub 122  陈浩，曹喜望 一类带有多项式迹形式的 Semi-Bent 函数的推广 ,1 rab f。 证明：假设 ,21 31 m rd，那么映射 是U上的一个对1映射。因为 ，所 以 d uud 21,211 mm 213 2 ,11 213 2 11 . m m nr rab uU d nrd uU fTrauTrbu dTrauTrbu 由于 213 2 11 md nrd uU Tr auTrbu 的值为正整数且 为整数，所以 d ,1 rab f 。 假设 ,21 31 m ，我们继续讨论 ,rab f 的取值情况。 r 定理 4.2 设 为奇数。设2,nmm 是U的生成元。设 4 bF ，2n aF 满足 j aav ，其 中2m aF ，vV ,21 31 r 且 。当 0, 1,2j m时，下述结论成立。 ,rab j f S 。 1) 若 ，则 0mod3r 2) 若 ，则下列结论成立： 1mod3 r 0j a) ，时，1b ,0rab f S； 当， 时，1b ,0 2 rab 0j1 f SS 。 b 时， ,0rab f S；当 1j ,b 时， ,0 2 rab 1 f SS。 b) , 1j 2 b 时， ,0rab f S ；当 2j ，2 b 时， ,0 2 rab c) ，2j1 f SS。 3)若 ，则下列结论成立： 2mod3 r 0j a) ，时， 1b ,0rab f S；当 0j ,1 b 时， ,0 2 rab 1 f SS。 2 b 时， ,0rab f S ；当 1j ，2 b 时， ,0 2 rab b) ，1j1 f SS。 时， ,0rab f S ；当 2j ，b 时， ,0 2 rab c) ，b2j1 f SS 。 证明：因为 ,21 31 m r ，所以映射 21r vv m 是V上的一个置换。由于 ，我们有 。又因为 ， 210mod3 m 211m m od3 21 m 213 n ，则 21 31 m rrrvr ，其中 。我们有 1 vV , 21 2 2 21 21 22 3 11 11 0 0 22 22 11 11 00 n mm rab rir niii nr ivVi vV inir inirj ivV ivV f Tr avTrbvTrbTr av Tr bTravTrbTrav 1) 若，则 且 0mod3 rV r vv 是 上的一个置换。由特征的正交关系可得V 22 1 0 1 i i Trb 。 r 所以， 22 ,1 1 0 inj ab j ivV f Tr bTravS . 2) 若，则假设 ，那么有 1mod3 31rk ir j v ，vV 。因此， r 22 ,1 1 0 ini rab ivV j f Tr bTr av Copyright © 2013 Hanspub 123  陈浩，曹喜望 一类带有多项式迹形式的 Semi-Bent 函数的推广 213 n 因为且，所以当 210 1b 时，我们 有 2 11 1 nn Tr bTr b 且 11 n Tr b ； 当 时， 1b 1n Tr b 1 以及 2nn b b 11 Tr 0Tr 。 因此，1) 当 时， i 0j 22 ,1 1 0 in rab ivV f Tr bTrav a) 当时，根据 1)中的讨论内容，有 1b ,0120 2 rab 1 f SSSSS； b) 类似地，当时，我们有0 ,012rab f SSS Sb ； 时， c) 当2 b ,012rab 0 f SSSS。 2) 当1j时， 2 ,1 1 0 ini rab ivV 21 f TbTrav r a) 若 ，则0 1b ,120rab f SSS S； b) 若b ，则 1 ,120 2 rab f SSS S S； ,120rab c) 若2 b 0 f SSSS。 2 ，则 3) 当 时， 2j 2 ,1 1 0 ini rab ivV 2 f Tr bTrav a) 若 ，则1b ,210rab 0 f SSS S； b) 若b ，则 ,201rab 0 f SSS S； c) 若2 b ，则 0 ,2012 rab 1 f SSSS S ir 。 ，则假设 ，我们 3) 若 mod3r有232rk 2i v ，vV 。因此， 2 j 2 1 0 ini ra iv 2 ,1 b f Tr b于2) V Tr av 使用类似 的讨论方法即可得出结论，在此我们省略具体步骤。 由文献[1]的推论 1、推论2，以及本文的引理 3.1、定理 4.2，我们可以得到下面的结论。 推论 4.3 设 为奇数。设2,nmm 是 的生成元。U设bF 4 ，2n aF 满足 j aav ，其 中2m aF ，vV 0,1,2。当 j ,21 31 m r时，则 ,1 rab f当且仅当 且 1) 若 1mr 2mod3r，则 4 m Ka ； od3或者 2) 若 ，则 时， 0mod3r a) 当 m 0j4Ka ； 时， b) 当 m 0j ,4 m Ka Caa 。 们对 [1]中的 seent 函数作推广，在此之前我们先定义一个位于有限域2n F 现在我 文献mi-B 上的布尔函数。这 个布 的表达式为 尔函数 21213 212121 ,2 ,,, mn mm r rs nnn abcd gxTr axTrbxTr cxTr dx 1 1 111 s 其中， 是整数，及r4 22 ,, nn aFbFcF 2 dF 0,1 4,1 6,3s。需要说明的是，在此我们只讨论 0d 时的情 形，至于 为奇数。设 1d时的情形，推广的结果同样成立。 定理 4.4设n2,mm 是22 \ nm F ，4 bFU的生成元。设cF ，2n aF 满足 j aav ，其中 Copyright © 2013 Hanspub 124  陈浩，曹喜望 一类带有多项式迹形式的 Semi-Bent 函数的推广 Copyright © 2013 Hanspub 125 2m aF ，V 且 0, 1,2j。 v 1) 若 ,2 m r，则 , ,,, rs abcd g不是 mi-Bent 函数。 若 se 1 31 2) ,2 m r 1mr 1 31，则是 semi-Bent 函数的充要条件是 或者 ，则 , ,,,0 rs abc g od3 2mod3r 4 m Ka ； ，则 时， ①若 ②若 r od30m 0j a) 当 m 4Ka ； 时， b) 当 m ,4 m Ka Caa 0j。 本文主要 一类含有多项式迹形式的位于有限域 5. 结束语 是对 2n F 中的 semi-Bent 函数作进一步的推广，使得这一类的 广泛的形式及更少的限制条件，这样更有助于具有此类形式的 semi-Bent 函数在编码理论 erences) emi-Bent functions from Dillon and Niho exponnets, Kloosterman sums and Dickson polynomials. IEEE Transactions on In- 7443-7458. Journal of Combinatorial Theory, Series A, 1976, 20: 300-305. semi-Bent函数具有更 等方 [1] S. M 面的应用。 参考文献 (Ref snager. Se formation Theory, 2011, 57(11): [2] O. S. Rothus. On “bent” functions. [3] S. Chee, S. Lee and K. Kim. Semi-Bent functions. Advances in cryptology-Asiacrypt 94. In: J. Pieprzyk, R. Safavi-Naini, Ed s., Proceedings of the 4th International Conference on the Theory and Applications of Cryptology, Wollongong, Australia. Lecture Notes on Computer Science, 1994, 917: 107-118. [4] X. Y. Zeng, C. Carlet, J. Y. Shan and L. Hu. More balanced Boolean functions with optimal algebraic immunity and nonlinearity and resistance to fast algebraic attacks. IEEE Transactions on Information Theory, 2011, 57(9): 6310-6320. [5] Y. Zheng, X. M. Zhang. Plateaued functions. Advances in Cryptology-ICICS Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag, 1999, 1726: 284-300. [6] Y. Zheng, X. M. Zhang. Relationships between bent functions and complementary plateaued functions. Lecture Notes on Computer Science, 1999, 1787: 60-67. [7] X. Y. Zeng, L. Hu. Constructing Boolean functions by modifying Maiorana-McFarland's superclass functions. IEICE Transactions on Funda- mentals, 2005, 88(1): 59-66. [8] P. Charpin, E. Pasalic and C. Tavernier. On bent and semi-Bent quadratic Boolean functions. IEEE Transactions on Information Theory, 2005, 51(12): 4286-4298. [9] G. Sun, C. Wu. Construction of semi-Bent Boolean functions in even number of variables. Chinese Journal of Electronics, 2009, 18(2): 231- 237. [10] J. H. Ch e on , S. Chee. Elliptic curv es and resilient functions. Lecture Notes on Computer Science, 2000, 2015: 386-397. [11] G. Lachaud, J. Wolfmann. The weights of the orthogonals of the extended quadratic binary Goppa codes. IEEE Transaction s on Information Theory, 1990, 36(3): 686-692. [12] L. Carlitz. Explicit evaluation of certain exponential sums. Mathematica Scandinavica, 1979, 44(1): 5-16. [13] P. Charpin, T. Helleseth and V. Zinoviev. Divisibility properties of Kloosterman sums over finite fields of characteristic two. Toronto: In ISIT, 2008: 2608-2612. |