唐 聃，舒紅平(成都信息工程大學軟件工程學院 成都 610225)

?

基于編碼的秘密重構(gòu)方法研究

唐 聃，舒紅平
(成都信息工程大學軟件工程學院 成都 610225)

【摘要】當前大多基于編碼實現(xiàn)的(k,n)門限秘密分享方案在秘密重構(gòu)時均假定只存在k個份額，忽略了秘密重構(gòu)時可用份額數(shù)量多于門限值k的情況。而實驗證明，多余的份額如果合理利用可以極大地降低秘密重構(gòu)的運算量。在基于秘密分享的實用系統(tǒng)運行過程中，特別是網(wǎng)絡(luò)數(shù)據(jù)傳輸或分布式存儲系統(tǒng)中，可用份額數(shù)量大于門限值k的情況又是經(jīng)常出現(xiàn)的。針對這一問題，該文提出了一種新的秘密重構(gòu)方法，該方法可以有效利用秘密重構(gòu)時所有的可用份額，且計算效率與當前主流方法相比有較大的提升。

關(guān) 鍵 詞編碼; 秘密重構(gòu); 秘密分享; 門限

Research of Secret Reconstruction Based on Coding Theory

TANG Dan and SHU Hong-ping
(Software Engineering College, Chengdu University of Information Technology Chengdu 610225)

Abstract Most (k,n) threshold secret sharing schemes based on coding theory ignores a case that the number of shares are more than the threshold value k when rebuilding the secret information. Such a case frequently occurs in practical systems based on secret sharing, especially the network data transmission or distributed storage systems. Many experiments have proved that the amount of secret reconstruction computation can be reduced greatly if reasonably using the surplus shares. To solve this problem for secret sharing schemes based on coding theory, this paper proposes a new method of reconstructing the secret which can effectively use all available shares when reconstructing the secret, and computational efficiency has greatly improved compared with the mainstream approaches.

Key words coding; secret reconstruction; secret sharing scheme; threshold

秘密分享技術(shù)由文獻[1-2]提出，這是一種能更加有效地保障秘密信息安全性的技術(shù)。利用秘密分享技術(shù)可將秘密信息分解成n個部分，每個部分稱作一個子秘密或份額，同時建立特定的規(guī)則，即只有滿足一定條件(將所有這些條件的集合稱作訪問結(jié)構(gòu))的多個份額才能共同恢復出原始秘密信息，因此，秘密分享技術(shù)具有非常高的安全性。以一個(k, n)門限秘密分享方案為例(其中k和n均為正整數(shù)，且2≤ k≤ n)，即使攻擊者截獲了一定數(shù)目(不多于k)的份額，也不能恢復出原始秘密甚至不能得到關(guān)于該秘密的任何信息；當相當數(shù)量的子秘密(不多于n k?個)毀壞或丟失(自然災(zāi)害或人為破壞等因素)，也不會對秘密的恢復造成任何影響。該技術(shù)最初應(yīng)用于密鑰信息的安全保存，將密鑰以秘密分享方式分發(fā)給多人管理，可以解決密鑰管理中的密鑰泄漏和遺失問題，提高系統(tǒng)的安全性和穩(wěn)健性，同時還能夠防止權(quán)力濫用等問題。秘密分享技術(shù)自產(chǎn)生以來就受到了信息安全領(lǐng)域?qū)W者們的高度重視，并在過去的30余年間得到了迅速的發(fā)展，多種構(gòu)造秘密分享系統(tǒng)的方案被陸續(xù)提出，包括拉格朗日插值多項式方案、多維空間矢量方案、中國剩余定理方案、橢圓曲線方案、矩陣投影方案、編碼方案和量子理論方案等[1-7]。

