Advances in Applied Mathematics
Vol.3 No.02(2014), Article ID:13492,7 pages DOI:10.12677/AAM.2014.32010

T-D猜想上多输出布尔函数构造

Yiran Chen, Meng Zhou

Key Laboratory of Mathematics, Information and Behaviour of the Ministry of Education, School of Mathematics and System Science, Beihang University, Beijing

Email: 13352225@qq.com, zm1613@sina.com

Copyright © 2014 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received: Feb. 18th, 2014; revised: Mar. 20th, 2014; accepted: Mar. 28th, 2014

ABSTRACT

An improvement has been made on the construction method of Boolean Functions and the relevant conclusions of combinatorial conjecture proposed by Ziran Tu. We generalized their results and extended to the vectorial case. A class of bent Boolean functions F with the maximum algebraic immunity is presented by a more general construction method. Then by modifying F, we get new vectorial balanced functions with optimum algebraic degree, good nonlinearity and good algebraic immunity even maximum algebraic immunity for some cases.

Keywords:Vectorial Boolean Functions, Algebraic Immunity, Bent Function, Balancedness, Nonlinearity

T-D猜想上多输出布尔函数构造

陈怡然,周  梦

北京航空航天大学数学与系统科学学院,数学、信息与行为教育部重点实验室,北京

Email: 13352225@qq.com, zm1613@sina.com

收稿日期:2014年2月18日;修回日期:2014年3月20日;录用日期:2014年3月28日

摘  要

本文针对基于涂自然等人提出的组合猜想上布尔函数的构造方法和有关结论,将组合猜想和构造方法一般化,并将其推广到多输出布尔函数上去,构造出具有最优代数免疫度的多输出bent函数F,同时通过修改F构造出具有好的非线性度、最优代数度和最优代数免疫度兼具的多输出平衡布尔函数函数。

关键词

多输出布尔函数,代数免疫度,Bent函数,平衡性,非线性度

1. 引言

布尔函数作为密码学的重要组成部分,随着信息时代的到来,其研究得到了快速发展。布尔函数按构造可分为单输出布尔函数和多输出布尔函数两种,单输出布尔函数一般用于流密码,而用于构成S-盒的向量布尔函数也叫做多输出布尔函数在分组密码和流密码都有着重要作用。2009年涂自然和邓映蒲提出了T-D猜想,构造出能抵抗代数攻击[1] -[4] 等多种攻击,具有最佳非线性性和代数免疫度[5] 的单输出布尔函数。2011年冯克勤等将其猜想和构造方法推广到多输出布尔函数中,构造出了在一定条件下非线性和代数免疫度很好的多输出布尔函数。后来又出现了基于T-D猜想的各种组合猜想,构造出了更多的密码学性质优异的单输出布尔函数,由此我们基于T-D猜想和其他组合猜想大胆构造出一个一般的组合猜想,并假设这个猜想也可以推广到多输出布尔函数中,从而同样可以构造出更多的密码学性质优异的多输出布尔函数,我们将系统的对这个假设进行验证。

本文主要有这几个部分:第2节介绍相关知识;第3节给出T-D猜想和相关新组合猜想;第4节给出了一类具有最优代数免疫度的偶数元多输出布尔函数的构造;第5节对此多输出布尔函数进行修改,并讨论它的平衡性和非线性度;第6节进行总结和展望。

2. 布尔函数基本知识

2.1. 单输出布尔函数

单输出元布尔函数定义为:设是二元有限域,上的维向量空间,一个元布尔函数是从上的一个映射。元布尔函数的全体记作。一个元布尔函数的基本表示方法是真值表表示,即上的一个长为的向量:。每一个元布尔函数还可以唯一表示为上的含个变元的多项式,称之为的代数正规型(Algebraic Normal Form, ANF):。非零布尔函数的代数次数定义为代数正

规型中系数非零项所含有最多的变元的个数,规定代数系数不超过1的布尔函数为仿射函数,全体元仿射函数的集合记为。设元有限域,则它可以看成上的维向量空间。上的任意布尔

函数也可以表示成唯一的单变元多项式:其中,,且满足。此时的代数次数,这里的二进制展开。

单输出元布尔函数的支撑集定义为:。支撑集所含元素的个数称为的Hamming重量,记为。若,则称元布尔函数是平衡的。两个元布尔函数的Hamming距离定义为

单输出布尔函数的非线性度定义为:

