宋海龍，王偉平

?

基于精確再生碼的秘密共享方案

宋海龍1, 2，王偉平1

(1. 中南大學信息科學與工程學院，湖南長沙，410083；2. 吉首大學信息科學與工程學院，湖南吉首，416000)

為解決云存儲系統(tǒng)中數據安全性問題，利用精確再生碼構造一種新的(，)門限秘密共享方案。方案由子秘密的分發(fā)、原始秘密的恢復和子秘密丟失者的數據重建共3種算法組成。子秘密的分發(fā)就是將原始秘密先進行分塊，再進行糾刪編碼，最后按一定的規(guī)則將編碼后的數據塊分發(fā)給個分享者。選取個分享者提供的數據塊，按糾刪碼的譯碼算法恢復原始秘密。選取個以上分享者的數據塊，按精確再生碼的譯碼算法重建出子秘密丟失者的數據。研究結果表明：訪方案是一種信息論安全的門限體制，與傳統(tǒng)的基于Lagrange多項式插值算法的秘密共享方案相比，具有運算復雜性低、節(jié)點存儲量小、丟失子秘密易再生等優(yōu)點。

再生碼；糾刪碼；網絡編碼；秘密共享；云存儲；分布式存儲

秘密共享就是參與者共同享有秘密，單獨1人不能得到秘密，只有達到一定門限值的人員共同提供自己的秘密份額，才可以得到完整秘密。利用秘密共享管理秘密，可以防止權力過度集中以致于被濫用。秘密共享也被應用于數據的加密存儲或提供冗余保護等領域[1?4]。自SHAMIR等[5?6]提出秘密共享概念以來，人們已對其進行了廣泛研究[7?9]。但隨著數據量增大，運行效率明顯下降。近年來，人們發(fā)現利用最大距離可分碼即MDS(the maximum distance separable)碼[10]可構建具有節(jié)點修復功能的分布式存儲系統(tǒng)。按照該算法，將大小為的數據文件分割編碼為個分片分別進行保存，每個分片大小為/，只要獲得了其中任意個分片，即可利用譯碼算法重建原始數據文件。然而，利用MDS碼要先重建原始數據，再重新編碼生成失效節(jié)點的數據。為解決此問題，DIMAKIS等[11]根據網絡編碼(network coding)[12]的思想提出了再生碼(regenerating codes)的概念。利用再生碼不但可以重建原始數據文件，而且可以直接或者間接重建失效節(jié)點的數據。若原始數據文件是個秘密，則利用再生碼就可以構造秘密共享方案。本文介紹秘密共享中的門限方案和再生碼的相關背景知識，給出基于精確再生碼的秘密共享方案的描述，通過實例給出算法的實現過程，并分析方案的性能。

1 基本概念

1個秘密共享方案一般是由秘密空間、秘密份額空間、秘密分發(fā)者、秘密享有者={1，2，…，u}、訪問結構、秘密分發(fā)算法和秘密重構算法等構成。為的子集的集合，即∈2。若中的子集是能夠計算出秘密∈的參與者的子集，則稱為訪問結構。作為訪問結構的特殊情況，{|í, ||≥}稱為門限訪問結構，稱為門限值。門限訪問結構是實現秘密共享的一種比較簡單的方案。

1.1 (，)門限秘密共享方案

定義1 秘密以某種方式被分割編碼成份秘密份額(或稱為子秘密)并分別發(fā)放給個參與者。個參與者的集合記為。若滿足下列條件：是的授權子集當且僅當||≥；而當í且||＜時，得不到關于秘密的任何信息，則稱{，，}構成1個(，)門限秘密共享方案，稱為門限值。

SHAMIR等[5]利用Lagrange多項式插值算法給出了一種(，)門限秘密共享方案的實現方法。假設為原始秘密，秘密分發(fā)者隨機選擇1個大素數，要求＞，且＞，并構造1個次數為?1的任意多項式：()=(ax+a?1x?1+…+)mod(其中，a為有限域()中隨機選擇的系數，它們是秘密的，在分發(fā)完共享秘密份額之后就丟棄，素數須公開)。各個共享秘密份額通過計算該多項式在各個不同點上的值得到k=(x)(其中：=1，…，；x為每個參與者的惟一標識號)。

