学文网摘要：本文介绍了在容错分布、量子密码学中的密钥分配以及流密码中的随机序列产生等领域都有着广泛应用的一类多输出布尔函数――弹性函数。弹性函数和0,1上多维空间的正交分划(一个正交矩阵组)是一致的。在此基础上，介绍了弹性函数的正交分划的递归构造方法和简单计数。
关键词：弹性函数；相关免***函数；正交矩阵；计数
中***分类号：TN911文献标识码：A文章编号：1009-3044(2008)16-21353-03
Review of Resilient Functions of Modern Cryptography
SUN Jing-jing, WANG Yun
(School of Mathematics,Huaibei Coal Industry Teachers College,Huaibei 235000,China)
Abstract:Constrction of resilient functions that some possible applications of which involve the fault-tolerant distributed computing, quantum-cryptographic key distribution,and random sequence generation for stream ciphers are introduced.Recurive construction and enumeration of resilient functions are introduced.
Key words:resilient functions;correlation-immune functions;orthogonal array;enumeration
1 引言
弹性函数首先由B.chor等和C.H.Bennett等提出并研究。这类函数可用于容错分布计算、量子密码学中的密钥分配，以及流密码中随机序列的产生。相关免***函数是由 提出的一类抵抗相关攻击的重要的密码函数，而弹性函数实际上就是无偏的多输出相关免***函数。
2 定义及引理
定义1. 记F(x)=(f1(x),f2(x),…fm(x))，其中f1,…fm为F2nF2m的布尔函数，则F:F2nF2m，称F为多输出布尔函数。
对于多输出布尔函数F，定义其非线性度为■的代数次数定义为■。这里■。
定义2. 设F(x)是GF(2)nGF(2)m的函数，若对任意的β∈GF(2)m，F-1(β)={xOF(x)= β}有相同的元素个数，则称F(x)是无偏的。
著名的XOD引理揭示了多输出函数和其分量函数之间的关系。
引理1. (XOD引理) 设F(x)=(f1(x),f2(x),…fm(x))是F2nF2m的函数，其中fi（1≤i≤m）是F2nF2的函数，F(x)是无偏的■f1(x), f2(x),…fm(x)的任意非零线性组合是平衡的。
定义3. 设有 平衡函数F:F2mF2n，其中1≤m≤n. 如果对任意的下标集{j1,j2,…jt∈}{1,2,…n}，对任意a{a1,a2,…at}∈GF(2)t，任意b∈GF(2)m，有■，即当任意t个输入固定，而其余n-t个输入跑遍所有2n-t个输入串时，F以相同的次数取到所有可能的输出m元串。如果F是(n,mt)弹性函数，但不是(n,m,t+1)弹性函数，则称F的弹性阶为t。
显然，弹性函数即为无偏的相关免***函数。
引理2. 设F(x)=(f1(x),f2(x),…fm(x))是F2nF2m的函数，其中fi(1≤i≤m)是F2nF2的函数，F(x)是(n,m,t)弹性函数■f1(x), f2(x),…fm(x)的任意非零线性组合是(n,1,t)弹性函数。
3 弹性函数的构造
文献5~7中重点讨论了弹性函数的构造，主要为由线性弹性函数构造高非线性度的非线性弹性函数。其主要方法是借助线性码构造成一些线性函数或借助线性码理论从已有的弹性函数构造新的弹性函数（这些函数是线性的或代数次数较低的），然后再通过置换或无偏多输出函数复合出代数次数较高的函数。 那么，如何构造一些弹性函数做为基础，下面介绍其中一种――正交分划的递归构造法。这种方法直观简单，便于实现。
定义4. 设 是GF(2)上的w×n矩阵，1≤t≤n，如果对任意给定的t列，每一个行向量a∈F2t恰好重复w/2t次，则称A为正交矩阵，记为(w,n,2,t).
定理1. 布尔函数f(x1,x2,…xn)是t阶相关免***函数■其特征矩阵为(w,n2,t)正交矩阵(w为f(x)的汉明重量)。
定义5. 设A1,A2,…Ak均是GF(2)上的(w,n2,t)正交矩阵，若GF(2)n的每个向量必且只在一个Ai(1≤i≤k)的行中出现，即Ai(1≤i≤k)的行互不相交，且■，则称A1,A2,…Ak是GF(2)n的一个t正交分划，这时■。
定理2. 设F(x)是F2nF2m上的无偏的t阶相关免***函数，即F(x)是t阶弹性函数■Aβ1,…,Aβ2m是GF(2)n的一个t正交分划，其中Aβ1={xOF(x)=β1},βi∈GF(2m), 1≤i≤2m。
根据定理2，构造t弹性函数等价于构造GF(2)n的一个t正交分划。
引理3. 设A,B都是w×n矩阵，若A,B都是(w,n,2,t)正交矩阵，则■是(2w,n+1,2,t)正交矩阵。
引理4. 设A是2n-1×n矩阵，若A是(2n-1,n,2,t)正交矩阵，则■是(2n,n+1,2,t+1)正交矩阵。其中A-表示GF(2)n中除A的向量以外的向量组成的矩阵。
引理5. 设A,B是w×n矩阵，若A,B都是(w,n,2,t)正交矩阵，且A,B无相同行，则■亦无相同行，且都是(2w,n+1,2,t)正交矩阵.
定理3. 对任意的t≥1,m≥1,GF(2mt+1)可写成分块形式：■，Ci是(2mt+1,mt+1,2,t)正交矩阵，1≤i≤2m。 即GF(2mt+1)有t正交分划C1,C2,…C2m。
定理4. 对任意的■有t-正交分划。
证明：由条件知mt+1≤n,若mt+1=n，由定理3即得证。
若mt+1
C11,C21,…C2m1都是(2mt-m+2,mt+2,2,t)正交矩阵，则C11,C21,…C2m1是GF(2)mt+2的t-正交分划.对任意1≤k≤n-(mt+1)，令
■.C1k,C2k,…,C2mk是GF(2)mt+k+1的t-正交分划.重复以上过程，当k=n-(mt+1)时就得GF(2)n到的一个正交分划C1*,C2*,…,C2m*。
定理4的构造性证明实际上给出了正交分划的一个递归构造方法.相应的就构造出了一个GF(2)nGF(2)m的t-弹性函数.
4 弹性函数的计数
设A1,A2…A2m是GF(2)n的一个t-正交分划. 对x∈Ai∩GF(2)n，令F(x)=βi，
βi ∈GF(2)m，则GF(2)nGF(2)m是的t-弹性函数. 显然，交换f(x)在Ai(1≤i≤2m)Ai上的取值得到的t-弹性函数是不同的. 所以，有一个t-正交分划，相应可得到2m！个t-弹性函数.所以，可以通过讨论正交分划的个数来推导出弹性函数的个数.
设A1,A2,…A2m是GF(2)n的一个t-正交分划，n≥m≥1，这些2n×m×n矩阵都是t-正交矩阵，从而2tO2n-m，故t≤n-m，由于t的大小刻画了函数抗信息泄露能力的大小，所以我们希望尽可能的大. 但当达到最大值，即t=n-m时，(n,m,t)弹性函数的个数将会受到很大限制.
我们用Nt(2t,n)记t-正交的2t×n矩阵的个数，用N(n,m,t)记(n,m,t)弹性函数的个数(此时t=n-m)。
定理5. 设t≥2，则■
即t-正交的2t×n矩阵，当n=t时有 个，n=t+1时有2个，其余情况为0个.
由前述，存在(n,m,t)弹性函数，则存在GF(2)n的t-正交分划A1,A2,…A2m，这些Ai(1≤i≤2m 是t-正交的2n-m×n矩阵，当t=n-m时成为t-正交的2t×n矩阵，由定理5可知，t-正交的2t×n矩阵仅当n=t+1存在，且只有 个：A1,A2（即m=1）。所以，t=n-m时，GF(2)n仅有一个t-正交分划：A1,A2，从而只有2m！=21！=2个(n,m,t)弹性函数，于是有
定理6. 对任意n≥m≥1,t≥2，满足t=n-m的(n,m,t)弹性函数只有2个.这时n=t+1,m=1.即为布尔函数。
推论1. 平衡的n+1元n阶相关免***函数只有2个.
推论2. m≥2,n-m≥2时GF(2)nGF(2)m，的多输出函数(m≥2)的弹性性t不能达到最大值n-m。
定理7. 设n≥m≥1，用N(n,m,t)记(n,m,t)弹性函数的个数，若t=n-m，则
1）当t=0时，N(n,m,t)=2n！。
2）当t=1时，N(n,m,t)=2n-1！。
3）当t≥2时，N(n,m,t)=2。
以上结果表明，t=n-m时，即弹性性能最佳的函数除m=n和m=n-1这些特殊情况外太少。弹性性t是衡量抗信息泄露能力大小的一个重要指标，若这样的函数个数太少其应用将受到很大限制。当t最大时，函数个数很少且都是线性函数，所以并不是t越大越好。所以，不能片面追求高弹性性。密码系统中使用的函数个数不能太少。因此，研究弹性函数的计数是一个很重要的课题。
参考文献：
[1] ChorB,GoldreichO,astad J H,Friedman J,Rudich S,Smolensky R.The bit extraction problem or t-resilient functions[A].in Proc 26th IEEE Symp.Foundations of Computer Science[C].1985,26: 396-407.
[2] Bennett C H, Brassard G, Robert J M. Privacy amplification by public discussion[J].SIAM J. Comput, 1988, 17(2): 210-229.
[3] Rueppel R A.Analysis and design of stream ciphers[M].Berlin Germany: Springer-verlag,1996.
[4] Siegenthaler.Correlation immunity of nonlinear combining functions for cryptographic[J].IEEE Trans Inform. Theory, 1984.IT-30 sept,776-779.
[5] ZHANG Xiao-mo,ZHANG Yu liang. Cryptographically resilient functions[J].IEEE Trans Inform Theory, 1997,43:1740-1747
[6] ZHANG Xiao-mo,ZHANG Yu-liang. On nonlinear resilient functions[A].In Advance in cryptology- Eurocrypt' 95C .Berlin: spring Cverlag,1996,274-290.
[7] CHEN Lu-sheng, FU Fang-wei. On the constructions of new resilient functions from old ones[J].IEEE Trans Inform Theory, 1999,45(6):2 077-2082.
[8] 温巧燕,杨义先.弹性函数的递归构造[J].北京邮电大学学报,2002,25(2):1007-5321(2002)02-0047-05.
[9] 温巧燕, 杨义先.弹性函数的计数[J].北京邮电大学学报, 2002, 25(4):1007-5321,(2002)04-0021-05.
[10] 温巧燕,钮心忻,杨义先.现代密码学中的布尔函数.北京:科学出版社,2000.
注：本文中所涉及到的***表、注解、公式等内容请以PDF格式阅读原文。
转载请注明出处学文网 » 现代密码学上的弹性函数综述