基于Hermite插值的多密鑰共享協(xié)議 

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

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

關(guān)鍵詞：Hermite插值法；多密鑰共享；雙變量單向函數(shù)；離散對(duì)數(shù)問題

DOIDOI：10.11907/rjdk.161577

中圖分類號(hào)：TP309.7

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文

章編號(hào)：16727800（2016）009015403

基金項(xiàng)目基金項(xiàng)目：2014年國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（201410476036）

作者簡(jiǎn)介作者簡(jiǎn)介：王英杰（1994-），女，河南南陽人，河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院學(xué)生，研究方向?yàn)槊艽a學(xué)。

0引言

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

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

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

本文基于Hermite插值多項(xiàng)式，利用雙變量單項(xiàng)函數(shù)以及離散對(duì)數(shù)提出一種可驗(yàn)證的多密鑰共享協(xié)議。

1相關(guān)概念

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

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

3結(jié)語

本文提出了一種（t，n）可驗(yàn)證的多密鑰共享方案，在協(xié)議中，因?yàn)閰⑴c者自己選擇子份額，所以分發(fā)者沒有欺騙的空間。在一輪協(xié)議中，多個(gè)密鑰可以同時(shí)獲取，并且可以動(dòng)態(tài)地改變密鑰數(shù)目、數(shù)值以及門限值。同時(shí)，因?yàn)槭褂昧穗p變量單向函數(shù)，參與者的子密鑰可以重復(fù)多次使用。

參考文獻(xià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.

責(zé)任編輯（責(zé)任編輯：黃健）