彭 詠,邵培南,李 翔,白建峰,孟珂舉

1(中國(guó)電子科技集團(tuán)公司第三十二研究所,上海 201808)

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

1 概述

秘密共享最早由Shamir[1]和Blakley[2]與1979年提出.秘密共享方案中存在一個(gè)可信的秘密持有者去分離一個(gè)秘密到多個(gè)不同的子份額.秘密持有者需要將子份額分發(fā)給多個(gè)子份額持有者.當(dāng)秘密恢復(fù)時(shí),子份額持有者互相交換子份額用于恢復(fù)秘密.為了避免子份額的持有者收到錯(cuò)誤的子份額,可驗(yàn)證秘密共享允許子份額持有者去驗(yàn)證自己收到的子份額.后來(lái)的可驗(yàn)證秘密共享方案拓寬了原始的概念,使得可驗(yàn)證體現(xiàn)在以下兩個(gè)方面:

1)秘密分發(fā)過(guò)程中,子份額持有者驗(yàn)證從秘密持有者獲得子份額的完整性和正確性.

2)秘密恢復(fù)過(guò)程中,秘密恢復(fù)者驗(yàn)證從其他子份額持有者那獲得的子份額的正確性和完整性.

秘密共享自提出之后就得到了廣泛關(guān)注,并成為眾多論文的研究熱點(diǎn)[3–8].此外,可驗(yàn)證秘密共享是密碼學(xué)方向中的一個(gè)重要領(lǐng)域.最早的方案是由文獻(xiàn)[9]提出,用以抵抗非法參與者欺騙攻擊來(lái)提高秘密共享方案的安全性.隨后,文獻(xiàn)[10]提出基于文獻(xiàn)[1]的非交互式的可驗(yàn)證秘密共享方案.該方案利用離散對(duì)數(shù)的同態(tài)性去完成認(rèn)證.其安全性是基于離散對(duì)數(shù)的計(jì)算難題假設(shè).文獻(xiàn)[11]總結(jié)并提出了一種公開(kāi)秘密共享方案,在其中有一種特別的屬性.任何一位參與者都允許檢查自己收到子份額是不是正確的.

從方案設(shè)計(jì)角度來(lái)看,已經(jīng)有很多種秘密共享方案被提出.大致可以分為兩類.

第一類,通過(guò)通信來(lái)完成子份額的驗(yàn)證.大多數(shù)該類方案主要采用雙變量多項(xiàng)式,該類方案主要問(wèn)題在于,過(guò)多的通信導(dǎo)致驗(yàn)證低效.比如,當(dāng)n個(gè)人參與恢復(fù)秘密時(shí),我們需要兩兩驗(yàn)證子份額的合法性,總共需要進(jìn)行輪通信.此外,在雙變量多項(xiàng)式的秘密方案中,每個(gè)子份額是一個(gè)多項(xiàng)式.該類的秘密共享本身從信息率角度來(lái)看,即秘密和子份額信息熵的比值,是低效的.它的信息率是該子份額多項(xiàng)式維度的倒數(shù).針對(duì)這其中的問(wèn)題,后來(lái)的研究者主要研究如何能夠降低通信復(fù)雜度.文獻(xiàn)[12,13]已經(jīng)展示了如果一個(gè)可被忽略的錯(cuò)誤概率被允許的話,過(guò)去的通信復(fù)雜度邊界不再適用.文獻(xiàn)[14]在一個(gè)可忽略的錯(cuò)誤概率被允許的情況下,給出了確切的通信輪復(fù)雜度.

第二類,采用數(shù)學(xué)難題來(lái)保證驗(yàn)證的安全性和有效性.很多該類可驗(yàn)證秘密共享方案,如著名的Feldman[10]和Pedersen[15]都是基于離散對(duì)數(shù)難題的.該類的方案主要特點(diǎn),利用公開(kāi)的參數(shù)信息進(jìn)行驗(yàn)證,可以做到非交互式的驗(yàn)證.然而針對(duì)離散對(duì)數(shù)問(wèn)題和大數(shù)分解難題,文獻(xiàn)[16]中Shor給出了一個(gè)高效的量子算法.雖然Pedersen[15]更是在Feldman[10]的基礎(chǔ)上,提出了無(wú)條件安全的可驗(yàn)證秘密共享方案,即安全性不依賴于數(shù)學(xué)難題.即使離散對(duì)數(shù)能被解決,也能保證子份額的安全性.但一旦出現(xiàn)這種情況,雖然能保證子份額的安全性,但方案將無(wú)法保持有效性,驗(yàn)證的過(guò)程可被任意偽造,方案不再有效.