只要能獲得個共享秘密份額，便可以利用Lagrange插值公式得出，再令=0即可得原始秘密=(0)mod。

上述算法在秘密的分發(fā)和恢復過程中要多次用到大整數模冪、模乘運算，運算量大，占用內存空間大，而這在有些環(huán)境下(如無線傳感器網絡、ad hoc網絡等，其節(jié)點運算和存儲能力有限)是無法接受的。隨著研究深入，一些方案如基于同余理論的Asmuth-Bloom方案[13]、基于矩陣乘法的Karnin-Greene-Hellman方案[14]等被提出，這些方案并沒有降低運算復雜度。

1.2 再生碼

分布式存儲系統(tǒng)的容錯策略通常分為基于復制的容錯技術和基于糾刪碼的容錯技術共2種[15]?；诩m刪碼的容錯技術則對多個數據塊及其冗余信息進行融合編碼，可有效減小存儲空間的開銷, 但需要一些計算開銷。以計算換空間的再生碼能有效降低數據修復時的通信開銷。下面通過例子說明再生碼的原理。

例1 將1個大小為的文件平均分割成1，2，1和2，按圖1所示保存到4個節(jié)點中(其中“+”表示異或運算)，這就可以構成1個(4，2)再生碼。再生碼的編碼規(guī)則比較簡單，就是將原始數據分割(本例中分成4塊)，確保每個節(jié)點中能存儲2塊，節(jié)點1和節(jié)點2是存儲的原始數據，而節(jié)點3和節(jié)點4存儲的是原始數據塊經過異或后的數據，也就是編碼后的數據塊。

若節(jié)點1失效，則可以利用其他3個節(jié)點的數據2，2+2和1+2+2進行修復，所以，總的數據通信量為。而若采用普通的MDS碼，則數據通信量為。可見，采用再生碼能節(jié)省0.25的通信量。另一方面，若節(jié)點4失效(如圖2所示)，則可利用其他3個節(jié)點的數據1，1+2和2+2進行修復，但在節(jié)點2處要先將本地的數據塊進行異或運算得到1+2，也就是說，要求節(jié)點有一定的網絡編碼能力。此外，在修復過程中，連接的幫助節(jié)點數可以超過2，這也與純粹的(4,2)-MDS碼不同。

根據文獻[11]的相關論述給出再生碼的形式化定義。

定義2 給定1個大小為的文件，將其進行某種編碼后存儲到個節(jié)點，每個節(jié)點都存儲大小為的數據塊。當某個節(jié)點失效時，置換節(jié)點能從剩余的?1個節(jié)點中連接任意個節(jié)點(≤≤?1)，從每個節(jié)點下載大小為≤的數據，并通過某種譯碼算法恢復出失效節(jié)點的數據，則稱這一模型構成1個參數集為(，，，，，)的再生碼(其中，為用于修復的整個數據下載量，稱為修復帶寬；為修復度數；閾值為能夠恢復數據所需要的最小度數)。

根據再生碼的定義可知：只要能夠恢復失效節(jié)點的數據，便可恢復整個原始數據。利用這一思想就可以構造秘密共享方案。

圖1 失效節(jié)點1的修復

圖2 失效節(jié)點4的修復

2 基于精確再生碼的秘密共享方案

整個方案分為3個算法，即子秘密的分發(fā)、原始秘密的恢復以及失效節(jié)點的數據再生。

2.1 子秘密的分發(fā)

首先，將大小為的原始秘密平均分成塊(這里要求≤)，使每個數據塊大小為(若最后1塊小于就以0補齊)，即有，并記為=((1)，(2)，…，(f))。利用某種(，)-MDS碼編碼算法將每個獨立的長度為的數據塊(i)編碼成長度為的向量(i)，即

其中：為×階的MDS碼生成矩陣，是可以公開的，而且要求的任何一個子方陣都必須是可逆的。此外，還需要計算1個向量和。

