基于內P-集合理論的門限秘密共享方案

吳玉杰，于秀清，李 雄

（1.德州學院數學科學學院，山東德州253023；2.湖南科技大學計算機科學與工程學院，湖南湘潭411201）

基于內P-集合理論的門限秘密共享方案

吳玉杰1，于秀清1，李 雄2

（1.德州學院數學科學學院，山東德州253023；2.湖南科技大學計算機科學與工程學院，湖南湘潭411201）

為確保密鑰安全，防止密鑰丟失，基于離散對數難題和內P-集合理論，提出一種新的（n，t）門限秘密共享方案。該方案將共享密鑰先分成小塊，然后混入構造的集合中。在密鑰重構過程中，選取某個參與者作為密鑰恢復者，有至少t個參與者為密鑰恢復者提供秘密份額，通過構造單項映射和內P-集合的計算進行密鑰恢復。由參與者自己設定子秘密，秘密分發者與參與者之間不需要維護安全信道，從而減小通信負擔。實例分析結果表明，該方案實現簡單，具有較高的安全性。

門限秘密；秘密共享；離散對數；內P-集合；屬性集；單向映射

1 概述

秘密共享思想是把一個共享密鑰S分解成n個秘密份額，并由n個參與者保管，在需要共享密鑰時，由t個或t個以上參與者利用其秘密份額重構出共享密鑰，而少于t個參與者利用其秘密份額得不到共享密鑰的信息，t稱為秘密共享門限。門限秘密共享技術可以有效保護重要信息，以防信息丟失、被破壞或被篡改等。秘密共享是現代密碼學的一個重要組成部分，已被廣泛應用于網絡安全中。最早的秘密共享體制是由Sham ir［1］和Blakley［2］于1979年各自獨立提出的。Sham ir提出的Lagrange插值法通過構造一個有限域中的（t-1）次多項式，將共享的密鑰作為這個多項式的常數項，將共享密鑰分成n個秘密份額分別由n個參與者保管，t個或多于t個參與者合作提供他們的秘密份額，利用Lagrange插值法恢復出共享密鑰，少于t個參與者合作得不到關于共享密鑰S的任何信息。Blak ley提出的幾何方法把共享的密鑰S看成是t維空間中的一個點，把n個秘密份額中的每個方程作為包含這個點的一個（t-1）維超平面方程，通過求解任意t個超平面的交點來確定共享的密鑰S，少于t個的秘密份額不能確定其交點，從而得不到關于共享密鑰S的任何信息。此后，許多學者又提出了不同的秘密共享方案，如文獻［3-4］提出了基于中國剩余定理的秘密共享方案，文獻［5］提出了利用矩陣乘法實現的K-G-H秘密共享方案，文獻［6］提出了利用線性分組碼的秘密共享方案，文獻［7］提出了循環群上同態秘密共享方案等，文獻［8］提出了可驗證的多策略秘密共享方案，文獻［9］給出了動態門限密碼共享方案。目前，有很多學者還在這些方法的基礎上提出了許多不同的門限秘密方案［10-12］。

在2008年，史開泉［13］提出了P-集合理論，對普通集合理論進行了動態化的研究。當前，該理論在信息圖像生成、信息圖像隱匿-潛藏、有效識別、信息檢索等領域有著廣泛應用。本文利用內P-集合理論，提出一種新的門限秘密共享方案。該方案的子秘密由參與者設定，分發者通過公共信道只公布一個集合和一個映射，秘密的恢復主要利用內P集合理論，分發者與參與者只通過公共信道進行通信，不需要安全信道，且在多秘密分享過程中，對子塊的長度和個數沒有限制。

2 預備知識

2.1 離散對數問題

將離散對數難解性問題描述為選取一個足夠大的素數q，GF（q）是一個有限域，g是GF（q）的生成元：

（1）給出a∈GF（q），尋找唯一的整數χ，使得gχ=a mod q，該問題是難解的。

（2）給定2個元素gμ和gν，找出對應元素gμν，該問題是難解的。

