理想型(t,k,n)緊耦合秘密共享構(gòu)造

白建峰，苗付友

中國科學(xué)技術(shù)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥230027

秘密共享作為密碼學(xué)的一個原語（primitive），廣泛應(yīng)用在各種密碼系統(tǒng)的構(gòu)造，比如：安全多方計算[1-2]、組認證[3]、門限密碼系統(tǒng)[4-5]等。最早在1979年，由Shamir[6]和Blakley[7]提出的門限秘密共享的概念。通常來說，門限秘密共享是用來保護秘密一種手段，通過將秘密分割成n份子份額（share），其中任意的t份組合在一起可以恢復(fù)出秘密。

到目前為止，提出的門限秘密共享方案，主要分為以下幾類，一類是Shamir提出的用拉格朗日差值多項式實現(xiàn)的門限秘密共享。一類是Massey[8]提出的使用線性碼來實現(xiàn)門限秘密共享。還有一類是Mignotte[9]和Asmuth-Bloom[10]提出的用中國剩余定理實現(xiàn)的門限秘密共享方案。

在門限秘密共享中，任意的t個子份額的組合能夠恢復(fù)出秘密。當參與者人數(shù)為k(k ＞t)個時，實際只需要用到t個份額就可以恢復(fù)秘密。多出的子份額對恢復(fù)秘密沒有任何幫助。這就會帶來問題，當k(k ＞t)個參與者參與恢復(fù)秘密時，這t個子份額到底由誰出。在理想的通信模型下，k(k ＞t)個參與者同時發(fā)送子份額，就會假定k(k ＞t)個參與者會同時收到除自身以外的k-1 個子份額。在現(xiàn)實生活中，這顯然是不現(xiàn)實的?，F(xiàn)實生活中，通信模型往往是異步的，即參與者發(fā)送和接收子份額是有先后順序的，當參與者收到的子份額數(shù)達到t時，就能恢復(fù)出秘密。如果該參與者是惡意用戶，可以用恢復(fù)出的秘密再構(gòu)造出一個正確的子份額發(fā)送給其他用戶，且其他用戶無法知道該用戶是不是惡意用戶。

針對上述的問題，阻止這樣的非法用戶恢復(fù)秘密?？梢允褂每沈炞C秘密共享[11-12]，在秘密恢復(fù)過程中首先驗證參與者的身份，再進行秘密的恢復(fù)。但是這樣就會帶來多輪的交互式通信和處理時間，以及秘密分發(fā)過程中需要額外的信息，來完成驗證，帶來極大的開銷。為了使用一種簡單的方法來解決上述問題，Harn等人[13]利用拉格朗日插值多項式的同態(tài)特性提出了一種(t,n)秘密安全恢復(fù)方案。方案使用l(l≥2)多項式生成l個子份額，即每個參與者擁有l(wèi)個子份額。它需要滿足kl ＞n-1，意味著所有多項式系數(shù)個數(shù)小于所有參與者的個數(shù)。換言之，門限t的個數(shù)受限于所有多項式和參與者的個數(shù)限制，不夠靈活。更嚴重的是，在2017 年，Ahmadian 等人[14]使用線性子空間的分析方法證明只要超過t+l-1 個參與者就可以恢復(fù)出秘密，違背了需要k個參與者都參與恢復(fù)秘密的原則，Harn等人的方案是不安全的。

緊耦合秘密共享是近年來提出的另外一種解決方法，具體指的是在秘密恢復(fù)過程中，將參與秘密恢復(fù)的k(t≤k≤n)個人作為一個整體，緊緊耦合在一起，每個參與者都必須參與到秘密恢復(fù)過程中，才能將秘密給恢復(fù)出來。相較于上述提到的解決方案，其主要具有以下優(yōu)點：（1）門限t沒有任何的限制條件；（2）秘密分發(fā)過程不需要額外的信息；（3）方案是無條件安全的，不依賴于數(shù)學(xué)難題。其最早是從文獻[15]中提出的隨機化組件應(yīng)用在面向組的秘密共享方案中抽象出來。安全性要求提升到攻擊者得到任意的k-1 個份額也無法獲取關(guān)于秘密的任何信息?，F(xiàn)已有工作在緊耦合秘密共享的基礎(chǔ)上提出了組認證[16]，拓展訪問結(jié)構(gòu)[17]等方案。

