一種基于Hamming碼的門(mén)限多秘密共享方案

李富林,劉 楊,王婭如

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230601)

0 引 言

秘密共享是一種將秘密分割儲(chǔ)存,以阻止秘密過(guò)于集中,保證秘密的安全性和可靠性的密碼技術(shù)。秘密共享是密碼學(xué)的一個(gè)重要研究分支,被廣泛應(yīng)用于信息安全與數(shù)據(jù)保密中。門(mén)限秘密共享方案又稱(chēng)作閾值秘密共享方案,于1979年由Shamir[1]和 Blalley[2]分別基于 Lagrange 插值多項(xiàng)式和射影幾何理論提出。在(k,n)門(mén)限秘密共享方案中,分發(fā)者將被共享的秘密信息分成n份,并通過(guò)安全信道將份額分發(fā)給n個(gè)參與者,其中任意k個(gè)參與者都能恢復(fù)秘密,任意k-1個(gè)或者更少的參與者無(wú)法恢復(fù)秘密。實(shí)現(xiàn)(k,n)門(mén)限秘密共享方案的方法除了以上2種,還包括Karnin-Greene-Hellman[3]矩陣法、Asmuth-Bloom[4]的中國(guó)剩余定理法等。文獻(xiàn)[1]提出的方案實(shí)現(xiàn)簡(jiǎn)單，計(jì)算代價(jià)小,并且是一個(gè)完備理想方案,得到了廣泛的研究和應(yīng)用。然而傳統(tǒng)的秘密共享方案存在著以下不足:① 秘密分發(fā)者和參與者并非都是誠(chéng)實(shí)可信的,可能存在一些欺詐行為;② 一次秘密共享過(guò)程只能共享一個(gè)秘密信息;③ 參與者的秘密份額是一次性的。即當(dāng)完成一次秘密共享過(guò)程,分發(fā)者必須通過(guò)安全信道重新為參與者分配新的份額來(lái)實(shí)現(xiàn)新一輪的秘密共享。

近幾十年來(lái),秘密共享領(lǐng)域的研究得到了快速的發(fā)展。針對(duì)欺詐行為,文獻(xiàn)[5]提出了可驗(yàn)證秘密共享的概念;文獻(xiàn)[6]在此基礎(chǔ)之上提出了可公開(kāi)驗(yàn)證的秘密共享策略的概念,并基于ElGamal的簽名策略實(shí)現(xiàn)了2個(gè)可公開(kāi)驗(yàn)證的秘密共享。為追求高效,文獻(xiàn)[7-8]提出了多秘密共享方案。文獻(xiàn)[9-10]利用Reed-Solomon譯碼方案實(shí)現(xiàn)對(duì)多個(gè)秘密的共享;文獻(xiàn)[11-12]利用極小授權(quán)集合和線(xiàn)性碼的對(duì)偶碼的極小碼字之間一一對(duì)應(yīng)的關(guān)系構(gòu)造方案;文獻(xiàn)[13]提出了一種基于強(qiáng)單向Hash函數(shù)構(gòu)造出一種可更新、多用途、多秘密共享方案;文獻(xiàn)[14]基于線(xiàn)性碼的糾錯(cuò)能力構(gòu)造了一個(gè)(l,t+l)門(mén)限秘密共享方案,選擇線(xiàn)性碼中的碼字作為秘密,通過(guò)線(xiàn)性碼譯碼問(wèn)題的難度保證了該方案的安全性和可靠性,但是無(wú)法保證秘密份額的安全性以及抵抗成員的合謀攻擊。