因此,為了應(yīng)對(duì)可能存在的量子計(jì)算機(jī),保證方案的有效性,我們需要設(shè)計(jì)出一種可以抵抗量子攻擊的新型無(wú)條件安全的可驗(yàn)證秘密共享方案.

本論文組織結(jié)構(gòu)如下.在第2節(jié),我們回顧一些基礎(chǔ)的定義,概念和定理.在第3節(jié),提出具體的可驗(yàn)證秘密共享方案并描述如何進(jìn)行子份額的驗(yàn)證.在第4節(jié),分析方案的效率安全性,比較其他的方案.在結(jié)束語(yǔ)中做出全文的總結(jié).

2 基礎(chǔ)知識(shí)

2.1 秘密共享

定義1.訪問(wèn)結(jié)構(gòu)

使{p1,···,pn}代表所有參與者的集合.一個(gè)集合A?2{p1,···,pn}是單調(diào)的如果滿足B∈A 并且B?C,則C?A .一個(gè)訪問(wèn)結(jié)構(gòu)A ?2{p1,···,pn}是集合{p1,···,pn}的非空子集.A中的集合為授權(quán)集而任何不在A 均為非授權(quán)集合.則A 是該秘密共享方案的訪問(wèn)結(jié)構(gòu).

定義2.秘密共享[17]

假定K是秘密s的有限集合.一個(gè)分發(fā)方案∏ 和集合K實(shí)現(xiàn)訪問(wèn)結(jié)構(gòu) A 在滿足下列條件下稱之為秘密共享.

正確性:任意在A 中授權(quán)集合可以恢復(fù)秘密.

隱私性:任意不在A 中的非授權(quán)集不能得到關(guān)于秘密的任何信息.

2.2 格

格[18]是m維歐式空間Zm的n個(gè)線性無(wú)關(guān)向量組b1,b2,···,bn的整系數(shù)線性組合,即:

向量組 b1,b2,···,bn稱為格的一組基.同一個(gè)格可以用不同的格基表示.m稱為格的維數(shù),n稱為格的秩.有了格的定義,下面我們將簡(jiǎn)單介紹格上常見(jiàn)的數(shù)學(xué)難題,如:最短向量問(wèn)題,γ-近似最短向量問(wèn)題(SVPγ),最短線性無(wú)關(guān)向量問(wèn)題.這些數(shù)學(xué)難題,已被用于構(gòu)造基于格的公私鑰密碼方案.

最短向量問(wèn)題(Shortest Vector Problem,SVP):給定格 L,找一個(gè)非零格向量v,滿足對(duì)任意非零向量u∈L,∥ v∥≤∥u∥.

γ-近似最短向量問(wèn)題(SVP-γ ):給定格L ,找一個(gè)非零格向量v,滿足對(duì)任意格中的非零向量u ∈L,∥v∥≤γ∥u∥.

最短線性無(wú)關(guān)向量問(wèn)題(Shortest Independent Vector Problem,SIVP):給定一個(gè)秩為n的 格L,找n個(gè)線性無(wú)關(guān)的格向量si,滿足λi(L)=∥si∥,(i=1,···,n).其中λi(L)表示格L中第i個(gè)逐次最小的向量.

2.3 Ajtai單向函數(shù)[19]

選定適合的整數(shù)q,n,m滿足條件m>nlogq,q=poly(n).令A(yù) ∈Znq×m為n×m的矩陣,矩陣中的元素均在 Zq上 .該矩陣包含m個(gè) 均勻隨機(jī)的向量ai∈Znq,記為A=[a1|···|am],其中{a1,···,am}相互線性無(wú)關(guān).

給定函數(shù)FA(x)=Ax(modq),x∈{0,1}m,反向計(jì)算出原像x的概率是可忽略的,其中,{ 0,1}m表示一個(gè)m位的0,1字符串.

上述單向函數(shù)的構(gòu)造十分簡(jiǎn)單,且計(jì)算十分高效,他的安全性依賴于格難題.根據(jù)Ajtai文章[19]中結(jié)論,我們有如下引理.