緊耦合秘密共享典型的應(yīng)用場景就是用于構(gòu)造組認證協(xié)議，完成對多個用戶的身份認證。在實際的應(yīng)用中，如果需要對多個用戶即一個組的用戶完成身份認證，有兩種解決方案。一是將這個組的每個用戶依次進行身份認證。二是將這個組作為整體，針對這個整體的進行身份驗證。顯然后者的效率更高。緊耦合秘密共享就可以用于構(gòu)建這樣的組認證協(xié)議，將多余t個用戶作為一個整體，耦合在一起。當這個群組能夠恢復(fù)出秘密，即對這個群組的身份驗證成功，反之失敗。

但現(xiàn)用方案中，無論是Harn 等人[13]的方案，還是提出緊耦合秘密共享方案[15，18]本身，仍然存在信息率不為1的，效率低下的特點，具體如下：

（1）緊耦合秘密共享方案[15]是在Shamir秘密共享方案基礎(chǔ)上提出。其中秘密s是在Fq上，子份額是在Fp上，然而p、q滿足關(guān)系式p ＞q+nq2。方案的信息率在區(qū)間（1/3，1/2）之間。

（2）緊耦合秘密共享方案[18]是在傳統(tǒng)的基于整數(shù)環(huán)上的中國剩余定理的秘密共享基礎(chǔ)上提出。構(gòu)造條件十分復(fù)雜，其中秘密s是在Fp0上，子份額是在Fpi上，p0＜p1＜…＜pn滿足兩兩互素且任意i≠j存在gcd(pi,pj)=1，其中i,j∈{0,1,…,n}。方案的信息率小于1/3。

（3）Harn 等人[13]的方案，需要每人參與者擁有l(wèi)個子份額，其中kl ＞n-1。方案的信息率為1l。

將會面臨這樣的問題，有沒有什么方法，能夠構(gòu)造出理想型緊耦合秘密共享。

為了解決這個問題，本文主要是通過在基于有限域多項式環(huán)上的中國剩余定理的基礎(chǔ)上，構(gòu)造出理想型緊耦合的秘密共享。其克服了文獻[13，15，18]中存在的缺陷，主要具有以下幾個特點：

（1）在k(t≤k≤n)參與者參與恢復(fù)秘密的過程中，任意k-1 參與者無法獲取秘密s的任何信息。

（2）從信息率的角度來看，本方案信息率為1，是理想型秘密共享方案。

1 預(yù)備知識

1.1 門限秘密共享

一個門限秘密共享機制包括兩個階段，一個是子份額的分發(fā)過程Π，一個是恢復(fù)秘密的過程Π-1。假定一個秘密共享中，n個參與者的集合為{P1,P2,…,Pn}，秘密s的采樣空間為K，n個自份額對應(yīng)的采樣空間分別為K1,K2,…,Kn，秘密s對應(yīng)的n個參與者的子份額集合為{s1,s2,…,sn}。則分發(fā)過程可以描述為：

其中，映射Π:K→K1×K2×…×Kt。

恢復(fù)秘密的過程可以描述為：

其中，映射Π-1:K1×K2×…×Kt→K。

定義1（門限秘密共享）如果一個(t,n)門限秘密共享機制包含秘密分發(fā)過程和秘密恢復(fù)過程，且滿足以下特性，稱之為門限秘密共享。

（1）正確性

（2）完美隱私性

對于任意的參與者集合B={Pi1,Pi2,…,Pi|B|}且|B|＜t，存在一個秘密分發(fā)過程Π:K→K1×K2×…×Kt，使得對于任意給定的秘密s∈K，都有：

定義2（信息率）一個秘密共享機制的信息率定義為：

定義3（理想型秘密共享）一個秘密共享機制滿足信息率ρ=1，則秘密共享稱之為理想秘密共享方案。

理想型秘密共享為信息率最大的情況下的秘密共享，其可以理解成信息編碼中的編碼效率。Shamir秘密共享方案中，子份額和秘密的采樣空間都是有限域Fp。它也是典型的理想型秘密共享方案。

1.2 中國剩余定理（CRT）

