该方案把用户间所分享的秘密作为插值多项式最高项的系数的逆;

1、该方案把用户间所分享的秘密作为插值多项式最高项的系数的逆；为了证实这个方案，我们应该证明它是完善的，即任意的不超过个成员不能得到秘密的任何信息由公开的数据可知在恢复秘密时,各分享者只需公开,而要从得出有关子秘密的任何有用信息等价于攻破模合数平方根问题；同时利用可验证加密的方法可防止用户间的欺诈（1）能防止外来攻击（欺骗） 密码分析员无法从公开数据与中求得的值，即攻击者无法得到分享者的子密钥，更无法恢复系统分享的秘密；退一步讲，密码分析员即使得到个子密钥或者能勾结至多个秘密分享者，这时对于中的每一个整数S，密码分析员能且仅能构造一个次多项式，满足， 由构造的方法可知，这些可能的多项式作为的概率是

2、相等的，从而密码分析员得不到能够帮助他导出的任何信息（2）本文所采用的子密钥传递函数是基于求合数的模平方根的难题，其困难性等价于因子分解问题（3）能防止内部欺骗：在系统参数生成阶段，发送给的应该是一对不同的大素数的乘积可以对此作出检验：首先，对是偶数和形如的数的情形，对此检验是计算上容易的，即上述形式的欺骗是可以检出的；若发送的是个不同素数的积，将不大可能识别这种形式的欺骗；但是这时就不能准确接收子密钥，即反而对不利；因此，不会进行这种形式的欺骗若，（是不同的奇素数），这种欺骗不会对协议产生影响3.3 可验证的动态秘密分享方案从实用性角度看，大数模算术运算不仅速度很慢，而且占用大量的存储空间相

3、反，Merkel-Hellman方法只涉及到四则运算、不涉及指数运算，故其加密和解密速度都很快MH背包密码体制是最早提出来的两个最著名的公钥密码体制之一不幸的是，一次背包体制中大部分均被破译了；这类体制受致命攻击的主要症结在于其背包向量的超递增性和密度过低另外，其存在实现保密性与真实性的差异，以至难以投入实用曹珍富，利用扩展的变换，提出了一个新型的背包体制，使其得到的向量没有超递增性而且密度也相当高以至于，已有的破译方法不能攻击这个体制 新的一次背包体制 这个一次背包体制是已有背包体制的一般向量形式： 密钥的生成（1） 任选三个正整数向量、，其中是超递增向量；（2） 随机选取正整数、和两个不同

4、的大素数、，使得 并且、的长度大致相等；，； （3） 用欧几里德扩展算法计算，满足，； （4） 计算 ，； （5） 公钥为、和 ；密钥为和 加密算法将秘密信息表示成二进制数：，；记为，则得秘文； 解密算法由于已知和，则容易得出： （1） 计算，；然后，验证若等式不成立，则发出一串抱怨并要求对方重新传递信息；否则，是初始的超递增向量与向量的内积； （2） 解简单背包问题，即得明文信息；从而，传送的秘密信息就被恢复出来秘密分享方案假设系统有一个可信的秘密分发者，个参与成员、；是待分享的系统秘密，并且可以表示成二进制数：，记为 ；秘密在个分享者之间分配 系统初始化（1）可信的秘密分发者任选三个正整数

5、向量、，其中是超递增向量； （2）秘密的分享者任选两个数、，使得，、是长度大致相等的两个大素数，并由计算出自己的密钥分享者将公开，同时利用Williams算法把发送给秘密分发者； （3）秘密分发者计算，其中，：， 然后，随机的选取一个大数，使得并且其中是一个安全参数 用、的顺序作用于三个选定的正整数向量、和，构造出向量使其不具有超递增性；则得密文（4）秘密分发者将和发布在公告栏中 秘密恢复系统中的所有成员必须联合起来按一个强制性的顺序来恢复系统秘密（1） 利用其密钥计算：，；并将向量传送给参与者； （2） 成员在接收到向量后，先检验是否与相等若它们不相等，则成员发出一串抱怨并且要求成员重新发送

