如何分摊秘密（九·完）

作者：安迁

十二、Shamir分摊法的特点

我们可以列举一些Shamir分摊法的特点，作为比较，我们称第七节中的分摊法为“准入集分摊法”。

Shamir分摊法具有和准入集分摊法同样的安全性。我们从理论上证明了这样的分摊方法不可能在不具备揭开秘密的条件时泄露关于秘密的任何信息。这样的安全性被称为完善保密性。

然后当然是它的高效性。我们已经看到，它克服了第八节中提到的组合爆炸问题。无论n和k是什么，每位分摊者都只需分摊和秘密可能范围一样大小的部分。这是准入集分摊法所没有的。

接下去的一些特点则相当有趣。

最初分摊秘密时必须有个组织人员，他知道整个秘密（如《鹿鼎记》中的摄政王多尔衮），并由他来产生Shamir分摊法中的那个多项式P(x)。这个人有超然的地位，不属于我们讲的分摊秘密的参与者。如果他决定要增加一个参与分摊秘密的人员，也就是原来打算在n人中分摊秘密，现在打算在n+1人中分摊秘密，而保持“其中k人或以上同意则可揭开秘密”中的k不变。那么使用准入集分摊法的话，就会增加不少准入集，需为这些准入集准备独立的秘密分拆，并将这些分拆分别交给准入集中的每个人保管。这样，原来的n个人中的每个人都会收到新的需要掌握的秘密。

而使用Shamir分摊法的话，事情就简单多了。那个组织人员只需用原有的P(x)来对一个GF(N)中从未使用过的新值（同余类）[m]来计算P([m])，并把[m]和P([m])交给新人保管即可，原先参与分摊的人员没有任何新秘密需要接收。

同样地，如果组织人员需要在原参与分摊秘密的人员中去掉一个人，用Shamir分摊法的话，只需这个人放弃原来他分摊的秘密即可，其他人持有的秘密则无需变动。相反，在准入集分摊法下，则需要所有人都放弃和包含此人的准入集有关的秘密。这是Shamir分摊法的灵活性。

上面所说的“放弃原来分摊的秘密”，往往是可能做到的。比如第八节中计算的藏宝图大小约为412MB，只能储存在如闪存盘之类的介质中，而不能记在人脑中。当此人要放弃原来分摊的秘密时，只需毁去储存介质中的文件即可。但是一个很自然的问题就是，如果做不到这点怎么办？闪存盘中的信息是可以被拷贝的，如何保证此人没有暗地里另拷一份？所以如果没有办法保证原来被分摊的这部分秘密能够真正被放弃，这种利用Shamir分摊法的灵活性来“去掉一个人”的办法还是不用为好。

那么如何正确地“去掉一个人”呢？或者更一般地，如果有类似韦小宝的局外人得到了一份或多份秘密（当然份数还没达到揭开秘密的程度），该怎么办？一个直接的方法当然是让那个知道整个秘密的组织人员再重新独立地生成需要分摊的秘密，并交给分摊秘密的诸人，这些人则销毁原来掌握的秘密。可是如果那个知道整个秘密的组织人员不存在了呢？（比如摄政王多尔衮早死了。）按照上面的方法，也许可以选出一个大家信得过的人做那个知道整个秘密的组织人员，先把各人的秘密都寄给他，合起来揭示出原始秘密，再生成需要分摊的秘密。

可是这个方法的缺点是显而易见的。现在会重新出现一个知道整个秘密的人，这往往是不可接受的。另外，这个过程中老的和新的被分摊的秘密需要被寄送，寄送过程也要冒泄密的可能。怎样做才能避免这些问题？

我们重新回忆一下上一节中Shamir分摊法的做法：对n个人，用随机数产生器产生出一个系数在GF(N)内的多项式P(x)，而P([0])就是那个需要被分摊的秘密。接着对n个GF(N)中的点（为简单起见设它们是[1]，[2]，……，[n]）计算出相应的P的值，并把这n个点和与每点相对应的P的值分别分摊给这n人。

现在选一个人（这个人可以选谁下面再讨论），把同余类[0]当作秘密，用Shamir分摊法来产生一个多项式Q(x)（于是Q([0])=[0]），并对参与分摊的每个人计算他对应的那个GF(N)中的点[t]的Q([t])的值，然后将这个值分别寄送给相应的参与分摊人员。每个参与分摊人员收到寄来的值后，将它和原来掌握的那个值相加，作为新的秘密保存，并销毁原来的秘密。现在每个人手中的掌握的秘密（假设此人对应的GF(N)中的值是[t]）是P([t])+Q([t])，也就是多项式P’(x)=P(x)+Q(x)在[t]点的值P’([t])。当有足够多的人同意恢复原始秘密时，他们就可以使用拉格朗日插值法来恢复出P’(x)来。虽然他们再也不能知道原来的P(x)是什么，但这并不重要，重要的是原始秘密P([0])。可是P’([0])=P([0])+Q([0])=P([0])+[0]=P([0])，用P’(x)也同样可以知道原始秘密。这个方法使得最终效果看上去好像原来选取的的多项式其实是P’(x)。