引理（CRT）若表示任意環(huán)R上互素的理想，且則 存 在 同 構(gòu) 關(guān) 系R/I2×…×R/Ik。

上述引理是中國剩余定理在任意環(huán)上的一般形式。對于任意兩兩互素的理想，能夠高效地計算出一個“CRT基”。在上述引理中，即：對于任意且屬于一組CRT基。

從上述引理中的同構(gòu)關(guān)系中，任意給定的向量w=能夠在商環(huán)R/I上計算出唯一解

1.3 Ning等人的CRT門限秘密共享方案

Ning 等人方案[19]可以理解成Asmuth-Bloom 方案[1]在有限域多項式環(huán)上的推廣。

（1）初始化

假定n個參與者的集合為{P1,P2,…,Pn}，p為一個素數(shù)。尋找n個有限域Fp上d階首一不可約多項式，m1,m2,…,mn∈Fp[x]，秘密s是d-1階多項式，m0=xd。其中p和n+1 個d階多項式為公開信息。

（2）秘密分發(fā)

①可信第三方（dealer）構(gòu)造出多項式F=s+α·m0，其中α是有限域Fp上的隨機多項式，階滿足deg(α)=

（3）秘密恢復(fù)

①任意t個參與者參與恢復(fù)秘密，例如：集合{P1,P2,…,Pt} 。將模數(shù)m1,m2,…,mt和對應(yīng)的子份額{s1,s2,…,st}發(fā)送給秘密恢復(fù)者。

②秘密恢復(fù)者根據(jù)模數(shù)m1,m2,…,mt，計算出一組CRT基c1,c2,…,ct。并執(zhí)行計算再由計算出秘密s。

以上的秘密恢復(fù)過程可以看成使用中國剩余定理解以下的同余方程組：

2 方案構(gòu)造

本章主要介紹構(gòu)造的(t，k，n)緊耦合秘密共享方案，方案主要有三個過程構(gòu)成，初始化：選擇各種參數(shù)包括素數(shù)p和模數(shù)mi；秘密分發(fā)：根據(jù)n個同余方程，生成n子份額并分發(fā)給每個參與者；秘密恢復(fù)：使用中國剩余定理求解出最終秘密。

2.1 具體方案

（1）初始化

假定n個參與者的集合為{P1,P2,…,Pn}，p為一個素數(shù)。尋找n+1 個有限域Fp上d階首一不可約多項式，m0,m1,…,mn∈Fp[x]，秘密s是d-1 階多項式。其中p和n+1 個d階多項式m0,m1,…,mn∈Fp[x]為公開信息。

（2）秘密分發(fā)

①可信第三方（dealer）根據(jù)選定的秘密s構(gòu)造出多項式F=s+α·m0，其中α是有限域Fp上的隨機多項式，階滿足deg(α)≤(t-1)d-1。

②可信第三方由si=F(modmi)生成子份額{s1,s2,…,sn}，分發(fā)給每個參與者Pi（對應(yīng)模數(shù)為mi）。

（3）秘密恢復(fù)

①假定有k(k≥t) 個參與者恢復(fù)秘密，例如：{P1,P2,…,Pk}。它們的模數(shù)分別對應(yīng)m1,m2,…,mk，計算出一組CRT基為c1,c2,…,ck。

②參與者Pi計算出并發(fā)送給其余k-1 個參與者。式中ri是Fp上的均勻隨機分布的多項式，且滿足deg(ri)=(k-1)d-1。

計算出秘密s。

2.2 具體實例

以下實例以(2,k,3)緊耦合門限秘密共享為例，具體的構(gòu)造過程如下：

（1）初始化

選取素數(shù)p=17，參與者集合為{P1,P2,P3}，其對應(yīng)的多項式分別為m1=x2+9x+11，m2=x2+5x+5，m3=x2+13x+1。此外，m0=x2+3x+1。

（2）秘密分發(fā)

可信第三方選取秘密s=5x+7，構(gòu)造出F=s+α·m0=2x3+7x2+10x+8，其中α=2x+1。由si=Fmodmi分別計算出參與者P1,P2,P3對應(yīng)的子份額為s1=2x+10，s2=15x+6，s3=10。

（3）秘密恢復(fù)

