PaperlayerView exact revision on arXiv

Source-linked AI summary

A Class of Two-Weight and Three-Weight Codes and Their Applications in Secret Sharing

Kelan Ding, Cunsheng Ding

arXiv:1503.06512v1cs.IT

TL;DR

The paper addresses the construction of linear codes over GF(p) with few nonzero weights and their use in secret sharing. It uses defining sets to construct two-weight and three-weight code families, derives their parameters and weight distributions, and reports examples meeting coding bounds. The resulting codes also support secret-sharing schemes and applications to authentication codes, association schemes, and strongly regular graphs.

  • Problem

    The paper investigates how to construct linear codes with two or three nonzero weights and apply them in secret sharing.

  • Method

    The authors use defining sets D ⊆ GF(q) and trace-based linear-code constructions, then analyze the resulting codes and their minimal codewords for secret sharing.

  • Results

    The constructed families include examples that are optimal under stated coding bounds, including [40,5,24] and codes.

  • Takeaways & Limitations

    The codes can support secret-sharing schemes and provide parameters for authentication codes, association schemes, and strongly regular graphs.

Abstract

from arXiv · show

In this paper, a class of two-weight and three-weight linear codes over $\gf(p)$ is constructed, and their application in secret sharing is investigated. Some of the linear codes obtained are optimal in the sense that they meet certain bounds on linear codes. These codes have applications also in authentication codes, association schemes, and strongly regular graphs, in addition to their applications in consumer electronics, communication and data storage systems.

I. INTRODUCTION

The paper constructs two-weight and three-weight linear codes over GF(p) using defining sets, then examines their parameters, punctured variants, and optimality against coding bounds.

  • I. INTRODUCTION: The defining-set construction selects D ⊆ GF(q) and produces a linear code C_D over GF(p).The paper describes the construction as generic, allowing known code classes to be obtained by choosing D.
  • I. INTRODUCTION: The paper targets codes with two and three nonzero weights and investigates their use in secret sharing.The weight distribution records codeword-weight information relevant to error correction and detection.
  • II. THE LINEAR CODES WITH TWO AND THREE WEIGHTS: For odd m, Theorem 1 constructs a [p^m−1,m] code with the weight distribution specified in Table I.The theorem states that all weights not listed in the table have zero multiplicity.
  • II. THE LINEAR CODES WITH TWO AND THREE WEIGHTS: The examples include a [80,5,48] ternary code and a [104,4,80] quinary code with the listed weight enumerators.The [40,5,24] punctured ternary code is optimal against the stated length-and-dimension bound, while the quinary code is optimal due to the Griesmer bound.
  • II. THE LINEAR CODES WITH TWO AND THREE WEIGHTS: Because the weights share a divisor p−1, the codes can be punctured to shorter codes whose weight distributions can be derived from the originals.The paper presents this puncturing as a consequence of the observed common divisor.

III. THE PROOFS OF THE MAIN RESULTS

This section proves Theorems 1 and 2, with Corollaries 3 and 4 following directly from them.

  • The proofs establish Theorems 1 and 2, while Corollaries 3 and 4 are immediate consequences, respectively.

A. Some auxiliary results

The auxiliary-results section develops character and Gauss-sum tools used to prove the paper’s main code theorems.

  • The proofs use group characters and Gauss sums as auxiliary tools.
  • Additive characters map GF(q) into nonzero complex numbers while converting field addition into multiplication.
  • Every additive character can be represented as χ_b(x) = χ_1(bx), with χ_1 the canonical additive character.
  • Multiplicative characters form a group of order q − 1, and η denotes the quadratic character extended by η(0) = 0.
  • The lemmas distinguish odd and even m through the behavior of η on GF(p)∗ and evaluate character sums according to trace conditions.

B. The proof of Theorems 1 and 2

The proofs derive code lengths and weights from character-sum evaluations, separately treating odd and even m to establish the two main theorems.

  • The code length n of C_D is obtained from an auxiliary lemma before calculating codeword weights.
  • For each b ∈ GF(q)∗, the Hamming weight wt(c_b) equals n_0 − N(b).
  • When m is odd, character-sum evaluations yield the conclusions of Theorem 1.
  • When m is even, corresponding evaluations yield the conclusions of Theorem 2.

IV. A GENERALIZATION OF THE CONSTRUCTION

The paper generalizes its code construction using planar functions satisfying specified conditions, while leaving equivalence of resulting parameters and weight distributions open.

  • The paper defines nonlinearity through a quantity P_f, with smaller P_f corresponding to higher nonlinearity.
  • A planar function is a perfectly nonlinear function between finite abelian groups of the same order, and known examples include several finite-field power constructions.
  • The code construction generalizes to planar functions f: GF(q) → GF(q) satisfying the paper’s stated conditions.
  • The generalized set defines a linear code C_Df over GF(p), and Magma confirms matching parameters for all four listed planar-function classes.
  • Whether C_Df and C_D always share the same parameters and weight distribution remains open for functions satisfying the three conditions.

