An Algebraic Method for Constructing Bases in Binary Linear Codes for Information Dispersal Algorithms
The algebraic analysis of linear code parameters reveals deep connections with cryptographic constructions, including the information dispersal algorithms (IDAs) and secret-sharing schemes. In this work, we propose an algebraic method for constructing bases of binary linear codes from subsets of codewords selected according to their generalized Hamming weights (GHWs). The approach employs a degree-compatible monomial ordering on the polynomial ring F2[x1, . . . , xn] and imposes the conditions d1(C) = 1 and dk (C) = n. Under these assumptions, we prove the existence of a generator matrix containing an invertible k × k submatrix, which guarantees correct information reconstruction. This structural property enables the direct application of binary linear codes to information dispersal and recovery mechanisms without the need for larger finite fields. We validate the proposed framework through algebraic proofs and an explicit example illustrating both the dispersal and recovery procedures. These results provide a theoretical foundation for the design of information dispersal schemes relying exclusively on binary linear codes.
