几种秘密共享方案的研究 毕业论文.docx

几种秘密共享方案的研究摘 要秘密共享是保护信息和数据的重要手段，它主要用于保护重要信息和数据，以防止重要信息的丢失、毁坏和篡改。秘密共享已经成为密码学研究的一个重要分支，同时也是信息安全方向的重要研究内容。本文首先介绍了秘密共享的研究现状，然后在此基础上提出了几种安全、有效的秘密共享方案。本文的主要工作表现在以下几个方面:可公开验证秘密共享是一种特殊的秘密共享，由分发者分发的秘密份额不仅能被份额持有者自己验证，而且可以被其他任何成员验证。然而，对于一般的可公开验证秘密共享，敌手可能使用很长的时间，攻破门限个份额服务器，获得秘密。为了解决这个问题，提出了第一个具有前摄能力的可公开验证的秘密共享方案，不仅能够可公开验证份额的正确性，而且具有份额定期更新的性质，这使得方案比其它一般可公开验证秘密共享方案更安全，能够更好地满足各种应用的安全需求。基于齐次线性递归提出了一个新的多秘密共享方案，然后，将其扩展成一个可验证的方案。在秘密分发过程中，只需公布很少的公开参数，在秘密重构过程中，每个成员只需提供伪份额,不会暴露秘密份额，当秘密更改时，不需重新分配秘密份额，实现了秘密份额的多次使用。提出的方案具有秘密份额可以多次使用、公开的参数少以及所要重构多项式的次数小的优点，这使得方案更高效，能够更好地满足各种应用需求。基于元胞自动机原理提出了一种无可信任中心的多秘密共享方案，它和一般的基于元胞自动机的多秘密共享方案不同的是，份额的分发不需要分发者的参与，能够满足没有分发者的情况下也能够实现秘密份额的分发，这使得这种方案能得到更广的应用。 关键词：秘密共享；可公开验证；齐次线性递归；元胞自动机abstractsecret sharing is an important tool for protecting the information and data. secret sharing is used for protecting important information and data from being lost, destroyed or falsified. secret sharing has been one important branch of cryptography and one important research field of information security. this article illustrates the research advances of secret sharing technology, based on which several secure and efficent secret sharing schemes are proposed. this article has finished the following work:a publicly verifiable secret sharing (pvss) scheme is a special secret sharing scheme in which the shares distributed by the dealer can be verified not only by shareholders themselves but also by any other party. however, in a normal publicly verifiable secret sharing scheme, an adversary may get the secret by attacking threshold shareholder servers for a long time. in order to deal with this problem, a publicly verifiable secret sharing scheme with proactive ability is newly proposed, which not only can publicly verify the validity of shares, but also has the property of periodically renewing shares. this makes the proposed scheme more secure than other common publicly verifiable secret sharing schemes, and makes it better satisfy security demand of various applications.a new multi-secret sharing scheme based on homogeneous linear recursion is proposed, and then it is converted into a verifiable scheme. in the distribution phase, very few of public values are needed to publish. in the recovery phase, each participant only needs to submit a pseudo shadow instead of his secret shadow, and his secret shadow cannot be disclosed. when secrets are changed, secret shadows dont need to be redistributed, which makes secret shadow able to be used multiple times. the proposed scheme has many advantages, for example, the secret shares can be used multiple times and the scheme publishes very few parameters as well as the reconstructed polynomial has a low degree. this makes the proposed scheme more efficient. therefore, it better satisfies demands of various applications.a multi-secret sharing scheme without a trusred party based on cellular automata is proposed. it is different from the other multi-secret sharing scheme based on cellular automata, because share distribution does not need dealer. this scheme can also distribute share without dealer. this makes the proposed scheme apply widely.key words: secret sharing; publicly verifiable scheme；homogeneous linear recursion；cellular automata目 录第一章 引言11.1 秘密共享的研究意义11.2 本文的研究内容和取得的成果11.3 本文的组织2第二章 相关工作的研究现状32.1 秘密共享32.2 可验证秘密共享（vss）42.2.1 feldman的可验证秘密共享方案（vss）42.2.2 pedersen的可验证秘密共享方案（vss）52.3 可公开验证秘密共享（pvss）72.3.1 schoenmakers的可公开验证秘密共享方案72.3.2 stadler的可公开验证秘密共享方案92.4 先应秘密共享（proactive secret sharing）102.5 多秘密共享132.5.1 yang等的多秘密共享方案142.5.2 shao等的可验证多秘密共享方案162.5.3 dehkordi等的可验证多秘密共享方案172.5.4 dehkordi等的基于齐次线性递归的多秘密共享方案182.5.5 庞辽军等的多秘密共享方案202.5.6 eslami提出的基于一维元胞自动机的可验证多秘密共享方案212.6 小结23第三章 具有前摄能力的可公开验证秘密共享243.1 预备知识243.1.1 符号定义243.1.2 模型和假设243.2 提出的具有前摄能力的可公开验证秘密共享方案253.2.1 初始化（init）263.2.2 私密钥更新协议（pku）263.2.3 秘密份额更新协议（sku）273.2.4 指控核实协议（acc）283.2.5 损坏秘密份额发现协议（bsd）283.2.6 恢复损坏秘密的份额（ssr）283.3 安全性分析和相关工作比较303.4 结论31第四章 基于齐次线性递归的可验证多秘密共享方案324.1 齐次线性递归的定义324.2 基于齐次线性递归的多秘密共享方案334.3 可验证多秘密共享方案354.4 安全分析384.5 相关工作的比较394.6 结论40第五章 基于元胞自动机的无可信任中心的多秘密共享方案415.1 一维存储元胞自动机415.2 基于元胞自动机的无可信任中心的多秘密共享方案425.2.1 符号说明425.2.2 提出的方案425.3 安全分析445.4 相关工作的比较445.5 结论45第六章 总结与展望46参考文献47攻读硕士学位期间的研究成果51致 谢52学位论文独创性声明53 第一章 引言第一章 引言当今社会，随着计算机网络技术的快速发展，特别是internet的广泛应用，人们的日常生活发生了巨大变化，人们利用网络可以进行网上购物、发送电子邮件以及进行远程教育等。与此同时，网络也给人们带来了信息安全问题，如黑客攻击等。因此，如何保证信息的安全性已成为当今社会十分紧迫的问题，信息安全无疑已成为信息科学领域的重要课题。从而对信息安全方面的研究会带来广泛的应用价值。密码学结合了信息科学、计算机科学和数学等多门学科为一身，它实现了对信息保密功能，保证了信息的完整性，有效地防止信息的篡改。秘密共享作为密码体制的基础，已经吸引了很多学者进行研究。1.1 秘密共享的研究意义秘密共享是把秘密进行分割，而分割后的每一部分叫做份额（或者子密钥），并把这些份额分发给不同的成员，只有多于特定个成员一起合作才能计算出秘密，而少于特定个成员合作时，得不到有关秘密的任何信息。所以，当有少于特定个成员都提供秘密份额时，他们也不能得到真正的秘密。相反，当有某几个成员的份额由于某些原因损坏，只要剩余的成员个数多于特定个，剩余的成员也能够得到秘密。可见，把秘密分发给多个成员不仅有利于保护秘密的安全性，而且还能够保证秘密的完整性，进一步提高了整个系统的安全性与健壮性。秘密共享技术在密钥管理、银行网络管理以及数据安全方面有着非常广泛的应用。另外，秘密共享在数字签名、身份认证等方面也有广泛的应用。1.2 本文的研究内容和取得的成果本篇论文主要研究了几种秘密共享方案，并取得了以下成果：（1） 提出了一个具有前摄能力的可公开验证秘密共享方案，攻击者不断攻击同一个方案时，如何保证方案的安全性问题，提出的具有前摄能力的可公开验证秘密共享方案，不仅能够可公开验证份额的正确性，而且具有份额定期更新（前摄）的性质，使得敌手在前一个时间段获得的份额，在当前时间段中完全失效，这使得方案比其它一般可公开验证秘密共享方案更安全，能够更好地满足各种应用的安全需求。（2） 基于齐次线性递归的思想，提出一种可验证多秘密共享方案，只需公布很少的公开参数，每个成员只需提供伪份额，而不需暴露秘密份额，当秘密更改时，不需重新分配秘密份额，实现了秘密份额的多次使用。这样，秘密份额可以多次使用、公开的参数少以及所要重构多项式的次数小的优点，这使得方案比其它一般的可验证多秘密共享方案更高效，能够更好地满足各种应用需求。（3） 提出了基于元胞自动机的无可信任中心的多秘密共享方案，由于使用了一维元胞自动机的原理，所以在重构秘密时，不需要计算拉格朗日多项式，这样就大大减少了运算量，另外，份额的分发不需要分发者的参与，所以能够满足不需要分发者的情况下也能够完成秘密共享的要求。1.3 本文的组织本文的组织结构如下：第一章是引言部分，介绍了秘密共享的研究意义、研究内容、取得的成果以及本文所做的工作等。第二章介绍了一些秘密共享的研究现状，主要包括：秘密共享、可公开验证秘密共享、具有前摄能力的秘密共享、多秘密共享、可验证多秘密共享、基于元胞自动机的多秘密共享等的一些基本思想及研究状况。第三章提出了一个具有前摄能力的可公开验证秘密共享方案。方案的基本思想是能够对子密钥进行周期性的更新，当重构者成员利用这些更新后的子密钥重构秘密与利用更新前的子密钥重构的秘密相同，方案还能够对子密钥正确性的进行检测，一旦发现有错误的子密钥还能够对错误子密钥进行恢复。第四章提出了一种新的可验证多秘密共享方案，该方案基于齐次线性递归，使得在保证不增加多项式次数的情况下，公开的参数更少。第五章主要对基于元胞自动机的无可信任中心的多秘密共享方案进行研究，文中对方案的安全性进行了分析以及与相关工作进行了比较。第六章全文的总结与展望，概括全文的研究内容以及创新点，并对未来的工作提出了一些设想。 53第二章 相关工作的研究现状第二章 相关工作的研究现状2.1 秘密共享密钥的安全关系着整个系统的安全，传统的密钥保存方法是把密钥交给一个人管理，这样做存在很多缺陷：首先，当密钥持有者不小心泄露了密钥，那么就会对整个系统带来危害；其次，密钥持有者丢失或损坏了密钥，整个系统中的信息就无法使用。为了解决上述问题，我们可以把密钥分发给多个人共同持有，这样人们就提出了秘密共享的思想。秘密共享是一种分发、保存密钥的方法：将密钥分成多个相互关联的秘密信息（称为份额、影子或子密钥）然后再分发给小组中的所有成员，使得小组中的每个成员拿出他们的份额根据既定的方法就可以重构出密钥。每一个根据既定方法都能计算出密钥的小组称为授权子集，而其他子集称为非授权子集，非授权子集不能恢复出秘密。如果对于每个非授权子集都不能恢复出秘密，那么就称为完美的秘密共享。可见，即使某几个（少于特定个）份额持有者泄露了自己的份额，由于攻击者不能得到特定个份额，他也不能重构出秘密，另外，当某几个（少于特定个）份额持有者丢失或损坏了份额，仍然可以恢复出秘密。在实际应用中，使用秘密共享方案可以防止密钥的丢失、损坏或攻击，能够很好地保证密钥的安全性与完整性。秘密共享方案最早由shamir1和blakley2提出，其中shamir提出的基于拉格朗日插值的秘密共享方案是一种比较简单、实用的方案，下面将简单介绍一下shamir的门限秘密共享方案。shamir的方案属于（t, n）门限秘密共享方案，即n个份额持有者成员中的任意t个有效成员都能重构出秘密，假设群体p（|p|=n）中的各成员记作，秘密份额分发者记作d（dealer），要分发的秘密是s，q是大素数，是模q的域。秘密份额分发阶段：首先,分发者d在域上任意选择一个次数最多是t-1次的多项式，使得，而。然后,分发者d再随机选择n个非零的、互不相同的数，其中，对所有的i计算。最后，分发者将秘密地传送给成员，并公开，就是成员的秘密份额。秘密重构阶段：任意t个成员合作可以重构出秘密。假设由任意t个成员组成的集合，根据拉格朗日插值多项式计算出：其中，于是秘密s就是其中。2.2 可验证秘密共享（vss）为了解决分发者的诚实性问题和参与者成员的诚实性问题，提出了可验证秘密共享（vss）。文献3首先提出了可验证秘密共享，而feldman4和pedersen5提出的可验证方案受到了更多密码研究者的青睐，他们的方案中，分发者不仅要分发各成员的份额，而且还公布对多项式系数的承诺，使得各成员在接收到份额时，可以验证自己的份额正确与否，同样，在秘密恢复阶段，当秘密重构者接收到其他成员的份额时，他也可以用同样的方法验证其他成员是否提供了正确的份额。若各成员在验证份额正确性时，不需要和他人交换信息，这种验证方案就是非交互的，反之，就是交互的。下面主要介绍feldman-vss方案和pedersen-vss方案，前者在计算上是安全的，后者在信息论上是安全的。2.2.1 feldman的可验证秘密共享方案（vss）参数设置：p,q都是大素数且有q|(p-1)，是中唯一的q阶乘法子群，秘密是s，随机选取。feldman的可验证方案：（1）分发者d随机选择多项式，满足，。（2）分发者d计算，并把通过秘密通道发送给成员。（3）分发者d计算承诺并广播。（4）成员接收到和广播的后，计算下式是否正确来确定份额的正确性： 2-(l)（5）任意t个成员的集合b拿出他们的份额，利用拉格朗日插值计算s： 2-(2)其中 ，然后根据公开信息来验证s的正确性：。事实上，式2-(l)之所以成立是因为：。2.2.2 pedersen的可验证秘密共享方案（vss）参数设置：p，q为大素数且q|(p-1)，记中唯一的q阶乘法子群为。秘密，随机选取，任何人都不知道。承诺的实现：首先选取，然后计算承诺，公开。可验证秘密共享方案如下：（1）分发者d随机选择多项式并且满足，然后计算。（2）分发者d随机选择多项式并且满足，然后计算。（3）分发者d秘密地将发送给成员，并广播对多项式系数的承诺。（4）成员接收到后，可根据下式来验证份额的正确性： 2-(3)（5）任意t个成员的集合b拿出他们的份额，可用拉格朗日插值计算秘密s和参数k：，其中，通过下式来验证s的正确性： 2-(4)事实上，式2-(3)之所以成立是因为：。 很显然，以上两种方案都是非交互式vss方案，在秘密分发过程中，不需要分发者和参与者成员的交互，以及各成员之间的交互，所以是一种比较高效的vss方案，但是在实际应用中，比如电子选举和可撤销匿名性的电子支付协议中，各成员不仅要知道自己的份额是否正确，而且还要知道其他成员的份额是否正确，可公开验证秘密共享解决了这一问题。2.3 可公开验证秘密共享（pvss）文献6和文献7分别是schoenmakers和stadler的可公开验证的秘密共享方案，下面分别介绍这两种方案。2.3.1 schoenmakers的可公开验证秘密共享方案参数设置：p，q为大素数且q|(p-1)，记中唯一的q阶乘法子群为，分发者d将一个形式为的秘密s（即）在n个成员中分发，各成员收到其加密子密钥（也叫加密份额），其中是成员的私有信息，故只有成员自己才能从中解密出。初始化阶段：设g，g是独立选择的群中的两个生成元，所以没有人知道g相对于g的离散对数。各成员随机选择一作为其私钥，而将作为其公钥。秘密分发阶段：分发者d随机选取，并将作为秘密分发给n个成员。分发者首先构造一个次数最多为t-1次的多项式 其中 分发者公开对系数的承诺和加密子密钥：，最后令。分发者d要用知识证明来证明的有效性、一致性，即满足：，对于每个，分发者d随机地选取并计算：利用hash函数h计算c如下： 2-(5)其中 “”是指两个比特串的连接，hash函数具有单向性，即由结果c推不出。计算。分发者d公布所构造的证据。子密钥验证阶段：验证者利用公开信息计算，然后再利用及c验证各成员收到的加密子密钥是否有效。首先计算然后代入2-(5)式验证是否成立。若成立，则说明分发者分发的加密子密钥有效，反之，则无效。秘密恢复阶段：成员利用私密钥计算子密钥，然后将和公布以证明确实是从中解密出来的，也就是说向所有人说明他知道某个使得且，的构造和的构造一样。若至少有t个成员已恢复子密钥，利用拉格朗日插值函数计算s： 2-(6)事实上其中。2.3.2 stadler的可公开验证秘密共享方案参数设置：p，q为大素数且q|(p-1)，记中唯一的q阶乘法子群为，设g，h是独立选择的群中的两个生成元，所以没有人知道g相对于h的离散对数。分发阶段：（1）分发者d随机选取多项式，满足，然后计算。（2）各个成员任意选取自己的私密钥并且公开他的公共密钥。（3）分发者d任意选取计算。令，那么，于是，若示证者给出的是错误的，那么他构造的数能写成的形式的概率是很小的。示证验证阶段：（1）分发者d任意选取，计算，计算r=，其中表示下式中的第i比特位， 2-(7)（2）验证者利用已知的 计算：，将他们代入式2-(7)验证是否成立，若成立，说明分发者分发的份额是正确，反之，则说明分发的份额是错误的。其中获取份额阶段：成员利用已知的和自己的私密钥计算份额：2.4 先应秘密共享（proactive secret sharing）秘密共享、可验证秘密共享和可公开验证秘密共享都能很好的提高密钥的安全性。但有些长期使用的密钥（如ca的密钥），如果受到敌手长期不断的攻击，敌手就有可能逐一的攻破多个服务器成员，那么就有可能重构出密钥。先应秘密共享很好地解决了上述问题，它是通过周期性的更新所有成员的份额，如果敌手在一个时间段内没有攻破足够多（多于门限）的份额，那么在下一个时间段他得到的份额信息完全失效，使得秘密信息更加安全。一个时间段一般都是比较短的时间，而利用新份额重构重构出密钥保持不变。ostrovsky8第一次在语境安全系统中提出了动态敌手模型，文献9比较系统全面的给出了如何解决密钥的永久泄露问题，文献10是一个可公开验证的先应秘密共享方案。下面主要介绍一下herzberg9的先应秘密共享方案。初始化阶段：分发者把秘密x分成n份 ，分发给每一个成员，每个持有，其中，。是记录非法成员的集合，初始值。成员生成其公私钥对，他自己隐藏，广播公钥。每个都拥有一个集合。私密钥更新协议：此协议在子密钥更新协议和子密钥重建协议之前运行，运行如下：成员首先选择新的公私钥对并广播，然后用签名并广播，其他成员用验证对的签名。子密钥更新协议：式子中的t-1表示在第t-1个周期。我们可以构造一个次数是k的多项式，其中，那么 ，每个成员的子密钥 。构造，其中是每一位成员自己构造的次数为k的常数项为0的多项式，也即 。在t时期可验证子密钥更新协议如下：（1）任意构造多项式 计算（2）计算， ， 表示对加密。（3）广播， 及其 。（4）对每个成员接收到成员发送的信息后，验证下式是否成立： 2-(8)（5）如果经成员验证所有信息都是合法的，他就会向其他人广播说“他得到的信息是正确的”。若不正确执行指控核实协议。（6）如果所有服务器收到的信息都是正确信息，那么他们会各自更新自己的份额，并计算，并销毁及其它接收到的有关信息。（7）若有成员发现某个成员给他发送的信息不正确，他将有两种处理方法，其一：不让其参与第（6）步；其二：重启他的服务器让其重新生成多项式。指控核实协议：当成员发出的消息错误时，第一种是错误的时间段、数据越界等；第二种是同一服务器发送多条含有有效签名的信息或根本就没有发信息；第三种错误是等式2-(8)不成立。第一种第二种错误任何其他成员都可以检测。每个成员把j放入“坏服务器”集合中，即，启动“reboot”操作，并调用子密钥恢复协议。对于第三种错误：当成员发现发出的信息不满足2-(8)式时，其他服务器需要验证谁在说谎。成员公开其他成员验证：和2-(8)是否成立。若都成立则说明成员在说谎，把i放入坏服务器集合中，即执行操作，对启动reboot操作，并调用子密钥恢复协议；若不成立，对进行以上操作。损坏子密钥发现协议：当某些服务器没有参与子密钥更新阶段或更新被敌手攻击但没有被发现，因此需要定期地对所有服务器进行检测。每个成员都广播和对其的签名。当得到所有的广播，他检测签名的正确性，再通过比较每一服务器和大多数服务器的不同决定哪个服务器是不诚实的，并将这些服务器加入到中，调用恢复损坏子密钥协议进行恢复。恢复损坏子密钥：需要恢复的子密钥 d=ab。（1）每个成员，在上构造一个最高次项为k阶的多项式且满足。构造方法：任取多项式系数 那么（2）对每个成员，广播 。（3）对每个成员，令 并把发送给。（4）根据这些份额插值算出。这是因为每个构造的多项式那么 成员根据这些， 插值多项式g(x)，仅仅具有的性质与其余的没有任何关系（即得不出每个）这保证了每个成员子密钥的秘密性。2.5 多秘密共享在（t, n）门限秘密共享方案中，由n个人共享一个秘密，任意t个被授权人就可以恢复出秘密。但是如果由n个人共享多个秘密，就需要针对每一个所要共享的秘密，分别进行多次秘密共享方案，很显然，这种秘密共享方案的计算量和通信量的开销都很大。为了减少开销，就产生了多秘密共享方案。在（t, n）门限多秘密共享方案中，在一次秘密分发过程中，多个秘密同时进行分发，而在秘密重构时，也是多个秘密同时进行重构。这样，多秘密共享方案大大减少了系统的开销，达到了和共享单个秘密相同的系统开销。1994年，jackson等11人把多秘密共享方案分成两种类型：一次使用的多秘密共享；多次使用的多秘密共享。同年，he和dawson12提出了一种基于单向函数的多秘密共享方案，在他们的方案中，需要公开pn个公共参数。为了减少公共参数的个数，harn13提出了一个可替代方案，他们的方案需要公开的参数比he和dawson12公开的参数少，仅需要公开p(n-t) 个公共参数。1995年，he和dawson14提出了基于双变量单向函数动态多秘密共享方案，双变量单向函数的应用很好地解决了秘密份额泄露的问题。harn15提出了基于拉格朗日插值多项式和dsa类型的数字签名16,17的门限多秘密共享方案。2000年，chien等18 提出了基于系统块编码的多秘密共享方案，在他们的方案中，他们指出harn15的方案不适合一般的多秘密共享使用，而他们提出的方案有以下几个优点：允许类似的秘密重构；秘密持有者可以动态的决定要分发秘密的个数；重构生成矩阵简单高效；多次使用的方案；计算效率很高。相比较方案12-14来说，chien等的方案需要公开的公共参数更少。2004年，yang等19利用拉格朗日插值构造出一种和chien等18同效率的多秘密共享方案，shao20利用了feldman4的可验证思想，将yang的方案改造成可验证多秘密共享方案，此方案解决了分发者和重构者成员的欺骗性问题，不过份额是通过秘密通道进行分发的。庞辽军于2005年和2006年提出的基于shamir方案的多秘密共享方案21和一个有效的（t，n）门限多重秘密共享体制22在yang的基础上进一步减少了公开参数的个数。2006年，zhao23提出的方案中，份额不需要通过秘密通进行分发，2007年，dehkordi24提出了另一种形式的不需要通过秘密通道就可以分发份额的方案。2008年，dehkordi等25提出的基于齐次线性递归的多秘密共享方案，不仅减少了所需重构多项式的次数，而且又进一步减少了公开参数的个数，是一种高效的方案。同年，他提出的基于非齐次线性递归和椭圆曲线的多秘密共享方案26和文献25中的方案具有同样的高效率。后来，有人基于元胞自动机理论提出了多秘密共享方案。2009年，wang27等人提出的方案中，秘密定期改变，分发者定期公开增加系统健壮性的信息，此外，参与者可以对接收到的信息进行验证。每一个参与者仅仅持有一个永久的私密钥，参与者中的某些成员可以在不同的阶段，在不泄露他们的私密钥的情况下重构秘密，因为一些公开信息是不断更新的，而旧的信息对于下一阶段秘密的重构没有任何帮助。2010年，elsami基于双线性映射提出了可验证多秘密共享方案28，不需要安全通道，重构阶段参与者可以验证参与重构的份额，提出的方案是多次使用的秘密共享，并且更新公开信息时是高效的，因此，提出的方案具有wang27的所有优点。此外，还有两处改进，第一，更改秘密时，公开的公共参数更少，第二，一次共享秘密的个数不受限制。同年，das基于单向冲突抵抗哈希函数提出了可更新多次使用多秘密共享方案29，当同时受到攻击时，即使成员的伪份额被泄露，方案也是安全的。2011年，hsu提出了理想的线性多秘密共享方案30，每一个授权子集都有不同的目标秘密，特别地，他们利用单调生成程序提出了构建这种方案的一般方法。而在他提出的基于单调生成程序提出的理想的线性多秘密共享方案31中，参与者集合的每一个子集都有联合的秘密。2.5.1 yang等的多秘密共享方案参数选择：假设是k个秘密，是n个成员，是一个双变量单向函数。分发者任意选择n个秘密份额，通过秘密通道分别分发给n个成员。份额分发阶段：当时，分发者执行以下步骤完成秘密份额的分发：（1）分发者选择大素数q， 然后选择一个次数是t-1的多项式：其中。（2）计算，其中。（3）公开。当时，分发者执行以下步骤完成秘密份额的分发：（1）分发者选择大素数q， 然后选择一个次数是k-1的多项式：其中。（2）计算，其中。（3）计算，其中。（3）公开。秘密重构阶段：当时至少t个成员拿出他们的伪份额，由已知的t对，利用拉格朗日插值重构多项式： 2-(9)当时至少t个成员拿出他们的伪份额，由已知的t对和公开的k-t对，利用拉格朗日插值重构多项式： 2-(10)他们的方案基于拉格朗日插值，是完美的门限秘密共享。不过他们的方案也存在一下两个问题：分发者的诚实性问题和重构者的诚实性问题。2.5.2 shao等的可验证多秘密共享方案shao等20利用了feldman4的可验证思想，将yang的方案改造成可验证多秘密共享方案，参数选择和yang的差不多，选择一个大素数p，并且满足q|(p-1)，g是gf(p)上的阶为q的生成元。秘密分发阶段：当时，分发者执行以下步骤完成秘密份额的分发：（1）分发者选择一个次数是t-1的多项式： 2-(11)其中。（2）计算，其中。（3）计算，其中，计算，其中。（4）公开。（5）成员通过计算下面的等式来验证他的秘密份额是否成立： 2-(12)当时，分发者执行以下步骤完成秘密份额的分发：（1）分发者选择一个次数是k-1的多项式：其中。（2）计算，其中。（3）计算，其中。（4）计算，其中。（5）公开。（6）成员通过计算下面的等式来验证他的秘密份额是否成立： 2-(12)秘密重构阶段：（略）参考yang的多秘密共享方案。shao 提出的可验证的多秘密共享方案，很好地解决了分发者和重构者成员的欺骗性问题，不过份额是通过秘密通道进行分发的。zhao23和dehkordi24的方案都解决了这个问题。2.5.3 dehkordi等的可验证多秘密共享方案首先，份额分发者选择两个大素数，计算。然后，分发者选择一个和互素的整数e，并根据e计算d，使之满足。选择大素数p，满足在上计算离散对数是困难的，选择，最后公开。初始化阶段：每一个参与者成员都选择自己的份额，并通过公共通道发送给分发者，具体步骤如下：（1）参与者成员任意选择作为他的份额，计算，然后把的值发送给分发者d。（2）d计算，其中。（3）分发者d必须确定对所有的，否则，就让成员或重新选择他们的份额，直到所有人的份额都不一样。然后分发者选择一个整数r，并计算，公开。构建阶段：当时，分发者d执行以下步骤：（1）分发者选择大素数q， 然后选择一个次数是t-1的多项式：其中。（2）计算，其中。（3）公开。当时，分发者执行以下步骤完成秘密份额的分发：（1）分发者选择大素数q， 然后选择一个次数是k-1的多项式：其中。（2）计算，其中。（3）计算，其中。（3）公开。验证阶段：重构者成员通过计算下面的等式来验证参与者成员是否提供了正确的份额： 2-(13)恢复阶段：（略）。 dehkordi的可验证方案和shao的方案不同之处就在于秘密份额分发方式的不同，前者是成员自己选择份额，而后者是分发者选择份额并通过秘密通道发送给各成员，这种情况下存在分发者欺骗的问题，即他有可能发送错误的份额。2.5.4 dehkordi等的基于齐次线性递归的多秘密共享方案下面是dehkordi25等的基于齐次线性递归的多秘密共享方案的详细介绍。初始化阶段：假设表示k个秘密，表示n个成员，是一个双变量单向函数，能够将任意长的r和s映射为固定长度的函数值。首先，份额分发者选择两个强的大素数并计算，任何人在知道n的情况下要想得到和是困难的。然后，分发者选择一个和互素的整数e，并根据e计算d，使之满足。分发者选择大素数p，满足在上计算离散对数是困难的，选择，分发者再任意选择一个大于零的整数，把作为辅助等式。最后任选一个素数，公开。每个成员任意选择作为他的秘密份额，计算，然后把发送给分发者，分发者验证确保对所有的时，否则让成员或重新选择秘密份额。构建阶段：分发者执行以下步骤完成秘密的分发：（1）任意选择r，对计算，。（2）构建下面的等式： 2-(14)（3）计算。（4）计算，计算。（5）公开。验证阶段：重构者成员通过计算下面的等式来验证参与者成员是否提供了正确的份额：恢复阶段：假设t个成员拿出他们的份额计算：现在有t对，利用拉格朗日插值计算次数是t-1的多项式：因此，所要重构的秘密：。2006年，庞辽军等22提出的方案没有把秘密隐藏在多项式的系数里，而将秘密当做构造多项式的数值对的一部分，所构造多项式的次数只与成员的个数和秘密的个数有关，而与门限个数无关。2.5.5 庞辽军等的多秘密共享方案参数设置：假设表示k个秘密，是一个双变量单向函数，q是一个大素数，系统中所有的参数都是gf(q)中的数。分发者任意选择n个秘密份额，并选取n个不同的随机数作为每位成员的身份标识。秘密分发：（1）分发者d随机选取一个整数r，对所有的计算。（2）根据构建多项式。（3）从集合中拿出最小的n+k-t个数，计算。（4）公开。重构阶段：不失一般性，假设选取的t个重构参与者是，这t个参与者拿出他们的伪份额组成t个数值对，再从集合中拿出最小的n+k-t个数，结合所公开的组成另外n+k-t个数值对，用表示这n+k个数值对，利用这些数值对就可以重构出n+k-1次多项式:。于是所要重构的k个秘密就是。2.5.6 eslami提出的基于一维元胞自动机的可验证多秘密共享方案元胞自动机最早是由von neumann32于1966年提出的。元胞自动机具有以下特点：组成单元的简单规则性；单元之间的局部互连性；信息处理的并行性；复杂的全局特性，以上特点使之适合应用于密码学中。在1985年美国密码学年会上，wolfram33 首次把元胞自动机的概念引入到秘密共享中，他把元胞自动机的初始序列作为密钥，利用元胞自动机的迭代功能产生一个随机序列作为密码。自此，人们提出了很多基于元胞自动机的密码系统，不仅应用于文本文件（见文献34-37），也被应用于图像文件（见文献38,39）。而真正应用于密码学中的自动机我们称之为可存储元胞自动机（memory cellular automata），可存储元胞自动机是由有限数量的元胞组成的一种离散的动态系统，这些元胞的状态是不断变化的40,41。文献42利用一维可存储元胞自动机构建了秘密共享方案，被证明是完美的和理想的。文献43利用二维元胞自动机对二维图像共享分发，并提出（n，n）门限方案。eslami44基于一维元胞自动机提出了可验证（t，n）门限多秘密共享方案，并且秘密的个数不受t和n的限制。下面是eslami方案的详细描述：参数设置：分发者d，秘密的个数是k，共享的秘密是，份额的最大位长度是l，参与者是，在成员间分发的份额是，一维可存储元胞自动机的邻域半径是r，一维可存储元胞自动机的院元胞个数是n。初始化阶段：分发者执行以下步骤完成对元胞自动机的构建：（1）选择一素数p，使得离散对数在有限域上是难解的，在选择循环群上的一个生成元g，公开p和g。（2）选择r满足，令n=l。（3）随机选择并公开t-1个数，并且对所有的 满足。（4）构建一个阶为t的可逆的一维可存储元胞自动机m：其中，是局部转移函数。（5）计算初始配置当时，令，任意选择长度为n的二进制串作为。当时，令。共享阶段：分发者通过执行以下步骤来分发份额：（1）任意选择一个数m，满足。（2）计算初始配置为，阶为m+n-1的m的演化：。（3）当时，计算，公开。（4）令。（5）计算。（6）公开。验证和恢复阶段：恢复秘密需要有t个连续的成员，假设t个连续成员的份额是，这k个秘密的验证和恢复过程如下：（1）每个成员都可以通过计算下面的式子是否成立来验证第j个成员的份额是否正确，。（2）如果所有的份额都正确，他们就可以利用公开的信息计算，然后演化次，得到。（3）所要重构的秘密是：当时，。当时，。2.6 小结本章回顾了秘密共享的发展，介绍了秘密共享、可验证秘密共享、可公开验证秘密共享以及多种多秘密共享方案，为以后的章节奠定了理论基础。首先，鉴于可公开验证秘密共享中，攻击者持续不断地攻击各成员的份额而重构出秘密的问题，本文提出了具有前摄能力的可公开验证秘密共享，它通过周期性地改变各成员的份额，使得攻击者在前一周期获得的份额在该周期中无效，即攻击者只有在同一周期中攻破足够多的份额才能重构出秘密。其次，鉴于多秘密共享方案中如何减少公开参数与如何减少重构多项式的次数问题，基于齐次线性递归，提出一种可验证多秘密共享。最后，针对基于元胞自动机的多秘密共享方案中没有可信任中心时，如何解决份额分发的问题，提出了基于元胞自动机的可信任中心的多秘密共享方案。这三个问题将分别在第三章、第四章和第五章中详细介绍。第三章 具有前摄能力的可公开验证秘密共享第三章 具有前摄能力的可公开验证秘密共享秘密共享是信息安全方向的一个重要分支，它是安全多方计算的理论基础，在保证计算机及网络安全方面具有重要的作用。1979年，shamir1和blakley2分别基于lagrange插值多项式和射影几何理论最先提出了门限秘密共享方案。文献4,7分别提出可验证和可公开验证秘密共享，它解决了分发过程中分发者的诚实性问题和秘密重构过程中份额持有者的诚实性问题。herzberg等人9最先提出前摄秘密共享，可定期地对每个秘密份额进行更新，从而使得攻击者在前一个时间周期内获得的秘密份额完全失效。文献10则提出了先动的可公开验证服务器辅助秘密共享。提出了一种具有前摄能力的可公开验证秘密共享方案。首先，执行一个初始化协议，分发者生成秘密x的n个秘密份额，使用变形的elgamal加密分发将其分发给n个服务器成员，每个服务器成员都可以对任意一个份额进行验证。每过一个时间周期，执行一个秘密份额更新协议，这n个服务器成员更新他们的份额，而对传送的信息的验证是可公开的。如果验证某个服务器成员发送的信息是错误的，就把它放入坏服务器集合，并执行重启操作，调用恢复损坏秘密份额协议重新生成秘密份额。这种前摄的属性对于保护长时间有效的秘密（如ca的签名密钥）十分有效。3.1 预备知识3.1.1 符号定义是大素数，满足。是中唯一的q阶乘法子群， 是中的两个生成元。是表示第个服务器成员（i=1,n）。表示第t个时间周期中的函数，表示第t个时间周期中的变量。表示第i个服务器成员用来记录非法服务器成员的集合，初始值。表示在第t时期的公私钥对，是的私钥，是的公钥。3.1.2 模型和假设假定系统由n个服务器成员构成，使用的是（k+1，n）门限