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资助项目。
参考文献