单输出布尔函数的Walsh谱定义为:令都属于。记,则Walsh谱。对于,其点的Walsh谱定义为:其中是从上的迹函数:。对于,其点的Walsh谱定义为:。一个布尔函数是平衡函数当且仅的非线性度也可以由Walsh谱给出:。对任意元布尔函数,有。达到这个上界的布尔函数称为Bent函数[6] 。

单输出布尔函数代数免疫度的定义:对的零化子的集合记作:。布尔函数的代数免疫度(Algebraic Immunity)指的是:的非零零化子的最低次数,即,可以证明,元布尔

函数的代数免疫度不超过[3] [5] 。如果一个元布尔函数的代数免疫度恰好等于,则称该函数具有最优代数免疫度或最大代数免疫度(Maximum Algebraic Immunity),简称MAI函数。

2.2. 多输出(向量)布尔函数

假设,多输出布尔函数定义为:

如果对所有称布尔函数是平衡的,其中,我们知道布尔函数是平衡的当且仅当布尔函数是平衡的,对每个

布尔函数的非线性度定义为:

已经证明出对每个。如果,称布尔函数为bent函数,只有可能当且仅当是偶数且时得到。从定义可以很容易得到布尔函数为bent函数当且仅当对每个,函数是bent函数。

布尔函数的代数度定义为:,如果是平衡的,那么所有都是平衡的,所以

布尔函数的代数免疫度定义为。令是满足的最小整数,那么已经证明,取等号时布尔函数取得最优代数免疫度。

3. 一些组合猜想

猜想1[7] (T-D猜想) 设,对任意,把展开成位二进制数,用表示的展开式中1的个数,对任意,令

[7] 中涂自然和邓映蒲说明了虽然至今无法精确证明此猜想,但已经可以证明当时猜想成立。D.Tang等人在文献[8] 又给出了一个类似的新组合猜想:

猜想2[8] 设。对任意,定义

这个猜想已经被证明[9] ,同时也提出了下面的猜想:

猜想3[8] 设。对任意,定义:

,则

并且,当时,文献[8] 对的情况给出了验证。可见猜想3包括了猜想2这种特殊情况,下面我们在这里将给出一个更一般化的组合猜想:

猜想4设。对任意,定义:

,则

证明文献[10] 中已证明了的情况等同于的情况,这里也可以用同样的手段得出猜想4等同于猜想3。

在文献[11] 中冯克勤等将组合猜想1推广到了多输出布尔函数上,于是大胆假设这几种猜想都同样可以推广到多输出布尔函数中,这里对猜想4进行推广:

猜想5令,定义:

其中对于。令是最大的整数那么

4. 最优代数免疫度的多输出布尔函数

根据上述猜想,和文献[11] 中的构造,给出了一个一般的构造:

构造1令的本原元,是下列个不相交子列的并集:

每个整数有2进制展开,相当于向量。对于每个,我们定义对

那么构造布尔函数

4.1. 代数免疫度

定理1:设是构造算法1中的多输出布尔函数,则,特别的,当

证明为了证明,我们只需要证明如果满足和至少有一个满足,那么。我们将表示为

我们知道

因为,所以

其中,集合是猜想5中定义的。

考虑多项式,我们知道对所有的。因此我们得到

的定义,我们知道,令

非零系数的个数最多为,又对所有。如果,由BCH码[12] 中BCH界知的所有系数都是0。当时,,如果,那么相当于此时是空集。如果不妨设,容易知道,所以中非零系数的个数最多为,而,得到。综上,的所有系数都等于0,即

注:证明的过程中没有用到,因此对任意满足,我们有不论的值是多少

4.2. 一类具有最优代数免疫度的Bent函数

我们可以看出构造1中定义的布尔函数的非线性度随着取值的变化而变化,我们考虑它可否成为非线性度达到最高的bent函数。

引理1:设的本原元,设。其中。定义如下:,其中是定义在上满足的布尔函数。当时,是bent函数。

证明:我们仅需计算。因为,显然

,有

易知,那么一定存在唯一的,使得,而,所以,于是我们有:

1),即对任意

(因为)

2),即对一些

注意到最多只存在一个满足,对

综上,对任意所以是bent函数。

注:事实上,这类bent函数是Dillon提出的PS类函数[13] 。因为

维线性子空间且对于

定理2令是构造1中定义的多输出布尔函数,若,那么是具有最优代数免疫度的bent函数,

证明:要证明F是bent函数,我们需要证明对每个是bent函数。由的定义知对于每个。假设

那么对于每个都存在满足:,从而对每个

因此,对每个满足

我们定义那么对于