（3）已知3個元素gμ，gν和gω，判定gω與gμν是否相等，該問題是難判斷的。

2.2 內P-集合理論

設U是有限元素論域，X是U上的有限非空集合，X?U；V是有限屬性論域，α是集合X的屬性集合，是元素遷移函數，是元素遷移族。

定義1 給定集合X=｛χ1，χ2，…，χq｝?U，α=｛α1，α2，…，αK｝?V是X的屬性集合，稱XFˉ是X生成的內P-集合，簡稱XFˉ是內P-集合，而且：

其中，X-稱作X的Fˉ-元素刪除集合，而且：

如果XˉF的屬性集合αF滿足：

其中，β∈V，β∈ˉα；f∈F把β變成f（β）=α′∈α；XFˉ≠φ。上式中XFˉ=｛χ1，χ2，…，χP｝，P≤q；P，q∈N+。

當不斷有外來屬性遷入屬性集合，會得到一個內P-集合串，即：

定義4 有限屬性論域V到P（U）上的單向映射為G，G（α）=X∈P（U），α∈V。

映射G滿足：由α易得G（α），但是由G（α）得不到屬性α。

3 本文方案

本文利用內P-集合理論提出（t，n）門限秘密共享方案。該方案假定有一個可信的秘密分發者D；n個參與者P=｛P1，P2，…，Pn｝；需要共享的密鑰是S；一個公告牌，用于存放公開信息。方案中的各方均可讀取公告牌上的內容，但只有秘密分發者才能更新公告牌上的內容。

3.1 系統初始化

分發者D執行下列步驟：

（1）隨機生成2個大素數P，q，滿足P=2P′+1，q=2q′+1，其中，P′，q′也是素數，計算N=Pq，R=P′q′，滿足攻擊者在知道N的情況下得到P，q在計算上是不可行的。D在有限域ZN中隨機選取一個階為R的元素g作為生成元。

（2）在ZN中選取K0，使得K0與P-1，q-1互素，計算f使得K0×f=1modφ（N），其中，φ（N）是歐拉函數。

（3）計算Y=gK0m od N。

（4）選取有限元素論域U=ZN，規定有限屬性論域V的元素為屬性值，不妨取V=ZN。

分發者D將f，g，Y，N公布在公告牌上，將P，q銷毀。

參與者執行的步驟如下：

每個參與者Pi在有限域ZR中隨機選取自己的秘密份額Ki，i=1，2，…，n，計算αi=gKim od N∈V作為其私鑰屬性由自己保存，計算Yi=YKimod N，通過公開信道傳送給分發者D，當i≠j時D要確保Yi≠Yj，否則D將要求參與者重新選取秘密份額，直到Yi，i=1，2，…，n互不相同為止。

3.2 構造階段介紹

3.2.1 集合選取

分發者D選取密鑰S∈ZN，把S分解成m個不同的子塊si，i=1，2，…，m，使得S=s1+s2+…+sm，

其中，m是保密的，記T*=｛s1，s2，…，sm｝作為內P-集合的核。選取互不相容的集合Tij?U，i=1，2，…，為保證少于門限t個參與者不能恢復出密鑰，選取一足夠大的數h，要求Tij中元素個數大于等于h。

3.2.2 集合構造

分發者D在n個參與者Pl，l=1，2，…，n中取t個參與者的組合，共計有種。若第i種組合為Pi1，Pi2，…，Pit，為這個組合中的第j個參與者Pij分配集合TiK，當K=j時，TiK=Φ（空集），K=1，2，…，t， i=1，2，…，若參與者Pij是n個參與者2，…，n中的第r個參與者Pr，然后把分配給參與者Pr的所有集合進行并運算得到Tr，計算Xr=Tr∪T*，其中，r=1，2，…，n，這樣可以保證t個或t個以上的集合的交集為核T*，構造集合3.2.3 單向映射構造

由冪集的定義，有Xr∈P（U），r=1，2，…，n。

分發者D計算：

