具有良好线性复杂度和错误线性复杂度性质的密码周期序列的设计与分析

This project will deeply and systematically study the cryptographic binary $2^n$-periodic sequences by using the tools including finite fields, number theory, combinatorics and designs, spectrum theory, Boolean functions theory, algebraic coding theory, etc. We will analyze the cryptographic properties of binary $2^n$-periodic sequences, the distribution and the expectation of the k-error linear complexity of binary $2^n$-periodic sequences and the falling rules of k-error linear complexity. We will study the construction of the error linear complexity spectrum and the properties of critical points in it. We will study the enumeration and algorithms about the critical error sequences of binary $2^n$-periodic sequences. We will study the construction of periodic sequences with large linear complexity and error linear complexity. We will study the relations between auto-correlation and error linear complexity of binary sequences. We will study the distribution of k-error linear complexity of sequences over general finite fields. We will also study the application of our results in the analysis and designs of stream ciphers and other domains such as repeated-root cyclic codes and CDMA(Code Division Multiple Access) communication systems. The results of this project will take some influence in the study of stream cipher and will generally apply to the analysis and designs of cryptographic systems and communications.

本项目将充分利用有限域理论、数论、组合设计、频谱理论、布尔函数、代数编码理论等工具对二元$2^n$周期序列进行深入系统的研究，分析这种序列的密码学性质；研究二元周期序列的k-错线性复杂度的分布、期望及其随k 增大而降低的规律；研究二元周期序列的错误线性复杂度谱的结构、严格点的性质；研究二元周期序列的严格错误序列的计数及算法；研究具有良好线性复杂度和错误线性复杂度的序列的构造；研究二元周期序列的自相关性质及其与错误线性复杂度之间的关系；研究有限域上序列的k-错线性复杂度的分布；进一步研究已得结果在流密码的分析与设计以及在其它多个领域如重根循环码及码分多址通信系统中的应用。其成果将对流密码理论的研究产生一定的影响，并将广泛应用于安全密码系统的分析和设计以及通信领域等多个领域中。

具有良好性质的序列在密码、通信等多个领域中有着重要的应用，构造具有良好性质的序列是一个重要的研究方向。本项目利用有限域理论、数论、组合设计、频谱理论、布尔函数、代数编码理论等多种工具，对多种序列的构造方法和性质进行了深入研究。经过三年的研究，取得的成果如下：(1)提出了二元2^n周期序列新的表示方法，并利用它研究了二元2^n周期序列的错误线性复杂度的下降规律，给出了线性复杂度下降时需要改变的序列的最少分量个数的确切公式，并给出了具有少量错误线性复杂度严格点的序列的计数公式。(2)研究了分圆序列，给出了不同周期的二元和四元广义分圆序列的多种构造方法，并详细分析了序列的线性复杂度性质。(3)研究了费马-欧拉商序列、高斯整数序列和Legendre-Sidelnikov序列，给出了多种构造方法，分析了序列的自相关和互相关分布，并给出一种具有良好互相关性质的序列集。(4)研究了de Bruijn序列的性质，基于并圈方法和线性反馈移位寄存器序列，给出了多种de Bruijn序列的构造方法。(5)研究了序列在DNA数据存储技术中的应用，根据已有序列的性质，确定了一些DNA序列谱向量的个数和下界。本项目丰富了已有的研究成果，为密码和通信系统提供了更多性质良好的序列，并给出了序列在新领域中的应用。