Paper 2022/002

Polynomial-Time Key Recovery Attack on the Lau-Tan Cryptosystem Based on Gabidulin Codes

Wenshuo Guo and Fang-Wei Fu

Abstract

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.

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographycode-based cryptography
Contact author(s)
ws_guo @ mail nankai edu cn
History
2022-02-09: withdrawn
2022-01-01: received
See all versions
Short URL
https://ia.cr/2022/002
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.