Cryptanalysis of a system based on twisted Reed-Solomon codes

DOI10.1007/S10623-020-00747-6zbMATH Open1455.94177arXiv1904.11785OpenAlexW3104110479MaRDI QIDQ780371FDOQ780371

Authors: Julien Lavauzelle, Julian Renner 

Publication date: 15 July 2020

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

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.

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

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

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)

Cites Work

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

Cited In (13)

• MDS multi-twisted Reed-Solomon codes with small dimensional hull
• New constructions of self-dual codes via twisted generalized Reed-Solomon codes
• The \([1, 0]\)-twisted generalized Reed-Solomon code
• MDS and near-MDS codes via twisted Reed-Solomon codes
• The \((+)\)-extended twisted generalized Reed-Solomon code
• Rank-Metric Codes and Their Applications
• A class of twisted generalized Reed-Solomon codes
• 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
• The error-correcting pair for direct sum codes
• The error-correcting pair for TGRS codes
• MDS or NMDS self-dual codes from twisted generalized Reed-Solomon codes
• Construction of MDS twisted Reed-Solomon codes and LCD MDS codes

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)