其次，給每個秘密分享者分配惟一的序列號u作為其識別號。將長度都為的向量(1)，…，(f)和按其分量循環(huán)分別分發(fā)到個分享者手中。對于第∈[1，]個分享者，它得到的秘密份額為(x(1)，x⊕1(2)，…，x⊕(f?1)(f)，s⊕)(其中，“⊕”表示模加法)。每個秘密分享者存儲的秘密份額如表1所示。

表1 各分享者存儲的子秘密

2.2 原始秘密的恢復

只要有個分享者提供其子秘密便可恢復出原始秘密。以(1)為例，它的分量被分別分發(fā)給個分享者，所以，只要有個秘密份額，就可以根據MDS碼的譯碼算法，求出原始秘密塊(1)。若1(1)，2(1)，…，x(1)已知，則據式(1)有，從而有。

由于生成矩陣是公開的，且它的任何1個子方陣都是可逆的，故有

這樣就恢復了(1)這個數據塊。同理，其他數據塊(2)，…，(f)也可以類似地被重建出來，這樣就得到整個原始秘密=((1)，(2)，…，(f))。

2.3 秘密丟失者的數據重建

若某一分享者的子秘密丟失，則不需要由秘密分發(fā)者重新進行秘密分發(fā)，只要有足夠的分享者提供子秘密，便可重建出丟失的子秘密。與秘密恢復不同的是：必要時，秘密丟失者可以從多于個分享者那里下載數據再生自己的秘密，而總的下載量小于原始秘密的下載量，從而可以節(jié)約帶寬。

以分享者1的子秘密(1(1)，2(2)，…，x(f)，s⊕1)的重建為例。首先進行s⊕重建。根據2.1中的定義， s⊕1=1⊕(1)+1⊕(2)+…+1⊕(f)，因此，只要到秘密分享者u⊕1，u，…，2那里下載相應數據塊再相加即可。其次進行數據塊1(1)的重建。這只要到相應節(jié)點下載1，1(2)，…，1(f)，便有1(1)=1+1(2)+…+1(f)。同理，2(2)，…，x(f)等都可以被重建出來。

以上算法稱為基于(，，)再生碼的秘密共享方案，它是一種基于精確再生碼算法的方案，可以精確恢復出丟失的秘密份額。

2.4 算法復雜度分析

子秘密的編碼分發(fā)和秘密丟失者的數據重建只需進行矩陣的乘法運算，運算量不是很大。原始秘密的修復算法復雜度主要取決于生成矩陣的求逆運算，而矩陣的求逆運算代價較高。根據再生碼的編碼要求，的任何1個子方陣都必須可逆(否則可能無法恢復秘密)，若的元素是在有限域(2)中隨機選取，這種矩陣可逆的概率可達99.6%[16]，所以，理論上可以用來作為再生碼的編碼矩陣。然而，對于這種一般矩陣，其逆矩陣的計算復雜度還是相當高。為提高效率，在算法的實現中可以采用范德蒙型矩陣作為生成矩陣。FINCK等[17]利用基本對稱函數乘積表算法得到了范德蒙矩陣求逆的固有復雜度為(lg2)。SHAMIR[5]方案的秘密恢復算法的時間復雜度為(2)，所以，本文方案在理論上效率更高。

3 算法的實現

在算法的具體實現中，可將源數據的最小符號看作是有限域(2)中的元素。由于目前計算機是以8 bit(即1個字節(jié))為信息存儲的最小單位，這里不妨取8。有限域中元素的加法就是異或運算，乘法運算則需要用到本原多項式。將有限域元素的二進制表示式看作降冪多項式的系數，2個元素相乘就相當于多項式相乘，再對本原多項式求模，所得結果再轉化為向量。不妨取本原多項式()84321作為模多項式，取任何其他8次本原多項式也都可以，對方案的實現無實質性影響。下面舉例說明算法的具體實現。

