On linear codes with random multiplier vectors and the maximum trace dimension property
Let CC be a linear code of length nn and dimension kk over the finite field Fqm{{\mathbb{F}}}_{{q}^{m}}. The trace code Tr(C){\rm{Tr}}\left(C) is a linear code of the same length nn over the subfield Fq{{\mathbb{F}}}_{q}. The obvious upper bound for the dimension of the trace code over Fq{{\mathbb{F...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2024-02-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2023-0022 |
| _version_ | 1797303168373096448 |
|---|---|
| author | Erdélyi Márton Hegedüs Pál Kiss Sándor Z. Nagy Gábor P. |
| author_facet | Erdélyi Márton Hegedüs Pál Kiss Sándor Z. Nagy Gábor P. |
| author_sort | Erdélyi Márton |
| collection | DOAJ |
| description | Let CC be a linear code of length nn and dimension kk over the finite field Fqm{{\mathbb{F}}}_{{q}^{m}}. The trace code Tr(C){\rm{Tr}}\left(C) is a linear code of the same length nn over the subfield Fq{{\mathbb{F}}}_{q}. The obvious upper bound for the dimension of the trace code over Fq{{\mathbb{F}}}_{q} is mkmk. If equality holds, then we say that CC has maximum trace dimension. The problem of finding the true dimension of trace codes and their duals is relevant for the size of the public key of various code-based cryptographic protocols. Let Ca{C}_{{\boldsymbol{a}}} denote the code obtained from CC and a multiplier vector a∈(Fqm)n{\boldsymbol{a}}\in {\left({{\mathbb{F}}}_{{q}^{m}})}^{n}. In this study, we give a lower bound for the probability that a random multiplier vector produces a code Ca{C}_{{\boldsymbol{a}}} of maximum trace dimension. We give an interpretation of the bound for the class of algebraic geometry codes in terms of the degree of the defining divisor. The bound explains the experimental fact that random alternant codes have minimal dimension. Our bound holds whenever n≥m(k+h)n\ge m\left(k+h), where h≥0h\ge 0 is the Singleton defect of CC. For the extremal case n=m(h+k)n=m\left(h+k), numerical experiments reveal a closed connection between the probability of having maximum trace dimension and the probability that a random matrix has full rank. |
| first_indexed | 2024-03-07T23:49:04Z |
| format | Article |
| id | doaj.art-5ea0eaf097ec47c8bb6060a3f5c08b5d |
| institution | Directory Open Access Journal |
| issn | 1862-2984 |
| language | English |
| last_indexed | 2024-03-07T23:49:04Z |
| publishDate | 2024-02-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-5ea0eaf097ec47c8bb6060a3f5c08b5d2024-02-19T09:02:06ZengDe GruyterJournal of Mathematical Cryptology1862-29842024-02-011815051010.1515/jmc-2023-0022On linear codes with random multiplier vectors and the maximum trace dimension propertyErdélyi Márton0Hegedüs Pál1Kiss Sándor Z.2Nagy Gábor P.3Department of Algebra and Geometry, Budapest University of Technology and Economics, Műegyetem rkp. 3, H-1111 Budapest, HungaryDepartment of Algebra and Geometry, Budapest University of Technology and Economics, Műegyetem rkp. 3, H-1111 Budapest, HungaryDepartment of Algebra and Geometry, Budapest University of Technology and Economics, Műegyetem rkp. 3, H-1111 Budapest, HungaryDepartment of Algebra and Geometry, Budapest University of Technology and Economics, Műegyetem rkp. 3, H-1111 Budapest, HungaryLet CC be a linear code of length nn and dimension kk over the finite field Fqm{{\mathbb{F}}}_{{q}^{m}}. The trace code Tr(C){\rm{Tr}}\left(C) is a linear code of the same length nn over the subfield Fq{{\mathbb{F}}}_{q}. The obvious upper bound for the dimension of the trace code over Fq{{\mathbb{F}}}_{q} is mkmk. If equality holds, then we say that CC has maximum trace dimension. The problem of finding the true dimension of trace codes and their duals is relevant for the size of the public key of various code-based cryptographic protocols. Let Ca{C}_{{\boldsymbol{a}}} denote the code obtained from CC and a multiplier vector a∈(Fqm)n{\boldsymbol{a}}\in {\left({{\mathbb{F}}}_{{q}^{m}})}^{n}. In this study, we give a lower bound for the probability that a random multiplier vector produces a code Ca{C}_{{\boldsymbol{a}}} of maximum trace dimension. We give an interpretation of the bound for the class of algebraic geometry codes in terms of the degree of the defining divisor. The bound explains the experimental fact that random alternant codes have minimal dimension. Our bound holds whenever n≥m(k+h)n\ge m\left(k+h), where h≥0h\ge 0 is the Singleton defect of CC. For the extremal case n=m(h+k)n=m\left(h+k), numerical experiments reveal a closed connection between the probability of having maximum trace dimension and the probability that a random matrix has full rank.https://doi.org/10.1515/jmc-2023-0022trace codessubfield subcodesdimension of trace codesrandom alternant codesweight enumeratorsingleton defect14g5015a03 |
| spellingShingle | Erdélyi Márton Hegedüs Pál Kiss Sándor Z. Nagy Gábor P. On linear codes with random multiplier vectors and the maximum trace dimension property Journal of Mathematical Cryptology trace codes subfield subcodes dimension of trace codes random alternant codes weight enumerator singleton defect 14g50 15a03 |
| title | On linear codes with random multiplier vectors and the maximum trace dimension property |
| title_full | On linear codes with random multiplier vectors and the maximum trace dimension property |
| title_fullStr | On linear codes with random multiplier vectors and the maximum trace dimension property |
| title_full_unstemmed | On linear codes with random multiplier vectors and the maximum trace dimension property |
| title_short | On linear codes with random multiplier vectors and the maximum trace dimension property |
| title_sort | on linear codes with random multiplier vectors and the maximum trace dimension property |
| topic | trace codes subfield subcodes dimension of trace codes random alternant codes weight enumerator singleton defect 14g50 15a03 |
| url | https://doi.org/10.1515/jmc-2023-0022 |
| work_keys_str_mv | AT erdelyimarton onlinearcodeswithrandommultipliervectorsandthemaximumtracedimensionproperty AT hegeduspal onlinearcodeswithrandommultipliervectorsandthemaximumtracedimensionproperty AT kisssandorz onlinearcodeswithrandommultipliervectorsandthemaximumtracedimensionproperty AT nagygaborp onlinearcodeswithrandommultipliervectorsandthemaximumtracedimensionproperty |