CS Paper Radar

Construction of Ternary Minimal Linear Codes with Dimension $n+r$ Via Index Codes and The Access Structures of Their Dual Codes

Haibo Liu, Qunying Liao

cs.IT ·submitted 2026-11-18 09:03 UTC · v1

Abstract

Recently, minimal linear codes have been extensively studied due to their applications in secret sharing schemes, secure two-party computations, and so on. Constructing minimal linear codes violating the Ashikhmin-Barg condition and then determining their weight distributions have been interesting in coding theory and cryptography. In this paper, we present a general construction of ternary linear codes of dimension $n+r$, where $n$ and $r$ are positive integers, and derive a necessary and sufficient condition for the resulting codes to be minimal. We first specialize the construction using index codes arising from spreads, with three classes of index codes satisfying the minimality condition, we obtain the parameters and weight enumerators of the corresponding minimal codes, and determine the access structures type of the secret-sharing schemes based on their dual codes. By the index codes from Krawtchouk polynomials, we then give a second specialization of the construction, with a class of index codes satisfying the minimality condition, we obtain the parameters of the resulting minimal codes, and determine the access-structure type of the secret-sharing scheme based on each dual code. Several constructed families of minimal codes violate the Ashikhmin-Barg condition.

Closest papers

Nearest neighbours by meaning across the whole index.

Minimality of Binary Codes From Weight Layers and Graph Cut Spaces

cs.IT ·2026-10-26 ·Xianhong Xie, Mengni Wang, Tingting Wu
similarity 0.70
Abstract

Minimal binary linear codes play an important role in secret-sharing schemes and in the structural study of linear codes. We study the minimality of three classes of known constructions: codes from a single complete Hamming-weight layer, codes from arbitrary unions of such layers and graph cut-space codes. For the previously studied single-layer codes C, we give a complete minimality classification: C is minimal if and only if t is even. For t = 4, we determine the minimum and maximum weights, and show that the family strictly violates the binary Ashikhmin Barg sufficient condition for every k. We also calculate the minimum distance of the dual code. For arbitrary unions of complete Hamming-weight layers, we obtain an if-and-only-if classification of minimality and uniform criteria for evenness, self-orthogonality, the doubly even property and hull dimension. We further analyze the family for odd k. Finally, using the classical bond characterization of cuts, we translate minimality of graph cut space codes into a graph-theoretic condition: a nonempty simple graph has a minimal cut code precisely when it has one edge-containing component and that component is complete. We also give a graph-function realization of the known binary tetrahedron code and explicitly identify the resulting code equivalence.

0.24

On the Leakage of Massey Secret Sharing Schemes under Linear Computations

cs.CR ·2026-09-17 ·Nadja Aoutouf, Daniel Augot
hot direction similarity 0.69
Abstract

Leakage attacks on secret sharing schemes exploit partial information about individual shares to recover the underlying secret. In coding theory, linear exact repair schemes (LERSs) enable the recovery of one codeword symbol from a small amount of information obtained from the remaining symbols, provided that the code has sufficiently low rate. This can be interpreted as recovering the secret from partial information, namely subfield symbols, of the shares. Recently, a randomized construction based on subfield subcodes was proposed for constructing LERS-derived leakage attacks against Massey secret sharing schemes based on general linear codes. We extend this framework to multiple shared secrets whose corresponding shares are related through linear computations, with leakage also allowed on the computation outcomes. More precisely, we consider N secrets, of which K $\le$ N are linearly independent input values and the remaining N -K secrets are determined by linear computations on these inputs. We analyse the existence of LERS-derived leakage that exploits this structure. We first study the case of addition and then generalize our construction to arbitrary linear computations. Our analysis applies to general linear codes of length n+1 and dimension k over F\_{q^m} with k $\le$ N n/(Km), and supports arbitrary linear computations, whereas the previous subfield subcode construction only applies to k $\le$ n/m -1. Consequently, exploiting the linear relations enables LERS based leakage which extend the range of code parameters vulnerable to such attacks. Finally, identical leakage functions can arise for certain linear relations, making this a more realistic yet still potentially powerful attack model. Finally, simulations indicate that identical leakage functions can be used for certain linear relations, yielding a more realistic attack model.

0.37

Systematic Derivation of Leakage in Massey Secret Sharing Schemes

cs.CR ·2026-11-02 ·Nadja Aoutouf, Daniel Augot
similarity 0.69
Abstract

Leakage attacks on secret sharing schemes can be based on the exploitation of partial information about individual shares to recover the underlying secret. In coding theory, linear exact repair schemes (LERSs) allow the recovery of a codeword symbol from limited information obtained from the remaining symbols. When applied to code-based secret sharing schemes, such repair schemes can be interpreted as recovering the secret from partial information about the shares, expressed in terms of subfield symbols. Guruswami and Wootters introduced the first explicit constructions of LERSs for low-rate Reed--Solomon codes that is optimal in terms of bandwidth. In this work, we first investigate the construction and algebraic properties of LERSs, building on the Guruswami-Wootters construction. We derive new explicit repair schemes from their construction and establish structural properties of the resulting schemes. Second, we further develop a systematic computational approach based on a Gr{ö}bner bases approach to identify leakage functions associated with LERSs for arbitrary linear codes. This approach enables us to investigate the existence and structural properties of LERSs across different code families and parameter ranges. We first applied our method to Reed-Solomon codes, which gave as further insights into the algebraic structure of LERSs. Moreover, by applying our method to generalized Reed-Muller and Tamo-Barg codes, we identify several LERSs that, to the best of our knowledge, have not previously been described in the literature.

