Welcome to the resource topic for 2025/111
Title:
On the structure of the Schur squares of Twisted Generalized Reed-Solomon codes and application to cryptanalysis
Authors: Alain Couvreur, Rakhi Pratihar, Nihan Tanisali, Ilaria Zappatore
Abstract:Twisted generalized Reed-Solomon (TGRS) codes constitute an interesting family of evaluation codes, containing a large class of maximum distance separable codes non-equivalent to generalized Reed-Solomon (GRS) ones.
Moreover, the Schur squares of TGRS codes may be much larger than those of GRS codes with same dimension.
Exploiting these structural differences, in 2018, Beelen, Bossert, Puchinger and Rosenkilde proposed a subfamily of Maximum Distance Separable (MDS) Twisted Reed–Solomon (TRS) codes over \mathbb{F}_q with \ell twists q \approx n^{2^{\ell}} for McEliece encryption, claiming their resistance to both Sidelnikov Shestakov attack and
Schur products–based attacks. In short, they claimed these codes to resist to classical key recovery attacks on McEliece encryption scheme instantiated with Reed-Solomon (RS) or GRS codes. In 2020, Lavauzelle and Renner presented an original attack on this system based on the computation of the subfield subcode of the public TRS code.
In this paper, we show that the original claim on the resistance of TRS and TGRS codes to Schur products based–attacks is wrong.
We identify a broad class of codes including TRS and TGRS ones that is distinguishable from random by computing the Schur square
of some shortening of the code. Then, we focus on the case of single twist ({i.e.}, \ell = 1), which is the most efficient one in terms of decryption complexity, to derive an attack. The technique is similar to the distinguisher-based attacks of RS code-based systems given by Couvreur, Gaborit, Gauthier-Umaña, Otmani, Tillich in 2014.
ePrint: https://eprint.iacr.org/2025/111
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .