主题：如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包
（首先声明，这是篇讲数学知识的文章，虽然这么说大概会赶走不少读者……）
这个世界上有很多秘密。所谓的秘密，就是不希望让不该知道的人知道的一些信息。
有些秘密是属于个人的，比方说大伙上西西河的密码，这个密码除了用户本人以外，其他人都不该知道；就算是家中LD也要上西西河，那么让她自己也注册一个账号，她自己有自己的密码也就是秘密，俩人互不相干。这种只属于某个个体的秘密，不在本文谈论的范围之内。本文谈论的是“如何分摊秘密”，只有一个人拥有的秘密谈不上“分摊”。
但是如果家里是个比较厉害的LD，她非要有你的西西河密码，比如说出于某种考虑想看看你的短信息啦什么的。这样你的密码连她都知道了，这算不算“分摊秘密”呢？也可以算，但是还是不属于本文谈论的范围，因为这个秘密其实是你们每个人都单独拥有了，每个人都知道完整的密码，就算只有一个在场，没有另一个，照样可以用密码登录西西河。这属于多个人里每人都独自地完整地掌握了同一个密码的情况。本文也不谈论这种“分摊秘密”，因为这秘密好像没“摊开”。
那我想说的到底是哪种““分摊秘密””呢？金庸的《鹿鼎记》里有个好例子，就是四十二章经中地图的秘密。在《鹿鼎记》第十五回中写道：
韦小宝站起身来，大声道：“啊，我明白了！”大车一动，他又坐倒，道：“这八幅地图，便藏在那八部四十二章经之中。”陶红英道：“好像也并非就是如此，到底真相如何，只有当时这八旗旗主才明白，别说我们汉人中无人知晓，连满洲的王公大臣，恐怕也极少知道。我师父说，满洲人藏宝的那座山，是他们龙脉的所在。鞑子所以能占我大明江山，登基为皇，全仗这座山的龙脉。”
韦小宝问道：“什么龙脉?”陶红英道：“那是一个风水极好的地方，满洲鞑子的祖先葬在那山里，子孙大发，来到中国做了皇帝。我师父说，咱们若是找到那座宝山，将龙脉截断，再挖了坟，那么满洲鞑子非但做不成皇帝，还得尽数死在关内。这座宝山如此要紧，所以我太师父和师父花尽心血，要找到山脉的所在。这个大秘密，便藏在那八部四十二章经之中。”
小说的后面叙述，藏宝地图被绘在一张羊皮上，然后又被切割成许多碎片，八部四十二章经中所藏的，正是这些羊皮碎片。
对于小说中韦小宝如何费劲心机找全这八本四十二章经等情节，自然是《鹿鼎记》中非常重要和精彩的一部分，但是这里我们对它不感兴趣。我们感兴趣的，是满清贵族分摊这个大宝藏秘密的技术方法。
首先，因为“满洲八旗，每一旗都各有势力”，所以这个秘密不是某个个体的秘密，而是必须由八旗旗主一起来分摊的。
其次，某个单独的八旗旗主是不是就知道完整的秘密？不是的。他只有自己的那本四十二章经，里面是一堆拼不成完整地图的碎羊皮，光有这些碎羊皮，无法知道宝藏在哪里。摄政王多尔衮应该是知道整个秘密的，但是这里我们不把他算成分摊秘密的人。因为当时考虑的是比较长久以后的事，当时开会的人也许都死光了，那时持有这个秘密的人（尽管每人只持有一部分秘密）就只有那时的八旗旗主了。后来出现的比如八旗旗主有些入狱抄家的事，还有韦小宝这种怪胎，当时八旗旗主会议时，自然都没考虑到。
最后，如果八个旗主都决定要揭开这个秘密，掘出宝藏，那么他们就只需将每人所持的地图碎片取出拼成完整地图。
所以，这是一个被多个个体所分摊的秘密。每个个体都不单独掌握秘密，但是在所有个体一起决定要揭开秘密时，他们就能够知道完整的秘密。
下一步我们要看看这个方法的优点和缺点，以及如何改善这个方法，克服其缺点。
喝口水再说……
本帖一共被 1 帖 引用 (帖内工具实现)
前面说到，有一些秘密需要这样被分摊：多个个体中任何一个个体都不单独掌握秘密，但是在所有个体一起决定要揭开秘密时，他们就能够知道完整的秘密。
据说可口可乐的秘密配方也是这么保密的，被拆成了三份，每个人都不知道其他两人的那部分配方。不过我觉得这好像有点问题，可口可乐配方毕竟不像宝藏，大家说挖出来吧，把秘密完整合起来就行了，然后这个秘密就作废了。可口可乐很长时间都会生产。在此就这么一说吧。
有时候电影里有租银行保险箱的情节，保险箱上两个钥匙孔，一把钥匙在银行工作人员那里，另一把则在客户手里，而保险箱要两把钥匙一起开才打得开。这也是一种类似的分摊秘密的方法，分摊的是打开保险箱的权力。
回到《鹿鼎记》的宝藏上，我得说金庸在设计藏宝图这个情节时是有一番考虑的。
比如说，按照陶红英所说，“将收藏财物的秘密所在，绘成地图，由八旗旗主各执一幅”，那么也可以理解成每个旗主都有一幅完整地图。但是这样就有问题了。也许会有某个旗主不告诉其他人，自己偷偷去把财宝掘出。所以这种“多个人里每人都独自地完整地掌握”秘密的方法是不好的，不能满足旗主会议的要求。
如果是绘一张地图，但不割成碎片，只割成面积相同的八块，然后八个旗主一人一块会怎么样呢？稍微想想的话，这也不合适。如果那地图是象动画片里的海盗藏宝图那样，画了宝藏周围地形，然后在藏宝处画个叉号，那么割开的八块小地图上，显然带叉的那块信息量比较大。地图割开以后虽说不完整了，但是还是有可能从局部的特征，比如海岸线的形状啦，山脉的走向啦，猜测到所绘的区域。就算分到的地图小块上没有藏宝处的叉，如果猜出了地图所绘的区域，那么就可以推知宝藏也离此不远。打叉的那块就更占便宜了，要是猜出了局部区域，那就跟拿到完整地图没啥区别。
如果说地图上还有文字说明，那也许更糟。比如宝藏给埋在鹿鼎山了，要是你拿的的那块地图上有鹿鼎两字，那泄露的消息也就够多了。碰上象《基督山伯爵》里法利亚长老那种能把烧掉一半的纸上的文字中缺少的部分猜出来的强人，你撕半张纸给他和把整张纸全给他是一样的，那这就谈不上“分摊秘密”了不是？
所以金庸就设想了先把地图剪成小碎片，再把碎片分成八份的方法。如果剪得足够碎，那么每小片上的地图的局部特征就不明显，加上各人拿到的碎片都是随机的，光凭八分之一的碎片数量就很难拼出较大的局部来。这不失为一种好方法。但是如果只有两个人来分摊秘密怎么办？那时候凭一个人手上的碎片，拼出较大的局部部分还是比较有可能的，而且这个时候拼出来的部分分布在原来的整个地图上，不再聚集在一个角落里，通过观察不完整的地图来得出整幅地图的一些信息也就更有可能。
这种情况在有多个但不是所有人都是同谋的时候更明显。比如八旗中的六个旗主说，另外两个不愿挖宝，但我们六个愿意。结果六个旗主拿了6/8=3/4数量的碎片来拼，就能拼出一幅虽然到处是破洞，但是很可能看得清的地图来。这就违背八旗会议的原意了。虽然说这也可能是个优点，万一八旗中有一旗旗主不小心把他那一份地图搞丢了，剩下七旗也还有比较大的可能可以挖宝，不至于因为不小心丢失一份地图碎片，整个秘密就永远无法揭晓了。
这就提出了一个新问题：怎么样在若干人之中分摊秘密，使得只要在规定人数以上（而不一定是所有人）同意揭开秘密的时候，秘密就可以被揭开，而如果同意的人数低于这个数目，秘密还是无法揭晓？比如八旗会议可以规定，只要有任何六个旗主决定挖宝，他们就可以拼出一幅完整的而不是满是破洞的地图来，但是如果只有五个旗主同意，他们就一定无法拼出地图来，甚至只是多知道一些信息也不行。小说中切成碎片的方法显然不行：六个旗主拼出来的地图会有很多洞，不能保证一定能找到宝藏；五个旗主拼出来的地图要比六个的更破烂一些，但是未必就一定找不到宝藏。
继续喝水……
记得当年学组合数学的时候，有一道习题
有一扇门，要求n个人有权限开，但是必须保证这n个人中有任意大于等于m个人在场时才能开，任意小于m个人在场时都不能打开门。问门上要挂几把不同的锁，每把锁要配几把钥匙，每个人拿几把锁的钥匙。
当时会做来着，容我想想
偷偷地溜去看了 wikipedia 上 secret sharing 的条目，呵呵，发现还有一个 Chinese Remainder Theorem，不过智商太低，实在看不懂，只能灰溜溜回来搬个板凳听讲解
现在要发个帖子还真不容易，因为没有通宝，还要现攒通宝才能发帖。
想出问题答案耗时2分钟，攒通宝耗时20分钟。。。无语。。。
回到刚才的问题，假设现在凑齐了m-1个人，他们打不开门，必定是缺至少一把锁的钥匙，而剩下的n-m+1个人只要到一个，就可以补上这把钥匙，所以一把锁要有n-m+1把钥匙。
还是假设现在凑齐了m-1个人，他们至少是打不开一把锁。这种组合一共是c（m-1,n），而且每种不同的组合不可能是打不开的是同一把锁，所以锁的数量是C(m-1,n)把。
而锁的数量x每把锁配的钥匙=每个人有的不同锁的钥匙数量x人数（n），所以每个人带几把钥匙也能算出来了。
最后再抱怨一下，新人回个帖子也这么难，还得现攒通宝。
话说前苏联作家抱怨：他们在八十年代出版一部小说，可以挣一部小轿车。同样的作家在九十年代出版一部小说，得先把自己的小轿车卖掉。。。
现在西西河也收版面费了。。。
唉，什么世道。。。
本帖一共被 1 帖 引用 (帖内工具实现)
再举个例子。
比方一个老板有两个手下，叫他们去某地拿某账号付一下某笔款项，而这个账号有个六位数密码。这个密码显然不能完整地告诉给两个人中的某个人，否则这个人可能独自偷偷拿了款潜逃。那么比如这个密码是123456，我告诉第一个人头三位123，第二个人后三位456，到时候付款的时候两人把这密码一拼就可以付款了。
这当然可以，但是显然密码的保险性降低了。本来如果我根本不知道密码，那么所有的可能性是10^6，也就是10的6次方1000000种。现在我知道了前三位123，那么密码的可能性就只有后三位的变化了，只剩1000种。虽说也不少，但总没有原来的1000000种保险。
况且这个方法不好推广。要是觉得两个人太容易合谋，就派6个人去，每人记一位密码，如果里面5个人合谋，那他们就只要猜剩下那个人的数字是多少，最多猜十次就猜到了。
这个方法的不利之处前面就讲过了：在这种分摊方法下，每个人都掌握了点秘密，而且每个人都的确知道一点秘密。注意这里“掌握”和“知道”的区别。掌握是说，这部分秘密你要是不泄露，别人无法知道，由你决定在某场合是不是要把你的这部分秘密和其他人的部分秘密合起来得到整个秘密。你要是真到付款的时候也不愿意说密码，那款也没法付。八旗某旗主就是不愿挖宝，就不拿出他那份地图碎片来，别人也没辙一定要叫他拿出来。这是“掌握”，但不一定是“知道”。比如某个八旗旗主虽然有一堆地图碎片，但是光凭这些碎片，他对宝藏在哪里一点头绪都不知道，特别是不比其他没有碎片的人知道得更多。
这点要展开来讲讲。所谓“知道”某个“秘密”，并不一定要确确实实地知道这个秘密是什么。比如说，如果你知道那个秘密不是什么，而别人不知道这点，对这个秘密，你就知道得比别人多了。举个例子，香港有八卦杂志，说明星的八卦事，什么艳照啦集邮啦，大家就猜，这谁啊。好，过一阵说那是L某某，其实你还是不知道其实是谁，连姓啥都不知道是刘还是梁呢，但是你已经知道的比原来多啦。如果杂志要是说“大眼睛”，那就更搞不清了，多大的眼睛算是大眼睛？但是我们知道，是曾志伟的可能性比较小，梁朝伟？可能比前面这个大点但也不太象。我们可以看到，就算我们得到的只是可能性的变化的信息，就可以说我们“知道”了更多的秘密。
"密码的前三位是123"这样的分摊的方法，不但让分摊人掌握了整个秘密的一部分，而且还让原本密码的1000000种可能性，减少到了1000种，这就泄露了整体秘密的一部分，让掌握秘密的人知道了比不掌握秘密的人知道的要更多的信息。地图碎片其实也是同一个道理，一个人掌握的碎片其实还是泄露了整幅地图的一部分信息，而同谋人数多起来时，这种信息的泄露就越来越严重。如果地图不被割碎，只是一个旗主一块，这种泄露秘密的现象就更严重了。
放在我们面前的任务是：让每个人都掌握一部分秘密（这是“分摊”要求的），但是被掌握的这部分信息却不会对掌握秘密者泄露任何被分摊的秘密的信息，也就是说，我们希望掌握秘密的每个个体对秘密的了解程度，不比不掌握秘密的人对秘密的知道程度更高。更进一步，即使有同谋，几个同谋把自己掌握的信息合起来后，也无法提高对秘密的知道程度。也就是说应该这样：八旗中的七个旗主如果都把自己掌握的地图碎片拿出，他们也无法取得哪怕一丁点他们以前不了解的秘密，只有第八个旗主也参与进来，那时候他们才会完整地了解整个秘密。
这好像很矛盾的样子，要求“掌握”却要求一点都不“知道”。但是这是可能做到的。
土鳖又要喝水，才能抗铁牛
本帖一共被 1 帖 引用 (帖内工具实现)
比如一个电路的加法逻辑开关或每个人打开一个水流开关的, 相加总流量推动大门之类的. 按你的算法, n个人有钥匙, 来2个人开: 要n-1把锁,每个人要n-2把钥匙.一共,(n-1) x (n-2)把钥匙.
先考虑简单的，两个人之间如何分摊秘密。比如那个两个人分摊六位数密码的事情。这俩人是甲和乙。
现在拿一个能均匀地随机地产生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
那么如果是三个人或更多人要分摊秘密怎么办？
非常方便。仍旧是那个6位数密码，假设现在老板要派三个人甲乙丙去。
按照原来的老方法，现在老板随机产生两个6位数，比如153607和582149，把它们分别给甲和乙，然后用真正的密码123456去逐位减这两个数字：
1-1-5 = -5 -->5
2-5-8 = -11 -->9
3-3-2 = -2 -->8
4-6-1 = -3 -->7
5-0-4 = 1 -->1
6-7-9 = -10 -->0
总之如果结果不在0-9中就加减若干个10，使得结果成为一个0-9之间的数。老板得到598710，给丙。
同样的分析，甲和乙凭手里的那个数能增加他对真正的密码是什么的信息吗？不能，那俩数根本就是随便产生出来的。丙靠他的数也一样不行，和前面两个人的情况中乙的情况差不多。
如果其中有两人合谋怎么办？比如甲和乙合谋——没用，他们那俩数都是随便产生出来的。甲和丙合谋？每一个可能的最终密码值都对应着一个乙手里的那个数的可能值，可是乙手里的那个数的可能是000000-999999中的任何一个，概率都是1/1000000，于是真正的密码还是在000000-999999中的任何一个，概率还是1/1000000。通过甲和丙的同谋，还是无法带给甲和丙任何他们以前不知道的事情。乙和丙的同谋情况也一样。
但是如果甲乙丙共同决定要得到密码，只要把他们手上三个数逐位加（可能要减去若干个10使得结果在0-9间）就可以了：
1+5+5 = 11 ->1
5+8+9 = 22 ->2
3+2+8 = 13->3
6+1+7 = 14->4
0+4+1 = 5->5
7+9+0 = 16->6
人数再多的话，多产生一些随机数即可。N个人产生N-1个随机数，最后一个人则分配给真正密码逐位减这些数字的结果。
很容易看出来，就算密码位数不是6位，而是非常非常长，这个方法也一样可行。如今啥都是数字化的，一个文件其实就是一个大数字，文字的记录是文本文件（或者Word文件也无所谓），如果是一张地图，或者是拍了些见不得人的照片啥的，就是个图像文件，一段录像是一个视频文件。既然这些文件无非都分别是一个（也许有很多很多位的）数，那么就可以用前面说的这个方法来分摊到若干人上。这个被分摊的秘密也不一定非得表示成10进制的，比如计算机文件一般是以二进制形式储存传送的，也可以看作是十六进制甚至是更大的数字进制的，假设是P进制，那就把前面那个随机数产生器改变一下，让它产生合适范围（0到P-1之间）的数字。这样我们就得到了一个在许多人之间分摊一个任意大小的秘密（大小不是说秘密泄露的严重性，是说内容多少）的方法。这个方法可以保证每个人“掌握”却不“知道”，而且即使是有若干同谋在一起也无法知道最终秘密更多的信息。只有在所有人都同意揭开秘密的时候，大家才能知道这个秘密。
不过正如前面所言，这个方法好是好，但未免过分严格了一点。要是在100个人中这么分摊秘密，万一有一个人三长两短把他掌握的秘密弄丢了怎么办？大家拿着99份分摊的秘密，可是对知道最终秘密一点用都没有。所以我们还得想出一个办法，能够只要求达到规定的一定人数比如说80个人，而不要求全体都同意，就可以揭开秘密。
喝水……
习题是为了巩固所学知识的，不是为了解决实际问题的，也不是脑筋急转弯。所以习题里的假定和规定的解题方法，必须遵守，才能达到练习的目的。
就好像计算机课的机习题，要求编2^N点fft的程序，你不能告诉老师matlab里都有，使用起来也更方便快捷，所以用matlab一算就行了。
看完分摊秘密不容易(2)后, 我还以为楼主接下来肯定要提到信息论了.
没想到荷包大才, 没有借助信息论, 也把问题讲的一清二楚. 把科学问题用浅显易懂的语言表达清楚, 需要大智慧啊, 佩服佩服 
是不是接下来会解释Threshold Cryptography的原理?
逐篇献花, 期待下文.
你的算法先假设了m-1人一定不能通过, m个人一定能开的前提, 但你得到结果后,忘了验算结果是否符合你的前提. 5个人掌匙, 3个人开. 10把锁, 30把钥匙, 每人6把. 为什么两个人12把钥匙一定不能开? 为什么不能1个是{1,2,3,4,5,6} 另一个是 {5,6,7,8,9,10}. 验算一下就知道你算的只是m个人一定能开的排列法.