一類新的秘密共享方案安全性分析及其改進

莊鋒茂，胡慧丹，林昌露

（1.福建體育職業技術學院 公共基礎部，福建 福州 350003;2.福建師范大學 數學與信息學院，福建 福州 350117）

1979年，Shamir[1]利用拉格朗日插值多項式提出了（t，n）-門限的秘密共享方案.在該方案中，一個誠實的第三方將秘密拆分成n份共享,并將每一份共享秘密地分發給n位不同的參與者；其中，任意t個或大于t個參與者的合作能重構出秘密（正確性），而任意小于t個參與者的合作得不到關于秘密的任何消息（隱私性）.同年,Blakley[2]借助幾何的方法提出了不同的秘密共享方案.1983年，Mignotte[3]和Asmuth-Bloom[4]借助中國剩余定理提出了新的門限秘密共享方案.

為了豐富秘密共享方案，許多的學者利用不同的數學工具，如：二進制序列，格，二元對稱多項式，雙線性映射，等等，分別地提出了各種秘密共享方案[5-9]，以滿足不同的應用需求.2017年,Deepika和Sreekumar[10]基于格雷碼和異或運算提出了一類新的秘密共享方案.其中利用格雷碼技術實現秘密分發，而用異或運算實現安全的秘密重構.作者稱該方案無信息丟失且可應用于視覺密碼學中.顯然，參與者僅僅需要進行異或運算就能還原出秘密，與傳統的其他方案比較，該方按可大量地減少了參與者的計算量.通過詳細的安全性分析發現，該方案存在安全漏洞并給出了具體的攻擊方式，進而給出了一個改進的安全方案.在改進方案中，我們在共享生成階段添加了隨機值用以破壞共享之間的關聯性；通過一些公開值實現了方案的正確性.

1 預備知識

1.1 格雷碼

格雷碼是一類循環二進制單位距離碼，它是任意兩個相鄰的碼字只有一位二進制數不同的編碼,它與奇偶校驗碼同屬可靠性編碼.

1.2 異或運算

異或也叫半加運算，其運算法則相當于不帶進位的二進制加法，二進制下1表示真，0表示假，則異或的運算法則為：0⊕0=0，1⊕0=0⊕1=1，1⊕1=1.

1.3 二進制碼轉換成格雷碼

二進制碼轉換成格雷碼，其法則是保留二進制碼的最高位作為格雷碼的最高位，而次高位格雷碼為二進制碼的高位與次高位相異或，而格雷碼其余各位與次高位的求法類似.例如：

某二進制數為：Bn-1Bn-2…B2B1B0

其對應的格雷碼為：Gn-1Gn-2…G2G1G0

具體地，最高位保留Gn-1=Bn-1，其他各位數Gi=Bi+1⊕Bi，其中 i=0，1，…，n-2.

2 Deepika-Sreekumar的秘密共享方案

Deepika和Sreekumar[10]借助格雷碼與異或運算提出一類新的秘密共享方案，該方案不同于基于多項式的秘密共享方案和基于中國剩余定理的秘密共享方案.該方案利用簡單的異或運算實現了秘密的重構，這可大量地減低了每位參與用戶的計算量.本節主要簡要回顧Deepika-Sreekumar的秘密共享方案.具體地，Deepika和Sreekumar給出了該類型秘密共享方案的兩種構造：一種是（7,7）-門限秘密共享方案，即只有7個參與者都拿出他們的共享才能重構出秘密；另一種是（3,7）-門限秘密共享方案，即僅有三個特定的參與者就可還原秘密.這兩種情形的秘密共享方案的共享的生成算法是一樣的，但是它們的秘密恢復算法不一樣.具體步驟如下所示.

2.1 共享的生成算法

第一步：輸入主秘密S，將S轉化為二進制數.

第二步：將秘密S轉化成它所對應的格雷碼G.

第二步：計算共享S1，S1=G；將秘密S1轉化成它所對應的格雷碼G1.

第三步：計算共享S2，S2=G1；將秘密S2轉化成它所對應的格雷碼G2.

第四步：計算共享S3，S3=G2；將秘密S3轉化成它所對應的格雷碼G3.

第五步：計算共享S4，S4=G3；將秘密S4轉化成它所對應的格雷碼G4.

第六步：計算共享S5，S5=G4；將秘密S5轉化成它所對應的格雷碼G5.

第七步：計算共享S6，S6=G5；將秘密S6轉化成它所對應的格雷碼G6.

