New Constructions of Non-GRS MDS Codes, Recovery and Determination Algorithms for GRS Codes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908686877720576 |
|---|---|
| author | Wang, Guodong Liu, Hongwei Luo, Jinquan |
| author_facet | Wang, Guodong Liu, Hongwei Luo, Jinquan |
| contents | In this paper, we propose a new method for constructing a class of non-GRS MDS codes. The lengths of these codes can reach up to $\frac{q+3}{2}$ (for finite fields of odd characteristic) and $\frac{q+4}{2}$ (for even characteristic), respectively. Owing to their special structure, we can use the Cauchy matrix method to obtain the necessary and sufficient conditions for these codes to be MDS codes and non-GRS MDS codes. Additionally, the inequivalence between these codes and twisted GRS codes is analyzed. Furthermore, we analyze the relationships among several existing classes of codes used for constructing non-GRS MDS codes, propose explicit constructions, and discuss the lengths of non-GRS MDS codes based on these constructions. Finally, we design two efficient algorithms to address two main problems in GRS code research, i.e., determining whether an unknown code $C$ is a GRS code from its generator matrix $G$, and recovering the key vectors $\bmα$ and $\bm{v}$ such that $C = \GRS_{n,k}(\bmα, \bm{v})$ if $C$ is indeed a GRS code. A computational complexity comparison of the proposed algorithms ($O(nk+n)$) with that of the Sidelnikov-Shestakov attack (exceeding $O(qk^2n+qk^3)$) shows that our methods offer superior computational efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02325 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Constructions of Non-GRS MDS Codes, Recovery and Determination Algorithms for GRS Codes Wang, Guodong Liu, Hongwei Luo, Jinquan Information Theory 94B05, 94B60 In this paper, we propose a new method for constructing a class of non-GRS MDS codes. The lengths of these codes can reach up to $\frac{q+3}{2}$ (for finite fields of odd characteristic) and $\frac{q+4}{2}$ (for even characteristic), respectively. Owing to their special structure, we can use the Cauchy matrix method to obtain the necessary and sufficient conditions for these codes to be MDS codes and non-GRS MDS codes. Additionally, the inequivalence between these codes and twisted GRS codes is analyzed. Furthermore, we analyze the relationships among several existing classes of codes used for constructing non-GRS MDS codes, propose explicit constructions, and discuss the lengths of non-GRS MDS codes based on these constructions. Finally, we design two efficient algorithms to address two main problems in GRS code research, i.e., determining whether an unknown code $C$ is a GRS code from its generator matrix $G$, and recovering the key vectors $\bmα$ and $\bm{v}$ such that $C = \GRS_{n,k}(\bmα, \bm{v})$ if $C$ is indeed a GRS code. A computational complexity comparison of the proposed algorithms ($O(nk+n)$) with that of the Sidelnikov-Shestakov attack (exceeding $O(qk^2n+qk^3)$) shows that our methods offer superior computational efficiency. |
| title | New Constructions of Non-GRS MDS Codes, Recovery and Determination Algorithms for GRS Codes |
| topic | Information Theory 94B05, 94B60 |
| url | https://arxiv.org/abs/2512.02325 |