（中國電子科技集團公司第三十研究所 成都 610041）

1 引言

2 準備工作

首先給出相關免疫的概念。

定義1設f(x1，x2，…，xn)是一個n元布爾函數，其中x1，x2，…，xn是均勻分布的獨立隨機變量，如果f與x1，x2，…，xn中任意的m個變元xi1，xi2， …，xim統(tǒng)計獨立，即對任意a1，a2，…，am和a，均有：

則稱f是m階相關免疫函數。

定義2平衡的m階相關免疫函數稱為m-彈性函數。

定義3f的Walsh譜為

這里，ωx=ω1x1+ω2x2+…+ωnxn。

由文獻［6］得以下定理。

定理1布爾函數f(x1，x2，…，xn)是m-彈性函數當且僅當對任何a∈F2n，0≤wt(a)≤m，均有F(a)=0。

由文獻［1］得以下定理。

定理2設布爾函數f(x1，x2，…，xn)是m-彈性函數，這里 ，n≥3并 且m≤n-3，則F(ω)≡0(mod2m+2)對任何ω∈{0 ，1}n成立。

由文獻［2］知道有下列定理。

定理3給定布爾函數f(x1，x2，…，xn)，若f是m-彈性函數（1≤m≤n-2），則degf+m≤n-1；若f是m-階相關免疫函數（1≤m≤n-1），則degf+m≤n。

由文獻［7］和文獻［8］知道有下列定理。

由Parseval關系有下列定理。

由文獻［4］可得下列定理。

定理6設f是0-彈性函數（即平衡函數），則

由文獻［5］可得下列定理。

定理7設f(x1，x2，…，xn)是一個m-彈性函數，則

3 主要結果

這里給出并證明主要結果。

定理8設f(x1，x2，…，xn)是一個m-彈性函數，n大于或等于3且0≤m≤n-3，則

結合定理6，定理7和定理8有以下定理。

定理 9設f(x1，x2，…，xn)是一個m-彈性函數，n大于或等于3且0≤m≤n-3，則

還可以將定理9細化。

所以此時有，σf≥2n+2m+4。因此，此下界比原來給出的下界要緊一些。

3）如果f是n-3-彈性函數，則由定理2，F(xiàn)(ω)≡0(mod2n-1)對任何ω∈{0 ，1}n成立。由定理5，要么有4個ω滿足|F(ω)|=2n-1，其余ω滿足F(ω)=0；要么有1個ω滿足|F(ω)|=2n，其余ω滿足F(ω)=0 。由定理4，要么σf=23n-2，要 么σf=23n。

當m大于或等于n-2時，平方和指標是確定的，見下列情況。

4）當m等于n-2，n-1時，由定理3可知，f一定是仿射函數，因此一定有σf=23n。

5）考察3≤n≤6的情形。

（1）n=3；如果f是0-彈性函數且非仿射函數，由3）知σf=23n-2=27。如果f是0-彈性函數且是仿射函數。則σf=23n=29。如果f是1-彈性函數或2-彈性函數，由4）知，σf=23n=29。

（2）n=4；如果f是 0-彈性函數，由 1）知σf≥22n+2n+3=28+27=384。列舉所有4元平衡函數f，發(fā)現(xiàn)σf≥640。因此用這個下界。如果f是1-彈性函數且非仿射函數，由3）知σf=23n-2=210。如果f是1-彈性函數且為仿射函數，則σf=23n=212，如果f是2-彈性函數或3-彈性函數，由4）知，σf=23n=212。

（3）n=5；如果f是 0-彈性函數，由1）知道，σf≥22n+2n+3=210+28。如果f是1-彈性函數，因為211=25+2+4＞210+28＞210+25+log26，所以，σf≥211。如果f是2-彈性函數且非仿射函數，由3）知σf=23n-2=213，如果f是2-彈性函數且為仿射函數，則σf=23n=215。如果f是3-彈性函數或4-彈性函數，由4）知，σf=23n=215。

（4）n=6；如果f是 0-彈性函數，由1）知道，σf≥22n+2n+3=212+29。如果f是1-彈性函數，因為212+29＞212=26+2+4，212+29＞212+26+log27，因此，這個時候，σf≥22n+2n+3=212+29。如果f是2-彈性函數，因為，26+4+4＞212+29，26+4+4＞212+26+log222，所以這個時候，σf≥214。如果f是3-彈性函數且非仿射函數，由3）知σf=23n-2=216，如果f是3-彈性函數且為仿射函數，由3）知σf=23n=218。如果f是4-彈性函數或5-彈性函數，由4）知，σf=23n=218。

上面的 1）、2）、3）、4）、5）包含了n≥3 ，0≤m≤n-1所有情況下n變元m-彈性函數的平方和指標的下界。

4 結語

布爾函數的代數免疫性質目前已有大量文獻研究［9～12］。關于函數全局雪崩特征有兩個指標，即平方和指標與絕對指標。這里，僅僅研究了彈性函數的平方和指標。提出彈性函數平方和指標一個新的下界，該下界可以與以前給出的下界結合起來使用。由這些下界發(fā)現(xiàn)：彈性函數的階m越大，則彈性函數的平方和指標越大。但是，m很小時又要受到分別征服攻擊。因此，應該選擇適當大小的m，使得彈性函數的階m較大，并且同時使得平方和指標較小。以后還應研究彈性函數的絕對指標［13～15］?？梢灶A計，彈性函數的絕對指標并沒有一個單一的下界。即對不同的彈性階，有不同的下界（由多個公式表達）。