Cryptanalysis of a system based on twisted Reed-Solomon codes

DOI10.1007/S10623-020-00747-6MaRDI QIDQ780371zbMATH OpenOpenAlexFDO

Authors Julien Lavauzelle, Julian Renner

Publication date 15 July 2020

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.11785

zbMATH Keywords

McEliece cryptosystemcode-based cryptographysubfield subcodestwisted Reed-Solomon codes

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05)

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.

Recommendations

• Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
• Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
• On the edge-independence number and edge-covering number for regular graphs
• Severely denting the Gabidulin version of the McEliece public key cryptosystem
• Public Key Cryptography - PKC 2006

Cites work

• scientific article; zbMATH DE number 3989251 (Why is no real title available?)
• scientific article; zbMATH DE number 177612 (Why is no real title available?)
• A public-key cryptosystem based on binary Reed-Muller codes
• Algebraic cryptanalysis of McEliece variants with compact keys
• An efficient structural attack on NIST submission DAGS
• Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes
• Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
• Cryptanalysis of the Sidelnikov Cryptosystem
• DAGS: key encapsulation using dyadic GS codes
• Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
• How to mask the structure of codes for a cryptographic use
• McEliece public key cryptosystems using algebraic-geometric codes
• On the edge-independence number and edge-covering number for regular graphs
• Progress in Cryptology – Mycrypt 2005
• Public Key Cryptography - PKC 2006
• Recovering short secret keys of RLCE in polynomial time
• Reducing Key Length of the McEliece Cryptosystem
• Structural cryptanalysis of McEliece schemes with compact keys
• Theory of codes with maximum rank distance

Cited in

(13)

• Duality of generalized twisted Reed-Solomon codes and Hermitian self-dual MDS or NMDS codes
• MDS or NMDS LCD codes from twisted Reed-Solomon codes
• MDS and near-MDS codes via twisted Reed-Solomon codes
• The \((+)\)-extended twisted generalized Reed-Solomon code
• MDS or NMDS self-dual codes from twisted generalized Reed-Solomon codes
• The error-correcting pair for direct sum codes
• A class of twisted generalized Reed-Solomon codes
• Construction of MDS twisted Reed-Solomon codes and LCD MDS codes
• Rank-metric codes and their applications
• MDS multi-twisted Reed-Solomon codes with small dimensional hull
• The error-correcting pair for TGRS codes
• New constructions of self-dual codes via twisted generalized Reed-Solomon codes
• The \([1, 0]\)-twisted generalized Reed-Solomon code

Describes a project that uses

Uses Software

• SageMath
• McEliece

This page was built for publication: Cryptanalysis of a system based on twisted Reed-Solomon codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q780371)