Paper 2019/432
Cryptanalysis of a System Based on Twisted Reed–Solomon Codes
Julien Lavauzelle and Julian Renner
Abstract
It was recently proved that twisted Reed--Solomon codes represent a family of codes which contain a large amount of MDS codes, non-equivalent to Reed--Solomon codes. As a consequence, they were proposed as an alternative to Goppa codes for the McEliece cryptosystem, resulting to a potential reduction of key sizes. In this paper, an efficient key-recovery attack is given on this variant of the McEliece cryptosystem. The algorithm is based on the recovery of the structure of subfield subcodes of twisted Reed--Solomon codes, and it always succeeds. Its correctness is proved, and it is shown that the attack breaks the system for all practical parameters in $O(n^4)$ field operations. A practical implementation is also provided and retrieves a valid private key from the public key within just a few minutes, for parameters claiming a security level of $128$ bits. We also discuss a potential repair of the scheme and an application of the attack to GPT cryptosystems using twisted Gabidulin codes.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Code-based cryptographyMcEliece CryptosystemSubfield SubcodesTwisted Reed-Solomon Codes
- Contact author(s)
- julian renner @ tum de
- History
- 2020-03-23: revised
- 2019-04-29: received
- See all versions
- Short URL
- https://ia.cr/2019/432
- License
-
CC BY