序列的几种复杂度及其关系研究

Complexity measures for sequences are important issues in randomness assessment of keystreams. Linear complexity and 2-adic complexity are two elementary complexity of sequences.The k-error linear complexity and k-error 2-adic complexity show the stability of the two elementary complexity of sequences, respectively. The detailed research of this project is as follows: the relationship between the linear complexiy profile and k-error linear complexity; expected value of the k-error linear complexity and 2-adic complexity of random sequences; the k-error linear complexity of l-sequences and the k-error 2-adic complexity of m-sequence. The significance of this project is to chracterize the distribution properties of the four complexity of random sequences and their inner connections in randomness assessment for sequences.

序列的复杂度衡量是序列伪随机性研究的重要内容，线性复杂度和2-adic复杂度是序列的两个基本的复杂度指标，k-错线性复杂度和k-错2-adic复杂度反映了序列的这两种复杂度的稳定性。本项目研究序列的这四种复杂度及其相互之间的关系。具体研究内容有：序列的线性复杂度谱与k-错线性复杂度之间的关系；随机序列的k-错线性复杂度和2-adic复杂度的均值与方差；l-序列的k-错线性复杂度和m-序列的k-错2-adic复杂度。通过本项目的研究，可以更加清晰地刻画随机序列的这四种复杂度的分布规律以及它们在序列伪随机性评价上的内在联系。

项目围绕序列的伪随机衡量、复杂度理论和轻量级密码算法的分析展开研究，取得了以下结果：（1）针对序列的零化子序列的最低线性复杂度和序列的谱攻击问题，给出了前馈序列谱免疫度紧的上界、前馈序列的谱免疫度与过滤函数代数免疫度的关系，并给出了平衡布尔函数过滤输出序列谱免疫度的渐近行为；（2）提出了利用线性反馈移位寄存器构造轻量MDS矩阵的方法，给出了构造4阶MDS矩阵的所有可能参数值；（3）对典型轻量级算法中的S盒按仿射等价关系进行了分类，对轻量S盒达到最大差分概率的差分对个数、具有最优线性逼近关系的掩码个数、以及单比特情况下的差分均匀度和非线性度进行了统计分析；（4）提出了针对初始化169轮的Grain-128a的条件差分分析，首次恢复了18个密钥的表达式。进一步在弱密钥条件下，提出了针对对初始化195轮的Grain-128a的区分攻击；（5）证明了Espresso密码算法的输出序列等效于同级线性反馈移位寄存器序列的过滤输出，并给出了其等效模型，基于该结果对Espresso算法进行了代数攻击，时间复杂度为2^66.86；(6)给出了LBlock-s密码的21轮不可能差分分析，时间复杂度为2^67.61，数据复杂度为2^63。给出了LBlock-s密码的23轮多维零相关线性分析，攻击时间复杂度为2^75.4，数据复杂度为2^62.3；（7）给出了17轮SKINNY的不可能差分分析，得到了目前最好的结果; （8）给出了二次特征函数NFSR的仿射子簇求取方法，证明了Grain-128序列密码驱动部件不含有阶数大于1的仿射子簇；（9）提出了一种轻量级序列密码算法设计的新模型。课题的这些研究成果将为轻量级密码算法的设计与分析提供一定的理论基础和技术支持。