论文部分内容阅读
密码加密方案主要分为两类:分组密码和流密码.像DES或AES的分组密码是多轮加密的叠加.而每轮加密都涉及从二元向量空间Vn到向量空间Vm的向量输出布尔函数,这样的布尔函数也称为S-盒或(n,m)-函数.流密码被广泛地用于保护世界范围内的通信安全以及提供一种可靠并且有效的安全通信方式.在流密码的标准模型中,密钥流是由一个非线性布尔函数的输出产生的,而这个非线性布尔函数的输入是由几个独立的线性反馈移位寄存器(LFSR)的输出构成的.明文与密钥流逐比特异或产生密文.在密码函数的现代设计中,我们经常用向量输出的布尔函数代替布尔函数.因为在流密码中使用向量输出的布尔函数做为结合函数可以在同一时刻得到更多比特,所以它可以加快流密码体制的速度.为了保护这些密码体制免受各种攻击,这些布尔函数或向量输出的布尔函数应该具有平衡性,高阶的相关免疫性,很高的代数阶数以及很高的非线性度等密码特性.但是这些密码标准彼此相互矛盾.因为上述参数之间又存在某些关联,所以我们不可能同时使每个参数分别取得最优值.在这篇论文中,我们主要讨论向量输出函数的密码性质并且引入两类重要的向量输出的布尔函数,他们分别称为二元向量输出的PartiallyBent函数和二元向量输出的Plateaued函数.其次,我们给出了一种构造(n+s,m,t+s)-resilient函数的方法.进一步,我们提供了三种在一般有限域上构造非线性的Zigzag函数的方法.最后,我们给出了从Fnq到Fmq向量输出的相关免疫函数以及Resilient函数的特征.
关于布尔函数,Carlet[9]证明了一个重要的不等式并且引入了PartiallyBent函数的概念,即使Carlet不等式中等式的所有布尔函数.在本文中,我们把关于布尔函数的Carlet不等式推广到向量输出的布尔函数并且引入了向量输出的PartiallyBent函数的概念,即使广义Carlet不等式中等式的所有向量输出的布尔函数.随后给出了一系列广义Carlet不等式中等式成立的充分必要条件.进一步,对二元向量输出的PartiallyBent函数的密码性质进行了详细的讨论.在一定条件下,这类新的向量输出的布尔函数不仅具有很高的非线性度而且具有平衡性,相关免疫性以及传播特征.一般地,所有的向量输出的PartiallyBent函数具有非零的线性结构.但是在文献[18]和[19]中,已经证明非零线性结构的存在是密码函数的一个弱点.这导致我们引入另一类重要的密码函数一二元向量输出的Plateaued函数.
Plateaued函数是由Zheng和Zhang在文献[57]中首次引入的,它表示Vn上Walsh谱等于0或±2n-r/2的布尔函数,其中r是一个偶数且0≤r≤n.这类布尔函数具有很好的密码性质并且Carlet和Prouff在文献[11]中对它们进行了更深入的研究.在本文中,我们把Plateaued函数推广到向量输出的布尔函数.关于向量输出布尔函数的分量函数的的所有非零线性组合的自相关函数和Walsh谱,我们建立了一系列重要的不等式.特别地,我们利用一系列等式来刻画向量输出的Plateaued函数并且讨论了它们和向量输出的PartiallyBent函数之间的关系.进一步,我们提供了一种构造这类函数的方法.
相关免疫函数由Siegenthaler[48]定义并且在文献[2],[6],[10],[13],[24]和[39]中得到更深入的研究.二元Resilient函数的概念分别由Chor[15]和Bennett[1]独立引入.事实上,Resilient函数就是平衡的相关免疫函数.在本文中,我们给出了一个从2s已知的(n,m,t)-resilient函数构造(n+s,m,t+s)-resilient函数的充分必要条件.它不仅提供了一种构造二元向量输出Resilient函数的方法,而且Resiliency的阶数和Vn的维数是同步增加的,以及Resiliency的阶数的增加速度比已知的构造方法更快.接下来我们讨论了利用此方法构造的(n+s)个输入,m个输出函数的非线性度和传播特征以及在特殊情况下计算它们的代数次数.最后,给出一个例子来说明我们的构造方法.
Zigzag函数是由G.Brassard,C.Crépeau和M.Sēátha[3]定义的.这类函数主要用来构造ObliviousTransfers,它们是密码协议的有用工具.设F(x)=(f1(x),…,fm(x))是一个从Fnq到Fmq的向量输出函数,如果f1(x),…,fm(x)都是线性的,则F(x)称为是线性的;否则,F(x)称为是非线性的.我们知道线性的Zigzag函数是很容易构造的.例如,G.Brassard,C.Crépeau和M.Sántha[3]已经证明了如下的结果:设M是q元[n,m]线性码c的生成矩阵,则函数F(x)=xMT是一个线性的(n,m,q)-zigzag函数的充分必要条件码c是一个Intersecting码.但是非线性的(n,m,q)-zigzag函数的构造很少被研究.在本文中,我们的主要工作之一就是构造非线性的Zigzag函数以及研究它们的非线性度.我们提供了三种构造从Fnq到Fmq的非线性的Zigzag函数的方法.利用FFmq置换,我们可以从已知的Zigzag函数构造新的Zigzag函数.这种方法可以使我们把一个线性的Zigzag函数转换成许多非线性的Zigzag函数.其次,利用qs个特殊的(n,m,q)-zigzag函数的级联我们可以构造非线性的(n+s,m,q)-zigzag函数.最后,通过一个q元线性Intersecting码我们给出一种构造非线性的Zigzag函数的方法.在这种情形下,可以直接计算所构造Zigzag函数的非线性度.
对于从Fnq到Fq的相关免疫函数和Resilient函数,K.Gopalakrishnan和D.R.Stinson[20]证明了它们的三个特征.本文的主要目的之一就是刻画从Fnq到Fmq的相关免疫函数和Resilient函数F(x).首先,我们给出一些复合函数G。F(x)的特征,其中G是一个从Fmq到Fsq的函数.同时,我们得到了一些关于F(x)的分量函数的所有非零线性组合的性质.其次,我们给出相关免疫函数和Resilient函数的相关矩阵特征.最后,我们给出平衡函数以及Resilient函数的Fourier变换特征.