- Home
- Documents
*Construction of minimal linear codes withfew weights from ... Construction of minimal linear codes...*

prev

next

out of 19

View

0Download

0

Embed Size (px)

Construction of minimal linear codes with few weights from weakly regular plateaued functions

Ahmet Sınak1,2

1 Department of Mathematics and Computer Science, Necmettin Erbakan University, 42090, Konya, Turkey 2 LAGA, Universities of Paris VIII and Paris XIII, CNRS, UMR 7539, Paris, France

sinakahmet@gmail.com

Abstract. The construction of linear (minimal) codes from functions over finite fields has been greatly studied in the literature since determining the parameters of linear codes based on functions is rather easy due to the nice structures of functions. In this paper, we derive 3-weight and 4-weight linear codes from weakly regular plateaued unbalanced functions in the recent construction method of linear codes over the odd characteristic finite fields. The Hamming weights and their weight distributions for proposed codes are determined by using the Walsh transform values and Walsh distribution of the employed functions, respectively. We next derive projective 3-weight punctured codes with good parameters from the constructed codes. These punctured codes may be almost optimal due to the Griesmer bound, and they can be employed to design association schemes. We lastly show that all constructed codes are minimal, which approves that they can be employed to design high democratic secret sharing schemes.

Keywords: Linear code ·minimal code · weight distribution · weakly regular plateaued function · unbalanced function

1 Introduction

There are many construction methods for linear codes, one of them is derived from functions over finite fields. Constructing linear codes from functions is a popular research topic in the literature although considerable progress has been done in this direction. A great number of linear codes have been obtained from popular cryptographic functions such as quadratic functions [6,7,10,11,25,29], (weakly regular) bent functions [6,7,19,24,26,29], (almost) perfect nonlinear functions [4,16,27] and (weakly regular) plateaued functions [6,20,21,23]. Two generic (say, first and second) construction methods of linear codes from functions can be isolated from the others in the literature. In the past two decades, several linear codes with excellent parameters have been derived from cryptographic functions based on the first generic construction method (e.g. [4,7,19,20]) and the second generic construction method (e.g. [7,11,24,25,29]). Recently, weakly regular plateaued (especially, bent) functions have been employed to design linear (minimal) codes with a few weights over the odd characteristic finite fields ([19,20,21,23,24,26]). In this paper, motivated by [15,26], we use some unbalanced weakly regular plateaued functions so that we can get minimal linear codes with new parameters. It is worth noting that a very nice survey [17] written by Li and Mesnager is devoted to the construction methods of linear codes from cryptographic functions over finite fields.

The rest of this paper is organized as follows. In Section 2, we set the main notation and give some properties of weakly regular plateaued functions. In Section 3, we introduce the parameters of 3-weight and 4-weight linear codes derived from these functions over finite fields. We also propose punctured codes for the constructed codes. We hereby obtain projective 3-weight codes with flexible parameters. We finally highlight that our codes are minimal codes.

2 A. Sınak

2 Preliminaries

For a set T , its size is shown by #T , and T ? = T \ {0}. The magnitude of a complex number z ∈ C is denoted by |z|. The finite field with q elements is represented by Fq, where q = pn for a positive integer n and an odd prime p. The trace of α ∈ Fq over Fp is defined as Trn(α) = α + αp + αp

2 + · · · + αpn−1 . The set of all non-squares and squares in F?p are represented by

NSQ and SQ, respectively. The quadratic character of F?p is η0, and for simplicity we write p∗ = η0(−1)p, which is frequently used in the sequel.

A cyclotomic field Q(ξp) can be obtained from the rational field Q by joining the complex primitive p-th root of unity ξp. The field Q(ξp) is the splitting field of the polynomial xp−1, and so the field Q(ξp)/Q is a Galois extension of degree p−1. Here, a field basis for an extension Q(ξp)/Q is the subset {1, ξp, ξ2p , . . . , ξ

p−2 p } of the cyclotomic field Q(ξp). The Galois group Gal(Q(ξp)/Q)

is described as the set {σc: c ∈ F?p}, where σc is the automorphism of Q(ξp) defined as σc(ξp) = ξcp. The cyclotomic field Q(ξp) has a unique quadratic subfield Q(

√ p∗), and its Galois group

Gal(Q( √ p∗)/Q) = {1, σγ} for some γ ∈ NSQ. For a, c ∈ F?p, we clearly have σc(ξap) = ξcap and

σc( √ p∗

n ) = η0

n(c) √ p∗

n . The following lemma is frequently used in the subsequent proofs.

Lemma 1. [18]

i.) ∑

c∈F?p η0(c) = 0,

ii.) ∑

c∈F?p ξ ca p = −1 for every a ∈ F?p,

iii.) ∑

c∈F?p η0(c)ξ c p = √ p∗.

2.1 Linear codes