0.03

On the structure of polynomial ideal codes and additive Reed--Solomon codes

cs.IT ·2026-10-15 ·Umberto Martínez-Peñas, Rubén Rodríguez-Ballesteros
similarity 0.69
Abstract

We study structural properties of polynomial ideal (PI) codes and additive Reed--Solomon (aRS) codes in the folded Hamming metric (equivalently, the Hamming metric over a larger alphabet). We first determine the maximum possible length of PI codes, prove that the dual of every PI code is a generalized PI code, and deduce that PI codes are dually QMDS together with an explicit formula for their weight distribution. We then show that PI codes defined by irreducible polynomials correspond to aRS codes with pairwise nonconjugate evaluation points. For these aRS codes, the previous results on PI codes apply (duality, QMDS property and weight distribution). We show that, asymptotically, aRS codes with nonconjugate evaluation points achieve the same length as PI codes. We also compute the permutation group of such aRS codes. We also extend the family of PI codes to consider arbitrary polynomial modules (not necessarily pairwise coprime), and study when these and general aRS codes satisfy the QMDS and dually QMDS properties.

0.15

Constructions of Secure Convertible Codes

cs.IT ·2026-10-26 ·Manasa Suresh B P, Vinayak Ramkumar, Myna Vajha
similarity 0.67
Abstract

Secure convertible codes, introduced by Zhang and Rashmi, achieve secrecy capacity under a passive eavesdropper model in which an eavesdropper is allowed to access any $\ell$ symbols from the initial and final codewords. In this paper, we construct two families of access-optimal secure convertible codes. The first family of codes based on Maximum Rank Distance (MRD) codes is constructed for all parameters in the merge and split regimes and requires a large field size. The second family of codes, constructed using Generalized Reed-Solomon codes, uses smaller fields but is applicable only for certain parameters in the merge and split regimes.

0.13

On Twisted Roth-Lempel Codes

cs.IT ·2026-09-15 ·Huiyue Lei, Haojie Gu, Jun Zhang, Haiyan Zhou
similarity 0.66
Abstract

In 1989, Roth and Lempel constructed a well-known family of non-Reed-Solomon maximum distance separable (MDS) codes. For decades, this family of codes has attracted extensive research attention due to its algebraic structure, low-complexity decoding, and broad applications in cryptography and data storage. In this paper, we present a class of twisted Roth-Lempel codes. We investigate their minimum distance, MDS and NMDS properties. Specifically, we determine the necessary and sufficient conditions for the TRL codes to have minimum distance n-k or n-k+1. Furthermore, we determine the necessary and sufficient conditions for the TRL code to be an MDS or NMDS code. Moreover, we show that the dimension of the Schur square of the TRL code is at least 2k+1, and thus the TRL code is a non-RS code inequivalent to the corresponding RL code.

0.15

The ordered sum-rank metric and linearized multiplicity codes: NRT meets sum-rank

cs.IT ·2026-11-15 ·Umberto Martínez-Peñas
similarity 0.65
Abstract

In this work, we introduce linearized multiplicity codes, which are a common generalization of linearized Reed--Solomon codes and univariate multiplicity codes. We also introduce the ordered sum-rank metric, which is a common generalization of the sum-rank metric and the Niederreiter-Rosenbloom-Tsfasman (NRT) metric (or ordered Hamming metric). We provide a Singleton bound for the ordered sum-rank metric and show that linearized multiplicity codes attain it. That is, they are maximum ordered sum-rank distance (MOSRD) codes. We introduce the support lattice for the ordered sum-rank metric and study duality, support distributions and weight distributions of MOSRD codes. We also show that MOSRD codes are ordered MDS, dually quasi MSRD and, under some divisibility conditions, MSRD (and thus MDS). For linear MOSRD codes, we give lower bounds on the field extension degree by the number of matrix columns, and upper bounds on the block length by the base field size. We conclude by showing that linearized multiplicity codes attain such bounds exactly in almost all cases, and the same growth order in all cases.

0.05

Generalized Hamming Weights and Subcode Support Weight Distributions of Twisted Reed-Solomon Codes

cs.IT ·2026-10-12 ·Chao Liu, Hao Chen, Dabin Zheng, Yaqi Chen
similarity 0.64
Abstract · 38 pages

In this paper, we determine the generalized Hamming weight hierarchies of two classes of twisted Reed--Solomon (TRS) codes. For TRS codes with one twist, we first determine all possible values of the generalized Hamming weights. We then give a complete characterization of the weight hierarchy in terms of the minimum distance of the dual code. Explicit conditions are derived for the minimum distances of the code and its dual, which make the whole weight hierarchy explicitly computable. As special cases, the obtained results recover several known characterizations for TRS codes to be MDS, NMDS codes, and $s$-gap AMDS codes. For TRS codes with two twists, we similarly determine the complete generalized Hamming weight hierarchy. In this case, the higher generalized Hamming weights are determined by the first two generalized Hamming weights of the dual code, for which explicit rank conditions are also obtained. In addition, we further determine the subcode support weight distributions of this class of single-twist TRS codes. More precisely, for each $1 \le r \le k$, we derive an explicit formula for the number of $r$-dimensional subcodes with a prescribed support size, thereby giving a complete description of the support distribution of subcodes.

0.22