如何分摊秘密（五）

六、数字世界

在前面几节中我们描述了如何在多人之间分摊秘密的方法，并具体地以如何分摊一个6位的十进制数字为例作了说明。容易看出来，就算密码位数不是6位，而是非常非常长，我们所说的这个方法也同样可行，只需把那个N取得非常非常大。

假如《鹿鼎记》中地图原图大小为一米见方，差不多是边长为40英寸的正方形。如果用每英寸300像素的图像质量来将其数字化，就是一幅12000×12000像素的图像；用24位真彩的话，每个像素可用一个24位的二进制数字来表示；整幅图像就可用一个12000×12000×24=3456000000位的二进制数字来表示。写成电脑文件，大小会有3456000000/(8×1024×1024)≈412兆字节。如果地图的尺寸更大几倍，像素密度更高一些，那么上面估计的文件也会更大一些。当然这是不考虑图像压缩的情况，否则文件可以更小。不过412兆字节或者再多若干倍的存储量也不是不可接受的——尤其如果它事关一个大宝藏的话。

我们取N为2^3456000000，这个数字比十的十亿次方稍微大些。上面这幅数字化了的地图，就是0到N-1之间的某个数s，即八旗旗主会议试图分摊给八位旗主的秘密。按照前面几节介绍的分摊秘密的方法，摄政王可以用一个好的（也就是能均匀地独立地产生随机数的）随机数产生器产生出7个0到N-1之间的随机数，将它们（的同余类）分别交给前七位旗主，再将s减去这七个数字，将它（的同余类）交给第八位旗主。这就完成了地图秘密的分摊。每位旗主需要记住的，是一个约412兆字节的文件。

这八位旗主中的任何七位联合起来，没有第八位旗主的同意，也无法知晓原地图图像文件到底是0到N-1之间的哪个数。当然，他们还是能知道那个数不会是——比如说——0，因为这意味着那是一张全黑的图像。但这样的“知道”是通过常识推断出来的，就算是不掌握那八个秘密数字的人也可以做到，并非这个分摊策略的弱点。

要分摊的秘密也不一定非要是账号密码或是一幅图像。它也可以是一段文字，数字化后是一个文本文件；也可以是一段录音或录像，数字化后是一个音频或视频文件；或是其他任何格式的文件。只要某个秘密能被数字化，那么我们都可以用前面所说的方式，在若干个人之间分摊秘密。每个人需要掌握的分摊给他的秘密文件的大小，等于原始秘密文件的大小。

七、无需所有人都同意的分摊秘密方法

不过正如前面所言，前几节中分摊秘密的方法好是好，但未免过分严格了一点。如果在100个人中这样分摊秘密，万一有个人三长两短把他掌握的数字弄丢了怎么办？那样的话，剩下的99个数字变得对揭晓秘密毫无用处。

所以我们还得想出一个办法，能够无需所有人都同意，只需达到规定的某个数目的人数（比如说80个人）同意时，就可以揭开秘密。当然，如果只有低于此数的人合谋，他们将不能增加哪怕一点对真正秘密的了解程度。

先考虑最简单的三个人分摊秘密的问题来。如果只要其中两个人同意就可以揭晓秘密，该怎么分摊？

有个很简单的方法，还是按老规矩把秘密拆成a、b、c三部分，只有拿到所有这三个部分才能揭晓秘密。老板让甲拿a和b，乙拿b和c，丙拿a和c。很显然，任何单个人都无法通过自己手上的那两部分获得任何关于秘密的知识；但是任何两个人在一起，总能凑齐abc三部分，从而得知秘密。

上面这个方法很简单，但不容易推广。我们再看另一种方法。

秘密可以拆成两部分a和b，也可以另外拆成a’和b’，还可以再拆成a”和b”。这三种拆法互相独立，所以必须拿到同一种拆法中的两个部分，才能得知秘密。否则的话，比如只拿到a，a’和a”，或是只拿到b，a’和b”等等，都无法恢复出原秘密来。然后把a和b分别给甲和乙，a’和b’分别给乙和丙，a”和b”分别给甲和丙（也即a和a”给甲，b和a’给乙，b’和b”给丙）。容易看出，单个人手里并没有任一种拆法中的完整两部分，但甲乙一起就有a和b，乙丙一起就有a’和b’，甲丙一起就有a”和b”，都能够揭晓秘密。

上面这种分摊秘密的方法同样满足我们的要求，而且有容易推广的好处。用类似的拆法可以实现“非对称”的秘密分摊。比如说，在上面的例子中把a和b分别给甲和乙，a’和b’分别给乙和丙，a”和b”丢弃不用。那么任何单个人都无法知道秘密，而甲乙或乙丙联合则可揭晓秘密，但甲丙联合则不可以。这种方法的关键在于，我们为每个允许揭秘的组合准备了一个拆分。而这个方法可以推广到一般的m个人的情况。

假设现有m个人，而且又有一张“允许揭秘组合”的列表，那么我们就能有一个和上面类似的分摊策略，使得秘密能被揭晓，当且仅当联合在一起的某些人恰好是这张列表中的某组合。用集合论的语言来说，给定m人的集合P，又有P所有子集的集合的一个子集A（即每个A里的元素都是P的一个子集，如果P的某个子集属于A，我们称它是准入集），那么我们可以构造一个分摊策略，使得P的一个子集U中的人联合起来就可以揭晓秘密，当且仅当U包含了某个准入集。

构造的方法很简单：对每一个准入集我们都独立地将秘密s分拆一次，分成k部分，其中k是这个准入集中的人数，然后将这k部分分别给此准入集中的k个人（特别地，如果k=1，也就是准入集中只有一个人，那么他将直接获得秘密s）。容易看出，秘密可以被揭晓当且仅当某拆分的所有部分都可以被收集齐，而这又当且仅当联合起来的人中的一些人可以组成某个准入集。

举个具体的例子。某公司有某秘密，经手人有两个执事甲乙和三个监督人丙丁戊共五人。允许揭晓秘密的条件是：至少有执事甲和任意两个监督人在一起时，或是至少有执事乙和所有三个监督人在一起时。

这时的准入集有四个，即｛甲丙丁｝，｛甲丁戊｝，｛甲丙戊｝，｛乙丙丁戊｝。我们构造秘密s的同余类的四个（独立的）拆分如下： [s]=[a₁]+[a₂]+[a₃] [s]=[b₁]+[b₂]+[b₃] [s]=[c₁]+[c₂]+[c₃] [s]=[d₁]+[d₂]+[d₃]+[d₄] 对每个准入集作如下的分摊： [a₁]→甲，[a₂]→丙，[a₃]→丁； [b₁]→甲，[b₂]→丁，[b₃]→戊； [c₁]→甲，[c₂]→丙，[c₃]→戊； [d₁]→乙，[d₂]→丙，[d₃]→丁，[d₄]→戊； 按每个人分类，我们有分摊表： 甲←[a₁]，[b₁]，[c₁]； 乙←[d₁]； 丙←[a₂]，[c₂]，[d₂]； 丁←[a₃]，[b₂]，[d₃]； 戊←[b₃]，[c₃]，[d₄]； 容易验证这样的分摊秘密方法符合我们的要求。

前面的构造中没有排除某一个准入集A是另一个准入集B的真子集的情况。如果准入集A是准入集B的真子集，容易看出准入集B是不必要作为准入集而存在的，因为凑够了B中的人就必定已经凑够了A中的人，可以用为A所作的那个拆分来揭示秘密，完全没有必要再单独为B作一个拆分。所以为实用起见，我们可以假设准入集之间互不包含。