幾類線性碼的擴(kuò)展碼及其在密鑰共享中的應(yīng)用*

李曉茹,衡子靈,李文婷

(長安大學(xué)理學(xué)院，陜西 西安 710064)

1 引言

令q為素數(shù)p的方冪，r=qm，m為整數(shù)且m>1，F(xiàn)r表示有r個元素的有限域，α為Fr的本原元。

1.1 線性碼及其擴(kuò)展碼

A(z)=1+A1z+A2z2+…+Anzn

(1)

稱為C的重量計算器。重量分布可以用來刻畫線性碼糾錯和檢錯的出錯概率,是線性碼理論中的重要研究課題，有大量文獻(xiàn)研究了線性碼的重量分布[1-4]。

x1+x2+…+xn+1=0}

(2)

1.2 極小碼及其在密鑰共享中的應(yīng)用

設(shè)C是參數(shù)為[n,k]的線性碼，c=(c1,c2,…,cn)∈C。定義c的支撐集supp(c)={i:ci≠0,1≤i≤n}。設(shè)c′∈C為任意與c線性無關(guān)的碼字。如果supp(c′)?supp(c)總成立，那么稱c為極小碼字。極小碼字可以用來描述基于線性碼構(gòu)造的密鑰共享方案的訪問結(jié)構(gòu)。

密鑰共享方案是一種設(shè)計秘密拆分方式和恢復(fù)方式的方法。設(shè)P表示參與者構(gòu)成的集合。秘密共享的基本思想是將秘密以適當(dāng)?shù)姆绞讲鸱郑鸱趾蟮拿恳环萦蒔中的每一個參與者管理，單個參與者無法恢復(fù)信息，只有被授權(quán)的P的某個子集Γ中的所有參與者共同協(xié)作才能恢復(fù)秘密信息。被授權(quán)的子集Γ稱為訪問結(jié)構(gòu)。1993年，Massey[6]利用線性碼構(gòu)造出密鑰共享方案，并建立了訪問結(jié)構(gòu)和對偶碼極小碼字之間的聯(lián)系。然而，線性碼的極小碼字一般很難確定，它和完全譯碼問題密切相關(guān)。2006年，Yuan等[7]提出利用一類特殊線性碼—極小碼來構(gòu)造安全高效訪問結(jié)構(gòu)上的密鑰共享方案,所有碼字都是極小碼字的線性碼稱為極小碼。Ashikhmin等[8]給出了如下判定線性碼為極小碼的充分條件:

根據(jù)引理1，很多研究人員[1-3,7,9]構(gòu)造出了可用于構(gòu)造密鑰共享方案的極小碼。

1.3 本文主要工作

令Trr/q表示從Fr到Fq的跡函數(shù)，其中Trr/q(x)=x+xq+…+xqm-1，x∈Fr。特別地，單位元素0的完全反象Trr/q-1(0)稱為跡函數(shù)Trr/q的核，記為ker(Trr/q)。

上述3個構(gòu)造所得的線性碼均為極小碼，從而都可用于構(gòu)造安全高效訪問結(jié)構(gòu)上的密鑰共享方案。

2 數(shù)學(xué)基礎(chǔ)

(3)

(4)

(5)

(6)

Trr/q(bαn-1),cn+1):

(7)

該擴(kuò)展碼是[n+1,m,qm-1]三重碼，其重量計數(shù)器如式(8)所示：

A(z)=1+(qm-2-1)zqm-1+2(qm-1-qm-2)zqm-1+1+

(qm-2qm-1+qm-2)zqm-1+2

(8)

(9)

令：

從而有式(10)成立：

(10)

(11)

□

(12)

從而可得CS的重量計數(shù)器。

□

Trr/q(bαn-1),cn+1):

(13)

是[n+1,m,qm-1-1]三重碼，其重量計數(shù)器為A(z)=1+(qm-1-qm-2)zqm-1-1+(qm-2qm-1+2qm-2-1)zqm-1+(qm-1-qm-2)zqm-1+1。

(14)

(15)

令:

從而有式(16)成立:

(16)

(17)

□

4 擴(kuò)展碼的參數(shù)和重量分布

引理5很容易證明，過程略去。

(18)

□

5 擴(kuò)展碼的參數(shù)和重量分布

(19)

Trr/q(bα(n-1)h),cn+1):

(20)

證明由于

(21)

令:

從而有式(22)成立：

(22)

(23)

□

6 結(jié)束語

Table 1 Some optimal or almost optimal codes