An algorithm for generalized syndrome decoding problem
Huimin Lao, Hao Chen · Advances in Mathematics of Communications · 2022
Syndrome decoding problem has received a lot of attention due to its applications in code-based cryptography. In this paper, we study a generalization of the syndrome decoding problem. This problem was recently introduced in Khathuria, Rosenthal, and Weger's cryptosystem. We present a new algorithm for the generalized syndrome decoding problem, which is adapted from the information set decoding algorithm proposed by Finiasz and Sendrier. Furthermore, our algorithm can be severed as an attack for Khathuria, Rosenthal, and Weger's cryptosystem. New parameters of their cryptosystem are suggested for which our algorithm needs \begin{document}$ 2^{128} $\end{document} and \begin{document}$ 2^{256} $\end{document} bit operations.