This paper presents a key recovery attack on the cryptosystem proposed by Lau and Tan in a talk at ACISP 2018. The Lau-Tan cryptosystem uses Gabidulin codes as the underlying decodable code. To hide the algebraic structure of Gabidulin codes, the authors chose a matrix of column rank $n$ to mix with a generator matrix of the secret Gabidulin code. The other part of the public key, however, reveals crucial information about the private key. Our analysis shows that the problem of recovering the private key can be reduced to solving a multivariate linear system over the base field, rather than solving a multivariate quadratic system as claimed by the authors. Solving the linear system for any nonzero solution permits us to recover the private key. Apparently, this attack costs polynomial time, and therefore completely breaks the cryptosystem.
翻译:本文展示了刘先生和陈先生在2018年ACISPA的谈话中提议的加密系统的关键恢复攻击。 刘丹先生的加密系统使用加比杜林代码作为基本的代谢代码。 为了隐藏加比杜林代码的代数结构,作者选择了一个一列的矩阵, 以美元为单位, 与秘密加比杜林代码的生成器矩阵混合。 然而, 公用钥匙的另一部分却揭示了私人钥匙的关键信息 。 我们的分析表明, 回收私人钥匙的问题可以降低到解决基场的多变量线性系统, 而不是像作者所说的那样解决多变量的四边系统 。 解决任何非零解决方案的线性系统可以让我们回收私人钥匙 。 显然, 这一攻击需要多种时间, 从而完全打破加密系统 。