文獻[8]提出的基于拉格朗日插值多項式的門限秘密分享方案以其理論成熟、構(gòu)造簡單和可應(yīng)用領(lǐng)域廣等特點，是目前使用范圍最廣的秘密分享構(gòu)造方案。而近年來，隨著信息技術(shù)的不斷進步，對秘密分享的研究和應(yīng)用也從最初的安全保存文本格式的密鑰擴展到了信息安全的諸多領(lǐng)域，例如圖像秘密分享、音頻秘密分享、視頻秘密分享、網(wǎng)絡(luò)文件傳輸和分布式文件安全管理等[8-17]。目前，已有不少基于文獻[8]的方案，即使用拉格朗日插值多項式方法構(gòu)建的應(yīng)用于多個領(lǐng)域的秘密分享方案被相繼提出[9-11]。但是這些方案在實用化過程中卻面臨一個很大的障礙，即拉格朗日插值方法的計算復雜度非常高，這對于普通的秘密分享應(yīng)用(如傳統(tǒng)小數(shù)量的文本格式密鑰分享)影響不大，但是面對大量需要進行秘密分享運算的數(shù)據(jù)時就會使得整個系統(tǒng)運行速度變得緩慢甚至不可接受。在此背景下，一些學者開始使用編碼(主要是刪除碼)來構(gòu)建秘密分享方案，在基于編碼的秘密分享方案中，份額產(chǎn)生大體可對應(yīng)編碼中碼字生成的過程，而秘密重構(gòu)則可大體對應(yīng)于編碼中的譯碼過程。其中最具代表性的為文獻[14]，該文獻采用有限域上代數(shù)幾何編碼的方法設(shè)計出實用的秘密分享方案，將運算的時間復雜度大大降低。基于此思想，以圖像和音頻為秘密信息的(k,n)門限秘密分享系統(tǒng)被構(gòu)造并實現(xiàn)[8,14-17]。但是經(jīng)過分析發(fā)現(xiàn)，此類方案(也包括以往幾乎所有(k,n)門限的秘密分享方案)在秘密重構(gòu)過程中僅用到了最低需求的k個份額來進行計算，即使當在秘密重構(gòu)過程中有k+ t個可用份額(t為正整數(shù))，系統(tǒng)也只是選取其中的k個份額，而剩余的t個份額并不參與運算而被丟棄。以網(wǎng)絡(luò)文件多路傳輸為例，發(fā)送端使用秘密分享手段將信息分拆成7個部分，對每個部分使用不同的鏈路進行傳輸，設(shè)定只需要其中任意4個部分就能夠重構(gòu)原始信息，而假設(shè)接收端每次平均能夠收到6個鏈路傳輸來的正確信息時，問題就出現(xiàn)了：平均每次傳輸多余門限值的2個信息部分使用了網(wǎng)絡(luò)帶寬，也被正確的傳送到了接收端，但是卻由于信息重構(gòu)方法的限制而被白白浪費掉了。因此，充分利用所有的可用份額，將多于門限值的份額用在提高信息重構(gòu)的運算效率上以提升系統(tǒng)的整體性能是本文研究的目標。基于此，本文在文獻[14]方案的基礎(chǔ)上提出了一種新的秘密重構(gòu)方法。

1 相關(guān)工作

令s表示需要同時進行分享操作的秘密數(shù)量，為正整數(shù)；L表示單個秘密信息中數(shù)據(jù)的數(shù)量，其單位根據(jù)運算的有限域來確定；P表示參與運算信息中的某個確定位置坐標；(k,n)表示秘密分享方案的門限結(jié)構(gòu)參數(shù)，其中k和n均為正整數(shù)，且滿足條件2≤ k≤ n。

此外，所有運算均在有限域GF(2m)(m為正整數(shù))上進行，其取值視具體應(yīng)用場合而定。為了所描述的方案具有普適性，本文認為多個秘密可以同時被分享，即s≥1，假設(shè)s個秘密為且每個秘密所含的信息量相同。

基于編碼的秘密分享方案中，份額產(chǎn)生可歸納為6個步驟：

1) 根據(jù)(k,n)門限，在有限域GF(2m)上構(gòu)造出矩陣及構(gòu)造的具體方法在文獻[14]中有非常詳細的步驟說明及證明，亦可參考文獻[8，15]相關(guān)章節(jié)的描述，本文不再贅述。

3) 根據(jù)一定規(guī)則(可以是順序也可以按照某種原則非順序)，從s個秘密信息中確定一取值點P，對上述每一個Vi取出其在位置P處的數(shù)據(jù)值構(gòu)成一個由k個數(shù)值組成的序列記作信息矢αk×1。

5) 將信息矢αk×1前s個元素銷毀，并將其余n個值作為n+ s k?個份額的一部分。

6) 按指定順序遍歷L個位置P，重復上述過程即可得到n+ s k?個份額，連同步驟2)中選取的k s?個信息，得到全部n個份額。

當聚集≥k個份額時，就可以對秘密進行重構(gòu)。其具體步驟為：

由于其中k個數(shù)值bi, P為已知將它們代入式(1)，可得到：

3) 根據(jù)份額產(chǎn)生時的規(guī)則，遍歷位置重復步驟2)，即可重構(gòu)出最初s個秘密信息。

2 新的秘密重構(gòu)方法

基于編碼的秘密分享方案中，份額生成時主要使用的是有限域上的矩陣乘法，因此在實現(xiàn)時可以采用縮小運算有限域等手段和技巧提高計算效率(相關(guān)內(nèi)容文獻[8]中已有詳細的論述)，而在秘密重構(gòu)計算時主要使用的方法為有限域上的矩陣求逆運算，算法復雜度高且不能應(yīng)用份額生成時的效率優(yōu)化方法。因此，無論是從算法的復雜度還是從實際效果而言，秘密重構(gòu)花費的時間要遠遠大于份額產(chǎn)生的時間。但是在秘密重構(gòu)的過程中，如果可用的份額數(shù)量超過k個，在實際運算時也只是利用到了其中的k個，多余門限值的份額將被閑置和浪費。

