布尔函数的密码性质及构造方法

最常用的流密码生成器由一个线性反馈移位寄存器和一个非线性布尔函数构成的前馈部分合成。相关攻击是对流密码传统的攻击方法，当一个布尔函数的非线性度越大时，由它生成的流密码抵御相关攻击的性能越强。近年来由于求解较低次数非线性方程组的方法日趋成熟，对于流密码的代数攻击的研究受到关注。为了能抵抗代数攻击，要求所利用的布尔函数具有较高的代数免疫度。本项目重点研究同时具有较高的非线性度和较高的代数免疫度的布尔函数的构造方法，以及具有较强的抵御快速代数攻击性能的布尔函数的构造方法。目前尚没有已知的这两种类型布尔函数的构造方法。

在本课题中我们取得的主要研究成果包括以下三个方面. .在标准代数免疫度方面, 我们给出了布尔函数具有最优代数免疫度的几个等价条件, 进一步研究了级联布尔函数的代数免疫度, 简化了一类特殊汉明重量的布尔函数达到最高代数免疫度的充要条件, 并且讨论了它们的代数次数和非线性度..在快速代数免疫性方面, 我们的研究工作主要包括三个部分..第一部分阐述对称布尔函数的快速代数免疫性. 我们证明了几乎所有的对称布尔函数具有较差的快速攻击免疫性, 包括那些具有高代数免疫度的对称布尔函数..第二部分提出完全代数免疫函数的理论. 完全代数免疫函数是对标准代数攻击和快速代数攻击都具有完全免疫性的布尔函数. 我们证明了完全代数免疫的平衡函数的变元个数为 2 的幂加 1; 而完全代数免疫的非平衡函数的变元个数为 2 的幂. 还证明了当 n 为 2 的幂时 n+1 元 Carlet-Feng 函数和 n 元变形 Carlet-Feng 函数是完全代数免疫函数..第三部分利用二元多项式表示研究布尔函数的快速代数免疫性. 基于二元多项式表示, 我们给出布尔函数达到良好快速代数免疫性的充要条件, 针对一大类布尔函数提出估计快速代数免疫性的有效方法, 并证明一类布尔函数是几乎完全代数免疫函数..除了上述两个方面, 我们还研究了布尔函数的概率代数免疫性. 首先, 指出存在滤波函数使得概率代数攻击优于确定代数攻击. 然后, 引入代数免疫距离和 k 错代数免疫度两个概念用来衡量布尔函数抵抗概率代数攻击的能力, 并分析了代数免疫距离的上下界. 最后, 研究了最优代数免疫度函数的概率代数免疫性.