門限秘密分享中高效添加新參與者方案

林修慧，林昌露，3，4，黃可可，李世唐

(1.福建師范大學 數(shù)學與統(tǒng)計學院，福建 福州 350117;2.福建師范大學 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室，福建 福州 350007;3.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004;4.重慶郵電大學 網(wǎng)絡(luò)空間與信息安全重慶市重點實驗室，重慶 400065)

Shamir[1]和Blakley[2]各自獨立提出了秘密分享概念，并分別基于多項式和射影幾何理論構(gòu)造了具體的門限秘密分享方案。一般地，(t，n)門限秘密分享方案由分發(fā)階段和重構(gòu)階段兩部分組成，并有一個秘密分發(fā)者和n個參與者，其中t為門限值。在分發(fā)階段，分發(fā)者把一個秘密隨機地生成n個份額，并分別把這些份額通過安全信道秘密地發(fā)送給n個參與者;在重構(gòu)階段，只要大于等于t個參與者分別拿出自己的份額就可以正確地重構(gòu)出秘密。1982年，Mignotte[3]提出了基于中國剩余定理(Chinese remainder theorem，CRT)的門限秘密分享方案。1983年，Asmuth和Bloom[4]改進了它的安全性，提出了安全的門限秘密分享方案。相較于Shamir的多項式門限秘密分享方案，基于CRT的秘密分享方案計算效率更高。

在門限秘密分享方案的實際應用場景中，有時需要增加新參與者。針對這樣的場景，許多學者提出了可以添加新參與者的門限秘密分享方案。1988年，Ben-Or等[5]基于范德蒙德行列式，提出了可以添加參與者的門限秘密分享。2003年，Desmedt等[6]基于拉格朗日插值多項式，也提出了可以添加參與者的門限秘密分享。以上兩個方案都是基于多項式的門限秘密分享，都不需要分發(fā)者的參與。在添加參與者過程中，需要原先的至少t個參與者的共同參與:參與者們兩兩互相發(fā)送一個值，每個參與者收到所有的值后再進行計算，之后把計算結(jié)果發(fā)送給新參與者，從而完成添加過程。在這過程中的總通信次數(shù)為t2次。

現(xiàn)有基于CRT的門限秘密分享文獻[7-10]分別構(gòu)造了添加參與者的方案。2016年，張明武等[7]提出了帶權(quán)重的動態(tài)可驗證門限秘密分享，可以驗證秘密的有效性，但在添加參與者過程中需要分發(fā)者的參與，這使得這個方案無法在無可信分發(fā)者的具體場景中應用。2018年，王巖等[8]提出了動態(tài)門限簽名方案，在添加新參與者過程不需要分發(fā)者，原先參與者僅需要互相通信一次，再與新參與者通信一次為新參與者生成新的份額，其總通信次數(shù)為t2次。2020年，洪璇等[9]提出了前向安全簽名方案，但這個方案在添加參與者時需要可信分發(fā)者的參與，同樣不適用于無可信分發(fā)者的具體場景。2020年，程亞歌等[10]提出了具有強前向安全性的動態(tài)門限簽名方案，在添加新參與者階段雖然不需要分發(fā)者的參與，其通信總次數(shù)也為t2次。上述添加新參與者的方案均是基于CRT的門限秘密分享，但是在添加新參與者階段并不能做到無分發(fā)者且通信總次數(shù)均為t2次。

對此，本文基于Asmuth-Bloom門限秘密分享方案提出一個高效的添加參與者方案。在添加新參與者階段，至少需要t個參與者參加;原先參與者之間不需要進行通訊，只需要通過安全信道向新參與者發(fā)送一個具體的數(shù)值。這個數(shù)值將由隨機數(shù)掩蓋，新參與者在收到所有的數(shù)值之后進行簡單的模運算就能得到新的份額。

本文方案的優(yōu)勢如下:

(1)由于隨機數(shù)的掩蓋，保證了秘密和原參與者份額的信息不會泄露;在添加參與者過程中，不需要分發(fā)者的參與。

(2)在整個階段的通信中，只需要有t個參與者發(fā)送一次值給新參與者，所以總通信次數(shù)為t次。

(3)在整個階段中，因為原有的信息不會泄露，所以原來的份額不用改變，且分享的秘密值也不需要改變。

1 預備知識和安全模型

1.1 (t，n)門限秘密分享

(t，n)門限秘密分享方案[1]中t表示門限值，n表示參與者總數(shù)，設(shè)n個參與者為Pi(i=1，2，…，n)。一般地，(t，n)門限秘密分享方案由分發(fā)函數(shù)Share和重構(gòu)函數(shù)Rec組成。

分發(fā)階段:設(shè)S是秘密的取值集合。S由一個分發(fā)函數(shù)Share映射到S1×S2×…×Sn，Si是參與者Pi(i=1，2，…，n)對應份額的取值集合。分發(fā)者要分發(fā)一個秘密s∈S，計算Share(s)=(s1，…，sn)，si∈Si，通過安全信道秘密地發(fā)送si給Pi。

重構(gòu)階段:至少有t個Pi拿出自己的份額si，然后執(zhí)行重構(gòu)函數(shù)Rec(si1，si2，…，sit)得到s。

(t，n)門限秘密分享需滿足如下的正確性和安全性:

正確性:至少有t個參與者都拿出他們的份額后，可以正確的重構(gòu)秘密，那么有H(s|{si1，si2，…，sit})=0。

安全性:就算任意小于等于t-1個參與者拿出他們的份額，他們也得不到關(guān)于秘密的任何信息，也就是有H(s|{si1，si2…，sit-1})=H(s)。

這里H(*)表示信息“*”的信息熵[11]。

1.2 中國剩余定理

中國剩余定理[12]是求解一次同余式組的方法，又稱為中國余數(shù)定理或?qū)O子定理。一次同余式組最早出現(xiàn)于中國南北朝時期的數(shù)學著作《孫子算經(jīng)》中。下文是這個定理的詳細介紹。

設(shè)m1，m2，…，mn為兩兩互素的正整數(shù)，即對任意的i≠j，i，j∈{1，2，…，n}時，有g(shù)cd(mi，mj)=1，這里gcd(a，b)表示為a與b的最大公約數(shù)。s1，s2，…，sn也為正整數(shù)，如果有如下的同余方程組成立

那么此方程組在模M下有唯一解，形式如下

1.3 Asmuth-Bloom方案

Asmuth-Bloom方案[4]是基于中國剩余定理構(gòu)造的(t，n)門限秘密分享方案，方案具體描述如下。

分發(fā)階段:分發(fā)者公開選取一組滿足下列條件的整數(shù){p，m1，m2，…，mn}:

(1)mi

(2)gcd(mi，mj)=1，i≠j，i，j=1，2，…，n;

(3)gcd(p，mi)=1，i=1，2，…，n;

分發(fā)者秘密地選取秘密s，且0≤s

分發(fā)者計算si≡x(modmi)，i=1，2，…，n，通過安全信道秘密地發(fā)送si給Pi。

重構(gòu)階段:每個參與者Pi公開自己的份額si，由中國剩余定理有

1.4 安全模型

在一般的秘密分享中，通?？紤]有兩種類型敵手:外部敵手和內(nèi)部敵手(也稱為半誠實敵手)，其中:

(1)外部敵手沒有合法的份額，但是會偽裝成合法的參與者(持有份額的參與者)去參加秘密重構(gòu)等，其目的就是獲取秘密值或正確的份額;

(2)內(nèi)部敵手是合法參與者，會正確地執(zhí)行協(xié)議，但是會試圖獲得其他參與者的份額。