與文獻[8,14-17]相似，在本文秘密重構(gòu)方法中所有運算使用的有限域仍然采用比特矩陣構(gòu)建的有限域，除了理論體系成熟、運算效率高、代碼實現(xiàn)便捷等優(yōu)點，選用此類有限域的重要原因是該有限域中每個元素的加法逆元是該元素本身，即相同元素的和為該有限域中的零元素，這一特性也是本文方法的正確性保障。

方法的具體步驟為：

1) 按照份額本身的順序編號對所有份額進行排序，并將其置于之后，形成一個具有s+ n個元素的向量，記作X，用來對應(yīng)一致校驗矩陣H的各個列。

2) 將向量X中的各個元素進行分類，將已知元素和未知元素分別集中放置于向量X的左邊和右邊，記作其中d表示全部的已知元素，而y表示全部的未知元素，而也包含其中。

3) 根據(jù)X中的各個元素與矩陣H各列的位置對應(yīng)關(guān)系，將矩陣H中的各列也相應(yīng)地重新排列后記作其中子矩陣A的各列對應(yīng)子向量d的各個元素，而子矩陣B的各列則對應(yīng)子向量y的各個元素。

4) 假設(shè)子矩陣B共有m列(m一定小于等于門限值k，否則秘密無法重構(gòu))，找出矩陣B中任意一組線性無關(guān)的m行，形成矩陣

3 分析與對比

首先證明新方法的正確性。

證明：在基于編碼的秘密分享方案中，所有的秘密數(shù)據(jù)均作為編碼運算中原始數(shù)據(jù)的一部分，因此，在前面步驟1)中的向量X可以認為是編碼后產(chǎn)生的碼字。如前所述，矩陣H可以認定為有限域上的校驗矩陣(其具體構(gòu)造及證明過程內(nèi)容較多，詳細請參考文獻[14])，因此等式HX=0一定成立。按照前文所述，向量X的元素和矩陣H的列向量都重新進行了排序，并分別記作由矩陣及分塊矩陣運算規(guī)則可得下列等式成立：整個運算體系使用的有限域具有元素為自身加法逆元的特性，因此可得等式Ad= By成立。而和分別為矩陣B和A的子矩陣，且具有行對應(yīng)關(guān)系，因而有等式成立。而同時又是矩陣H的子矩陣，所以一定可逆。所以，新的方法可以正確重構(gòu)出秘密信息。證畢。

基于編碼的秘密分享方案中，文獻[14]給出了具有代表性的秘密重構(gòu)方法，該方法也是當前基于編碼秘密分享的最常用方法，而本文則提出了一種新的秘密重構(gòu)方法。兩種秘密重構(gòu)方法均使用到了有限域上的矩陣求逆運算(整個秘密重構(gòu)過程中計算量最大的操作)，而最大的區(qū)別在于對份額的利用上，文獻[14]中的方法在秘密重構(gòu)時無論有多少個可用份額，均假定可用份額數(shù)量為k，即從可用份額中任意選用其中的k個(滿足門限條件)，新的方法則利用了在秘密重構(gòu)時全部的已知份額，且在秘密重構(gòu)時可利用的份額越多，需要進行求逆運算的矩陣規(guī)模就越小，從而減少秘密重構(gòu)的整體計算量。

由于字節(jié)是大多計算機運算的實際最小單位，為了便于計算量統(tǒng)計，因而在不失一般性的前提下假設(shè)所有運算的有限域為8GF(2 )，在秘密重構(gòu)時獲得的可用份額數(shù)量等概率隨機取自k到n，其中前面所述的兩種方法對于每一個秘密中某特定位置數(shù)據(jù)進行計算的時間復雜度對比如圖1所示。而使用本文方法在對秘密進行重構(gòu)時，運算量將隨著已知份額數(shù)量的增大而不斷降低；由前面算法描述不難看出，有限域上的矩陣求逆運算為整個秘密重構(gòu)過程的最大工作量部分，而新方法的核心即通過份額數(shù)量的增加有效減少求逆運算的工作量。圖2中分別以(2,5)、(3,8)、(5,9)和(9,17)門限結(jié)構(gòu)為例說明了使用新方法恢復秘密中某個特定位置數(shù)據(jù)時，隨著可用份額增多后求逆計算量的下降情況。

圖1　平均計算復雜度對比

圖2　本文方法的求逆運算總量與份額數(shù)量關(guān)系

4 結(jié) 束 語