定義5 有限屬性論域V到P（U）上的單向映射G：

其中，αr是Xr的屬性值。然后把集合X和映射G公布在公告牌上。

3.3 密鑰的恢復

在密鑰恢復時，需要至少t個參與者提交自己的秘密份額，參與者利用自己的秘密份額計算出私鑰屬性。密鑰恢復者（可以是任何人）需要收集足夠多私鑰屬性。

3.3.1 私鑰屬性提交

必須有不少于t個參與者參與密鑰恢復，如有t個參與者Pi1，Pi2，…，Pit做如下操作：利用自己的秘密份額計算出私鑰屬性αir=gKir，r=1，2，…，t，提交給密鑰恢復者。

3.3.2 提交者集合計算

密鑰恢復者運用公告牌上的映射G計算G（αir）=Xir，r=1，2，…，t。在這里映射G是單向的，可以保證即便破譯出了Xir中的部分元素構成的子集，也不能反向計算出αir，從而得不到完整的Xir。

3.3.3 密鑰計算

這里遷移函數沒有具體寫出，屬性遷移函數的作用就是某參與者提供了屬性元素αir，元素論域的遷移函數的作用就是把刪除集合X-中的元素遷移出去。于是得到內P-集合的核sm｝，計算S=s1+s2+…+sm，恢復出秘密S。

3.4 方案證明

在n個參與者中必須有不少于t個參與者參與秘密恢復，不妨設t個參與者為Pj1，Pj2，…，Pjt。

計算αji=gKji，G（αji）=Xji，i=1，2，…，t。

當i=2時：

當i=t時：

若少于t個參與者參與密鑰恢復，如有t-1個參與者參與密鑰恢復，不妨設為Pj1，Pj2，…，Pjt-1，只能恢復出Xj1∩Xj2∩…∩Xjt-1，而不能恢復出核T*，因此，本文方案是完備的。

4 安全性與性能分析

本文方案秘密份額是參與者自己選的，而且只要求保存自己的秘密份額。所以，具有很高的安全性。

4.1 安全性分析

4.1.1 參與者的私鑰屬性安全性分析

若某參與者想得到其他參與者的私鑰屬性，需由Yi=YKimod N得到αi=gKi，這需要解決Yi=YKi=（gK0）Ki去求αi=gKi，根據離散對數的難解性，不可能求解出結果，所以，私鑰屬性是安全的。

4.1.2 密鑰的安全性分析

密鑰的安全性分析具體如下：

（1）若某個參與者通過映射G得到Xr=Tr∪T*，要想從中得到核T*，從而得到密鑰，因為Xr中的元素不少于m+h，m是保密的，即要從m+h個元素中選出核中的m個元素，其概率小于只要選取的h足夠大就可以保證其安全性。

（2）因為要想得到核，進而得到秘密S，必須要有至少t個參與者提供其子集，通過求交集得到核。若有少于t個參與者想恢復出密鑰S，在求交集運算時不可能得到核，所得交集元素個數最少為m+ h個，若要破譯出密鑰S，其概率不會超過只要選取的h足夠大就可以保證其安全性，所以該方案是完備的。

4.2 性能分析

本文利用內P-集合理論提出一種新的方案，該方案與Sham ir提出方案不同之處是，Sham ir提出的方案是運用Lagrange插值法，而本文方案是利用集合的運算來實現秘密的恢復，方案計算復雜性和時間的復雜性還有待于研究，但是它有以下優點：

（1）秘密S分成的子塊只要求互不相同，對子塊的長度和個數沒有限制，甚至對秘密的類型沒有限制。

（2）本文方案公共參數只有一個集合和一個映射，公開的參數是極少的。

（3）參與者只保存自己選的秘密份額，不需要安全信道，所占空間少。

（4）本文方案與Sham ir方案的不同之處是：通過選取h的大小可控制密碼破譯的難度。而在新個體的加入、可驗證的門限秘密共享等不同方面的應用還有待于研究。

5 實例分析

