密码学报（中英文）2024，Vol.11Issue(6)：1278-1292,15.DOI:10.13868/j.cnki.jcr.000733
采用定权最近邻搜索的信息集译码算法
Information Set Decoding Algorithm Using Fixed-Weight Nearest Neighbor Search
摘要
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分类
信息技术与安全科学引用本文复制引用
刘冰,冯雨薇,聂艇,吴旭聃..采用定权最近邻搜索的信息集译码算法[J].密码学报（中英文）,2024,11(6):1278-1292,15.基金项目
北京电子科技学院一流学科建设项目(1201011)First-class discipline construction project of Beijing Electronic Science and Technology Institute(1201011) （1201011）