对每个非零向量,方程的解的个数是因此,即是平衡的,由引理1知对每个是bent函数,因此是bent函数。

5. 具有最优代数免疫度的平衡布尔函数

平衡性是布尔函数又一个重要的密码学性质,一个非平衡的布尔函数其输出序列的随机性是最不理想的吗,易受区分攻击,bent函数有最大的非线性度,但不是平衡的。这个部分我们将把构造1中布尔函数改造为平衡函数,同时也兼具好的代数免疫度和非线性度。

构造2令的两个本原元。令其中是构造1中定义的布尔函数,定义为:

其中

那么是平衡的,且

证明:因为对任意是不相交的所以是平衡的。的证明参照定

理1后的注。现在只需证明

注意到,其中:

因为相当于

如果,那么

(是证明定理1中构造的平衡函数)。

所以

我们已经知道对于,由文献[14] 中定理3的证明我们知道。因此

6. 总结与展望

我们发现当时,所构造的多输出布尔函数就是文献[11] 中的函数,也就是冯克勤教授等通过对T-D猜想的推广构造出的多输出布尔函数。这里本文的推广给出了可能的更一般的多输出布尔函数构造方法,能提供更多的布尔函数供研究所用,在本文中,我们基于T-D猜想构造出一般化的组合猜想,并将构造方法推广到多输出布尔函数中,构造出具有最优代数免疫度的多输出布尔函数,这时可以通过确定的取值来讨论布尔函数的各种密码学性质,这样更多的布尔函数可被发现并应用。本文还存在一些待解决的问题,如这种构造方法是否比已有方法更优还待考证,不同取值时构造出的布尔函数性质的比较,这类构造方法构造出的布尔函数与已有的多输出布尔函数的比较等等,都是以后的研究重点。

致  谢

本文工作受国家自然科学基金资助,涂自然等的研究成果给予了深厚的研究基础和启发,同时张喆琳硕士提供了重要的参考文献,在此一并致以衷心的感谢。

项目基金

国家自然科学基金NSFC 11271040资助项目。

参考文献 (References)

  1. Armknecht, F. (2004) Improving fast algebraic attacks: FSE 2004. Springer Verlag, 65-82.

  2. Batten, L.M. (2004) Algebraic attacks over GF(q): Cryptology-INDOCRYPT 2004. Springer Verlag, 84-91.

  3. Courtois, N. and Meier, W. (2003) Algebraic attacks on stream ciphers with linear feedback: Cryptology-EUROCRYPT 2003. Springer Verlag, 345-359.

  4. Courtois, N. (2003) Fast algebraic attacks on stream ciphers with linear feedback: Advances in Cryptology-CRYPTO 2003. Springer Verlag, 176-194.

  5. Meier, W., Pasalic, E. and Carlet, C. (2004) Algebraic attacks and decomposition of Boolean functions: CryptologyEUROCRYPT 2004. Springer Verlag, 474-491.

  6. Rothaus, O.S. (1976) On bent functions. Journal of Combinatorial Theory A, 20,300-305.

  7. Tu, Z. and Deng, Y. (2010) A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity. Designs, Codes and Cryptography, 1-14.

  8. Tang, D., Carlet, C. and Tang, X. Highly nonlinear Boolean functions with optimum algebraic immunity and good behavior against fast algebraic attacks. Cryptology ePrint Archive. http://eprint.iacr.org/2011/366.pdf

  9. Cohen, G. and Flori, J.P. On a generalized combinatorial conjecture involving addition mod 2k-1. Cryptology ePrint Archive. http://eprint.iacr.org/2011/400.pdf

  10. Jin, Q., Liu, Z., Wu, B. and Zhang, X. A general conjecture similar to T-D conjecture and its applications in constructing Boolean functions with optimal algebraic immunity. Cryptology ePrint Archive. http://eprint.iacr.org/2011/515.pdf

  11. Feng, K. and Yang, J. (2011) Vectorial Boolean functions with good cryptographic properties. International Journal of Foundations of Computer Science, 22, 1271-1282.

  12. MacWilliams, F.J. and Sloane, N.J.A. (1977) The Theory of Error-Correcting Codes. North-Holland, Amsterdam.

  13. Dillon, J.F. (1974) Elementary hadamard difference sets. Ph.D. Thesis, University of Maryland, College Park.

  14. Carlet, C. and Feng, K. (2009) An infinite class of balanced vectorial Boolean functions with optimal algebraic immunity and good nonlinearity. In: Xing, C., et al., Eds., Proceedings of the IWCC 2009, 1-11.

期刊菜单