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

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.Source: §I · p. 1
• 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.Source: §I · p. 1

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.Source: §II · p. 2, Table I · p. 2
• 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.Source: §II · pp. 2–3
• 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.Source: §II · p. 2

• The proofs establish Theorems 1 and 2, while Corollaries 3 and 4 are immediate consequences, respectively.Source: §III · p. 3

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

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

• The paper defines nonlinearity through a quantity P_f, with smaller P_f corresponding to higher nonlinearity.Source: §IV · p. 7
• 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.Source: §IV · p. 7
• The code construction generalizes to planar functions f: GF(q) → GF(q) satisfying the paper’s stated conditions.Source: §IV · p. 8
• The generalized set defines a linear code C_Df over GF(p), and Magma confirms matching parameters for all four listed planar-function classes.Source: §IV · p. 8
• Whether C_Df and C_D always share the same parameters and weight distribution remains open for functions satisfying the three conditions.Source: §IV · p. 8

• The paper examines secret sharing schemes constructed from some of the linear codes it presents.Source: §V · p. 8

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

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

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

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.Source: D. The secret sharing schemes from the… · pp. 10–11

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.Source: D. The secret sharing schemes from the… · p. 11

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.Source: D. The secret sharing schemes from the… · p. 11

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.Source: §VI · p. 11

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.Source: §VI · p. 11
• 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.Source: §VI · p. 11

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.Source: §VI · p. 11