无可信第三方的可验证多秘密共享

    朱锦华

    

    

    

    摘 要：一般秘密共享方案需要有可信第三方作为分发者进行秘密分配，实际应用中，不存在完全可信的第三方，因此已有方案均存在安全隐患，降低了实用性。为提高方案的实用性，提出了一种无可信第三方的可验证多秘密共享方案。方案利用哈希函数作为安全假设，减少了计算开销。通过广播消息避免了对安全信道的需求并且降低了通信代价。方案无需无可信第三方，提高了秘密共享方案的安全，方案一次可共享多个秘密，且可验证秘密份额的有效性。

    关键词：秘密共享；可验证；无可信第三方

    秘密共享是密码学中密钥管理的重要分支之一，最早由Shamir提出。Shamir的（t， n）门限共享方案基于多项式插值实现的，该方案准许诚实的分发者将秘密S分成n份子秘密发送给n个参与者，使得大于等于t个分发者可以重构秘密S，任意小于t个参与者无法获得秘密的信息。秘密共享思想得到广泛应用，如电子投票、电子拍卖、数字签名等。

    Shamir门限共享方案具有简单、实用的特点，但方案仍存在不足。首先，方案为单秘密共享方案，共享效率较低；其次，方案可能存在欺骗攻击，在秘密重构阶段，参与者可能发送虚假子秘密导致重构失败；最后，完全可信的第三方现实中不存在，实际应用中存在安全隐患。为解决上述问题，有的方案提出了多秘密共享方案，方案一次可共享多个秘密，有效的提高了共享效率。方案1提出了可验证的秘密共享方案，方案可验证子秘密的有效性，有效的解决了参与者的欺骗的攻击。而针对分发者的诚实问题，方案2提出了抗泄露的秘密共享方案，有效防止半诚实分发者存在的攻击，但只可共享一个秘密。方案3基于离散对数问题提出一种无可信中心的可公开验证秘密共享方案，但方案计算与通信开销较大。

    为解决上述文献存在的问题，综合已有方案的优点，本文提出了一种无可信第三方的可验证多秘密共享方案，方案利用单向哈希函数简单易于实现的优点，实现子秘密的验证过程，有效的降低了计算开销，方案采用由参与者共同创造多项式系数的方式，降低了分发者的权限，可以有效的抵抗半诚实参与者的攻击。

    一、预备知识

    （一）单向哈希函数

    单向哈希函数是指具有单向性和抗碰撞性的哈希函数H。

    （1）单向性：已知H（x），计算满足y = H（x）的x是困难的。

    抗碰撞性：对于x的哈希值H（x），找到x满足H（x） = H（x）是困难的。

    （二）半诚实分发者

    半诚实分发者不同于传统的欺骗分发者直接发送假的秘密份额，半诚实分发者只是将秘密信息隐藏在有效的子秘密中，具有一定隐蔽性而且打破了秘密共享的门限限制。

    （三）无可信第三方的可验证多秘密共享

    无可信第三方的可验证多秘密共享方案是一种符合正确性、安全性、可验证性的多秘密共享方案。

    正确性：如果分发者是半诚实分发者，那么由任意不小于t个参与者提供的秘密份额能够正确重构秘密S。

    安全性：如果分发者是半诚实分发者，那么通过任意小于t个参与者提供的秘密份额将无法得到任何关于秘密S的信息。

    可验证性： 如果分发者是半诚实分发者，那么参与者可以验证分发者分发的秘密份额的有效性，分发者D也可以验证参与重构的参与者提供的秘密份额的有效性。

    三、方案分析

    （一）正确性分析

    定理1 分发者是半诚实的，方案可保证任意大于等于t个参与者正确恢复k个秘密。

    证明：根据半诚实分发者定义，当方案执行时，分发者按照方案执行。参与者Pi正确计算子秘密f （ i ） ，并且诚实提供子秘密。根据拉格朗日插值，已知大于等于t个多项式函数值可唯一确定一个t-1阶多项式。因此，参与者可以正确恢复f （0）， 利用公布的gi，进而恢复k个秘密。

    （二）安全性分析

    定理2 分发者是半诚实的，方案可保证小于t个参与者无法获得任何关于秘密的信息。

    证明：根据半诚实分发者定义，分发者按照方案执行。根据方案描述，公布的信息包括gi， vi， f （i） ，其中已知gi，未知f （0）敌手无法获得任何秘密的信息。又因为vi =H（f （i） ），根据哈希函数单向性，已知vi，敌手无法获得任何关于f （i） 的信息。由于公布的f （i） = ri + f （i） 中ri为每个参与者选择的随机数，因为即使公布 f （i）每个参与者也不能获得多余的有效子秘密。假设有t-1个参与者{P1， P2， ...， Pt}试图恢复秘密，根据拉格朗日插值定理，t -1个函数值只能唯一确定t -2阶多项式，而f （x）为t-1阶，因此t-1个参与者无法得到任何关于f （0）的信息，即无法重构k个秘密。

    （三）可验证性分析

    定理3 分发者是半诚实的，方案可使参与者验证个人计算的子秘密是否正确；在重构阶段，每个参与者可验证其他参与者发送的子秘密是否有效。

    证明1：假设参与者不具可验证性，即参与者可半诚实分发者发送的虚假秘密份额。假设分发者公布消息为，根据方案描述，参与者利用随机数ri计算秘密份额，利用哈希函数计算并和vi比较：

    根据方案，参与者要求分发者重新发送，因此，与假设矛盾，方案参与者具有可验证性。

    证明2：在秘密恢复阶段，每个参与者接受其他参与者的秘密份额，根据方案描述，参与者在接受到所有子秘密后，计算秘密份额的哈希值，并判断是否与vi相等，，当验证通过后进行秘密恢复，因此方案秘密恢复阶段，参与者具有验证性。

    四、方案比较

    本文方案在共享秘密个数，安全假设以及是否依赖可信第三方上具有较大优势。多秘密共享表示共享秘密个数，安全假设描述方案计算负责度，是否依赖可信第三方是指方案分发者是否完全诚实。根据对已有文献研究，对比结果如表1：

    表1中Y表示具有该项性质，N表示不具有该项性质。在安全假设中hash、RSA、DLP分别表示单向哈希函数、RSA假设、离散对数问题。根据对比分析，本方案属于多秘密共享发难，方案使用单向哈希函数作为安全假设，增强了实用性，方案不需要依赖可信第三方，降低方案的条件限制，提高了方案的安全性以及实用性。

    五、总结与展望

    本文提出了一种无可信第三方的可验证多秘密共享方案，方案无需诚实的分发者进行秘密分发，降低了已有方案的限制条件，使得方案更具有实用性；方案基于单向哈希函数，方案无需花费较大的计算开销。

    参考文献：

    [1]Shamir A. How to share a secret [J]. Communications of the ACM， 1979， 22（11）： 612-613.

    [2]Li H， Sui Y， Peng W. A viewable e-voting scheme for environments with conflict interest[C].//Proceeding of the 2013 IEEE conference on communcication and network security， 2013：251-259.

    [3]Peng K. Secure e-commerce based on distributed processing[C].//Proceeding of the 12th international Conference on Parallel and Distributed Computing， PDCAT 2011：406-411.

    [4]Huang X Y， Liu J K， Tang S H， et al. Cost-effective authentic and anonymous data sharing with forward security[J]. IEEE Transaction on computers，2015，64（4）：971- 983.

    [5]Carpentieri M， Santies D， Vaccaro U. A perfect threshold secret sharing scheme to indentifiy cheaters Designs[J].Codes and Cryptography， 1994， 5（3）：183-187

    [6]Chang T Y， Hwang M S， Yang W P. An improvement on the Lin-Wu （t， n） threshold verifiable multi-secret sharing scheme [J]. Applied Mathematics and Computation， 2005， 163（1）： 169-178.

    [7]Young L， Yung M. Kleptography： Using Cryptography Against Cryptography [C] // Advances in Cryptology- EURO CRYPT97. Berlin， Heidelberg： Springer-Verlag， 1997： 62-74.

    [8]Jun S. Efficient verifiable multi-secret sharing scheme based on hash function [J]. Information Sciences， 2014， 278（9）： 104 - 109.

    [9]limid R F. Dealer-Leakage resilient verifiable secret sharing [EB/OL]. Cryptology ePrint Archive， 2014.

    [10]Harn L， Fuyou M， CHange C C. Verifiable secret sharing based on the chinese remainder theorem[J].Security and Communication Networks， 2014， 7（6）： 950-957.

    [11]于佳，陈养奎，郝蓉等. 无可信中心的可公开验证多秘密共享[J]. 计算机学报， 2014， 37（5）： 1032.