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

白建峰，苗付友

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

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

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

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

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

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

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

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

（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)上的中國(guó)剩余定理的秘密共享基礎(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)個(gè)子份額，其中kl ＞n-1。方案的信息率為1l。

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

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

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

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

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

1.1 門限秘密共享

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

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

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

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

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

（1）正確性

（2）完美隱私性

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

定義2（信息率）一個(gè)秘密共享機(jī)制的信息率定義為：

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

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

1.2 中國(guó)剩余定理（CRT）

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

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

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

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

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

（1）初始化

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

（2）秘密分發(fā)

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

（3）秘密恢復(fù)

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

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

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

2 方案構(gòu)造

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

2.1 具體方案

（1）初始化

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

（2）秘密分發(fā)

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

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

（3）秘密恢復(fù)

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

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

計(jì)算出秘密s。

2.2 具體實(shí)例

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

（1）初始化

選取素?cái)?shù)p=17，參與者集合為{P1,P2,P3}，其對(duì)應(yīng)的多項(xià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分別計(jì)算出參與者P1,P2,P3對(duì)應(yīng)的子份額為s1=2x+10，s2=15x+6，s3=10。

（3）秘密恢復(fù)

假設(shè)現(xiàn)在3個(gè)參與者{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。再由每個(gè)參與者Pi分別計(jì)算出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，其中隨機(jī)數(shù)r1=3x3+5x2+10x+1，r2=x3+10x2+15x+16，r3=12x3+x2+x+11。

3 方案分析

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

3.1 正確性分析

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

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

由引理1可知：

因此：

定理得證。

3.2 安全性分析

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

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

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

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

命題得證。

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

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

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

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

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

命題得證。

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

3.3 方案特性分析

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

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

所以定理得證。

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

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

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

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

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

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