例2 為了簡便，不妨假設原始秘密是4字節(jié)長的，其16進制ASCII碼表示為(3，5，9，7，以下利用基于(4，2，2)再生碼的秘密共享算法進行處理。因為在進行MDS編碼時需要1個2×4的生成矩陣，這里不妨采用范德蒙矩陣，，其中，α都是有限域2)中的非零元素，且要求12，如取145，22。范德蒙矩陣的特點是它的任何1個子方陣都是可 逆的。

1) 子秘密的分發(fā)。首先對=(1(1),2(1),1(2),2(2))進行MDS碼編碼，得

將以上得到的數據再按順序進行組合并發(fā)放到4個共享者，它們分別得到的子秘密數據如表2所示。

表2 分享者存儲的子秘密

2) 原始秘密的恢復。只要獲得任意2個共享者的子秘密便可恢復原始秘密。例如，若獲得1和2的數據，則根據方程(1)可得

(5)

同理，可以根據2(2)和3(2)得(1(2)2(2))=(97)，這樣就得到了整個原始秘密=(1(1)，2(1)，1(2)，2(2))=(3，5，9，7)。

3) 秘密丟失者的數據重建。假如1的秘密份額丟失，則可以到其他分享者下載相關數據塊進行重建。1(1)可以通過從3下載1(1)+1(2)以及從4下載1(2)，然后進行運算1(1)+1(2)+1(2)=1(1)得到；同理，易得2(2)。3(1)+3(2)可以通過從2下載3(2)和從3下載3(1)再相加得到。

在具體實現中，若處理的文件較大，則可以對文件先進行條帶化，使之變成一些大小相同的分塊，再對每個分塊分別使用本方案進行處理。此外，有限域的選取也可以根據硬件設備機器字的位數合理選取，一般選取較大的有限域可以提高效率。

4 實驗與分析

為驗證本文方案的可行性，將其與SHAMIR[5]基于Lagrange多項式插值的門限方案進行對比。實驗平臺為Intel(R) Core2 Duo 2.20GHz CPU，2GB RAM，Windows XP PC機，Matlab R2014a編譯環(huán)境。

4.1 效率對比

由于子秘密分發(fā)算法都只涉及有限域中矩陣的加法和乘法，對運行時間影響不大，所以，只對比2種方案的秘密恢復算法的效率。

實驗：對1個大小為1 920字節(jié)的文件、門限值和分享者數目變化時2種方案的秘密恢復效率進行對比。

實驗中2種方案的運算都是在有限域(216)上進行的，即每次對2字節(jié)的數據塊進行操作，在實際應用中可以根據硬件設備情況選擇更大的有限域，效率會更高。每一組測試都獨立運行20次，取其運行時間的平均值。當分享者數目和門限值變化時，實驗結果如圖3所示。

1—本文方案；2—SHAMIR方案[5]。

從圖3可以看出：在進行秘密恢復時，隨著門限值及分享者數目增加，SHAMIR方案[5]所需時間迅速增大，本文方案所需時間也較快增大。這是因為隨著門限值及分享者數目的變大，編解碼用到的生成矩陣的規(guī)模也相應變大，在進行秘密恢復時用到的矩陣求逆運算非常耗時。但從實驗結果看，本文方案所需時間增長速度比SHAMIR方案[5]的要少，說明本文方案仍有一定優(yōu)勢。

4.2 安全性分析

再生碼是在MDS糾刪碼[18]基礎上繼續(xù)進行一定的線性變換而得到的，它仍然滿足MDS糾刪碼的特性，因而可以看作是一種特殊的MDS碼，PIEPRZYK等[19]指出MDS碼可以用來構造理想的門限體制。對于本文構造的算法，在此以定理的形式給出其安全性。

定理1 本文構造的基于(，，)再生碼的秘密共享算法，它是1個安全的(，)門限秘密共享體制。

