基于Hermite插值的多密钥共享协议 

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

摘要：（t，n）门限密钥共享方案是一种重要的密码学机制。基于拉格朗日插值法和Hermite插值法提出了多密钥共享协议。使用双变量单向函数，使参与者的子份额能多次重复使用。子密钥可多次使用的性质大大降低了密钥分发的开销。每个参与者自己选择子密钥，分发者则没有欺骗的余地。同时，还利用离散对数问题的复杂性来验证数据正确性。此外，该协议可以动态地改变门限值、密钥数目以及密钥数值大小。

关键词：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.

责任编辑（责任编辑：黄健）