引理1.如果格上的近似最短向量問(wèn)題(SVP)和近似最短線性無(wú)關(guān)向量問(wèn)題 (SIVP)是多項(xiàng)式時(shí)間不可解的,對(duì)于m>nlogq,q=poly(n),FA(x)是單向函數(shù).

3 方案構(gòu)造

本節(jié)介紹我們提出的可驗(yàn)證秘密共享方案.該方案示基于Shamir的(t,n)秘密共享,并且具有高效和抵抗量子攻擊的特性.

3.1 符號(hào)

首先,定義Fp作為在素?cái)?shù)p上的數(shù)域.Pi表示第i個(gè)參與者,si表示Pi用于恢復(fù)秘密的子份額并且si∈Fp.我們使用⊕ 代表異或運(yùn)算.此外,用A ∈Znq×m表示一個(gè)由n個(gè)m維 線性無(wú)關(guān)向量組成的矩陣,其中n,m和q滿足最后,記FA(x)等于Axmodq,其中x∈{0,1}m.

3.2 可驗(yàn)證秘密共享方案

該方案由以下3個(gè)步驟組成:初始化階段,子份額分發(fā)階段和秘密恢復(fù)階段.

初始化階段:

秘密持有者在Fp上 隨機(jī)生成一個(gè)t?1 階的多項(xiàng)式f(x):

其中,秘密s即為多項(xiàng)式的常數(shù)項(xiàng).也就是說(shuō),s=a0.此外,秘密持有者選擇 整 數(shù)n,m和q滿足m>nlogq,q=這里我們可以將Fp上的一個(gè)元素看成一個(gè)m比特的二進(jìn)制字符串.最后生成m個(gè)線性無(wú)關(guān)的向量αi∈Znq,記為A :=[α1|···|αm].

分發(fā)階段:

(1)秘密持有者計(jì)算si=f(xi)并且隨機(jī)從{ 0,1}m中選擇ti,將(si,ti)一 起發(fā)送給子份額持有者Pi.注意到如果sisj且titj,那么si⊕ti一定不等于si⊕tj.

(2)秘密持有者公開(kāi)矩陣A,FA(si⊕ti)和s′i的值,其中s′i=si⊕ti.

(3)子份額持有者Pi收到(si,ti)后,首先要對(duì)自己接收到的子份額進(jìn)行驗(yàn)證:

如果驗(yàn)證所得到的子份額是正確的,那么繼續(xù)以下的驟,如果驗(yàn)證失敗,則要求秘密持有者重新發(fā)送子份額.

秘密恢復(fù)階段:

假設(shè)有k個(gè)子份額持有者參與恢復(fù)秘密s,其中k≥t,他們需要執(zhí)行以下步驟:

(1)子份額持有者之間互相驗(yàn)證對(duì)方子份額的合法性,具體操作如下:

如果驗(yàn)證正確,則繼續(xù)下邊的步驟.否則,我們可以通過(guò)以下操作檢查每個(gè)參與者的身份從而確定哪個(gè)是非法的參與者.

(2)參與秘密恢復(fù)的子份額持有者互相交換信息si并用所得到這些子份額采用Shamir秘密共享的方式去恢復(fù)秘密.

為證明驗(yàn)證秘密恢復(fù)階段步驟(1)的正確性,我們給出定理1.

定理1.單向函數(shù)FA具有線性同態(tài)的特性,并且滿足以下公式:

證明:假設(shè)有k個(gè)子份額持有者組成的授權(quán)集合,他們的子份額構(gòu)成Γ ={s1,···,sk}.每個(gè)Γ 中的si均綁定一個(gè)對(duì)應(yīng)的隨機(jī)值ti,所有的si和ti都 是從{ 0,1}m中選取的.使用 A∈Znq×m表示一個(gè)由n個(gè)m維線性無(wú)關(guān)向量組成的矩陣,也就是說(shuō)A :=[α1|···|αm].那么有:

此外,因?yàn)?(si⊕ti)仍然是一個(gè)m比特位的二進(jìn)制字符串,可以被寫為因此,上述公式等于:

因此,函數(shù)FA有線性同態(tài)性并且該定理成立.

4 分析