證明：一方面，只要有個分享者提供子秘密，就可以恢復出原始秘密；另一方面，可證明當秘密份額少于份時，就不能恢復出原始秘密。事實上，通過方程(1)可以看到，由于(1)，…，(f)是相互獨立的，因而其線性變換1(1)，…，x(f)也是相互獨立的。按照給出的再生碼算法，每個分享者持有的子秘密來自于1(1)，…，x(f)以及的不同分量，因而，其每個數據塊之間也是相互獨立的。這樣，要想恢復某個數據塊如1(1)，就只能根據各個分享者提供的1(1)相關分量來進行運算，這就歸結到MDS碼的譯碼問題上。在數據塊少于個情況下，這就相當于解1個方程數少于的元一次線性方程組，它具有無窮多個解，其安全性相當于1次一密亂碼本加密方式，它在信息論意義上是安全的，所以，不能恢復秘密。證畢。

4.3 子秘密再生性

由于算法是基于再生碼的，因而，本方案的1個優(yōu)點是：在某個分享者的秘密丟失時，可以不必與秘密分發(fā)者進行通信；秘密分發(fā)者完成秘密分發(fā)后就可以丟棄原始秘密，這也有利于秘密的安全性。丟失秘密的分享者只需到另外一些秘密分享者那里下載一定的數據塊即可重建自己的子秘密。這一特點可以解決一些環(huán)境下分享者秘密丟失的問題，如P2P網絡中某失效節(jié)點在重新加入系統(tǒng)時的秘密恢復等。

4.4 分享者的數據存儲量

對于1個大小為的秘密文件來說，本方案中每個分享者只需存儲+1的數據量，其中=[/]。而對于SHAMIR方案[5]，每個分享者都需要存儲數據量，因此，本方案可以節(jié)省存儲空間。這對于一些存儲能力有限的設備(如智能卡、無線傳感器網絡，移動互聯(lián)網等)，布署該方案是十分有利的。

5 結論

1) 利用精確再生碼構造了一種新的秘密共享方案，并以實例說明了方案中算法的具體實現。方案由子秘密的分發(fā)、原始秘密的恢復、子秘密丟失者的數據重建3個過程組成。

2) 與傳統(tǒng)秘密共享算法相比，本方案具有安全性高、運算復雜性低、共享者的秘密份額可以再生、節(jié)點存儲量小等特點。

3) 下一步研究的重點是精確再生碼在云存儲、無線傳感器網絡、移動互聯(lián)網、ad hoc網絡以及P2P網絡等環(huán)境下的應用。

[1] MAO Bo, WU Suzhen, JIANG Hong. Improving storage availability in cloud-of-clouds with hybrid redundant data distribution[C]//Proceedings of the 29th IEEE International Parallel & Distributed Processing Symp(IPDPS’15). Piscataway, NJ: IEEE, 2015: 1?10.

[2] CHEN H C H, HU YUCHONG, LEE P P C, et al. NCCloud:A network-coding-based storage system in a cloud-of-clouds[J]. IEEE Transactions on Computers, 2014, 63(1): 31?44.

[3] 馮登國, 張敏, 張妍, 等. 云計算安全研究[J]. 軟件學報, 2011, 22(1): 71?83. FENG Dengguo, ZHANG Min, ZHANG Yan, et al. Study on cloud computing security[J]. Journal of Software, 2011, 22(1): 71?83.

[4] 馮朝勝, 秦志光, 袁丁. 云數據安全存儲技術[J]. 計算機學報, 2015, 38(1): 150?163. FENG Chaosheng, QIN Zhiguang, YUAN Ding. Techniques of secure storage for cloud data[J]. Chinese Journal of Computers, 2015, 38(1): 150?163.

[5] SHAMIR A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612?613.

[6] BLAKLEY G R. Safeguarding cryptographic keys[C]// Proceedings of AFIPS 1979 National Computer Conference. Monval, USA: AFIPS Press, 1979: 313?317.

[7] BEIMEL A, CHOR B. Secret sharing with public reconstruction[C]//COPPERSMITH D. Advances in Cryptology-CRYPTO ’95, LNCS 963. Berlin: Springer-Verlag, 1995: 353?366.

[8] PIEPRZYK J, ZHANG X M. On cheating immune secret sharing[J]. Discrete Mathematics & Theoretical Computer Science, 2004, 6(2): 253?264.

