流密码可约性高效判别算法存在性的研究

Stream ciphers are prospectively employed for confidentiality and authentication in a broad expansion of information technology, and reducibility is a substantial index to measure security of stream ciphers. It is therefore of significant theoretical interests to study whether there exists an efficiently computable criterion or algorithm to determine reducibility of stream ciphers. First, whether there exists an efficient algorithm to decide reducibility of nonlinear feedback shift registers is studied. Furthermore, abstract models of stream ciphers are configured respectively from the perspective of graphs, finite state automata and algebraic geometry. Finally, through the relation of local parts and global ciphers and via obscuration of those models, it is expected to answer existence of efficient algorithms for reducibility of stream ciphers. The achievements serve as theoretical base of, and also as witness to difficulty of, testing degeneracy of stream ciphers. Additionally, algorithms are devised to search recurrent expressions of stream ciphers, and thereby reducibility of stream ciphers with certain particular structures is tested algorithmically, which adds technical ingredients in design and analysis of stream ciphers.

流密码在信息保密和认证领域有广泛的应用前景，可约性是影响流密码安全强度的一个重要指标，研究是否存在高效率的一般性准则或方法判定流密码算法的可约性具有重要的理论意义。通过重点考察是否存在高效率的方法以判定非线性移位寄存器的可约性，从图论、有限状态机、代数几何等多角度建立流密码算法的抽象模型，发掘模型中体现的整体和局部关系，利用模型刻画颗粒的模糊度变化，探索流密码算法可约性的高效一般性判别算法的存在性，为有效判定流密码算法是否退化提供理论依据，对流密码算法退化性问题的难度给出理论证据。设计流密码算法的迭代表达方式搜索算法，针对若干类流密码模式，提出判断其可约性的可计算的指标或高效率的算法，为流密码算法的设计和分析提供技术支撑。

流密码在信息保密和认证领域有广泛的应用前景，可约性是影响流密码安全强度的一个重要指标，研究是否存在高效率的一般性准则或方法判定流密码算法的可约性具有重要的理论意义。以反馈移位寄存器不可约性的一般性判别方法存在性为突破点，研究了流密码算法不可约性的一般性判别方法的存在性，密码体制的迭代模式表达方式的计算，并设计特殊模式流密码算法的不可约的核心部件的搜索算法。在关于流密码可约性判别算法存在性的研究方面，首次从计算复杂度理论的角度明确了判定移位寄存器的不可约性、不可分解性是NP难问题，从理论上刻画了最坏情况下移位寄存器和流密码的不可约性判别的困难程度；对具有稀疏转移方程的一类流密码提出自动化判定退化性的算法并给出用于计算迭代表达的一个算法，基于迭代表达给出一个充分性条件检测算法本身的退化性；对素数幂次环上几乎所有线性反馈移位寄存器给出了压缩映射保熵性的充要判定条件，量化估计了保熵的压缩映射的数量，构造了数量级为先前平方级别的新的保熵压缩映射；设计了轻量级流密码中不可约的两类组件化序列生成器模块的搜索算法并估计搜索算法的成功率下界。项目已经在国际学术刊物（均为SCI检索期刊）上公开发表5篇文章，相关内容获发明专利授权1项，并提交发明专利申请1项。项目的主要内容增加了流密码退化性研究的新的理论成分，对流密码的安全性评估有重要的理论支撑作用，成为自主知识产权的自动化密码测评技术的一部分，助力于提高流密码的设计水平，有益于推动我国流密码算法标准化进程。