假設(shè)現(xiàn)在3個參與者{P1,P2,P3}參與恢復(fù)秘密。由模數(shù)m1,m2,m3得到一組CRT 基c1,c2,c3。其中c1=13x5+5x4+14x3+2x2+15x+11，c2=12x5+5x4+15x3+16x2+7，c3=9x5+7x4+5x3+16x2+2x。再由每個參與者Pi分別計算出Mi=si·ci+ri·m0。分別如下：M1=9x6+7x5+7x4+2x3+x2+15x+9，M2=10x6+12x5+13x4+2x3+14x2+15x+7，M3=5x4+15x3+5x2+3x+11，其中隨機數(shù)r1=3x3+5x2+10x+1，r2=x3+10x2+15x+16，r3=12x3+x2+x+11。

3 方案分析

本章首先分析方案滿足正確性和緊耦合秘密共享的安全性，接著分析方案特性，即：該方案是信息率為1的理想型秘密共享。

3.1 正確性分析

定理1 在本文的方案中，任意給定k(k≥t)個M1,M2,…,Mk，存在一個多項式時間的算法通過CRT唯一確定秘密s。

證明在秘密恢復(fù)過程中：

由引理1可知：

因此：

定理得證。

3.2 安全性分析

只需要考慮最壞情況下，方案的安全性。即：當有k(t≤k≤n)個參與者恢復(fù)秘密的時候，在給定k-1 個Mi的情況下，無法獲取秘密s的任何信息。

定理2 在本文的方案中，給定任意的Mi,i∈{1,2,…,n}，無法獲取到關(guān)于子份額si的任何信息，即

證明已知，其中ri是Fp上的均勻隨機分布的多項式，且滿足deg(ri)=(k-1)d-1。式中CRT基ci滿足deg(ci)≤kd-1，秘密子份額si和公開多項式參數(shù)m0，分別滿足deg(si)=d-1和deg(m0)=d。

由上述階的大小關(guān)系，可以知道deg(ri)=(k-1)d-1，多項式ri具有(k-1)d個系數(shù)，采樣空間大小為。deg(si)=d-1，多項式秘密子份額si具有d個系數(shù)，采樣空間為pd。因為k≥t≥2，所以ri的采樣空間遠遠大于si的采樣空間。

命題得證。

定理3 假定k個參與者參與恢復(fù)秘密，任意給定k-1 個M1,M2,…,Mk-1，無法獲取關(guān)于秘密s的任何信息。存在：

證明已知Mi=si·ci+ri·m0，其中ri是Fp上的均勻隨機分布的多項式，且滿足deg(ri)≤(k-1)d-1。

由引理1可知，通過k-1 個Mi，計算出結(jié)果如下：

其中{c1,c2,…,ck}是模數(shù){m0,m1,…,mk}的CRT基。

則集合A為在知曉k-1 個Mi情況下，F(xiàn)′的采樣空間。集合B為秘密s的采樣空間，故：

命題得證。

由定理2可知，給定任意的Mi，無法獲得si的任何信息。由定理3可知，k個參與者參與恢復(fù)秘密的情況下，給定任意k-1 個Mi，無法獲得秘密s的任何信息。因此本文的方案是安全的。并且不依賴于任何的數(shù)學(xué)難題，屬于無條件安全。

3.3 方案特性分析

定理4 本文的方案是理想的門限秘密共享方案。

證明由本文的方案可知，秘密s和子份額si滿足deg(s)=deg(si)，采樣空間都為pd。因此信息率：

所以定理得證。

在這里，需要提醒的是子份額屬于每個參與者需要保密的信息。在本文的方案中，每個參與者持有的子份額就是si，但在實際恢復(fù)秘密過程中，每個參與者提供的是Mi。

在表1 中列舉了緊耦合秘密共享方案和相關(guān)方案的比較。

表1 相關(guān)方案的比較

4 結(jié)束語

本文主要對基于中國剩余定理的緊耦合秘密共享進行推廣，將CRT推廣到有限域的多項式環(huán)上，構(gòu)造出理想型緊耦合秘密共享方案。

下一步研究將會考慮如何將本方案和具體的應(yīng)用場景結(jié)合起來，構(gòu)造出認證協(xié)議等具體的應(yīng)用。