On linear codes with random multiplier vectors and the maximum trace dimension property

Let C C be a linear code of length n n and dimension k k over the finite field F q m {{\mathbb{F}}}_{{q}^{m}} . The trace code Tr ( C ) {\rm{Tr}}\left(C) is a linear code of the same length n n over the subfield F q {{\mathbb{F}}}_{q} . The obvious upper bound for the dimension of the trace code ove...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Erdélyi Márton Kristóf
Hegedűs Pál
Kiss Sándor Z.
Nagy Gábor Péter
Dokumentumtípus: Cikk
Megjelent: 2024
Sorozat:JOURNAL OF MATHEMATICAL CRYPTOLOGY 18 No. 1
Tárgyszavak:
doi:10.1515/jmc-2023-0022

mtmt:34589743
Online Access:http://publicatio.bibl.u-szeged.hu/32941
Leíró adatok
Tartalmi kivonat:Let C C be a linear code of length n n and dimension k k over the finite field F q m {{\mathbb{F}}}_{{q}^{m}} . The trace code Tr ( C ) {\rm{Tr}}\left(C) is a linear code of the same length n n over the subfield F q {{\mathbb{F}}}_{q} . The obvious upper bound for the dimension of the trace code over F q {{\mathbb{F}}}_{q} is m k mk . If equality holds, then we say that C C 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 C a {C}_{{\boldsymbol{a}}} denote the code obtained from C C and a multiplier vector a ∈ ( F q m ) 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 C a {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 ≥ 0 h\ge 0 is the Singleton defect of C C . 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.
Terjedelem/Fizikai jellemzők:13
ISSN:1862-2976