3.6 秘密分割

    设想你已发明了一种新的、特别粘、特别甜的奶油饼的馅,或者你已经制作了一种碎肉夹饼的调味料,那怕它比你的竞争者的更无味。重要的是:你都必须保守秘密。你只能告诉最信赖的雇员各种成分准确的调合,但如果他们中的一个背叛到对手方时怎么办呢?秘密就会泄漏,不久,每个出售黄油的宫殿将做出和你的一样的无味的调味料。

    这种情况就要求秘密分割。有各种方法把消息分割成许多碎片[551]。每一片本身并不代表什么,但把这些碎片放到一块,消息就会重现出来。如果消息是一个秘方,每一个雇员有一部分,那么只有他们放在一起才能做出这种调味料。如果任意一雇员辞职带走一部分制法,这个信息本身是毫无用处的。

    在两个人之间分割一消息是最简单的共享问题。下面是Trent把一消息分割给Alice和Bob的一个协议:

        (1)Trent产生一随机比特串R,和消息M一样长。

        (2)Trent用R异或M得到S:

M ⊕ R = S

        (3)Trent把R给Alice,将S给Bob。

    为了重构此消息,Alice和Bob只需一起做一步:

        (4)Alice和Bob将他们的消息异或就可得到此消息:

R ⊕ S = M.

    如果做得适当,这种技术是绝对安全的。每一部分本身是毫无价值的。实质上,Trent是用一次一密乱码本加密消息,并将密文给一人,乱码本给另一人。1.5节讨论过一次一密乱码本,它们具有完全保密性。无论有多大计算能力都不能根据消息碎片之一就确定出此消息来。

    把这种方案推广到多人也是容易的。为了在多个人中分割一消息,将此消息与多个随机比特异或成混合物。在下面的例子中,Trent把信息划分成四部分:

        (1)Trent产生三个随机比特串R、S、T,每个随机串与消息M一样长。

        (2)Trent用这三个随机串和M异或得到U:

M  ⊕  R  ⊕  S  ⊕  T = U

        (3)Trent将U给Alice,S给Bob,T给Carol,U给Dave。

    Alice、Bob和Carol、Dave在一起可以重构此消息:

        (4)Alice、Bob、Carol和Dave一起计算:

R  ⊕  S  ⊕  T ⊕ U = M

    这是一个裁决协议,Trent有绝对的权力,并且能够做他想做的任何事情。他可以把毫无意义的东西拿出来,并且申明是秘密的有效部分。在他们将秘密重构出来之前,没有人能够知道它。他可以分别交给Alice、Bob、Carol和Dave一部分,并且在以后告诉每一个人,只要Alice、Carol和Dave三人就可以重构出此秘密,然后解雇Bob。由于这是由Trent分配的秘密,这对于他恢复信息是没有问题的。

    然而,这种协议存在一个问题:如果任何一部分丢失了,并且Trent又不在,就等于将消息丢掉了。如果Carol有调味料制法的一部分,他跑去为对手工作,并带走了他的那一部分,那么其他人就很不幸了,她不可能重新产生这个秘方,但Alice、Bob、Dave在一起也不行。Carol的那一部分对消息来说和其它部分的组合一样重要。Alice、Bob和Dave知道的仅是消息的长度,没有其它更多的信息了。这是真的,因为R、S、T、U和M都有同样的长度;见到他们中的任何一个都知道它的长度。记住,M不是通常单词意义的分割,它是用随机数异或的。

3.7 秘密共享

    你正在为核导弹安装发射程序。你想确信一个疯子是不能够启动发射。你也想确信两个疯子也不能启动发射。在你允许发射前,五个官员中至少有三个是疯子。

    这是一个容易解决的问题。做一个机械发射控制器,给五个官员每人一把钥匙,并且你在允许他们起爆时,要求至少三个官员的钥匙插入合适的槽中(如果你确实担心,可以使这些槽分隔远些,并要求官员们同时将钥匙插入。你不愿一个官员偷窃另两把钥匙,使他能够毁坏多伦多)。

    我们甚至能把它变得更复杂。也许将军和两个上校被授权发射导弹,但如果将军正在打高尔夫球,那么启动发射需要五位上校。制造一个发射控制器,该发射器需要五把钥匙。给将军3把钥匙,给每位上校一把钥匙。将军和任何两位上校一起就能发射导弹。五个上校一起也能,但将军和一位上校就不能,四位上校也不行。

    一个叫做门限方案的更复杂的共享方案,可在数学上做到这些甚至做得更多。起码,你可以取任何消息(秘密的秘方,发射代码,你的洗衣价目表),并把它分成n部分,每部分叫做它的“影子”或共享,这样它们中的任何m部分能够用来重构消息,更准确地说,这叫做(m,n)门限方案。

    拿(3,4)门限方案来说,Trent可以将他的秘密调味料秘方分给Alice、Bob、Carol和Dave,这样把他们中的任意三个“影子”放在一起就能重构消息。如果Carol正在渡假,那么Alice、Bob和Dave可以做这样的事。如果Bob被汽车撞了,那么Alice、Carol和Dave能够做这件事。然而如果Carol正在渡假期间,Bob被汽车撞了,Alice和Dave就不可能重构消息了。

    普通的门限方案远比上面所说的更通用。任何共享方案都能用它建造模型。你可以把消息分给你所在大楼中的人,以便重构它,你需要一楼的7个人和二楼的5个人,就能恢复此消息。如果有从三楼来的人,在这种情况下,你仅需要从三楼来的那个人和从一楼来的3个人及从二楼来的2个人,如果有从四楼来的人,在这种情况下,你仅需要从四楼来的那个人和从三楼来的1个人,或从四楼来的那个人和从一楼来的2个人及从二楼来的1个人,或者LL好的,你明白这个概念了。

    这种思想是由Adi Shamir[1414] George .Blakley[182]两人分别创造的。并由Gus Simmons 做了更广泛的研究,23.2节讨论几种不同的算法。

留言评论(旧系统):

佚名 @ 2014-10-24 16:07:11

请在这里填写留言内容,最长不超过 1000 字。

本站回复:

[暂无回复]