The security of most code-based cryptosystems relies on the hardness of the syndrome decoding(SD) problem.The best solvers of the SD problem are known as information set,decoding(ISD) algorithms.Recently,Weger,et al.(...The security of most code-based cryptosystems relies on the hardness of the syndrome decoding(SD) problem.The best solvers of the SD problem are known as information set,decoding(ISD) algorithms.Recently,Weger,et al.(2020) described Stern’s ISD algorithm,s-blocks algorithm and partial Gaussian elimination algorithms in the Lee metric over an integer residue ring Z_(pm),where p is a prime number and m is a positive integer,and analyzed the time complexity.In this paper,the authors apply a binary ISD algorithm in the Hamming metric proposed by May,et al.(2011)to solve the SD problem over the Galois ring GR(p^(m),k) endowed with the Lee metric and provide a detailed complexity analysis.Compared with Stern’s algorithm over Zpmin the Lee metric,the proposed algorithm has a significant improvement in the time complexity.展开更多
基金supported by the National Natural Science Foundation of China under Grant No. 61872355the National Key Research and Development Program of China under Grant No. 2018YFA0704703
文摘The security of most code-based cryptosystems relies on the hardness of the syndrome decoding(SD) problem.The best solvers of the SD problem are known as information set,decoding(ISD) algorithms.Recently,Weger,et al.(2020) described Stern’s ISD algorithm,s-blocks algorithm and partial Gaussian elimination algorithms in the Lee metric over an integer residue ring Z_(pm),where p is a prime number and m is a positive integer,and analyzed the time complexity.In this paper,the authors apply a binary ISD algorithm in the Hamming metric proposed by May,et al.(2011)to solve the SD problem over the Galois ring GR(p^(m),k) endowed with the Lee metric and provide a detailed complexity analysis.Compared with Stern’s algorithm over Zpmin the Lee metric,the proposed algorithm has a significant improvement in the time complexity.
