主题：如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包

先考虑简单的，两个人之间如何分摊秘密。比如那个两个人分摊六位数密码的事情。这俩人是甲和乙。

现在拿一个能均匀地随机地产生0到9之间的数字的随机产生器。

一个好的骰子可以算一个“能均匀地随机地产生1到6之间的数字的随机产生器”。骰子有六面，分别标着1到6的数字，因为是“好的”，掷一次，掷到每个数字的可能性都是一样的，都是1/6。如果那个骰子是灌铅用来出老千的，掷出6的可能性比较大，那就不算好骰子。如果把掷出来的数字减1，它也就是一个“能均匀地随机地产生0到5之间的数字的随机产生器”。要均匀地随机地产生0到9之间的数字，也有办法。现在的计算机程序也能产生一些叫“伪随机数”的数字序列。这些都是技术问题，具体该怎么得到这样的随机数和本文无关，所以就不多说了。反正我们假设现在有这样一个机器，每次我们问它它就随机给一个0到9之间的数字，每个数字出现的可能性都是1/10。

现在老板就让随机产生器产生六个0-9之间的数字，比如735049。把这个数字给甲，这是他掌握的秘密。

然后老板用密码（真正的秘密）123456去逐位减735049。怎么个减法？

1-7 = -6 --> 4

2-3 = -1 --> 9

3-5 = -2 --> 8

4-0 = 4 --> 4

5-4= 1 --> 1

6-9 = -3 --> 7

我们注意到每个结果如果是负的，就加个10让它变成正的，仍在0-9之间的数字。于是老板得到498417，把这个数字给乙，这是他掌握的秘密。

我们看看甲和乙都掌握和知道什么秘密。

甲拿到735049这个数，可是这个数字根本就是老板拿随机产生器产生出来的，跟密码123456没有一点关系，他拿到这个数字，不会增加一点点对密码本身的知识。甲知道了735049这个数字以后，对他来说，所有000000-999999之间这1000000万种可能的密码的范围没有一点改变，每个都有1/1000000的可能是真正的密码。关于这点，他没拿到735049以前就知道了。

乙拿到498417，他会对真正的密码是什么增多点了解吗？不会。真正的密码当然有可能是123456，如果甲的数字是735049的话；但是真正的密码也有可能是999999，如果甲的数字是501581的话。甲的数字可能是000000-999999之间这1000000万种，而且每种都有1/1000000的可能会是甲手里的数字；而每个可能是甲手里的数字，都对应着一个最终的密码。最后乙能推断出来的结论还是：最终的密码是000000-999999之间这1000000万种可能，每个都有1/1000000的可能是真正的密码。可是关于这点，他没拿到498417以前就知道了。

但是一旦甲和乙一起决定要取款了，他们就可以把他们掌握的两个数字逐位加起来：

7+4 = 11 -->1

3+9 = 12 -->2

5+8 = 13 -->3

0+4 = 4 -->4

4+1 = 5 -->5

9+7 = 16 -->6

和减法时差不多，如果结果大于9，就减一个10让它变成仍在0-9之间的数字。我们就得到了密码123456。

总结一下上面我们做到了什么：首先我们用一个6位随机数把密码123456拆成了让甲和乙分摊的两部分。当他们都决定要知道账号密码时，他们掌握的这两部分秘密可以很方便地推断出账号密码（要算几个加减法，但比吭哧吭哧地拼地图碎片方便多了）；其次也是更重要的一点是，甲或乙无法单独地通过自己新掌握的秘密来得到以前不知道的信息。这正是我们希望得到的效果。

我们是怎么证明，甲或乙在获得他们分摊的那部分秘密时，没有增加任何他们以前不知道的信息的？是通过说明，对他们来说，原本账户密码有1000000万种可能，每种的可能性都是1/1000000，而等他们拿到分摊的秘密后，他们知道的还是这样。这跟被告诉了账号密码的前三位或后三位大不一样。

注意到那个随机数产生器必须是“好的”，产生出0-9之间每个数字的可能性都要一样。否则的话，比方说它产生7的可能比产生3的要大，而这点被乙知道了。那么当乙拿到他那部分秘密时，看到比如第一个数字是4，那么真正的账号密码的第一位是7+4=11->1的可能性就要比是3+4=7的可能要大，这样，对于乙来说，1000000万种可能中，每种的可能性不再都是1/1000000，而是有多有少，这样乙就获得了他以前不知道的关于账号密码的信息。同样，如果随机数产生器产生出来的每一位数不是独立的，比方说如果先出来个一个3，后面那位就更容易出来一个5，这样的信息也会让乙推断出他以前不知道的关于账号密码的信息。所以随机数产生器的质量是非常要紧的。

