编码中的复杂性问题及其在密码学中的应用

Recently, more and more relationships between coding theory and computation complexity are discovered. On the one hand, we would know the complexity of some coding problems to direct the algorithm designs. On the other hand, some codes are applied to the theory of computation and make it forward. Furthermore, the compounded results in coding theory and computation complexity result in the development of cryptography. We will investigate the following problems: (1) Analyze the complexity of some coding problems, and look for new NP-hard problems; (2) Improve the encoding and decoding algorithms for certain well-known codes, e.g. the list-decoding algorithms for Reed-Solomon and Reed-Muller Codes; (3) Investigaet the complexity of Learning with errors(LWE); (4) Analyze and Attack cryptosystems based on the hardness of the two problems Learning Parity with Noise (LPN) and Learning With Errors (LWE), and find some efficient methods. We hope that our research will push forward the mixed research among cryptography, coding theory and computation complexity.

近年来，编码理论与计算复杂性理论产生越来越紧密的联系：一方面，人们需要判断许多编码问题的复杂性来指导具体算法设计；另一方面，一些特定的编码方式成为复杂性理论中的工具，促进复杂性理论的发展。编码理论与计算复杂性之间的交叉成果又促进了密码学的发展。本项目将研究如下问题：1）分析一些编码问题的复杂性，发现新的NP-难问题；2）改进特定编码方式的编解码算法，比如Reed-Solomon码和Reed-Muller码的列译码算法等；3）研究Learning with errors(LWE)问题的复杂性；4）分析与攻击基于两个难问题Learning parity with noise(LPN)和LWE的密码系统，找到一些有效的分析与攻击方法。希望本项目的研究促进密码学、编码理论与计算复杂性的交叉理论发展。

近年来，编码理论与计算复杂性理论产生越来越紧密的联系，编码理论的一些方法可以应用于复杂性的研究中，而计算复杂性的又可以指导编码地设计，编码与复杂性的成果在密码中有重要的应用。在本课题中，我们对编码、密码、计算复杂性中的一些主要问题进行了比较系统的研究，取得如下成果：.（1）列译码与局部可解码（局部可修复码）是近几年编码理论的重要研究方向，如何构造好的列译码与局部可解码是这个领域的中心问题。我们利用有理域上自同构及组合设计方法来构造列译码与局部可解码，给出了新的构造方法，构造出了新的列译码与局部可解码。相关成果发表在IEEE TIT、《中国科学》等杂志上。.（2）量子自对偶的最大距离分离码（MDS码）与拟最大距离分离码（NMDS码）具有重要的理论与实际意义，我们给出了量子MDS码与NMDS码新的构造方法，并构造出了新的具有好的参数的量子MDS码与NMDS码。相关成果发表在IEEE TIT、Des. Codes Crypto. 等杂志上。.（3）布尔函数广泛应用于流密码与分组密码中，基于布尔函数的密码体制的安全性与所使用的布尔函数密码性质有密切的关系，如果构造具有好的密码性质的布尔函数是编码与密码领域的核心问题之一。我们构造出构造出了差分4-均匀的新的布尔函数类、具有好的差分均匀度的置换多项式、具有Niho指数的置换多项式，相关结果发表在Des. Codes Crypto. 、《中国科学》、IEICE Trans.上。.（4）研究LWE与LPN问题复杂性，并且国外著名团队进行合作研究，联合培养人才。.（5）研究了一些计算复杂性问题及应用，如属性密码相关的复杂性问题及构造方法，并把属性密码与区块链结合来设计灵活的访问控制模型，开发了相关的软件产品，申请了专利与软著，并在实际中得到应用。.共计发表22篇SCI杂志论文与2篇会议论文，其中CCF A类论文有 5篇， CCF B论文有 12篇。申请了20个专利，其中 3个获得授权，获得了 8个软件著作权。