5.6 不经意签名

    说实话,我不认为它们好用,但是有两种类型[346]:

    1.Alice有n份不同的消息。Bob可以选择其中之一给Alice签名,Alice没有办法知道她签的哪一份消息。

    2.Alice有一份消息。Bob可以选择n个密钥中的一个给Alice签署消息用,Alice无法知道她用的哪一个密钥。

    这是一个巧妙的想法;我相信它在某些地方有用。

 

5.7 同时签约

带有仲裁者的签约

    Alice和Bob想订立一个合约。他们已经同意了其中的措词,但每个人都想等对方签名后再签名。如果是面对面的,这很容易:两人一起签。如果距离远的,他们可以用一个仲裁者。

    (1)Alice签署合约的一份副本并发送给Trent。

    (2)Bob签署合约的一份副本并发送给Trent。

    (3)Trent发送一份消息给Alice和Bob,指明彼此都已签约。

    (4)Alice签署合约的两份副本并发送给Bob。

    (5)Bob签署合约的这两份副本,自己留下一份,并把另一份发送给Alice。

    (6)Alice和Bob都通知Trent他们每个人都有了一份有他们两人合签的合约副本。

    (7)Trent撕毁在每一份上只有一个签名的两份合约副本。

    这个协议奏效是因为Trent防止了双方中的某一方进行欺骗。如果在步骤(5)中Bob拒绝签约,Alice可以向Trent要求一份已经由Bob签署的合约副本。如果在步骤(4)中Alice拒绝签名,Bob也可以这么做。当在步骤(3)中Trent指明他收到了两份合约,Alice和Bob知道彼此已受到和约的约束。如果Trent在步骤(1)和(2)中没有收到这两份合约,他便撕掉已收到的那份,则两方都不受合约约束。

无仲裁者的同时签约(面对面)

    如果Alice和Bob正面对面坐着,那么他们可以这样来签约[1244]:

    (1)Alice签上她名字的第一个字母,并把合约递给Bob。

    (2)Bob签上他名字的第一个字母,并把合约递给Alice。

    (3)Alice签上她名字的第二个字母,并把合约递给Bob。

    (4)Bob签上他名字的第二个字母,并把合约递给Alice。

    (5)这样继续下去,直到Alice和Bob都签上他们的全名。

    如果你忽视掉这个协议的一个明显问题(Alice的名字比Bob长),这个协议照样有效。在只签了一个字母之后,Alice知道法官不会让她受合约条款约束。但签这个字母是有诚意的举动,并且Bob回之以同样有诚意的举动。

    在每一方都签了几个字母之后,或许可以让法官相信双方已签了合约,虽然如此,细节却是模糊的。当然在只签了第一个字母后他们确实不受约束,正如在签了全名之后他们理所当然受合约约束一样。在协议中哪一点上他们算是正式签约呢?在签了他们名字的一半之后?三分之二之后?四分之三之后?

    因为Alice或Bob都不能她或他受约束的准确点,他们每一位至少有些担心她或他在整个协议上都受合约约束。Bob在任一点上都无法说:“你签了四个字母而我只签了三个,你受约束,但我不受。”Bob也没有理由不继续这个协议。而且,他们继续得越久,法官裁决他们受合约约束的概率越大。另外,也不存在不继续执行这个协议的理由。毕竟他们都想签约,他们只是不想先于另一方签约。

无仲裁者的同时签约(非面对面)

    这个协议使用了同一类型的不确定性[138]。Alice和Bob轮流采用小步骤签署,直到双方都签约为止。

    在这个协议中,Alice和Bob交换一系列下面这种形式的签名消息:“我同意我以概率P接受这个合约约束。”

    消息的接方可以把它提交给法官,法官用概率p考虑被签署的合约。

    (1)Alice和Bob就签约应当完成的日期达成一致意见。

    (2)Alice和Bob确定一个双方都愿意用的概率差。例如,Alice可以决定她不愿以超过Bob概率2%以上的概率受合约约束。叫Alice的概率差为a,叫Bob的概率差为b。

    (3)Alice发送给Bob一份p=a的已签消息。

    (4)Bob送给Alice一份p=a+b已签署的消息。

    (5)令pˊ为Alice在前一步中从Bob那里收到消息的概率。Alice发送给Bob一份p= pˊ+a或1中较小的已签署消息。

    (6)令pˊ为Bob在前一步中从Alice那里收到消息的概率。Bob发送给Alice一份p= pˊ+b或1中较小的已签署消息。

    (7)Alice和Bob继续交替执行步骤(5)和步骤(6),直到双方都收到p=1的消息,或者已通过在第(1)步中达成一致的日期。

    随着协议的进行,Alice和Bob都以越来越大的概率同意接受合约约束。例如,Alice还定义她的的a为2%,Bob可以定义他的b为1%(如果他们选择较大的增量则更好;我们会在这里停留片刻)。Alice的第一份消息可能声明她以2%的概率受约束,Bob可能回答他以3%的概率接受约束。Alice的下一份消息可能声明她以5%的概率受约束,等等,直到双方都以100%的概率受约束。

    如果由于完成日期Alice和Bob二者完成这个协议,则万事大吉。否则,任何一方都可把合约拿给法官,并同时递上另一方的最后签的消息,法官在看合约之前在0或1之间随机选择一个。如果这个值小于另一方签名的概率,则双方都受合约约束。如果这个值大于那个概率,则双方都不受约束(法官接着保存这个值,以防需判定涉及同一合约的其它事件)。这就是以概率p受合约约束的意思。

    这是一个基本的协议,但还可以有更复杂的协议。法官可在一方缺席的情况下作出判决,法官的判决可约束双方或哪一方都不受约束;不存在一方受约束而另一方不受约束的情况。而且只要一方愿意有比另一方稍微高一点(不管多小)的概率受约束,这个协议将终止。

无需仲裁者的同时签约(使用密码技术)

    这种密码协议使用了同样小步进方法[529]。在协议描述中使用了DES,但也可用任一种对称算法。

    (1)Alice和Bob二者随机选择2n个DES密钥,分成一对对的。这些密钥对没有什么特别之处,它们只是因协议要求而那样分组。

    (2)Alice和Bob都产生n对消息,例如Ln和Rn:“这是我的第i个签名的左半部分”和:“这是我的第i个签名的右半部分。”标识符i从1取到n。每份消息可能也包含合约的数字签名以及时戳。如果另一方能产生一个单签名对的两半Li和Ri,那么就认为合约已被签署。

    (3)Alice和Bob二者用每个DES密钥对加密他们的消息对,左半消息用密钥对中的左密钥,右半消息用密钥对中的右密钥。

    (4)Alice和Bob相互发送给对方2n份加密消息,弄清哪份消息是哪对消息的哪一半。

    (5)Alice和Bob利用每一对的不经意传输协议相互送给对方,即, Alice送给Bob或用于独立地加密n对消息中每一对左半消息的密钥;或用于加密右半消息的密钥。Bob也这样做。他们可以交替地发送这些“半消息”或者先送100对,接着再送其余的——这都没有关系。现在Alice和Bob都有每一对密钥中的一个密钥,但都不知道对方有哪一半。

    (6)Alice和Bob用收到的密钥解密他们能解的那一半消息。他们确信解密消息是有效的。

    (7)Alice和Bob都把所有2n个DES密钥的第一个比特发送给对方。

    (8)Alice和Bob对所有2n个DES密钥的第二个比特、第三个比特。重复步骤(7),如此继续下去,直到所有DES密钥的所有比特都被传送出去。

    (9)Alice和Bob解密剩余一半消息对,合约被签署。

    (10)Alice和Bob交换在第(5)步的不经意传输中使用的私钥,并各方验证对方没有欺骗。

    为什么Alice和Bob必须通过所有步骤呢?让我们假设Alice想要欺骗,看看会发生什么。在第(4)步和第(5)步中,Alice可以通过送给Bob一批毫无意义的比特字符串来破坏这个协议。Bob能在第(6)步中发现这一点,即在他试图解密他收到的那一半时,Bob就可以安全地停止执行协议,此后Alice便不能解密Bob的任何消息对。

    如果Alice非常聪明,她可能只破坏协议的一半。她可以正确地送出每对的一半,但送一个毫无意义的字符串作为另一半。Bob只有50%的机会收到正确的一半,故Alice在一半的时间里可以进行欺骗。但是,这只有在只有一对密钥的情况下起作用。如果有两对密钥,这类欺骗可在25%的时间里成功。这就是n必须很大的原因。Alice必须正确地猜出n次不经意传输协议的结果;她有2n分之一的机会成功。如果n=10,Alice有1024分之一的机会欺骗Bob。

    Alice也可以在第(8)步中给Bob发送随机比特。也许Bob直到收到了全部密钥并试图解密余下的一半消息时才知道Alice送给他的是随机比特。但是,Bob这边也有机会发现。他已经收到了密钥的一半,并且Alice不知道是哪一半。如果n足够大,Alice如果确实送给他一个无意义的比特到他已收到的密钥中,则他能立即发现Alice在试图欺骗他。

    也许Alice将继续执行第(8)步直到她有足够多的密钥比特使用穷举攻击,然后再停止传送比特。DES有一个56比特长的密钥。如果她收到56比特中的40个比特,她只须试验216(65,536)个密钥便能读出这份消息——这个任务对计算机来说当然是轻而易举的。但是Bob有同样多数量的她的密钥比特(或最坏是少一个比特),故他也可以读出消息。Alice除了继续这个协议外别无选择。

    基本点是Alice必须公正地进行这个协议,因为要欺骗Bob的机会太小。在协议结束时,双方都有n个签名消息时,其中之一就足以作为一个有效的签名。

    有一个Alice可以进行欺骗的办法;她可以在第(5)步中发给Bob相同消息。Bob直到协议结束都不能察觉这点,但是他可以使用协议副本让法官相信Alice的欺骗行为。

    这类协议有两个弱点[138]。首先,如果一方比另一方有强大得多的计算能力,就会产生一个问题。例如,如果Alice使用穷举攻击的速度比Bob快,那么她能在第(8)步中较早地停止发送比特,并自己推算出Bob的密钥。Bob不能在一个合理的时间内同样做到这一步,将会很不幸。

    其次,如果一方提前终止协议,也会产生一个问题。如果Alice突然终止协议,双方都面对同样的计算量,但Bob没有任何实际合法的追索权,例如,如果合约要求他在一周内做一些事,而在Alice真正承诺前的某一时刻终止协议,使得Bob将不得不花费一年的计算量,那么就有了一个问题。这里的实际困难是没有一个整个过程能嘎然,而且双方都受约束或者双方都不受约束的近期截止期限。

    这些问题也适用于5.8节和5.9节中的协议。