本文在此基礎(chǔ)上提出一種新的(n,n)門(mén)限多秘密共享方案,以Ham(k,q)的糾錯(cuò)能力為基礎(chǔ),通過(guò)將參與者進(jìn)行分組并建立組員信息,來(lái)提高秘密份額的安全性和完成對(duì)參與者的更新。利用雙變量單向函數(shù)的性質(zhì),保證秘密的準(zhǔn)確性,避免參與者的欺詐行為。本方案具有以下重要特點(diǎn):① 以Hamming碼的多個(gè)碼字作為方案的多重秘密,利用Hamming碼的糾錯(cuò)能力來(lái)重構(gòu)秘密;② 將參與者進(jìn)行分組,將秘密份額的掌握權(quán)限賦予每個(gè)組,只有全部n個(gè)小組提供其正確秘密份額才能重構(gòu)秘密,缺一不可;③ 共享多秘密,每個(gè)小組的秘密份額可重復(fù)使用,用于恢復(fù)不同的秘密,具有高效性;④ 抵抗合謀攻擊,完成對(duì)欺騙行為的識(shí)別。本文首先介紹Hamming碼和秘密共享方案的一些基礎(chǔ)知識(shí)，接下來(lái)給出算法,進(jìn)行安全性分析,并通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明該方案。

1 預(yù)備知識(shí)

1.1 Hamming碼

定義1 Ham(k,q)分別從Vα1,Vα2,…,Vαn中任取一個(gè)向量作為列向量構(gòu)成一個(gè)k×n階矩陣H。以H為校驗(yàn)矩陣的線(xiàn)性碼稱(chēng)為q元Hamming碼,記為Ham(k,q)。

定義3 設(shè)C為域Fq上的一個(gè)[n,n-k]線(xiàn)性碼,對(duì)任意的向量a,集合{a}+C={a+x|x∈C}叫做碼C的陪集。陪集首是指一個(gè)陪集中漢明重量最小的字(陪集首不一定唯一)。

可知Ham(k,q)至多可以糾正一個(gè)錯(cuò)誤,因此V(n,q)中所有重量不大于1的向量恰好就是Ham(k,q)的標(biāo)準(zhǔn)陣中的所有陪集首。

S={(0 …xi… 0)∈V(n,q)|

0≠xi∈GF(q),1≤i≤n}。

設(shè)Ham(k,q)的校驗(yàn)矩陣H中的第i列為Hi,1≤i≤n,任取

則

則S中任意2個(gè)不同的向量屬于Ham(k,q)的不同陪集,又因S中的每個(gè)向量不在Ham(k,q)中,且|S|=n(q-1)=qk-1,因此S中的向量是Ham(k,q)的非零陪集的陪集首,即V(n,q)中重量為1的向量都是陪集首。

q元Hamming碼Ham(k,q)的譯碼過(guò)程描述如下:

(1)對(duì)于在信道接收端收到的向量y,計(jì)算校驗(yàn)子S(y)=yHT。

(2)若S(y)=0,則認(rèn)為沒(méi)有錯(cuò)誤發(fā)生,y就是發(fā)送的碼字。

1.2 秘密共享方案

定義4 設(shè)s是秘密,n個(gè)參與者將秘密s分為v1,v2,…,vn個(gè)秘密份額,滿(mǎn)足下列條件：①n中任意k個(gè)參與者都能重構(gòu)秘密s;② 任意k-1個(gè)或者更少的參與者都無(wú)法重構(gòu)秘密s。

此方案被稱(chēng)為(k,n)門(mén)限秘密共享方案[1]。(n,n)門(mén)限秘密共享方案是此方案的一個(gè)簡(jiǎn)化門(mén)限方案。

定義5 雙變量單向函數(shù)[16],令f(r,s)表示一個(gè)有2個(gè)變量的單向函數(shù),它能夠?qū)⑷我忾L(zhǎng)的r和s映射為固定長(zhǎng)的函數(shù)值f(r,s)。該函數(shù)具有以下性質(zhì):

(1)已知r和s，f(r,s)易于計(jì)算。

(2)已知s和f(r,s)，求r在計(jì)算上是不可行的。

(3)已知r和f(r,s)，求s在計(jì)算上是不可行的。

(4)在s未知的情況下,對(duì)于任意的r,難以計(jì)算f(r,s)。

(5)在已知s的情況下,找到r1≠r2且滿(mǎn)足f(r1,s)=f(r2,s)在計(jì)算上是不可行的。