第八步：計算共享S7，S7=G6

第九步：將二進制 S1，S2，S3，S4，S5，S6，S7轉化為十進，輸出十進制的 7 個共享 S1，S2，S3，S4，S5，S6，S7，并秘密地分發給7位不同的參與者.

2.2 （3，7）-門限秘密共享方案的重構算法

1）第一階段

第一步：輸入 S1，S2，S3，S4，S5，S6，S7.

第二步：判定共享的下標i是否整除2；如果i-2=0，則Si是授權集里的共享；否則Si不是授權集里的共享.

第三步：輸出共享 S2，S4，S6.

2）第二階段

第一步：輸入 S2，S4，S6,并將 S2，S4，S6轉化為二進制數.

第二步：計算S2⊕S4⊕S6.

第三步：將M轉化為十進制數.

第四步：輸出秘密S=M.

2.3 （7，7）-門限秘密共享方案的重構算法

第一步：輸入 S1，S2，S3，S4，S5，S6，S7，并將 S1，S2，S3，S4，S5，S6，S7轉化為二進制數.

第二步：計算 S1⊕S2⊕S3⊕S4⊕S5⊕S6⊕S7=M.

第三步：將M轉化為十進制數.

第四步：輸出秘密S=M.

3 安全漏洞分析

本節將通過具體實例來闡述Deepika和Sreekumar提出的兩種情形的門限秘密共享方案存在嚴重的安全漏洞.將指出它們無法滿足門限秘密共享方案的最基本的隱私性與正確性要求.不失一般性,假設秘密S=860，通過執行“共享的生成算法”得到秘密S的二進制形式S=1101011100，以及7個共享：S1=1011110010，S2=1110011011，S3=1001010110，S4=1101111101，S5=1011010011，S6=1110111010，S7=1001110111.

3.1 隱私性分析

將分析 Deepika 和 Sreekumar設計的 （3，7）-門限秘密共享方案與（7，7）-門限秘密共享方案均無法確保其隱私性：1）每個參與者利用所持有的一個共享都可以恢復秘密；2）參與者能獲得其他參與者的共享.

3.1.1 參與者P1利用S1得到秘密S

參與者P1可通過執行以下的兩個步驟成功地獲得秘密.

第一步：P1可以得到S的格雷碼G=S1=1011110010.

第二步：設 S=B9B8B7B6B5B4B3B2B1B0，G=G9G8G7G6G5G4G3G2G1G0,其中 B9=G9=1,B8=B9⊕G8=1⊕0=1，B7=B8⊕G7=1⊕1=0，B6=B7⊕G6=0⊕1=1，B5=B6⊕G5=1⊕1=0，B4=B5⊕G4=0⊕1=1，B3=B4⊕G3=1⊕0=1，B2=B3⊕G2=1⊕0=1，B1=B2⊕G1=1⊕1=0，B0=B1⊕G0=0⊕0=0， 易知，參

與者P1通過以上計算可獲得秘密S.

3.1.2 參與者Pi獲得其他參與者Pj的共享

參與者Pii=（2,3,…,7）不僅能得到秘密S，還能得到其他參與者Pj（j＜i）的共享.具體地，參與者 Pii=（2,3,…,7）通過以下的步驟成功地獲得其他參與者Pj（j＜i）的共享，且可恢復出秘密.

第一步：Pi可以獲得Pi-1的共享Si-1的格雷碼Gi-1=Si.

第三步：Pi重復的執行i-1次步驟1,2即可得到Si-2,Si-3,…,S1,S，并可正確地恢復出秘密S.

3.2 正確性分析

本節僅對Deepika和Sreekumar提出的 （3,7）-門限秘密共享方案不滿足正確性要求給出詳細的分析.即該方案不滿足任意3個或大于3個參與者能正確地恢復秘密；小于3個參與者無法還原秘密.由于（7,7）-門限秘密共享方案中7個參與者全部參與能還原出秘密，因此 Deepika和 Sreekumar提出的（7,7）-門限秘密共享方案滿足正確性.通過以下例子說明（3,7）-門限秘密共享存在的缺陷，具體步驟如下所示：

設參與者P1,P2,P3去重構秘密，參與者P1,P2,P3利用所得到的三個共享S1=1011110010，S2=1110011011，和S3=1001010110進行異或運算去還原秘密.首先對S1和S2進行異或運算得結果m1=S1⊕S2=1011110010⊕1110011011=0101101001，然后再將m1和S3進行異或運算得到結果m2=m1⊕S3=0101101001⊕1001010110=11001111111.我們發現通過共享，S1,S2和S3所得到的結果m2≠S.具體的重構秘密的運算過程如下所示.