V. APPLICATIONS OF THE LINEAR CODES IN SECRET SHARING SCHEMES

This section describes and analyzes secret sharing schemes derived from selected linear codes.

  • The paper examines secret sharing schemes constructed from some of the linear codes it presents.

A. Secret sharing schemes

Secret sharing distributes a secret among participants through shares and a recovery procedure. Its access structure records which participant groups can recover the secret, with minimal groups characterizing monotone schemes.

  • A secret sharing scheme includes a dealer, participants, a secret space, share computation, and secret recovery.
  • An access set is a participant group that can determine the secret from its shares.
  • In a monotone scheme, every superset of an access set is also an access set.
  • Monotone access structures are completely characterized by their minimal access sets.
  • Secret sharing schemes have applications in banking, cryptographic protocols, electronic voting, and nuclear-weapons control.

B. The covering problem of linear codes

The covering problem asks which nonzero codewords are minimal, a task that is generally difficult but tractable for certain linear codes.

  • The paper introduces the covering problem to describe secret sharing schemes based on linear codes.
  • The support of a vector consists of the coordinates associated with its nonzero components.
  • A vector x covers y when the support of x contains the support of y as a proper subset.
  • A minimal codeword is a nonzero codeword covering no other nonzero codeword, and finding all such codewords is generally very hard.

C. A construction of secret sharing schemes from linear codes

The paper constructs secret sharing schemes from linear codes and characterizes their minimal access sets through codewords, with access patterns determined by dual distance and minimality conditions.

  • Any linear code over GF(p) can generate a secret sharing scheme; the construction uses the code and its dual parameters and generator matrices.
  • The dealer selects u so that s = uh0, treats u as an information vector, and computes the corresponding codeword.
  • Each participant Pi receives ti as the share corresponding to its codeword coordinate.
  • A group of shares recovers s exactly when h0 is a linear combination of the corresponding dual-code generator vectors.
  • Minimal access sets correspond to minimal codewords of C whose leftmost component is 1; their other nonzero components identify participants.
  • If every nonzero codeword is minimal, the scheme based on C⊥ has n−1 participants and pk−1 minimal access sets.
  • When d⊥ = 2, coordinates whose generator vectors are multiples of g0 belong to every minimal access set and act as dictators.
  • When d⊥ ≥ 3, every group of t participants appears in (p−1)t pk−(t+1) of the pk−1 minimal access sets for 1 ≤ t ≤ min{k−1,d⊥−2}.

D. The secret sharing schemes from the codes of this paper

The paper derives secret-sharing access structures from minimal codewords of dual codes, with behavior determined by the dual minimum distance. Several constructed codes yield democratic schemes, while others have dictators; explicit participant and access-set counts are given for selected cases.

  • General access structures: All nonzero codewords of the relevant codes are minimal when m ≥ 6, giving dual-code schemes with the access structures described by Theorem 12.For the Corollary 14 family, minimality holds for m ≥ 5 and d⊥ ≥ 3.
  • Corollary 14: For the Corollary 14 family, the scheme has p^m−2 participants, p^m−1 minimal access sets, and each participant belongs to (p −1)p^m−2 minimal access sets.The stated result applies for m ≥ 5.
  • Example 5: For m = 5 and p = 5, the example has 125 participants, 625 minimal access sets, and 500 minimal access sets containing each participant.The small secret space GF(5) can be extended to GF(5^h) by sharing encoded symbols successively.

VI. CONCLUDING REMARKS

The concluding remarks position the codes as simple, previously unlisted two-weight and three-weight constructions with applications beyond secret sharing. Their weight distributions support new parameters for strongly regular graphs, association schemes, and authentication codes.

  • Relation to prior work: The reported two-weight and three-weight codes differ from much of the literature because their lengths do not usually divide p^m −1, and their parameters were not found in prior work.The paper compares its constructions with surveyed two-weight and three-weight code families.
  • Applications: Two-weight codes automatically produce strongly regular graphs with new parameters, while three-weight codes may yield association schemes with new parameters.The stated connections use established frameworks for relating few-weight codes to these combinatorial structures.
  • Applications: The codes can construct authentication codes with new parameters, provided their complete weight distributions are determined.Gaussian sums can be used to settle these complete distributions, which are known for only a few code classes in the literature.
  • Construction method: The construction is defined by the simple function Tr(x^2), making analysis easier than for other two-weight and three-weight code constructions.This simplicity is presented as a comparative advantage of the method.
Loading 1503.06512v1…