在本節(jié),我們分析提出方案的效率以及安全性.事實(shí)上,我們的方案就是將Ajtai單向函數(shù)函數(shù)應(yīng)用到Shamir方案中,同時(shí)引入隨機(jī)變量ti,使得可驗(yàn)證方案是無(wú)條件安全的.即使最終格難題被破解,也無(wú)法獲得關(guān)于子份額的任何信息.當(dāng)然方案的有效性仍然依賴于格難題.

4.1 效率分析

首先,我們需要考慮方案的信息率.信息率是作為衡量一個(gè)秘密共享系統(tǒng)的重要手段,被廣泛用于衡量秘密共享方案本身的效率.信息率 σ 被定義為秘密長(zhǎng)度與最大子份額長(zhǎng)度的比值,也就是說(shuō):

在我們的方案中,因?yàn)樽臃蓊~不僅僅是單獨(dú)的si,而是一對(duì)值(si,ti).因此,該方案的信息率為1/2而不是1.此外,還有以下一些指標(biāo)用于衡量可驗(yàn)證秘密共享方案的效率:

(1)驗(yàn)證子份額時(shí)所要通信的輪數(shù).

(2)子份額持有者用于驗(yàn)證子份額合法性所需的通信數(shù)據(jù)量.

(3)子份額持有者驗(yàn)證子份額合法性所要做出的運(yùn)算量.

指標(biāo)(1)和(2)用于衡量通信的效率,也是大多數(shù)分析通信協(xié)議通信復(fù)雜度的指標(biāo).指標(biāo)(3)用于衡量計(jì)算的效率.

可驗(yàn)證秘密共享的輪數(shù)復(fù)雜度主要是在實(shí)際方案設(shè)計(jì)中需要考慮的.通信輪數(shù)相較于通信量來(lái)言,往往需要更多的時(shí)間.因此,在實(shí)際的通信協(xié)議中往往作為重要因素被考量.我們的方案類似于方案[9,16],是非交互式的可驗(yàn)證秘密共享,在分發(fā)階段,并不需要在驗(yàn)證時(shí)額外交互信息.在秘密恢復(fù)時(shí),僅僅只需要將自己的驗(yàn)證信息廣播出去即可,所以不會(huì)提高通信輪數(shù),通信的輪數(shù)復(fù)雜度可被忽略.

子份額持有者用于驗(yàn)證子份額合法性所需的比特?cái)?shù)可以被分為以下兩部分:秘密持有者分發(fā)的信息和子份額持有者之間互相交互的信息.第一部分與其它可驗(yàn)證秘密共享方案差別較大而后一部分和其它可秘密共享方案大致相同,因此我們主要分析第一部分的信息量.在我們的方案中,秘密持有者需要公開(kāi)一個(gè)矩陣A ∈Znq×m和FA(si⊕ti)的值.它總共包含的比特?cái)?shù)如下:

在本文中,計(jì)算開(kāi)銷是可以預(yù)估的.為了更好的說(shuō)明,我們比較我們的方案與其它3篇基于Shamir秘密共享的可驗(yàn)證秘密共享方案.假設(shè)所有的秘密和子份額的空間都是在Fp,我們將Fp上一次乘法運(yùn)算記為1次運(yùn)算.

我們只在此比較子份額持有者用于驗(yàn)證其它子份額合法性所需要的計(jì)算量.在我們的方案中,子份額持有者僅僅需要在很小的整數(shù)中進(jìn)行線性運(yùn)算.總共所需要在Zq中 執(zhí)行nlogp乘 法運(yùn)算,其中l(wèi) ogp>nlogq.為了方便比較計(jì)算復(fù)雜度,我們通過(guò)除以 2n將我們的結(jié)果從Zq轉(zhuǎn)化到Zq.

下面我們將從通訊量,計(jì)算量和適用性3個(gè)方面,比較本文方案和以往方案.通訊量是秘密恢復(fù)階段,每個(gè)參與者需要廣播多少比特的驗(yàn)證信息.計(jì)算量是每個(gè)在于者在最壞情況的計(jì)算復(fù)雜度來(lái)表示.比較結(jié)果如表1所示.

在表1中,Schoenmakers的方案[20]取決于公鑰密碼,所以無(wú)法進(jìn)行評(píng)估.此外,我們使用“普適”去代表我們方案的適用性.它代表我們的方案可以應(yīng)用于任何的方式構(gòu)造的秘密共享方案中,例如基于拉格朗日插值多項(xiàng)式,基于中國(guó)剩余定理,基于超平面空間,基于線性碼等密碼共享方案.顯然,我們的方案相對(duì)于其它可驗(yàn)證秘密共享方案具有更好的計(jì)算效率.

