《1 引言》
1 引言
由于具有抗差分攻击和最优仿射逼近的能力, 以及具有最高的非线性度和高度的稳定性
众所周知, 构造剩余类环上完全非线性函数是比较困难的, 笔者在用2-基分解的思想研究剩余类环上完全非线性函数新构造方法时, 发现了一类新的布尔函数类, 对这类函数做一种类似于“差分”的运算后可以得到平衡函数, 于是定义了布尔函数的“类差分”和布尔函数中的类差分平衡函数, 研究了类差分平衡函数的性质, 给出了类差分平衡函数的一些构造方法。作为类差分平衡函数的重要应用, 给出了Z
将会看到, 由于Z
《2 基本概念》
2 基本概念
以GF (2) 表示二元域, 记Ω=GFn (2) , F={A:A⊂Ω}, 可测空间 (Ω, F) 上的概率测度P (·) 满足
又定义
《图1》
《图2》
易知X1, X2, …, Xn是概率空间 (Ω, F, P) 上的n个相互独立的布尔随机变量, 且满足
从GFn (2) 到GF (2) 的一个映射称为布尔函数, 布尔函数f可以用关于x1, …, xn的多项式唯一表示, 该多项式称为f的代数标准形, 简记为ANF
它反映了f与各个仿射函数的距离, 分组密码中的线性攻击和流密码中的相关攻击都等价于寻找一个与给定布尔函数距离最近的仿射函数或线性函数。自相关函数rf (s)
它反映了当输入改变量为s时的输出与原输出的符合优势, 显然, rf (s) =0等价于差分函数f (x+s) + f (x) 平衡。布尔函数的Walsh循环谱与自相关函数之间有如下联系
如果对任意的w∈GFn (2) 都有[S (f) (w) ]2=2-n (等价于对任意的0≠s∈GFn (2) , 都有rf (s) =0) , 则称f是Bent函数。
《3 类差分平衡函数及其性质》
3 类差分平衡函数及其性质
《3.1类差分函数与类自相关函数》
3.1类差分函数与类自相关函数
在这节中n为正偶数。
定义1 设f (x) , x= (x1, …, xn) ∈GFn (2) 是布尔函数, 对s= (s1, …, sn) ∈GFn (2) , 称
为f (x) , x= (x1, …, xn) ∈GFn (2) 在s点的类差分函数。
为了书写方便, 记
《图3》
注意:此处的x⊕s不同于通常意义下2个n维布尔向量之间的逐个比特模2加。
定义2 设f (x) , x= (x1, …, xn) ∈GFn (2) 是布尔函数, x⊕s的定义如式 (3) , 称
《图4》
为f (x) 关于变量组 (x1, x2) , …, (xn-1, xn) 的类自相关函数, 简称为f (x) 的类自相关函数。
注1 δf (s) =0的充要条件是类差分函数f (x⊕s) +f (x) 平衡。
注2 由于当s的下标为奇数的分量都是0, 即s形如 (0, s2, …, 0, sn) 时,
《图5》
故此时有δf (s) =rf (s) , 其中rf (s) 是布尔函数f (x) 自相关函数在s= (0, s2, …, 0, sn) 处的函数值, 特别地有δf (0) =rf (0) =0。
另外δf (s) , s∈GFn (2) 还有如下特点:
定理1 设f (x) , x= (x1, …, xn) ∈GFn (2) 是布尔函数, ek∈GFn (2) 是n维标准单位向量——只有第k分量是1的布尔向量, 1≤k≤n, 则
证明 只证δf (e1) =δf (e1+ e2) , 其他类似可证。由式 (4) 容易得到
《图6》
注意对任意的x= (x1, …, xn) ∈GFn (2) , 可有
《图7》
其中hi (x3, …, xn) , 0≤i≤3是关于 (x3, …, xn) 的n-2元布尔函数, 因而有
《图8》
于是
《图9》
《图10》
类似可证
《图11》
所以,
《图12》
再由式 (5) 即知δf (e1) =δf (e1+e2) 。
自相关函数和Walsh循环谱之间有关系式 (2) , 那么类自相关函数和Walsh循环谱之间是否也有类似的关系?事实上只有在形如w= (w1, 0, …, wn-1, 0) 的点处类似的关系式才成立。
定理2 设f (x) , x∈GFn (2) 是布尔函数, 其类自相关函数和Walsh谱分别为δf (s) 和S (f) (w) , 则在形如w= (w1, 0, …, wn-1, 0) 的点处下列等式成立:
《图13》
证明 首先注意有
《图14》
所以
《图15》
因而, 对任意的w∈GFn (2) , 根据类自相关函数的定义及式 (6) 可得:
《图16》
将定理题设条件w2=…=w2k=…= wn=0代入式 (7) , 再用式 (1) 即得
《图17》
《3.2类差分平衡函数》
3.2类差分平衡函数
定义3 设f (x) , x∈GFn (2) 是布尔函数, 若对任意的0≠s∈GFn (2) , 类差分函数f (x⊕s) + f (x) , x∈GFn (2) 都平衡, 等价的就是δf (s) =0, 则称f (x) 是关于变量组 (x1, x2) , … , (xn-1, xn) 的类差分平衡函数。
根据类差分平衡函数的定义, 可以验证x1x2, x1x4+x2x3, x1x6+x2x4+x3x5+x1x2x3x5分别是二元、四元、六元类差分平衡函数, 所以类差分平衡函数的存在性是勿庸置疑的。
由于布尔函数的许多密码学性质都可以通过其Walsh谱予以刻画, 下面来考察类差分平衡函数的谱特征。由定理2可以得到类差分平衡函数的Walsh循环谱的取值有如下特点:
定理3 若f (x) , x∈GFn (2) 是类差分平衡函数, 则一定有
《图18》
证明 因为f (x) 是类差分平衡函数, 故对任一0≠s∈GFn (2) , 都有δf (s) =0, 且δf (0) =1, 由定理2即知, 当w= (w1, 0, …, wn-1, 0) 时有
《图19》
定理4 若f (x) , x∈GFn (2) 是类差分平衡函数, 则其常义下的自相关函数rf (s) 满足
《图20》
证明 由前述关于类自相关函数定义的注2即得。
众所周知, n元Bent函数的代数次数至多可达到n/2, 即在n元Bent函数的多项式表达式中代数次数大于n/2的单项式的系数都是0, 然而对于类差分平衡函数可以得到下面的结论:
定理5 若f (x) , x= (x1, …, xn) ∈GFn (2) 是类差分平衡函数, 则当n≥4时, f (x) 的ANF中不含有以x2x4…xn作为因式的单项式。
证明 设i1, i2, …, ik是奇数, 且1≤i1≤i2≤ … ≤ik≤n-1, 记
《图21》
则由文献
《图22》
《图23》
而当k=1时,
例如, 四元类差分平衡函数的多项式表达式中不含有x1x2x4, x2x3x4, x1x2x3x4六元类差分平衡函数的多项式表达式中不含有x1x2x4x6, x2x3x4x6, x2x4x5x6, x1x2x3x4x6, x1x2x4x5x6x2x3x4x5x6, x1x2x3x4x5x6等, 所以定理5为确定类差分平衡函数的多项式表达式提供了一定的理论依据。
《4 类差分平衡函数与Bent函数的关系》
4 类差分平衡函数与Bent函数的关系
由于布尔函数的类差分和差分的运算法则不同, 所以类差分平衡函数和Bent函数这2个概念是有区别的, 例如类差分平衡函数x1x6+x2x4+x3x5+x1x2x3x5就不是Bent函数, 而四元Bent函数x1x2+x3x4+x2x4等也不是类差分平衡函数。 但类差分平衡函数与Bent函数也有一些相同的地方, 例如在形如 (w1, 0, …, wn-1, 0) 点的循环谱的二次方都是2-n, 在形如 (0, s2, …, 0, sn) 的点处的差分都平衡等。因此类差分平衡函数与Bent函数是交集非空的2个不同的函数类。关于二者的联系, 有下面的定理:
定理6 代数次数为2的类差分平衡函数都是Bent函数。
证明 由于代数次数为2的布尔函数都是部分Bent函数
下面的定理7可以用来判定Bent函数何时是类差分平衡函数。
定理7 若f (x) , x∈GFn (2) 是Bent函数, 且其循环谱满足:对任意的
《图24》
都成立
《图25》
则f (x) , x∈GFn (2) 是类差分平衡函数。
证明 这是因为一方面由f (x) 是Bent函数知
《图26》
另一方面根据式 (7) 和式 (8) 又有
《图27》
因而有
即f (x) 是类差分平衡函数。
满足定理7中条件的Bent函数是存在的, 例如f (x, y) =xy, x, y∈GF (2) 便是一类。
《5 类差分平衡函数的构造》
5 类差分平衡函数的构造
定理8 形如
的布尔函数都是关于变量组 (x1, x2) , … , (xn-1, xn) 的类差分平衡函数, 其中
是关于变元 (x1, x3, …, xn-1) 的任一布尔函数。
证明 因为形如式 (9) 的布尔函数都是Bent函数
所以对于任意的0≠s∈GFn (2) , 都有δf (s) =rf (s) =0。
引理1 设fi (x (i) ) , x (i) , ∈GFni (2) , 1≤i≤k都是布尔函数, x (i) ∈GFni (2) , x= (x (1) , x (2) , …, x (k) ) , f (x) = f1 (x (1) + f2 (x (2) ) + … + fk (x (k) ) , s (i) ∈GFni (2) , s= (s (1) , s (2) , …, s (k) ) , δf (s) 是f (x) 的类自相关函数, 则有
证明 为记号简单, 仅证k=2时结论成立:记s= (s (1) , s (2) ) ∈GFn1+n2 (2) , 其中s (1) ∈GFn1 (2) , s (2) ∈GFn2 (2) , 则由类自相关函数的定义知
《图28》
由引理1不难得到下面的类差分平衡函数的构造方法:
定理9 设fi (x (i) ) , x (i) ∈∈GFni (2) , 1≤i≤k都是布尔函数, 则
是类差分平衡函数的充分必要条件是fi (x (i) ) , x (i) ∈GFni (2) , 1≤i≤k都是类差分平衡函数。
证明 充分性显然。
必要性 设f1 (x (1) ) +f2 (x (2) ) +…+fk (x (k) ) , x (i) ∈GFni (2) 是类差分平衡函数, 由引理1, 对任意的0≠s= (s (1) , s (2) , …, s (k) ) , 都有
特别取s (1) ≠0, 而s (i) =0, 2≤i≤k, 即知
因δfi (0) =1, 2≤i≤k, 故对任意的s (1) ≠0, δf1 (s (1) ) =0, 可见f1 (x (1) ) 是类差分平衡函数, 同理可知, fi (x (i) ) , 1≤i≤k都是类差分平衡函数。
在构造密码函数时, 总希望所构造的函数具有较高的代数次数和不要过于简单的代数结构形式, 而由定理9所构造的布尔函数的代数次数不会超过2个函数的代数次数的最大值, 结构形式也过于简单, 为了构造具有较高代数次数, 代数形式稍微复杂的密码函数, 有必要去寻求其他的构造方法, 定理10将给出一种新的构造方法, 这里处理问题的思想方法不同于Rothous 在文献
定理10 设fi (x (i) ) , x (i) ∈GFni (2) , i=1, 2都是类差分平衡函数, 若存在hi (x (i) ) , i =1, 2 使得fi (x (i) ) +hi (x (i) ) , i=1, 2也都是类差分平衡函数, 则下述函数是类差分平衡函数:
用与文献
例 设f1 (x (1) ) =x1x2+x1x5+x1x6+x2x3+x2x6+x4x6+x2x3x4+x1x3x4x5, f2 (x (2) ) =x7, h1 (x (1) ) = x1x6+x2x4+x3x5+x1x2x3x5, h2 (x (2) ) =x7x8, 则上述函数满足定理10的条件, 故f1 (x (1) ) + f2 (x (2) ) + h1 (x (1) ) h2 (x (2) ) 是代数次数为5的类差分平衡函数。
《6 类差分平衡函数的应用》
6 类差分平衡函数的应用
下面给出类差分平衡函数在Z4上完全非线性函数构造中的应用。
定义4
因在Z4上完全非线性函数的概念中涉及到变元之间以及逻辑函数之间的模4加法、减法运算, 故先给出2-基分解意义下各个变量yi∈Z4, 1≤i≤n及函数f的2-基分解表示:
当y1∈Z4时, y1可以分解表示为
其意义是
称y1= (x1, x2) 为y的2-基分解。由此不难知道, 当v1∈Z4的2-基分解为v1= (s1, s2) 时, y1和v1在Z4中的“和”y1+v1的2-基分解即为
在2-基分解的意义下, Z
其中f1 (y1, y2, …, yn) , f2 (y1, y2, …, yn) 都是定义在Z
所以可将定义在Z
《图29》
《图30》
对于a=a1+2a2, b=b1+2b2∈Z4, 易知a和b在Z4中的“差”a-b的2-基分解为
由式 (10) 知, 在上述意义下, 对v∈Z
可如下转换
再将y+v, y都用2-基分解表示可得到
f (y+v) -f (y) =[f1 (x1+s1, s1x1+
x2+s2, …, xn-1+sn-1, sn-1xn-1+xn+sn) +
f1 (x) ]mod2 +2[f1 (x1+s1, s1x1+x2+s2 , …,
xn-1+sn-1, sn-1xn-1+xn+sn) f1 (x) +
f1 (x) +f2 (x1+s1, s1x1+x2+s2, …, xn-1+
sn-1, sn-1xn-1+xn+sn) +f2 (x) ]mod2 =
[f1 (x⊕s) +f1 (x) ]mod2+2{[f2 (x⊕s) +
f2 (x) +f1 (x) +f1 (x⊕s) f1 (x) ]mod2}, (12)
其中
运用式 (11) 和式 (12) 及相关知识可以得到如下定理:
定理11 4值逻辑函数f (y) , y∈Z
差分函数f (y+v) -f (y) 的2-基分解表示式 (11) 中的2值布尔函数
都平衡, 等价的就是式 (12) 中的2n元布尔函数
都平衡。
证明 必要性显然。充分性由定理的假设及文献
注3 由定理11的结论知, 若记n元四值完全非线性函数f (y1, y2, …, yn) 的“2-基分解”为
则作为关于 (x1, x2, …, x2n-1, x2n) 的布尔函数
一定是关于变量组 (x1, x2) , …, (x2n-1, x2n) 的类差分平衡函数。
根据定理11若想构造Z
假设f1 (x) , f2 (x) 的常数项为0。首先通过理论分析找到所有的四元类差分平衡函数, 共192个, 然后对于每个四元类差分平衡函数f1 (x) , 通过上机搜索找到与上述各四元类差分平衡函数做成二元四值完全非线性函数的四元布尔函数f2 (x) , 共得到16 384个二元四值完全非线性函数。另外, 可以证明完全非线性函数的2个分量函数中的任意一个分量加1后所得到的新的函数仍然是完全非线性函数, 所以二元四值完全非线性函数的总个数为16 384×4=65 536。这个搜索过程在Pentium (Ⅳ) 计算机上用不到2 h的时间便全部完成, 而若直接按照真值表穷尽搜索所有的二元四值完全非线性函数, 搜索量是416, 如果没有快速算法这个计算量在普通计算机上实施起来是比较困难的, 可见类差分平衡函数的研究是很有意义的。下面给出用这种方法得到的2个二元四值完全非线性函数:
《7 结语》
7 结语
笔者提出了类差分平衡函数的概念, 讨论了类差分平衡函数的性质及其在剩余类环上的完全非线性函数研究中的应用。因为完全非线性函数的直和仍然是完全非线性函数, 所以Z4上关于任意正偶数个变量的完全非线性函数都存在, 并且上面得到的二元四值完全非线性函数可以大量构造。
计算表明, 当m>2时, 环Z2m上的完全非线性函数的2-基分解意义下的第一个分量函数的形式和性质与类差分平衡函数相似, 故类差分平衡函数的研究对环上的完全非线性函数的研究也有重要的指导意义;另外, 用2-基分解的方法研究环上的问题, 这一思想还可用于一般剩余类环Zpm (p是大于2的素数) 上该类逻辑函数的研究中。
关于类差分平衡函数的研究仍然有许多遗留问题, 比如类差分平衡函数是否像Bent函数那样非退化?其谱特征和自相关特征为何?笔者曾经计算了大量的六元类差分平衡函数的Walsh谱及自相关函数值, 发现这些六元类差分平衡函数都是非退化的, 其Walsh谱至多取下述5个值:0, ±2-3, ±2-2, 其自相关函数在非零点至多取下述3个值:0, ±2-2。 由此猜测n元类差分平衡函数的Walsh谱取值可能比较均匀;自相关函数在非零点的绝对值也比较均匀。 故类差分平衡函数除去可用于构造Z