本文所設(shè)計的方案在添加參與者階段只考慮內(nèi)部敵手，即秘密值是否會在添加參與者階段泄露給參與者，合法參與者之間的份額是否會在添加參與者階段互相泄露。

2 本文方案

本文所構(gòu)造的方案分為分發(fā)階段，添加新參與者階段，重構(gòu)階段3個部分。本文的主要貢獻就是在添加新參與者這個階段。添加參與者階段:在無分發(fā)者的情況下，每個原先的參與者(大于等于t個)給新參與者不公開地發(fā)送一個由他們的私鑰與隨機數(shù)構(gòu)成的數(shù)值;然后新參與者針對這些數(shù)值進行一些模計算，就能得到自己的份額。整個過程中秘密的信息不會暴露給任何人，每個參與者的份額也不會暴露給其他參與者(包括新參與者)，在重構(gòu)過程中新參與者也可以參加秘密的重構(gòu)，并正確地重構(gòu)出秘密。方案的具體過程如下。

添加新參與者階段:任意t個原先持有份額的參與者隨機選擇一個隨機數(shù)乘以mn+1，再選取一個隨機數(shù)乘以M，然后與自己份額的計算結(jié)果相加之后將得到的值發(fā)送給新參與者。新參與者在收到至少t個參與者發(fā)送的值之后，進行一次求和運算與兩次模運算就可以得到自己的份額。具體構(gòu)造步驟如下。

(2)不失一般性，假設(shè)前t個參與者Pi，i=1，2，…，t。Pi隨機選取一個隨機數(shù)ri，0

那么sn+1就是新參與者Pn+1的份額。

重構(gòu)階段:這一階段與1.3節(jié)所述的方案重構(gòu)方法一致，這里不加贅述;唯一的不同就是n+1個參與者都可以參加重構(gòu)。

3 方案分析

3.1 正確性分析

針對方案的正確性分析，本文考慮的是新參與者從至少t個原參與者獲取的份額應該和有分發(fā)者在的時候直接分發(fā)的份額是一樣的，所以需要證明的是sn+1≡x(modmn+1)。

定理1如果在添加新參與者階段步驟(1)、(2)中的參與者誠實正確地執(zhí)行協(xié)議，那么Pn+1可正確地獲得份額sn+1。

證明當Pn+1收到所有的ci(i=1，…，t)后，對它們進行求和模M運算，將會得到

對上式進行模mn+1運算有

所以，Pn+1可正確地計算出自己的份額sn+1，證畢。

3.2 安全性分析

本文主要考慮在分發(fā)過程中秘密不會泄露給任何參與者，任何參與者的份額不會暴露給其他參與者。由于t個參與者都是通過安全信道把信息傳輸給新參與者，所以只要考慮3個方面:

(1)秘密是否會泄露給新參與者。

(2)原參與者的份額是否會暴露給新參與者。

(3)方案要滿足t-1安全性。

由于在構(gòu)造過程中每個用戶子秘密都是由隨機數(shù)掩蓋，所以考慮新用戶進行取模運算是否可能消掉隨機數(shù)來獲得子秘密或真實秘密的信息。

定理2對于內(nèi)部敵手Pn+1，秘密值x不會暴露給Pn+1。

證明若Pn+1拿到ci，i=1，2，…，t后，直接對其進行模M計算，那么有

由于每個ri都是t個參與者隨機選取，所以Pn+1不可能從上式的右邊解出x，即Pn+1無法得知秘密的信息，證畢。

定理3對于內(nèi)部敵手Pn+1，Pi(i=1，2，…，t)的份額不會暴露給Pn+1。

證明下面將對可能出現(xiàn)的3種情況進行分類討論:

第二種:若Pn+1拿到Pi發(fā)過來的份額ci時，不進行求和，而對每個分開的ci單獨進行如下計算

ci≡siMiyi+rimn+1+r′iM(modmi)≡

si+rimn+1(modmi)

