基于Hermite插值的多密鑰共享協議 

王英杰++范海博++羅冰

摘要：（t，n）門限密鑰共享方案是一種重要的密碼學機制?；诶窭嗜詹逯捣ê虷ermite插值法提出了多密鑰共享協議。使用雙變量單向函數，使參與者的子份額能多次重復使用。子密鑰可多次使用的性質大大降低了密鑰分發的開銷。每個參與者自己選擇子密鑰，分發者則沒有欺騙的余地。同時，還利用離散對數問題的復雜性來驗證數據正確性。此外，該協議可以動態地改變門限值、密鑰數目以及密鑰數值大小。

關鍵詞：Hermite插值法；多密鑰共享；雙變量單向函數；離散對數問題

DOIDOI：10.11907/rjdk.161577

中圖分類號：TP309.7

文獻標識碼：A文章編號文

章編號：16727800（2016）009015403

基金項目基金項目：2014年國家級大學生創新創業訓練計劃項目（201410476036）

作者簡介作者簡介：王英杰（1994-），女，河南南陽人，河南師范大學計算機與信息工程學院學生，研究方向為密碼學。

0引言

在現代密碼學中，密鑰共享是一個重要的研究課題，它的任務就是把一個或多個主密鑰分成若干子份額，并把這些子份額分配給參與者。只有當提前指定的參與者序列共同發送他們的子份額，才能重構出主密鑰。在密鑰共享家族中一個很重要的成員是（t，n）門限密鑰共享，如文獻[1][6]所示。第一個（t，n）門限密鑰共享方案是由A Shamir[1]和G Blakley[2]于1979年各自提出的。A Shamir的方案是基于拉格朗日插值多項式而G Blakley的方案是基于射影幾何定理。在以上兩種方案中，分發者將一個主密鑰分發給n個參與者，只有當t個或更多參與者發送他們的子份額才能重構密鑰，任何少于t個參與者的序列都不能得到有關主密鑰的任何信息。

2000年，chien等[3]基于系統分組對稱碼提出了一種新的（t，n）多密鑰共享協議。當參與者共同發送他們的子份額時，能夠重構m個密鑰。該協議的一個重要應用即共享大密鑰，因為密鑰特別大，所以將該大密鑰打散成m個小密鑰s1，s2，...，sm。但是該協議的問題是，需要解聯立方程組，計算相當復雜；2004年，Yang等[4]基于A Shamir的思想提出另一個（t，n）多密鑰共享方案，相比chien的協議，Yang等的協議中，當密鑰數目小于一個門限值時，需要公布更多公共數值，因此Yang的協議不是非常高效；2005年，Pang等[5]提出了（t，n）門限密鑰共享協議，就高效性而言，該協議與Yang等的協議相似，但是Pang的協議需要公開的數值對，與chien的協議一致。最近幾年，密鑰研究趨勢已朝著減少計算復雜度和公開數值對[6]的方向努力。1995年，He和Dawson[7]使用雙變量單向函數提出了可以多次使用的密鑰協議。在該協議中，參與者不需要直接公開他們的私有密鑰，而是把他們的私有密鑰作為雙變量單向函數輸入，把函數輸出作為重構密鑰的偽子密鑰。通過這種方式，他們的私有密鑰可以永遠只有自己知道。He和Dawson[7]的協議也是動態的。因為這些協議的高靈活性，協議啟動很快，并且再次啟動的代價很低[89]。

Chor等[10]是首先構建可驗證密鑰共享協議的研究學者。在密鑰重構階段使用可驗證的方法允許系統驗證參與者或分發者接收到的信息是否正確。近年來，大量多次使用的可驗證密鑰共享協議被提出，在這些協議中，可以發現文獻[8]利用了離散對數的性質，文獻[11]充分利用了RSA算法的優點，文獻[13]使用了ECS和BMS的性質。2005年，Huang等提出了基于DL性質的多密鑰共享協議，盡管該協議是可驗證的，但是它缺少多次使用的性質，并且還需要安全信道；2011年，Wang等[14]發表了另外一篇論文，提出關于可驗證的多次使用的多密鑰共享方法。跟以上著作相似，他們的方法是基于求解線性方程組，密鑰數目永遠被限制在少于門限值的范圍之內，這一特點限制了協議的實用性。