若有3個參與者P1，P2，P3，n=3，門限t=2，密鑰分發與秘密恢復如下：

（1）分發者D隨機生成2個大素數P，q，滿足P=2P′+1，q=2q′+1，其中，P′，q′也是素數，計算N=Pq，R=P′q′，滿足攻擊者在知道N的情況下得到P，q在計算上是不可行的。D在有限域ZN中隨機選取一個階為R的元素g作為生成元。

（2）分發者D在ZN中選取K0，使得K0與P-1，q-1互素，計算f使得K0×f=1modφ（N），其中，φ（N）是歐拉函數。

（3）分發者D計算Y=gK0mod N，選取有限元素論域U=ZN，規定有限屬性論域V=ZN，分發者D將f，g，Y，N公布在公告牌上，銷毀P，q。

（4）每個參與者Pi在有限域ZR中隨機選取自己的秘密份額Ki，i=1，2，3，計算αi=gKimod N∈V作為其私鑰屬性由自己保存，計算Yi=YKimod N，通過公開信道傳送給分發者D，當i≠j時，D要確保Yi≠Yj，否則D將要求參與者重新選取秘密份額，直到Yi，i=1，2，3互不相同為止。

（5）分發者D選取密鑰S=11，把密鑰S分解成11=2+3+6，m=3，記T*=｛2，3，6｝作為內P-集合的核。選取互不相容的集合Tij?U，i=1，2，3；j=1，2，要求Tij中元素個數大于等于h。為容易說明問題，選取h=3，T11=｛1，2，3｝，T12=｛4，5，6｝，T21=｛7，8，9｝，T22=｛10，11，12｝，T31=｛13，14，15｝，T32=｛16，17，18｝，分發者D在3個參與者中取2個參與者的組合，共計有種。若i=1對應的組合為P1，P2，i=2對應的組合為P1，P3，i=3對應的組合為P2，P3。運用上述方法為參與者分配集合如圖1所示。

圖1 參與者分配集合

計算下列公式：

（6）構造單向映射。P（U）是有限元素論域U的冪集，則有Xr?P（U）。

G是有限屬性論域V到P（U）上的映射：

把集合X和映射G公布在公告牌上。

（7）在秘密恢復時，需要至少2個參與者提交自己的秘密份額。如2個參與者是P1，P2，對應的私鑰屬性分別為α1，α2，運用公告牌上的映射G計算G（αi）=Xi，i=1，2。

設XF為X的內P-集合，X-為X的XF-元素刪除集合，XF=X，秘密恢復者取參與者的私鑰屬性做以下運算：

1）當i=1時，α=α1，X-=XF-G（α）=X-X1，XF=XF-X-，得XF=X1=T12∪T22∪T*。

2）當i=2時，α=α2，X-=XF-X2=X1-X2，XF=XF-X-=X1-（X1-X2）=X2∩X1=（T11∪T32∪T*）∩（T12∪T22∪T*）=T*。

于是得XF=T*=｛2，3，6｝。

這樣構造出S=2+3+6=11。

若有少于2個參與者，如參與者P1想恢復出秘密S，其掌握的子集是：

X1=T12∪T22∪T*=｛2，3，4，5，6，10，11，12｝

里面元素的個數超過h=3，需要從中選出2，3，6，選中的概率為：

因此，只要元素的個數h選的足夠大，要想得到核是非常困難的，所以，該方案是完備的。

6 結束語

基于P-集合理論，本文提出一種新的秘密共享方案。該方案通過內P-集合理論構造了一個內P-集合和一個映射函數，參與者只要提供正確的秘密份額，通過內P-集合的運算就可以恢復出秘密。實例結果表明，只要分發者選取的集合中的元素個數足夠多，其破解的難度就足夠大，同時該方案不需要安全信道，秘密的分發只公布一個集合、一個單向映射，在秘密的恢復階段只運用集合運算。然而，在該方案中，分發者必須是可信的，不能防止分發者的欺騙，且不能檢測分發者與參與者、參與者與參與者之間的欺騙行為。因此，研究解決分發者與參與者的欺騙問題、新個體的加入問題是今后的研究方向。