这就把前面提到的“先恢复原始秘密再重新生成多项式”方法的缺点完全克服了。用具体的例子可以更清楚地说明，仍以10人分摊秘密需至少8人同意才能揭晓秘密为例子。

首先用随机数产生器产生出一个系数在GF(N)内的多项式P(x)，P([0])为需要被分摊的秘密。10个人分别拿到P([1])，P([2])，……，P([10])。现在怀疑有某些人掌握的秘密已被外人所知。于是选一个人，用随机数产生器产生出一个系数在GF(N)内的多项式Q(x)，并且有Q([0])=[0]。计算出Q([1])，Q([2])，……，Q([10])，分别寄送给相关各人。各人分别计算P([1])+Q([1])=P’([1])，P([2])+Q([2])=P’([2])，……，P([10])+Q(10)=P’([10])并保存，销毁原来各P值和新得到的各Q值。

如果原先有恶意的外人已经掌握了比如P([1])，P([2])和P([3])，在上面的寄送过程中又截获了Q([3])，Q([4])和Q([5])，那么他只能计算出P’([3])=P([3])+Q([3])，而P([1])，P([2])，Q([4])及Q([5])都毫无用处：和P([1])，P([2])（及P([3])）一起配套使用的其他P值已经不存在，要和它们配套计算P’([1])和P’([2])的Q([1])和Q([2])也不存在了；而没有P([4])和P([5])，则Q([4])及Q([5])显然也毫无用处。于是这个过程就让外人原来掌握的3个值作废了2个，剩下的1个也是因为另化代价截获了新的对应信息才继续保持有效。在最极端的情况下，就算所有寄送的Q值都被截获了，那么此外人原先掌握3个值，现在也还是掌握3个值。但外人要截获信息，显然要付出不菲的代价。而分摊秘密诸人付出的代价，则只是产生和寄收诸Q值而已。

既然这个方法能如此低价而有效地堵住已经泄密的漏洞，于是有条件的话，即使没有泄密的迹象，也可以时不时地实施一下，谁知道是不是真的没有某处泄密了呢？这就是主动防御。

选取产生Q(x)的那个人，可以是分摊秘密众人中的一个，也可以是某个大家都信得过但不参与分摊秘密的人。另外既然此法代价不大，也可同时让几个人产生独立的几个Q(x)，相当于一下子实行好几次主动防御。

值得一提的是准入集分摊法也能采取类似的主动防御行动，即产生对[0]的分摊秘密并寄送给各人，各人收到后和原先掌握的秘密相加。但考虑到每次寄送的信息的规模都和单独一次分摊秘密所需寄送的信息的规模一样，会有组合爆炸问题的准入集分摊法在主动防御方面也是低效的。

当然，Shamir分摊法和准入集分摊法相比也并不是没有缺点。准入集分摊法中揭开秘密的组合条件是相当灵活的，而Shamir分摊法则局限于“n人分摊秘密需至少k人同意”这样的形式。在某些情况下，用Shamir分摊法也可以处理一些其他的组合条件。比如A，B，C，D四人分摊秘密，允许揭开秘密的情况是A与其他任何一人同意，或是BCD三人同意。那么我们可以用“5人分摊秘密需至少3人同意”的Shamir分摊法产生5份分摊秘密，并由A持有2份，其他3人分别持有1份的方法来完成这个分摊。但更一般的组合则无法用Shamir分摊法来模拟。

十三、结语

在上节中我们看到，分摊秘密的方法有许多值得注意的性质，各种性质都和它的实用性有关。寻找符合某些要求的分摊秘密的方法，是这方面的重要课题。

比如说，在本文讨论中，我们都假设参与分摊秘密的各方有可能是好奇的，也就是暗中希望获得其他人掌握分摊的秘密，但总是诚实的，即当需要揭示秘密的那一刻到来时，各方都会把他掌握的那份秘密原样地拿出来以合成原秘密。但在实际中并不总是如此。一个心怀鬼胎的秘密分摊方，有可能伪造他掌握的那份秘密，从而在合成秘密时向其他方揭示出一个错误的秘密，而在暗地里独自合成出真实的秘密。这就牵涉到找到能够验证信息完整性的秘密分摊法。诸如此类的特别性质还有很多，但本篇小文，则就在这里结束了。

参考文献

[1] Beimel Amos, Secret-sharing schemes: a survey. Proceedings of the Third International Conference on Coding and Cryptology, IWCC’11, pp. 11–46. Springer, Berlin, Heidelberg (2011).

[2] 金庸, 《鹿鼎记》, 明河社出版有限公司 (1981).

[3] Adi Shamir, How to share a secret, Communications of the ACM, 22(11):612–613 (1979).