主题：如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包
家园 荷包好人品啊，两个通宝奉上 荷包好人品啊，铁手对您的文章非常赞赏。
谢谢：作者意外获得【通宝】一枚
鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消
提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。
谢谢：作者意外获得【通宝】一枚
鲜花已成功送出，消耗 铢钱 1 个，可能得宝。可通过工具取消
提示：此次送花为【有效送花赞扬，加乐善、声望、帖得花总数】。
家园 俺搓着手说：嘿嘿嘿，不好意思啊……
家园 如何分摊秘密（六）——无需所有人都同意 回到三个人分摊一个6位账户密码的问题来，如果说只要其中两个人同意就可以推出账户密码来，该怎么分摊秘密？
有个很简单的方法，还是按老规矩把账户密码拆成三个6位数，只有拿到所有这三个6位数才能推导出最终的密码。假设这三个数是A，B和C，老板让甲拿A和B，乙拿B和C，丙拿A和C。
很显然，任何单个人都无法通过自己手上的那两个数获得任何关于账号密码的知识，但是任何两个人在一起，总能凑齐ABC三个数字，从而得知账户密码。
这个办法也可以推广到一般的N个人只要有超过M个人同意（N>=M>0）就可以得知最终秘密的情况。想法就是把最终秘密拆成许多份，而每个人都拿其中的若干份，然后想办法保证让少于M个人在一起，一定凑不齐所有的份数，而如果M个人在一起则一定能凑足所有的份数。
不过我们也可以从另一个方面考虑，这个考虑方法解释起来比较简单。（其实也就是下面multiple的方法，可我觉得我说得比他详细，比他清楚
）（8月23日注：我的方法和multiple兄的方法似乎不同，请看下面我和乌贼兄的讨论：乌贼:按有个疑问）同一个6位数的账号密码可以用不同的随机数拆成不同的分摊方法。比如123456要拆成3份，可以是153607，582149，598710，也可以是405071，951239，877256，等等等等。如果要求在5个人中分摊秘密，使得任何其中3个人同意就可以知道秘密，可以这样做：
找到所有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位数，这和上面的结果对上了。
甲拿到属于他的那6个数，会增加他对账号密码的知识吗？不会，其中单独的任何一个数都不会使他增加知识。而这6个数分别是6个分拆中的一部分，这6个分拆之间是独立没有关系的，于是就算拿了这6个数也没法组合起来得到对账号密码的新知识。
如果是两个人合谋，比如甲和乙，那么他们最多能够凑到诸如“甲乙丙”“甲乙丁”之类三人组合中那些分拆里3份中的2份，可这还是不够，因为一定要拿到一个分拆的所有3个部分，才能知道账户密码。
如果有任何三个人在一起，比如甲乙丙，那么他们就凑齐了他们那个三人组合的账户密码分拆的所有3个部分，于是就能知道账户密码。
这个方法很容易推广成一般的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人组合的拆分信息恢复出最终秘密。
于是我们就知道了，从理论上来说，无论N和M是多少，我们总能找到方法来让这N个人分摊秘密，使得少于M个人在一起无法知道最终秘密（不仅如此，是一点新知识都不增加），而M个人以上在一起就能够得知最终秘密。不过从实际上来说，这个方法只能用在N和M不大的情况，比如上面N=5，M=3的情况，每个人记6个6位数，也还好。但是N=100，M=80呢？组合爆炸了。其中的80人组合会有(100,80)=100!/(80!20!)=535983370403809682970个，超过5x10^20个。而每个人得记住(99,79)=99!/(79!20!)=428786696323047746376也就是超过4x10^20个6位数，这得拿多少硬盘才存得下来啊。还不说分拆啊检索啊所需要的时间。而且这还只是要分摊一个6位数，如果是一个大文件，那就更提也别提了。一句话，这种简单的想法不实用。
前面那种“所有人都同意秘密才可揭晓”的情况下，每个人要掌握的秘密的长度都和最终秘密的长度一样，要分摊一个6位数的密码，3个人分摊就会拆成3个6位数，100个人分摊就拆成100个6位数，每个人总是只要记住一个6位数就可以了。如果在“N个人M个同意”的情况下，不管是什么M和N，要求每个人记的数也都只是一个6位数（或者一般地，是和最终秘密一样大小的一个信息），那该有多好啊。
好消息就是，这种方法是有的。坏消息是，我们需要稍微高深一点的数学知识才能理解这个方法。
喘气喘气……
元宝推荐：游识猷, 通宝推：明心灵竹,
本帖一共被 1 帖 引用 (帖内工具实现)家园 很类似应用在存储系统领域的raid技术 RAID 5
“RAID Level 5 是一种存储性能、数据安全和存储成本兼顾的存储解决方案。它使用的是Disk Striping（硬盘分割）技术。RAID 5 至少需要三顆硬碟， RAID 5不对存储的数据进行备份，而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上，并且奇偶校验信息和相对应的数据分别存储於不同的磁盘上。当RAID5的一个磁盘数据发生损坏後，利用剩下的数据和相应的奇偶校验信息去恢复被损坏的数据。 ”
家园 七呢？就这么吊在这啦！！！ 这么喘气，都一年半了，还没喘够啊。
家园 等
家园 按有个疑问 找到所有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兄的结果吻合。
不知对否。
本帖一共被 1 帖 引用 (帖内工具实现)- 复 按有个疑问
家园 Multiple兄的锁和我说的锁不是同一种 先说一下锁的串联和并联（没图只好文字说明了）。
门上如果有好多对门扣，每对门扣锁一把锁，这是锁的并联，想开门的话非得把所有锁都打开了不可。
门上如果只有一对门扣，两把锁串联锁门的方法是，用一把锁锁上左门扣，再用另一把锁套住第一把锁和右门扣。可以想象如果若干把锁也可以这样一个套一个地把锁象链条一样连在一起锁门，这是锁的串联，想开门的话只要能打开其中任何一把锁就可以了。
Multiple兄的锁和我说的锁不是同一种，连锁门的方式也不一样。所以用他的方法算出来的锁和钥匙数目和我的方法算出来的数目对不上是正常的。他的每只锁都是只要一把钥匙就能开的，而锁是以并联方式锁在门上的，这样的解释方法比较容易让人晕头，存在性证明也要另外作出。这种方法要转换到我说的方法还得绕一下，不过原理是差不多的。所以说我觉得我解释得比他清楚。
－－－－－－－－－－－－－－－－－－－－－－－－
我的解释方法中的每只锁都有好几个锁孔，非得此锁的所有锁孔都插上对应的钥匙才能开（其实就是几只并联的单钥锁，但想象成一只多钥锁比较方便），而各锁是以串联的形式锁在一起的，一串锁中只要开了一只锁，门就开了。
现在我们希望五个人中任意三个人都能打开门，而任意两个人以下都打不开门，怎么办？五人里的三人组合是(5,3)=10，我就买上10只三钥锁（这十把锁之间互相没关系，某把锁的钥匙只能在这把锁上用），每只锁对应一个三人组合，然后把那只锁的三把钥匙分别给三人组合中的三人。每个人会属于几个不同的三人组？(4,2)=6个，于是每人会有6把钥匙，分别用于不同的六只锁。
如果只有两个人在场，他们凑不齐任何一把锁的三把钥匙，所以开不了任何一只锁。而只要三个人在场，他们就可以打开对应于他们那个三人组的那只锁。
不知这样解释是否清楚？
家园 您说的我看得似懂非懂 这里似乎有个经济性的问题
家园 先不管Multiple兄的问题 我说的那种用若干只多钥锁串联的解决方案讲得是不是清楚呢？
家园 这个我看得明白 也能够理解
按需要消化消化的是为何这两种合理的方法相差一个数量，相差一个怎样的数量
我想m兄的C（m-1,N)和您的C（m，n)相差一个数量的原因是钥匙可以有不同，但是我得再想想
自己没想明白的东西，真称不上懂，呵呵，不过我想您已经给我指出方向了
- 复 这个我看得明白
家园 相差一个数量的原因 相差一个数量的原因，我前面说了，其实是锁的结构不同。我的锁是多钥锁，但每把钥匙都不同。M兄的锁是单钥锁，但是允许有多把相同的钥匙。
M兄的方法应该这么理解：对于任何一个m-1人组，我们要有一只“禁制锁”，除了这m-1人外，其他(n-m+1)人都能开这锁。这样一共有C(m-1,n)只禁制锁，它们都并联地锁在门上。
任何m-1个人的话，都有一只对付他们的禁制锁，所以那只锁他们是开不了的。但是只要有m人，无论哪只禁制锁都只最多能对付其中的m-1人（有些锁说不定这m个人里有好几个都有钥匙）于是一定能开。
如果考虑总共8人如3人可开门的情况。我的方法是弄C(3,8)只3钥锁串在一起，而M兄的方法弄C(2,8)只禁制锁并联来一起，每锁有8-2=6把钥匙。
所以我前面的说法有问题，我开始以为可以统一成“一锁一钥”的串联并联法。事实上我们的方法并不等价，一个是先并后串（多钥一起才能开锁可以看成是一锁一钥的并），一个是先串后并（多钥每钥都可单独开锁可以看成一锁一钥的串）。不过这两种方法的钥匙数量总是相同的，就是truth兄底下说的C(m-1,n)*(n-m+1) = C(m-1,n-1)*n = C(m,n)*m。等式左边是M兄的方法，右边是我的方法。不过我相信还是有某种转换的理解方式可以统一这两种方法。
家园 按今天突然想到 C(m-1,N)等价于在N人中最多的人到场不能解密的组合
C(m,N)等价于在N人中最少的人到场必能解密的组合
这是一个问题的两个方面。
按兄的并联再串联法，两组并联锁记为：
A1，A2。。。Am
B1，B2。。。Bm
Am和Bm的多钥锁是可以相同的，A1...Am或者B1...Bm的并联内部的钥匙不同。简化点说，只要把秘密分成M份，然后，再在N人中的任选M人中分配，共分配C（m,N)组，也可以达到至少M人到场才能解密的结果，也就是说对应“密码”只要M个，不需要C（m,n)*m个。不知兄以为然否？