本文基于Hermite插值多項式，利用雙變量單項函數以及離散對數提出一種可驗證的多密鑰共享協議。

1相關概念

（t，n）門限密鑰共享協議是定義在一位密鑰分發者與n位參與者之間的協議。分發者將密鑰打散拆分成若干個子密鑰份額，將其分配給各個參與者，主密鑰則被多人掌管。標記分發者為D，參與者集合是P={P1，P2，...，Pn}，參與者Pi的子份額集合是s={s1，s2，...，sn}。（t，n）門限密鑰共享協議滿足：任意大于等于t個參與者的集合能在多項式時間內恢復密鑰，反之不能得到關于密鑰的任何信息。這也是門限密鑰共享協議被認為完善的原因。

雙變量單向函數f（r，s）指將數r和s映射成一個固定長度的比特流。對應法則f具有以下6點性質：①給出r和s，計算f（r，s）非常容易；②已知r和f（r，s），很難得到s的值；③已知s和f（r，s）的值，很難得到r的值；④不知道s的值，對于任意r很難得到f（r，s）；⑤已知s，很難求得兩個完全不同的r1和r2，使f（r1，s）=f（r2，s）；⑥已知有ri和f（ri，s）這樣的數值對，很難得到f（r′，s）的值r′≠ri。

3結語

本文提出了一種（t，n）可驗證的多密鑰共享方案，在協議中，因為參與者自己選擇子份額，所以分發者沒有欺騙的空間。在一輪協議中，多個密鑰可以同時獲取，并且可以動態地改變密鑰數目、數值以及門限值。同時，因為使用了雙變量單向函數，參與者的子密鑰可以重復多次使用。

參考文獻：

[1]SHAMIR A. How to share a secret[J].Communications of the Acm，1979， 22（11）：612613.

[2]BLAKLEY G R. Safeguarding cryptographic keys[C].afips.IEEE Computer Society， 1979：313.

[3]CHIEN H Y. A practical （t，n） multisecret sharing scheme[J]. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences， 2000（12）：27622765.

[4]YANG C C， CHANG T Y， HWANG M S. A （t，n） multisecret sharing scheme[J]. Applied Mathematics & Computation，2004，151（2）：483490.

[5]PANG L J， WANG Y M. A new （t， n） multisecret sharing scheme based on Shamirs secret sharing[J].Applied Mathematics & Computation，2005，167（2）：840848.

[6]ZHOU Y， WANG F， XIN Y， et al. A secret sharing scheme based on NearMDS codes[C]. Network Infrastructure and Digital Content，2009.IEEE International Conference on，2009：833836.

[7]HE J， DAWSON E. Multisecretsharing scheme based on oneway function[J]. Electronics Letters，1995，31（2）：9395.

[8]CHEN W， LONG X， BAI Y， et al. A new dynamic threshold secret sharing scheme from bilinear maps[C].International Conference on Parallel Processing Workshops. IEEE，2007：19.

[9]QU J， ZOU L， ZHANG J. A practical dynamic multisecret sharing scheme[C]. Information Theory and Information Security （ICITIS），2010 IEEE International Conference on，2010：629631.

[10]CHOR B， GOLDWASSER S， MICALI S，et al. Verifiable secret sharing and achieving simultaneity in the presence of faults[C]. Proceedings of the 26th Annual Symposium on Foundations of Computer Science. IEEE Computer Society， 1985：383395.

[11]ZHAO J， ZHANG J， ZHAO R. A practical verifiable multisecret sharing scheme[J].Computer Standards & Interfaces，2007，29（1）：138141.

[12]HUANG M J， ZHANG J Z， XIE S C. A secure and efficient （t， n） threshold verifiable multisecret sharing scheme[M]. Computational Intelligence and Security. Springer Berlin Heidelberg，2005：532537.

[13]PANG.An efficient and secure multisecret sharing scheme with general access structures[J].Wuhan University Journal of Natural Sciences， 2006， 11（6）：16491652.

[14]WANG S J， TSAI Y R， SHEN C C. Verifiable threshold scheme in multisecret sharing distributions upon extensions of ECC[J]. Wireless Personal Communications， 2011，56（1）：173182.

[15]SZEGO G.Orthogonal polynomials（scientific books： orthogonal polynomials）[J].Science，1940：91.

責任編輯（責任編輯：黃?。?