設參與者P1,P2,P4,P6去重構秘密,參與者P1,P2,P4,P6利用所得到的四個共享 S1=1011110010，S2=1110011011，S4=1101111101 和 S6=1110111010 執行重構算法去還原秘密.首先需要對S1=1011110010和S2=1110011011執行異或運算得到結果m3=S1⊕S2=0101101001，然后再對 m3=101101001和S4=1101111101執行異或運算得到結果 m4=m3⊕S4=1000010100，最后計算 m4⊕S6得到結果 m6=0110101110.我們發現通過共享 S1，S2，S4和 S6所得到的結果m5≠S.具體的運算過程如下所示.

通過以上的兩個例子說明Deepika和Sreekumar所提出的（3,7）-門限秘密共享方案無法滿足任意的三個或大于三個參與者都能還原出真正的秘密這個性質.

4 方案改進

本節將改進Deepika和Sreekumar的秘密共享方案，僅對提出（3,7）-門限秘密共享方案的給出具體的改進.在改進的方案中，在重構階段也僅只需要做異或運算，且滿足正確性和隱私性.該改進方案的共享生成算法和秘密恢復算法分別描述如下.

4.1 共享生成算法

第一步：可信第三方執行第2.1節中“生成算法”過程中將秘密 S 生成 7 個偽共享 S1，S2，S3，S4，S5，S6，S7.

第二步：第三方任意的選擇7個隨機值K1，K2，K3，K4，K5，K6，K7, 將 K1， K2，K3，K4，K5，K6，K7, 轉化為二進制數,再計算共享 Y1=S1⊕K1，Y2=S2⊕K2，Y3=S3⊕K3，Y4=S4⊕K4，Y5=S5⊕K5，Y6=S6⊕K6，Y7=S7⊕K7.

第三步：第三方計算公開值Ai1i2i3.具體地，Ai1i2i3=Yi1⊕Yi2⊕Yi3⊕S，其中這里 S 為秘密且｛i1,i2,i3｝是{1,2,…,7}的任意3元子集，公開哈希值H（S），其中H為安全的哈希函數.

第四步： 第三方通過安全的信道將 Y1，Y2，Y3，Y4，Y5，Y6，Y7傳輸給參與者 U1，U2，U3，U4，U5，U6，U7.

4.2 秘密重構算法

假設任意三位參與者Ui1,Ui2,Ui3重構秘密S,利用公開值Ai1i2i3和三個共享Yi1,Yi2,Yi3即可計算秘密.

5 安全性分析

本節將通過兩個定理來論證改進的秘密共享方案滿足正確性和隱私性要求.

定理 1（正確性）：在改進方案中，任意3個或大于3個的參與者利用手中的共享執行秘密重構算法可以重構出正確的秘密.

定理2（隱私性）：在改進的方案中，小于3個參與者利用手中的共享執行秘密重構算法無法恢復秘密.

證明：不失一般性，假定參與者U1,U2擬重構秘密S.由于參與者U1,U2只有共享Y1,Y2但沒有公開值A1,2，因此參與者無法利用公開值A1,2執行秘密重構算法，這使得秘密重構算法無法正確的計算Y1⊕Y2⊕A1,2并恢復正確的秘密.此外，參與者U1或U2各自均無法通過公開值或自己的共享份額計算得到其他參與者的共享.其原因是，他們各自的共享中包含了一個隨機值，即Y1=S1⊕K1和Y2=S2⊕K2中分別含有隨機值K1和K2，且這隨機值只有分發者知道，而任何一個參與者不僅不知道與自己共享相關的隨機值，而且無法預測得到與其他參與者相關的那個隨機值的任何信息.

6 總結

本文對Deepika和Sreekumar所提出的兩種秘密共享方案給出了具體的安全性分析.分析結果表明：他們所提出的方案中每個參與者僅僅通過自己的共享可以還原秘密，同時還能得到其他參與者的共享，即無法達到隱私性.同時通過兩個具體的例子說明他們設計的（3,7）-門限的秘密共享方案無法保證正確性.最后，本文對（3,7）-門限的秘密共享方案給出了的一種改進的方案，并確保了改進的方案能達到秘密共享的隱私性及正確性.