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

这第六节终于有些晕了,中学的排列组合早已忘得精光了.

送了半天花,居然没给自己挣来半分....

感觉这篇文章和密码有得一比.

谢谢：作者意外获得【通宝】一枚

鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消

提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。

Zero knowledge指的是零知识证明：我知道一个秘密，而且我能既不告诉你这个秘密，却又同时让你相信我的确知道这个秘密。当然零知识证明也很有意思的一件事，也许我以后可以写点这方面的帖子。

“学海无涯”这话已经说得很明白了，寻求知识这事，你就是跳了一大坑，这个坑大到象海，还“无涯”，没指望了，爬不出来了。大海啊大海，这么多的水，我灌的这点水实在不算啥。

再往下说，我得解释两件事情，一件叫“有限域”，一件叫“拉格朗日插值”，这就需要另挖新坑。请往新坑数学闲话捧场。

的分发对作者是最优解。

谢谢：作者意外获得【通宝】一枚

鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消

提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。

好文

谢谢：作者意外获得【通宝】一枚

鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消

提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。

multiple证明的是, 为了保证任意m个人在场时能开门, 而任意m-1个人都不能开门, 那么至少需要C(m-1,n)个锁, 每个锁至少需要n-m+1把钥匙.

接下来可以证明, C(m-1,n)和n-m+1作为下界是可以达到的. 即存在一种钥匙分配方式, n个人中的每一个都分配C(m-1,n-1)把钥匙, 使得任意m个人在场时能开门, 而任意m-1个人都不能开门. 注意C(m-1,n)*(n-m+1) = C(m-1,n-1)*n = C(m,n)*m.

这个证明应该不难, 但也不直观. 具体到n=5,m=3的情况时, 可给出以下的分配方案: {1,2,3,4,5,6}, {4,5,6,7,8,9}, {1,2,4,7,8,10}, {2,3,5,8,9,10}, {1,3,6,7,9,10}. 不难验证, 此方案可以保证任意3个人能开门, 而任意2个人不能开门.

关于存在性的一般证明, 我想任意m-1个人应该恰好拥有n-m+1把共同钥匙, 同时他们的合集应该恰好缺少1把钥匙.

这是我上过的最有意思的数学课

1 5把钥匙，有任意3把就能打开锁

2 5把钥匙，但是其中1把顶2把用（权重2），任意3把能打开锁，

3 对已丢失钥匙的废弃。。。

《应用密码学-算法、协议与源程序》 ^_^

第一题就是（六）讲过的，第三题估计不会讲了这方面的内容了，第二题却很简单也很值得一提。

5把钥匙，但是其中1把顶2把用（权重2），任意3把能打开锁，那么其实那把权重2的钥匙其实就是两把钥匙，只要制作6把钥匙，使得其中任何3把在一起就可以打开锁，把其中的两把给同一个人的话，这个人其实就是有了一把权重2的钥匙。

这在实际中也很有用处的，每个人的重要性不一定都相同。公司的董事长也许一个人就可以决定是否揭开秘密，但是执行董事的话必须有三人以上同意才行，至于一般董事则要10人以上。制作一把顶n把钥匙的方法就可以解决这种问题。

能够使某两人开锁通过，但不能使任选两人都能开锁通过。

前面的题目上不仅有M个人可以通过，还有任一M人选都可通过的限制。

找到所有5个人中的“三人组合”，这个我们在中学排列组合课里学过，是5件东西取3件的组合取法，一共有(5,3)=5!/(3!(5-3)!)=10个“三人组合”。对于每个这样的三人组合，我们都把那个账号密码象前面那样用随机数拆成3份，然后给这个三人组合中每人一份。一共会拆出10x3=30个6位数来。每个人当然都会属于好几个三人组合。对一个具体的甲，他分别属于(4,2)=4!/(2!2!)=6个不同的“三人组合”，所以他会拿到6个6位数，其中每个6位数都是其中一个三人组合中分摊给他的那份秘密。5个人一共有5x6=30个6位数，这和上面的结果对上了。

-----------------------------------------------------

这个方法很容易推广成一般的N个人中只要有超过M个人同意（N>=M>0）就可以得知最终秘密的情况。N个人中的M人组合有(N,M)=N!(M!(N-M)!)=A个，我们就把秘密对这A个组用A种方法拆分，每种方法都独立地将秘密拆成M份，然后给对应的这个M人组合中每人一份。就象上面的特殊的N=5，M=3的情况看到的，少于M个人在一起是没办法恢复出最终秘密的，但是只要有任何M个人在一起，就可以用为这个M人组合的拆分信息恢复出最终秘密。

这两段的说法和multiple兄的结果似乎有矛盾。如用（6，3）验算结果相差很多。multiple兄的结果和按想出来的一样。

我以为老兄5选3的解释（第一段）应当是5人当中4人可组合出秘密的情况。

而后面的应当是N人中任M+1人可组合出秘密的情况。

这样就和Multiple兄的结果吻合。

不知对否。

• 如何分摊秘密（六）——无需所有人都同意

先说一下锁的串联和并联（没图只好文字说明了）。

门上如果有好多对门扣，每对门扣锁一把锁，这是锁的并联，想开门的话非得把所有锁都打开了不可。

门上如果只有一对门扣，两把锁串联锁门的方法是，用一把锁锁上左门扣，再用另一把锁套住第一把锁和右门扣。可以想象如果若干把锁也可以这样一个套一个地把锁象链条一样连在一起锁门，这是锁的串联，想开门的话只要能打开其中任何一把锁就可以了。

Multiple兄的锁和我说的锁不是同一种，连锁门的方式也不一样。所以用他的方法算出来的锁和钥匙数目和我的方法算出来的数目对不上是正常的。他的每只锁都是只要一把钥匙就能开的，而锁是以并联方式锁在门上的，这样的解释方法比较容易让人晕头，存在性证明也要另外作出。这种方法要转换到我说的方法还得绕一下，不过原理是差不多的。所以说我觉得我解释得比他清楚。

－－－－－－－－－－－－－－－－－－－－－－－－

我的解释方法中的每只锁都有好几个锁孔，非得此锁的所有锁孔都插上对应的钥匙才能开（其实就是几只并联的单钥锁，但想象成一只多钥锁比较方便），而各锁是以串联的形式锁在一起的，一串锁中只要开了一只锁，门就开了。

现在我们希望五个人中任意三个人都能打开门，而任意两个人以下都打不开门，怎么办？五人里的三人组合是(5,3)=10，我就买上10只三钥锁（这十把锁之间互相没关系，某把锁的钥匙只能在这把锁上用），每只锁对应一个三人组合，然后把那只锁的三把钥匙分别给三人组合中的三人。每个人会属于几个不同的三人组？(4,2)=6个，于是每人会有6把钥匙，分别用于不同的六只锁。

如果只有两个人在场，他们凑不齐任何一把锁的三把钥匙，所以开不了任何一只锁。而只要三个人在场，他们就可以打开对应于他们那个三人组的那只锁。

不知这样解释是否清楚？

这里似乎有个经济性的问题

我说的那种用若干只多钥锁串联的解决方案讲得是不是清楚呢？