喝水ing

偷偷地溜去看了 wikipedia 上 secret sharing 的条目，呵呵，发现还有一个 Chinese Remainder Theorem，不过智商太低，实在看不懂，只能灰溜溜回来搬个板凳听讲解

前面说到，有一些秘密需要这样被分摊：多个个体中任何一个个体都不单独掌握秘密，但是在所有个体一起决定要揭开秘密时，他们就能够知道完整的秘密。

据说可口可乐的秘密配方也是这么保密的，被拆成了三份，每个人都不知道其他两人的那部分配方。不过我觉得这好像有点问题，可口可乐配方毕竟不像宝藏，大家说挖出来吧，把秘密完整合起来就行了，然后这个秘密就作废了。可口可乐很长时间都会生产。在此就这么一说吧。

有时候电影里有租银行保险箱的情节，保险箱上两个钥匙孔，一把钥匙在银行工作人员那里，另一把则在客户手里，而保险箱要两把钥匙一起开才打得开。这也是一种类似的分摊秘密的方法，分摊的是打开保险箱的权力。

回到《鹿鼎记》的宝藏上，我得说金庸在设计藏宝图这个情节时是有一番考虑的。

比如说，按照陶红英所说，“将收藏财物的秘密所在，绘成地图，由八旗旗主各执一幅”，那么也可以理解成每个旗主都有一幅完整地图。但是这样就有问题了。也许会有某个旗主不告诉其他人，自己偷偷去把财宝掘出。所以这种“多个人里每人都独自地完整地掌握”秘密的方法是不好的，不能满足旗主会议的要求。

如果是绘一张地图，但不割成碎片，只割成面积相同的八块，然后八个旗主一人一块会怎么样呢？稍微想想的话，这也不合适。如果那地图是象动画片里的海盗藏宝图那样，画了宝藏周围地形，然后在藏宝处画个叉号，那么割开的八块小地图上，显然带叉的那块信息量比较大。地图割开以后虽说不完整了，但是还是有可能从局部的特征，比如海岸线的形状啦，山脉的走向啦，猜测到所绘的区域。就算分到的地图小块上没有藏宝处的叉，如果猜出了地图所绘的区域，那么就可以推知宝藏也离此不远。打叉的那块就更占便宜了，要是猜出了局部区域，那就跟拿到完整地图没啥区别。

如果说地图上还有文字说明，那也许更糟。比如宝藏给埋在鹿鼎山了，要是你拿的的那块地图上有鹿鼎两字，那泄露的消息也就够多了。碰上象《基督山伯爵》里法利亚长老那种能把烧掉一半的纸上的文字中缺少的部分猜出来的强人，你撕半张纸给他和把整张纸全给他是一样的，那这就谈不上“分摊秘密”了不是？

所以金庸就设想了先把地图剪成小碎片，再把碎片分成八份的方法。如果剪得足够碎，那么每小片上的地图的局部特征就不明显，加上各人拿到的碎片都是随机的，光凭八分之一的碎片数量就很难拼出较大的局部来。这不失为一种好方法。但是如果只有两个人来分摊秘密怎么办？那时候凭一个人手上的碎片，拼出较大的局部部分还是比较有可能的，而且这个时候拼出来的部分分布在原来的整个地图上，不再聚集在一个角落里，通过观察不完整的地图来得出整幅地图的一些信息也就更有可能。

这种情况在有多个但不是所有人都是同谋的时候更明显。比如八旗中的六个旗主说，另外两个不愿挖宝，但我们六个愿意。结果六个旗主拿了6/8=3/4数量的碎片来拼，就能拼出一幅虽然到处是破洞，但是很可能看得清的地图来。这就违背八旗会议的原意了。虽然说这也可能是个优点，万一八旗中有一旗旗主不小心把他那一份地图搞丢了，剩下七旗也还有比较大的可能可以挖宝，不至于因为不小心丢失一份地图碎片，整个秘密就永远无法揭晓了。

这就提出了一个新问题：怎么样在若干人之中分摊秘密，使得只要在规定人数以上（而不一定是所有人）同意揭开秘密的时候，秘密就可以被揭开，而如果同意的人数低于这个数目，秘密还是无法揭晓？比如八旗会议可以规定，只要有任何六个旗主决定挖宝，他们就可以拼出一幅完整的而不是满是破洞的地图来，但是如果只有五个旗主同意，他们就一定无法拼出地图来，甚至只是多知道一些信息也不行。小说中切成碎片的方法显然不行：六个旗主拼出来的地图会有很多洞，不能保证一定能找到宝藏；五个旗主拼出来的地图要比六个的更破烂一些，但是未必就一定找不到宝藏。

继续喝水……