［1］ Sham ir A.How to Share a Secret［J］.Communications of the ACM，1979，22（11）：612-613.

［2］ Blakley G.Safeguarding Cryptographic Keys［C］//Proceedings of AFIPS National Computer Conference. New York，USA：AFIPS Press，1979：313-317.

［3］ Mignotte M.How to Share a Secret［C］//Proceedings of Workshop on Cryptography.Berlin，Germany：Springer-Verlag，1983：371-375.

［4］ Asmuth C A，Bloom J.A Modular Approach to Key Safeguarding［J］.IEEE Transactions on Information Theory，1983，29（2）：208-210.

［5］ Karnin E D，Greene J W，Hellman M E.On Sharing Secret System s［J］.IEEE Transactions on Information Theory，1983，29（1）：35-41.

［6］ Bertilsson M，Ingemrsson I.A Construction of Practical Secret Sharing Schemes Using Linear Block Codes［C］// Proceedings of AUSCRYPT'92.Berlin，Germany：Springer-Verlag，1992：67-79.

［7］ 劉木蘭，周展飛.循環群上理想同態密鑰共享體制［J］.中國科學：E輯，1998，（6）：524-533.

［8］ 王 鋒，谷利澤，鄭世慧，等.可驗證的多策略秘密共享方案［J］.北京郵電大學學報，2010，33（6）：72-75.

［9］ 吳昊天，陳 越，譚鵬許，等.基于門限的組密鑰管理方案［J］.計算機工程，2013，39（3）：167-173.

［10］ 王 鋒，周由勝，谷利澤，等.一個群組驗證的多策略門限數字簽名方案［J］.計算機研究與發展，2012，49（3）：499-505.

［11］ 孫 華，王愛民，鄭雪峰.標準模型下可證安全的基于身份的門限環簽密方案［J］.計算機科學，2013，40（5）：131-135.

［12］ 付小晶，張國印，馬春光.一個改進的動態門限基于屬性簽名方案［J］.計算機科學，2013，40（7）：93-97.

［13］ 史開泉.P-集合［J］.山東大學學報：理學版，2008，43（11）：77-84.

編輯 劉 冰

Threshold Secret Sharing Scheme Based on Internal P-sets Theory

WU Yujie1，YU X iuqing1，LIX iong2
（1.College of Mathematical Sciences，Dezhou University，Dezhou 253023，China；2.School of Computer Science and Engineering，Hunan University of Science and Technology，Xiangtan 411201，China）

In order to protect secret，a new efficient（n，t）threshold secret sharing scheme is proposed based on discrete logarithm problem and the P-sets theory in this paper.In this scheme，the sharing secret is divided into small pieces and is mixed into the structural set，in the secret reconstruction，the sharing secret is reconstructed through Computing a map and the internal P-sets by more than t secret shares by a designated participant，and the computational complexity is very low. The secret shares are chosen by the participants themselves，so there is no secure channel between the secret dealer and participants and reduces the communication costs.Example results show that the proposed scheme has high security and is easy to implement.

threshold secret；secret sharing；discrete logarithm；internal P-sets；attribute set；one-way mapping

吳玉杰，于秀清，李 雄.基于內P-集合理論的門限秘密共享方案［J］.計算機工程，2015，41（9）：159-163.

英文引用格式：Wu Yujie，Yu Xiuqing，Li Xiong.Threshold Secret Sharing Scheme Based on Internal P-sets Theory［J］. Computer Engineering，2015，41（9）：159-163.

1000-3428（2015）09-0159-05

A

TP309

10.3969/j.issn.1000-3428.2015.09.029

國家自然科學基金青年基金資助項目（61300220）；山東省自然科學基金資助項目（ZR2010AL019）。

吳玉杰（1964-），男，副教授，主研方向：門限密碼學；于秀清，教授；李 雄，講師、博士。

2014-09-01

2014-11-08 E-m ail：w yj9030@163.com