A linear [n, k, d] code C over Fp is a subspace with k-dimension of vector space Fnp . Here, n is the length of C, k is its dimension and d is its minimum Hamming distance. For a vector v = (v1, . . . , vn) ∈ Fnp , its Hamming weight WH(v) is the size of its support described as supp(v) = {1 ≤ i ≤ n: vi 6= 0}. We remark that d is the smallest Hamming weight of the nonzero elements (codewords) of C. The dual code of C is defined to be the set

C⊥ = {(u1, . . . , un) ∈ Fnp : u1v1 + · · ·+ unvn = 0 for all (v1, . . . , vn) ∈ C},

which is represented by [n, n − k, d⊥] over Fp, where d⊥ is the minimum Hamming distance of C⊥. The weight distribution of C is given by (1, A1, . . . , An) and its weight enumerator is the polynomial 1 +A1y + · · ·+Anyn, where Aω is the number of nonzero codewords with weight ω in C. As a result, we say that C is an l-weight linear code if the number of nonzero Aω in {Ai}i≥1 is equal to l, where l is an integer with 1 ≤ l ≤ n. The first two Pless power moments are given as

n∑ i=0

Ai = p k and

n∑ i=0

iAi = n(p− 1)pk−1 −A⊥1 pk−1,

where A⊥1 is the number of codewords with weight 1 in C⊥. For the proposed codes in this paper, A⊥1 = 0 since their defining sets do not cover the element (0, 0).

Construction of minimal linear codes with few weights from weakly regular plateaued functions 3

2.2 Weakly regular plateaued functions

Let f : Fq −→ Fp be a p-ary function. The Walsh transform of f is a complex valued function defined as

Wf (β) = ∑ x∈Fq

ξp f(x)−Trn(βx), β ∈ Fq.

A function f is called balanced over Fp if f gets all elements of Fp with the same number of pre-images; or else, f is said to be unbalanced. Note that f is balanced iff Wf (0) = 0.

A function f is said to be a bent function if |Wf (β)|2 = pn for every β ∈ Fq (see [22] for Boolean bent and [14] for p-ary bent). In addition, f is said to be s-plateaued if |Wf (β)|2 ∈ {0, pn+s} for every β ∈ Fq, with 0 ≤ s ≤ n, (see [28] for Boolean plateaued and [5] for p-ary plateaued). For an s-plateaued f , its Walsh support is described as the set

Sf = {β ∈ Fq: |Wf (β)|2 = pn+s}.

From the Parseval identity, we have #Sf = pn−s, and the explicit Walsh distribution of a plateaued function is given as follows.

Lemma 2. Let f be an s-plateaued function. For β ∈ Fq, |Wf (β)|2 takes the values pn+s and 0 for the times pn−s and pn − pn−s, respectively.

Mesnager et al. [20] have described the notion of weakly regular plateaued functions. An s- plateaued f is called weakly regular if we have

Wf (β) ∈ {

0, up n+s 2 ξf

?(β) p

} ,

where u ∈ {±1,±i}, f? is a p-ary function over Fq with f?(β) = 0 for every β ∈ Fq \ Sf ; otherwise, f is called non-weakly regular. We remark that a weakly regular 0-plateaued is the weakly regular bent function.

The following lemma is very useful to compute the Hamming weights of codes.

Lemma 3. [20] Let f be a weakly regular s-plateaued function. Then, we have

Wf (β) = �f √ p∗

n+s ξf

?(β) p

for every β ∈ Sf , where �f = ±1 is the sign of Wf and f? is a p-ary function over Sf .

The following two lemmas are needed to determine the weight distributions of proposed codes.

Lemma 4. [21] Let f be a weakly regular s-plateaued function. For x ∈ Fq,∑ β∈Sf

ξf ?(β)+Trn(βx) p = �fη

n 0 (−1)

√ p∗

n−s ξf(x)p ,

where �f = ±1 is the sign of Wf and f? is a p-ary function over Sf .

4 A. Sınak

Lemma 5. [21] Let f be a weakly regular s-plateaued function with 0 ≤ s < n, and it has Wf (β) = �f

√ p∗

n+s ξ f?(β) p for every β ∈ Sf , where �f = ±1 is the sign of Wf and f? is a p-ary

function over Sf . For j ∈ Fp, define Nf?(j) = #{β ∈ Sf : f?(β) = j}. Then we have

Nf?(j) =

{ pn−s−1 + �fη

n+1 0 (−1)(p− 1)

√ p∗

n−s−2 , if j = 0,

pn−s−1 − �fηn+10 (−1) √ p∗

n−s−2 , if not,

when n− s is even; otherwise,

Nf?(j) =

pn−s−1, if j = 0,

pn−s−1 + �fη n 0 (−1)

√ p∗

n−s−1 , if j ∈ SQ,

pn−s−1 − �fηn0 (−1) √ p∗

n−s−1 , if j ∈ NSQ.

Mesnager et al. [21] have very recently introduced the subclass WRP of weakly regular plateaued functions over the odd characteristic finite fie