[9] GUO Y B, MA J F. Proactive secret sharing in synchronous networks with unreliable links[J]. Acta Electronica Sinica, 2004, 32(3): 399?402.

[10] 楊義先. MDS碼在保密學中的應用[J]. 北京郵電學院學報, 1988, 11(1): 30?36. YANG Yixian. The applications of MDS codes in cryptography[J]. Journal of Beijing University of Posts and Telecommunications, 1988, 11(1): 30?36.

[11] DIMAKIS A G, GODFREY P B, WU Y, et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory, 2010, 56(9): 4539?4551.

[12] AHLSWEDE R, CAI N, LI S R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204?1216.

[13] ASMUTH C, BLOOM J. A modular approach to key safeguarding[J]. IEEE Transactions on Information Theory, 1983, 29(3): 208?210.

[14] KARNIN E D, GREENE J W, HELLAN M E. On sharing secret systems[J]. IEEE Transactions on Information Theory, 1983, 29(3): 35?41.

[15] 王意潔, 孫偉東, 周松, 等. 云計算環(huán)境下的分布存儲關鍵技術[J]. 軟件學報, 2012, 23(4): 962?986. WANG Yijie, SUN Weidong, ZHOU Song, et al. Key technologies of distributed storage for cloud computing[J]. Journal of Software, 2012, 23(4): 962?986.

[16] CHOU P A, WU Y, JAIN K. Practical network coding[C]//Proceedings of 41st Annual Allerton Conference on Information Control and Computing. Monticello, USA: Springer-Verlag, 2003: 214?218.

[17] FINCK T, HEINIG G, ROST K. An inversion formula and fast algorithm for Cauchy-Vandermonde matrices[J]. Linear Algebra and Its Applications, 1993, 183(1): 179?191.

[18] 王新梅, 肖國鎮(zhèn).糾錯碼—原理與方法[M]. 修訂版. 西安: 西安電子科技大學出版社, 2001: 178?179. WANG Xinmei, XIAO Guozhen. Error correction codes-principle and method[M]. Revised ed. Xi’an: Xian University of Electronic Science and Technology Press, 2001: 178?179.

[19] PIEPRZYK J, ZHANG Xianmo. Ideal threshold schemes from MDS codes[C]//Proceedings of the 5th International Conference on Information Security and Cryptology. Berlin: Springer-Verlag, 2003: 253?263.

(編輯 陳燦華)

Secret sharing scheme based on exact regenerating codes

SONG Hailong1, 2, WANG Weiping1

(1. School of Information Science and Engineering, Central South University, Changsha 410083,China;2. School of Information Science and Engineering, Jishou University, Jishou 416000, China)

In order to solve data security issues in cloud storage system, a new (,) threshold secret sharing scheme was constructed based on exact regenerating codes. The scheme was composed of three algorithms which were distribution of share secret, recovery of the original secret and data reconstruction of lost share secrets. Distribution of share secret means that original secret is firstly split into some pieces, then is erasured codes, and finally is distributed topartners. Choosing data blocks provided bypartners, the original secret can be recovered through some decoding algorithms of erasure coding. Choosing more thandata blocks,the lost data of partner who losts his data can be reconstructed following decoding algorithm of exact regenerating codes. The results show that the scheme is an information theoretical secure threshold system. Compared with the traditional secret sharing scheme based on Lagrange polynomial interpolation algorithm, the scheme has the advantages of lower computation complexity, less nodes storage and easier regeneration of lost share secrets.

regenerating codes; erasure coding; network coding; secret sharing; cloud storage; distributed storage

TP309

A

1672?7207(2017)04?0984?06

10.11817/j.issn.1672?7207.2017.04.018

2016?06?20；

2016?08?26

國家自然科學基金資助項目(61173169, 61363037)；湖南省教育廳科研資助項目(13C755)(Projects (61173169, 61363037) supported by the National Natural Science Foundation of China? Project (13C755) supported by the Science Foundation of Education Department of Hunan Province)

王偉平，博士，教授，從事網絡編碼、匿名通信等研究；E-mail：wpwang@csu.edu.cn