基于編碼理論的秘密分享方案現(xiàn)在已經(jīng)廣泛的應(yīng)用于信息安全的諸多領(lǐng)域，如圖像秘密分享、音頻秘密分享、分布式文件安全管理以及P2P文件傳輸?shù)?。針對當前已有的方案，本文提出了一種新的秘密重構(gòu)方法，該方法能充分利用所有的可用份額來減少運算量，而經(jīng)過試驗及分析表明新的方法大大降低了秘密重構(gòu)的計算復雜度，這對于網(wǎng)絡(luò)中的多路傳輸系統(tǒng)等相關(guān)應(yīng)用尤為重要。此外，該方法并不改變當前主流方案的核心思想，因此現(xiàn)有系統(tǒng)能非常便捷的將本方法嵌入到已有的實用系統(tǒng)中，也具有一定的現(xiàn)實意義。

參 考 文 獻

[1] SHAMIR 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 the National Computer Conference. New York, USA: Wiley, 1979.

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

[4] CHEN H, LING S, XIANG C P. Access sturctures of elliptic secret sharing schemes[J]. IEEE Transaction on Information Theory, 2008, 54(2): 850-852.

[5] YANG Y G, WEN Q Y, ZHU F C. An efficient two-step quantum key distribution protocol with orthogonal product states[J]. Chinese Physics, 2007, 16(4): 910-914.

[6] MCELIECE R J, SARWATE D V. On sharing secrets and reed-solomon codes[J]. Communications of the ACM, 1981(9): 583-584.

[7] LI Bai. A reliable (k,n) image secret sharing seheme. dependable, autonomic and secure computing[C]//2nd IEEE International Symposium on Dependable, Autonomic and Secure Computing. Indianapolis, USA: Hans-Andrea Loeliger, 2006.

[8] 唐聃. 圖像秘密分享技術(shù)研究[D]. 北京: 中國科學院，2010. TANG Dan. Research on secret image sharing scheme[D]. Beijing: Chinese Academy of Sciences, 2010.

[9] THIEN C C, LIN J C. Secret image sharing[J]. Computer & Graphic, 2002, 26(5): 765-770.

[10] MOL J J D, POUWELSE J A, EPEMA D H J, et al. Free-riding, fairness, and firewalls in P2P file-sharing in peer-to-peer computing[C]//Eighth International Conference on P2P. Aachen, Germany: [s.n.], 2008.

[11] LEIN H, LIN Chang-lu. Asynchronous secret reconstruction and its application to the threshold cryptography[J]. International Journal of Communications, Network and System Sciences, 2014, 7(1): 22-29.

[12] MASSEY J L. Minimal codewords and secret sharing[C]// Proceedings of the Joint Swedish-Russian International Workshop on Information Theory. Sweden: Willy, 1993.

[13] BLAKLEY G R, KABATIANSKI G A. Ideal perfect threshold schemes and MDS codes[C]//Proceedings of the International Symposium on Information Theory. Washington, USA: Springer, 1995.

[14] 王曉京, 方佳嘉, 蔡紅亮, 等. 視圖的秘密分享及其代數(shù)編碼方法[J]. 計算機應(yīng)用, 2012, 32(3): 669-678. WANG Xiao-jing, FANG Jia-jia, CAI Hong-liang, et al. Secret image sharing and its algebraic coding method[J]. Journal of Computer Applications, 2012, 32(3): 669-678.

[15] 王一丁. 音頻秘密分享技術(shù)研究[D]. 北京: 中國科學院, 2011. WANG Yi-ding. Research on secret audio sharing scheme[D]. Beijing: Chinese Academy of Sciences, 2011.

[16] 方佳嘉. 感官信息秘密分享技術(shù)及其應(yīng)用研究[D]. 北京:中國科學院, 2012. FANG Jia-jia. Research on sensory information secret sharing and its applications[D]. Beijing: Chinese Academy of Sciences, 2012.

[17] 唐聃, 王曉京. 基于編碼理論的圖像秘密分享技術(shù)研究[J]. 計算機應(yīng)用與軟件, 2013, 30(9): 141-146. TANG Dan, WANG Xiao-jing. Research on secret sharing of image based on coding theory[J]. Computer Applications and Software, 2013, 30(9): 141-146.

編 輯 葉 芳

作者簡介：唐聃(1982 ? )，男，博士，副教授，主要從事編碼理論和秘密分享方面的研究.

基金項目：國家自然科學基金(61501064) ; 四川省科技支撐計劃(2016GZ0122); 四川省教育廳科技成果轉(zhuǎn)化重大培育項目(15CZ0019)

收稿日期：2014 ? 07 ? 05；修回日期： 2015 ? 09 ? 25

中圖分類號TP391

文獻標志碼A

doi:10.3969/j.issn.1001-0548.2016.01.015