摘 要：文章利用Hermite插值的思想，提出了一種基于橢圓曲線的多秘密共享方案。在該方案中，可靈活的增刪參與者，參與者的子秘密可以重復(fù)使用且可認(rèn)證，多個(gè)主秘密能夠同時(shí)被重構(gòu)。所給方案能夠有效抵御管理者欺騙和參與者欺騙。

關(guān)鍵詞：Hermite插值公式；橢圓曲線；多秘密共享；橢圓曲線離散對(duì)數(shù)問題

中圖分類號(hào)：TP309

秘密共享方案[1-2]就是一個(gè)秘密被分成n個(gè)子秘密，再分發(fā)給n個(gè)參與者，當(dāng)任意大于或等于t個(gè)參與者合作能夠恢復(fù)出該秘密。現(xiàn)有的秘密共享門限方案中，通常存在以下部分不足[3-4]：（1）參與者擁有的子秘密不能多次使用；（2）只能共享一個(gè)秘密；（3）無(wú)法抵御管理者欺騙；（4）無(wú)法抵御參與者欺騙。本文基于橢圓曲線密碼體制和Hermite插值法提出了一種新的可驗(yàn)證的多秘密共享方案。該方案能夠同時(shí)避免以上不足，還有參與者能夠靈活增減，多個(gè)主秘密能夠同時(shí)被重構(gòu)出來(lái)，能識(shí)別公開信息被惡意篡改等特點(diǎn)。

1 方案的構(gòu)造

1.1 準(zhǔn)備階段

設(shè)秘密的管理者為UD，S={s1，s2，…，sm}是m個(gè)需要共享的主秘密集合，U={u1，u2，…，un}是共享S中秘密的具有n個(gè)參與者的參與者組。UD生成公告牌PB用于存儲(chǔ)公開參數(shù)。UD在有限域GF（q）（其中q為大素?cái)?shù)）上選取一條安全的橢圓曲線：y2=x3+ax+b。選擇E（Fq）上的一個(gè)基點(diǎn)G，G的階為大素?cái)?shù)N。h（x）為單向hash函數(shù)。UD把（E，G，N，h（x））放入PB中。UD在區(qū)間[1，N-1]隨機(jī)選擇n個(gè)不同的整數(shù)Ki（i=1，2，…，n）作為ui（i=1，2，…，n）的子秘密，并通過(guò)安全通道秘密發(fā)送給各個(gè)參與者。

因Hermite插值多項(xiàng)式系數(shù)與門限值t有關(guān)，因此我們針對(duì)m與t的關(guān)系分別設(shè)計(jì)方案。

1.2 m≤2t-1時(shí)的方案：

1.2.1 構(gòu)造階段

（1）UD構(gòu)造一個(gè)2t-1階多項(xiàng)式f（x）：

當(dāng)1≤i≤m，ai=si；當(dāng)m

（2）計(jì)算yi=f（h（ki））和y`i=f`（h（ki））（i=1，2，…n）的值。

（3）針對(duì)多項(xiàng)式系數(shù)，計(jì)算檢查向量M=（M1，M2，…，M2t），其中Mi=aiG（i=1，…，2t）。把M存入PB中。

（4）在橢圓曲線E（Fq）上任選一點(diǎn)R，計(jì)算Di（i=1，…，n）：

Di≡（yi，yi`）-kiR（modN） 公式（1）

為了參與者相互之間能檢驗(yàn)子秘密的真?zhèn)?，?jì)算參數(shù)Ci=h（KiR）（i=1，2，…，n）。

（5）UD將點(diǎn)R，參數(shù)M，Di（i=1，2，…，n）和Ci=（i=1，2，…，n）放入中。

1.2.2 子秘密的驗(yàn)證

當(dāng)參與者ui收到子秘密ki之后。通過(guò)公式（1）檢驗(yàn)子秘密ki的有效性。

公式（2）

若公式（1）成立，則表示UD發(fā)給ui的子秘密ki是誠(chéng)實(shí)的。

1.2.3 主秘密的恢復(fù)

當(dāng)任意t個(gè)參與者欲恢復(fù)出主秘密結(jié)合S={s1，s2，…，sm}時(shí)，其恢復(fù)過(guò)程如下：

（1）參與者計(jì)算并提供屏蔽子秘密Wi≡KiR（modn）（i=1，2，…，t）。

（2）其他參與者驗(yàn)證等式Ci=h（Wi），若成立則該屏蔽子秘密是有效的。

（3）通過(guò)公式（1）及公式（2）可以驗(yàn)證相關(guān)公開參數(shù)的正確性，然后通過(guò)公式（yi，yi`）=（Di+Wi）（modN）計(jì)算出（yi，yi`）。

（4）由t個(gè)（yi，yi`）對(duì)，結(jié)合Hermite插值公式，即可恢復(fù)出多項(xiàng)式f（x）。其中前m個(gè)系數(shù)既是主秘密{s1，s2，…，sm}。

