信息集解码算法若干问题研究

The information set decoding algorithms are a class of general methods to decode random linear codes. Such algorithms are crucial for choosing appropriate security parameters for a code-based cryptographic scheme, which makes them a more and more attractive topic along with the arrival of the post-quantum era. However, the existing algorithms are still imperfect ——neither their theoretical analysis is yet thorough, nor their application scope is adequate..In order to obtain better information set decoding algorithms, this project focuses on the algorithms’ mechanism theoretically. And the main contributions will be as follows: (1) Based on the analytic simplification technique, the way to choose an optimal value for the recursive depth is given; (2) The theoretical proof of the validity of the current algorithms’ extension from the binary field to the q-ary field is given by using the estimation technique in combinatorial mathematics and the concept of coordinate-balance based on the discrete Gaussian distribution;(3) Based on the description of geometric properties, an algorithm defined by the generation matrix is given and extended to problems with general linearity structures..The results of this project will provide both an inspiring direction for the improvement of the information set decoding algorithms and an important hint for cryptographers to evaluate the security of new cryptosystems.

信息集解码算法是求解随机线性码问题的一类通用算法，该算法因为能够对基于编码的密码体制这一类具有应用潜力的抗量子攻击密码方案进行安全分析而成为近年来密码学界关注的热点。然而，现有算法仍存在复杂度理论分析不够完善和缺乏新型密码体制针对性等不足之处。.为形成更有效的信息集解码算法，本项目着眼于算法机理的分析，并探索算法在密码学领域应用的新理论与新方法。本项目的主要研究内容包括：（1）基于复杂度表达式解析化简技术，给出算法递归深度的界；（2）利用组合数学复杂度表达式的界估计技巧和基于离散高斯分布的坐标平衡性概念扩展，给出算法在q元域上有效性的理论证明；（3）基于线性空间几何性质描述，给出线性码生成矩阵描述条件下的算法，并将其扩展到具有更一般线性结构的问题解法中。.本项目的研究成果将为信息集解码算法的改进提供启发性方向，同时，对评估新型密码体制的安全性提供重要依据。

本项目围绕信息集解码算法机理的分析，针对现有算法存在复杂度理论分析不够完善和缺乏新型密码体制针对性等不足之处，通过形式化分析与证明、组合估计、线性结构扩展等方法进行研究，探索算法在密码学及其他信息技术领域应用的新理论与新方法。从理论角度，本项目深入分析并给出了现有同类算法典型适用特征，通过对其适用空间数据的分布进行讨论，抽象及推广了算法的形式和结构；从实践角度，本项目探索基于编码的密码体制这一类具有抗量子攻击潜力的密码方案分析与设计思路，给出其在智能电网、区块链、金融安全等领域的典型应用。本项目的研究成果将为信息集解码算法及同类结构算法的改进提供启发性方向，同时，对多领域应用安全评估积累经验。

内容获取失败，请点击重试