6、向量；否则，他将自己计算出的向量传送给成员； （3） 参与者在收到并验证传送来的向量后，利用自己的密钥计算， 从而,他就得到秘密的超递增向量，从而恢复出简单加法背包： ，其中满足：，； （4） 容易求解简单背包问题，得向量；从而，恢复出系统秘密 欺诈者的检测 当需要恢复分享的秘密信息时，分享成员中有可能存在内部欺诈者或外部欺诈者，其中内部欺诈者出示假的秘密份额以阻止分享秘密的正确恢复，外部欺诈者是设法参与秘密的恢复以获取秘密信息该机制可以利用下述验证信息有效的检测出系统的欺诈者，保证体制的安全性：假设待恢复的秘密信息是，对于参与者，如果，则为出示了真正秘密份额的合法参与者；否则，为系统的欺诈者

7、 安全性及其性能分析（1）素数、可采用概率判别法快速求得；选定后，可通过欧几里德算法计算得到加密、解密过程都可以通过快速算法实施，总之新的背包公钥密码体制很容易实现；（2）当背包算法中各参量的比特数足够大（如不小于）并且满足文中要求时，就能够抵抗攻击者的无穷搜索；引入扩展的变换使不再具有超递增性，这使得Shamir类型和Brickell类型的攻击方法显然无效由上述分析知，选择满足要求的参量后，直接利用公开的信息攻击新的背包体制，目前还不可行；（3）在恢复秘密时，分享者提供的是屏蔽子秘密由因子分解问题的困难性知，攻击者无法获得每个分享者的子秘密；由背包体制设计的合理性知，攻击者也无法从公开数据确

8、定，所以也无法求出系统的秘密信息；（4）当需要重新分配一个新秘密时，秘密分发者只需刷新公告栏即可；因而，系统有较强的动态特性，可以无限次地恢复不同的秘密信息；（5）当系统需要增加新成员时，选择一个数和，并将它们作为公钥传送给秘密分发者，作为自己的私钥；秘密分发者更新公告栏上的数组即可；当要删除某个成员时，只需重新选择正整数向量、，然后利用它们更新布告栏上的有序数组，此时无需计算，则成员的子密钥无效 结论由于背包算法只涉及四则运算，而不涉及模指数运算，故其加密和解密速度都很快但是这类体制易受Shamir类型和Brickell类型的攻击；同时它存在实现保密性与真实性的差异，因而难以投入实用本文在已

9、有一次背包体制的基础上，提出了一个混合背包算法，使其得到的向量没有超递增性而且密度也相当高；然后，基于新的背包算法，设计了一个可以公开验证的动态秘密分享方案与已知分享方案的主要不同点在于：它可以验证自己的子秘密，可以在秘密恢复过程中便捷的验证其他成员提供的信息以检测出不诚实者；而且，由于整个机制的实现只需要进行四则运算，故它的运行速度非常快、计算量很小3.4 本章小结本章研究的重点在于可验证秘密分享方案的设计在分析了设计这类秘密分享方案应满足的性质（2.2）的基础上，构造了安全有效的基于一些经典插值公式和背包问题的可验证秘密分享方案1. 利用孙子定理和Nevill插值公式设计了一个门限秘密分享

10、方案，该方案基于求有限域上离散对数和模合数平方根的难解问题，能有效的解决利益冲突双方共享秘密的实际问题，并且能够简单的推广至更多方之间共享的情况，所以具有广泛的应用价值2. 基于一个经典的插值定理和模合数平方根的难解问题，设计了一类新型的秘密分享方案；该方案把用户间所分享的秘密作为插值多项式最高项的系数；在恢复秘密时各用户只需公布其所拥有子秘密的屏蔽信息，而且在秘密恢复阶段引入了可验证加密的方法以防止用户间的欺诈行为该方案的另一个显著的特点是能够安全的分享多个秘密；同时，该方案能不需要安全传输信道，整个过程所需的计算量小，是高效安全的3. 提出了一个基于背包算法的动态秘密分享机制它与已知分享方案的主要不同点在于：它可以公开验证成员的合法性，还可以在秘密恢复过程中检测出不诚实者；而且，由于整个机制的实现只需要进行迭代四则运算、模运算和移位，故它的运行速度非常快该秘密分享机制的另一个重要