2 方案描述

2.1 系統(tǒng)初始化

D將H傳入公告欄,所有人可查。

2.2 秘密份額分發(fā)

D取矩陣E的第t列bt作為秘密份額傳給小組Pt,t=1,2,…,n。秘密份額在小組內(nèi)共享,即同一個(gè)小組中的參與者掌握同一秘密份額。計(jì)算雙變量單向函數(shù)f(t,bt)的值,記為f(t)。D將偽秘密份額f(1),f(2),…,f(n)傳入公告欄,所有人可查。

2.3 秘密重構(gòu)

醫(yī)保辦工作人員積極參加醫(yī)保經(jīng)辦機(jī)構(gòu)組織的各種醫(yī)保會(huì)議及醫(yī)保管理方法分享等活動(dòng)，學(xué)習(xí)最新醫(yī)保管理策略。邀請(qǐng)上級(jí)醫(yī)保經(jīng)辦機(jī)構(gòu)人員來(lái)院進(jìn)行醫(yī)保知識(shí)講座和對(duì)新政講解，針對(duì)理解不到的內(nèi)容和案例互動(dòng)交流，達(dá)成對(duì)醫(yī)保政策理解的共識(shí)，從而保持醫(yī)保政策貫徹執(zhí)行的一致性。

3 安全性分析

3.1 可驗(yàn)證性分析

3.2 安全性

(1)秘密份額的安全性。為了防止每個(gè)小組的秘密份額不被泄露,秘密分發(fā)者D在構(gòu)造檢驗(yàn)是否存在參與者欺騙行為的公共信息時(shí),傳入公告欄的是各組的偽份額f(t,bt),而不應(yīng)該是各組的真正秘密份額。即使f(t,bt)被泄露,依據(jù)雙變量單向函數(shù)f(r,s)的單向性,難以得到bt,真正的秘密份額則不會(huì)泄露。

(2)任何小于n個(gè)小組合作都無(wú)法得到秘密。假設(shè)n-1個(gè)小組合作,分別記為P1,P2,…,Pn-1,其秘密份額組成l×(n-1)階矩陣，即

當(dāng)i=1,2,…,l時(shí),取得向量vi,其碼長(zhǎng)為n-1,譯碼過(guò)程無(wú)法正常進(jìn)行。因此,只有全部n個(gè)小組提供其正確秘密份額時(shí)才能重構(gòu)秘密。

3.3 動(dòng)態(tài)性

方案具有動(dòng)態(tài)性,能夠完成對(duì)參與者的更新。若參與者集合U有w個(gè)新的參與者uN+1,uN+2,…,uN+w,D將這些參與者分發(fā)到M(1≤M≤n)個(gè)組,添加成員信息到公告欄。例如,D分發(fā)uN+1到P1則uN+1的信息記為(1,uN+1)。小組分享該組秘密份額給新組員,無(wú)需重新分發(fā)秘密份額。若參與者集合U存在參與者退出,t=1,2,…,n,當(dāng)|Pt|≠0,刪除參與者信息即可;當(dāng)|Pt|=0,則將所有參與者重新分組,在公告欄中更新新的組內(nèi)成員信息。

4 實(shí)例分析

5 結(jié) 論

本文討論了一種新的構(gòu)造(n,n)門(mén)限多秘密共享方案的方法,該方法將Hamming碼的不同碼字作為多個(gè)不同的秘密,根據(jù)Hamming碼只能糾正一個(gè)錯(cuò)誤的性質(zhì)重構(gòu)秘密,并且可重復(fù)使用秘密份額,來(lái)恢復(fù)不同的秘密；然后依據(jù)雙變量單向函數(shù)的性質(zhì),在重構(gòu)秘密時(shí)利用函數(shù)驗(yàn)證秘密份額的有效性,能夠有效地防止外界敵手和參與者的欺騙行為；最后通過(guò)實(shí)例來(lái)驗(yàn)證該方案的有效性和可行性。