Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Code-based cryptography, McEliece Cryptosystem, Subfield Subcodes, Twisted Reed-Solomon Codes

Date: received 26 Apr 2019

Contact author: julian renner at tum de

Available format(s): PDF | BibTeX Citation

Version: 20190429:020900 (All versions of this report)

Short URL: ia.cr/2019/432


[ Cryptology ePrint archive ]