由于ri是Pi隨機選取的隨機數(shù)，且gcd(mn+1，mi)=1，最后得到的結(jié)果依賴于ri的選取，所以Pn+1不能從上式的右邊得到關(guān)于si的信息。

第三種:考慮Pn+1對ci進行模mn+1運算，得到

ci≡siMiyi+rimn+1+r′iM≡siMiyi+r′iM(modmn+1)

由于gcd(M，mn+1)=1且gcd(r′i，mn+1)=1，所以r′iM(modmn+1)的結(jié)果是未知的，故Pn+1不能從上式得到關(guān)于si的信息。

綜上所述，Pi(i=1，2，…，t)的份額不會暴露給Pn+1，證畢。

定理4如果方案正確執(zhí)行，那么任意的t-1個參與者得不到秘密的信息。

證明根據(jù)Asmuth-Bloom方案可知，在原先的n個參與者中，任意的t-1個參與者得不到秘密的信息，所以只需考慮Pn+1與另外的t-2個參與者共謀。在本文方案中，假設(shè)的是前t個參與者發(fā)送ci給Pn+1，所以要考慮兩種情況:

第一種:發(fā)送ci給Pn+1的參與者{P1，P2，…，Pt-2}與Pn+1參與共謀。

第二種:沒有發(fā)送ci給Pn+1的參與者{Pt+1，Pt+2，…，P2t-2}與Pn+1參與共謀。

在第一種情況中，{P1，P2，…，Pt-2}擁有{s1，s2，…，st-2}，Pn+1擁有sn+1與ci=siMiyi+rimn+1+r′iM，i=1，2，…，t。這樣，只需證明不能從{ct-1，ct}獲得st-1或st的信息即可。因為rt-1，r′t-1是Pt-1獨立選取的隨機數(shù)，rt，r′t是Pt獨立選取的隨機數(shù)，所以ct-1和ct是獨立的，根據(jù)定理3可知，不能從ct-1和ct中解出st-1或st的值，證畢。

在第二種情況中，{Pt+1，Pt+2，…，P2t-2}擁有{st+1，st+2，…，s2t-2}，Pn+1擁有sn+1與ci=siMiyi+rimn+1+r′iM，i=1，2，…，t。這樣，只需證明不能從ci中得到任意一個si即可。因為ri-1，r′i是Pi獨立選取的隨機數(shù)，所以ci是相互獨立的，根據(jù)定理3可知，不能從單獨的ci中解出任意的si。

綜上所述，任意的t-1個參與者得不到秘密的信息,證畢。

4 性能分析

本文所構(gòu)造的方案在添加階段不需要分發(fā)者的加入，通過增加隨機數(shù)的方法保證了原先參與者的份額與秘密的信息不會泄露給新用戶。在添加新參與者階段沒有額外的公開值，僅需t次通信總次數(shù)，新參與者在收到其他參與者發(fā)送的消息后，只需要進行簡單的模計算就可以計算出自己的份額。總體而言，本文方案較大地降低了通信代價。表1是其他基于CRT的門限秘密分享方案[8-10]與本文方案在添加參與者階段的詳細比較。

表1 方案的特性對比

5 結(jié)束語

本文基于Asmuth-Bloom方案提出了一種基于CRT可實現(xiàn)添加參與者的門限秘密分享方案。在添加新參與者階段，原先的每個參與者發(fā)送一個隨機數(shù)掩蓋的數(shù)值給新參與者，新參與者只需進行求模計算就能得到新的份額，從而完成分發(fā)過程。安全性分析表明本文方案保證了秘密的信息和原先參與者的份額信息不會泄露給新參與者。在不改變原方案任何信息的情況下實現(xiàn)了通信總次數(shù)為t的秘密分享方案。本文所提方案可以作為一種工具，比如嵌入到表1中其他方案或用于其他網(wǎng)絡(luò)空間結(jié)構(gòu)[14]，以提高它們的通信效率，使它們具有更高的應用價值。