1.3 m≥2t時(shí)的方案：

1.3.1 構(gòu)造階段

（1）UD構(gòu)造一個(gè)m-1階多項(xiàng)式f（x）：

，其中ai=si，記為f（x）導(dǎo)數(shù)。

（2）計(jì)算yi=f（h（ki））和yi`=f`（h（ki））（i=1，2，…，n）的值。

（3）通過(guò)Hermite插值公式，重構(gòu)m-1階多項(xiàng)式f（x）。

當(dāng)m為奇數(shù)時(shí)（m為偶數(shù)類似可求）：

計(jì)算Zv=f（bv）（v=1，2，…，（m+1）/2-t），Zv`=f`（bv）（v=1，2，…，（m+1）/2-t）

，并將（Zv，Zv`）（v=1，2，…，（m+1）/2-t）存入中。

（4）在橢圓曲線E（Fq）上任選一點(diǎn)R，放入PB，類似2.2.1（3）（4）（5）過(guò)程，計(jì)算并將M，Di（i=1，2，…，n），Ci（i=1，2，…，n）放入PB，。

1.3.2 子秘密的驗(yàn)證

當(dāng)參與者ui收到子秘密ki之后。通過(guò)公式（3）檢驗(yàn)子秘密ki的有效性。

公式（3）

1.3.3 主秘密的恢復(fù)

當(dāng)任意t個(gè)參與者欲恢復(fù)出主秘密結(jié)合S={s1，s2，…，sm}時(shí)，其恢復(fù)過(guò)程如下：

（1）類似2.2.3（1）（2）（3）過(guò)程，求出（yi，yi`）（i=1，2，…，t）。

（2）通過(guò)下式檢驗(yàn)（Zv，Zv`）（v=1，2，…，（m+1）/2-t）是否有效。

公式（4）

（3）參與者由t個(gè)點(diǎn)（yi，yi`）及（Zv，Zv`）（v=1，2，…，（m+1）/2-t），結(jié)合插值公式，可恢復(fù)出多項(xiàng)式f（x），從而獲得了主秘密。

2 方案分析

2.1 正確性分析

公式（1）的證明過(guò)程如下，證明：由Di≡（yi，yi`）-kiR（modN）（i=1，2，…，n）知：（yi，yi`）≡（Di+kiR）（modN）（i=1，2，…，n）。假若參與者ui收到的子秘密ki正確無(wú)誤。則必有：。所以：

即（2）成立。公式（3）（4）的驗(yàn)證過(guò)程類似。

2.2 安全性分析

攻擊1：惡意者試圖通過(guò)公開信息恢復(fù)主秘密mi。由Mi求ai，其中Mi=aiG，因?yàn)榛跈E圓曲線離散對(duì)數(shù)問題的計(jì)算難解性，所以求不出，即無(wú)法恢復(fù)出主秘密。

攻擊2：管理者欺騙。 假若管理者給參與者提供虛假的子秘密，這時(shí)參與者通過(guò)公式（2）或（3）可以驗(yàn)證子秘密的正確性，識(shí)別管理者的欺騙。

攻擊3：參與者欺騙。在本方案中參與者如果想提供虛假屏蔽子秘密且不被其他參與者發(fā)現(xiàn)需通過(guò)的通過(guò)Ci=h（wi）的驗(yàn)證，而這難度等同找到函數(shù)的一個(gè)碰撞。

3 結(jié)束語(yǔ)

在本文提出的可驗(yàn)證多秘密共享方案中，分發(fā)者能夠動(dòng)態(tài)決定要共享的主秘密個(gè)數(shù)，且多個(gè)主秘密能夠被同時(shí)重構(gòu)出來(lái)。主秘密更新時(shí)，參與者可以反復(fù)多次使用自己的子秘密。本方案的每一個(gè)階段，都進(jìn)行了嚴(yán)格的論證，能有效地抵御各種形式的偽造欺騙。

參考文獻(xiàn)

[1]Shamir A.How to share a secret[J].Communications of the ACM，1979，22（11）：612-613.

[2] Blakley G.R.Safeguarding cryptographic keys[C].Proceedings of the 1979 National computer conference，New York，June 47，1979，vol.48，AFIPS Press，313-317.

[3]吳春英，李順東.一類特殊超圖與理想秘密共享方案[J].計(jì)算機(jī)工程，2013，39（7）：205-208.

[4]張曉敏.基于線性單向函數(shù)的可驗(yàn)證的多秘密共享方案[J].計(jì)算機(jī)應(yīng)用，2013，33（5）：1391-1393.

作者單位：湖南化工職業(yè)技術(shù)學(xué)院，湖南株洲 412000