Paper 2019/432

Cryptanalysis of a System Based on Twisted Reed-Solomon Codes

Julien Lavauzelle and Julian Renner

Abstract

Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed--Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic key-recovery methods. In this paper, an efficient key-recovery attack on the TRS variant that was used in the McEliece cryptosystem is presented. The algorithm exploits a new approach based on recovering the structure of a well-chosen subfield subcode of the public code. It is proved that the attack always succeeds and breaks the system for all practical parameters in $O(n^4)$ field operations. A software implementation of the algorithm retrieves a valid private key from the public key within a few minutes, for parameters claiming a security level of 128 bits. The success of the attack also indicates that, contrary to common beliefs, subfield subcodes of the public code need to be precisely analyzed when proposing a McEliece-type code-based cryptosystem. Finally, the paper discusses an attempt to repair the scheme and a modification of the attack aiming at Gabidulin-Paramonov-Tretjakov cryptosystems based on twisted Gabidulin codes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.Designs, Codes and Cryptography
DOI
10.1007/s10623-020-00747-6
Keywords
Code-based cryptographyMcEliece CryptosystemSubfield SubcodesTwisted Reed-Solomon Codes
Contact author(s)
julian renner @ tum de
julien lavauzelle @ univ-rennes1 fr
History
2020-03-23: revised
2019-04-29: received
See all versions
Short URL
https://ia.cr/2019/432
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/432,
      author = {Julien Lavauzelle and Julian Renner},
      title = {Cryptanalysis of a System Based on Twisted Reed-Solomon Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/432},
      year = {2019},
      doi = {10.1007/s10623-020-00747-6},
      note = {\url{https://eprint.iacr.org/2019/432}},
      url = {https://eprint.iacr.org/2019/432}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.