采用定权最近邻搜索的信息集译码算法
Information Set Decoding Algorithm Using Fixed-Weight Nearest Neighbor Search
刘冰 1冯雨薇 1聂艇 1吴旭聃1
作者信息
摘要
伴随式译码问题是基于编码的密码算法核心问题之一,通常用信息集译码(ISD)方式来评估这类算法,而近期信息集译码算法的进展又依赖于该算法中非常重要的步骤—最近邻技术.本文整理了信息集译码算法的发展过程,给出信息集译码算法的复杂度变化情况,分析改进的方向与方案之间的区别.总结出三个主要的改进方向,即框架、搜索方式和搜索树的深度.针对信息集译码算法中的核心内容,研究了最近邻技术的变化.在BM算法的框架基础上提出了采用定权最近邻技术且深度为 6 的BM-plus-depth6算法,所提算法在最坏码率情况下,全距离译码时间复杂度可以降低至 20.0944n,半距离译码时间复杂度可以降低至 20.0444n.
Abstract
The syndrome decoding problem is one of the core issues in code-based cryptographic algorithms,which is usually assessed by the information set decoding(ISD)method.Recent progress in ISD algorithms relies on a very important step in the algorithms—the nearest neighbor technique.This study summarizes the development process of ISD algorithms,presents the complexity changes of these algorithms,and analyzes the differences between the directions and schemes of improvement.According to the analysis,three main improvement directions are summarized:the framework,search methods,and the depth of the search tree.Focusing on the core content of ISD algorithms,the evolution of the nearest neighbor technique has been studied.Based on the framework of the BM algorithm,this study proposes a BM-plus-depth6 algorithm with a depth of 6 using fixed-weight nearest neighbor technique.The proposed algorithm can reduce the full-distance time complexity to 20.0944n and the half-distance time complexity to 20.0444n in the worst case rate.
关键词
信息集译码/最近邻搜索/伴随式译码Key words
information set decoding/nearest neighbor search/syndrome decoding引用本文复制引用
出版年
2024
国家科技期刊平台
NSTL
万方数据