表1 本方案與已有方案的性能比較

4.2 安全性分析

我們的方案是基于Shamir秘密共享,所以任何授權(quán)集合都應(yīng)該能夠恢復(fù)秘密而任何的非授權(quán)集合都不應(yīng)該能恢復(fù)秘密.此外,我們還需要考慮驗(yàn)證過(guò)程的安全性,也就是說(shuō)子份額持有者在驗(yàn)證子份額合法性時(shí)是否泄漏了秘密.

定理2.本文方案的驗(yàn)證機(jī)制,包括分發(fā)和秘密恢復(fù)過(guò)程,基于Ajtai單向函數(shù),滿足不可區(qū)分和不可偽造特性.

證明:在我們的方案中,si⊕ti滿足均勻隨機(jī)分布.此外,Ajtai單向函數(shù)FA(si⊕ti)是均勻隨機(jī)分布.我們不能夠區(qū)分所以該驗(yàn)證機(jī)制滿足不可區(qū)分的特性.

為了證明綁定特性,我們需要證明不存在 概率多項(xiàng)式時(shí)間的算法去找到兩個(gè)不同的si.也就是說(shuō),不存在 概率多項(xiàng)式時(shí)間的算法去找到sisj∈{0,(1}m使)得Asi≡Asj(modq).如果我們找得到,那么存在0(modq).因?yàn)閟isj∈{0,1}m,我們有構(gòu)成了一個(gè)針對(duì)格難題中小整數(shù)問(wèn)題的一個(gè)解法,而小整數(shù)問(wèn)題被認(rèn)為是一個(gè)不可解的數(shù)學(xué)難題.因此,本方案中驗(yàn)證機(jī)制滿足不可偽造性.

我們已經(jīng)證明了我們方案的驗(yàn)證機(jī)制滿足不可區(qū)分和不可偽造兩個(gè)特性.不可區(qū)分特性意味著方案的驗(yàn)證過(guò)程不會(huì)泄露秘密的任何信息.不可偽造特性意味著只有正確的子份額才能通過(guò)驗(yàn)證.在上述證明過(guò)程中,不可區(qū)分和不可偽造均是依賴于格難題.

定理3.即使Ajtai單項(xiàng)函數(shù)被破解,驗(yàn)證子份額的過(guò)程也不會(huì)泄露任何秘密的信息.

證明:根據(jù)引理1,我們知道Ajtai單項(xiàng)函數(shù)可以被約簡(jiǎn)為格難題中的近似最短線性無(wú)關(guān)向量問(wèn)題.至今還沒(méi)有任何多項(xiàng)式時(shí)間的算法去解決近似最短線性無(wú)關(guān)向量問(wèn)題.假設(shè)近似最短獨(dú)立向量問(wèn)題和Ajtai單項(xiàng)函數(shù)都被破解,攻擊者可以從FA(si⊕ti)得 到值si⊕ti.因?yàn)閠i是 在子份額空間中的隨機(jī)值,所以si⊕ti是隨機(jī)分布在子份額空間的,從而我們無(wú)法從si⊕ti得到任何秘密的信息.這就表明了,即使Ajtai單項(xiàng)函數(shù)被破解,驗(yàn)證子份額的過(guò)程也不會(huì)泄露任何秘密的信息.

通過(guò)以上證明,我們得到我們的方案是無(wú)條件安全的.換言之,格難題保證了可驗(yàn)證的有效性,即使格難題被破解,我們的方案依舊不會(huì)泄露子份額的任何信息.即本方案的驗(yàn)證機(jī)制是無(wú)條件安全的.

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

我們?cè)诒疚恼故玖嘶诟竦目沈?yàn)證秘密共享方案,能夠在秘密分發(fā)和恢復(fù)過(guò)程中,驗(yàn)證子份額的合法性.同時(shí)該方案具備無(wú)條件安全的特性,即使格難題被其他什么未知工具破解,也能保證子份額的安全性.

本方案通過(guò)與已有方案的比較,我們的方案具有以下特性:更高的效率;量子攻擊抵抗性;普適性(可以應(yīng)用于任何數(shù)學(xué)工具實(shí)現(xiàn)的秘密共享方案).