1、公平交换协议的基本概念n公平交换协议的定义n公平交换协议的基本模型n公平交换协议的基本要求公平交换协议的定义n假设Alice想在Bob公司购买一张机票。Alice首先发出一个预订请求，Bob公司确认后向Alice发出一个通知。n问题：Alice发出了预订请求，但后来没有购买机票，Bob公司受损；另一方面，若Bob公司收到了预订请求，却将机票卖给了别人，那么Alice只好延期旅行。n如果只有一方诚实的执行协议，就无法保证双方的利益不受损失。即使Alice的请求和Bob公司的通知都具有不可否认性，也不能完全解决协议的公平性，这是因为双方的行为不具有同时性。若Alice首先发出一个不可否认请求，而B
2、ob没有进行响应，于是，Alice就面临风险；如果她在别处预订，就有可能买到两张机票；如果不预订，则有可能面临没有机票的风险。公平交换协议的定义n当一个系统涉及到两个或者多个互不信任的主体，就要考虑满足所有主体的安全性。n从主体利益的角度考虑，如果一个系统不会损害其中任何一个诚实主体的利益，那么该系统具有公平性。n从交换的结果考虑，如果在交换结束后，要么每一方都得到了他所期待的信息或者物品，要么每一方都没有得到任何有意义的东西，我们也认为系统具有公平性。n需要存在相应的安全机制来保证交换顺利进行。这种安全机制就是公平交换协议。公平交换协议的基本模型n假设desc()为交换商品的描述函数(对输入
3、的任何一个交换商品，返回一个对该物品的描述)，P、Q为参与双方，他们的交换物品用表示iP、iQ，期望得到的对方交换物品描述为dP、dQ。公平交换问题描述如下：n交换之前P输入iP、dQ、Q，Q输入iQ、dP、P，代表P想用iP跟Q交换描述为dQ的交换物品，Q想用iQ跟P交换描述为dP的交换物品。交换之后P输出iQ，Q输出iP。公平交换协议的基本模型PQ输入iP、dQ、Q 经过公平交换输出iQ，其中dQ=desc(Q)或者取消取消输出iP，其中dP=desc(P)输入iQ、dP、P 公平交换协议的基本要求n有效性：如果两个参与者行为正确，在不涉及第三方的情况下，仍能获得各自所需的东西。n秘密性：
4、交换必须保护用户的隐私信息。n高效实用性：协议的效率要高，以保证实用性。n不可否认性：在进行有效的交换后，交换的任何一方都不能对他所传递和收到的信息进行否认。公平交换协议的基本要求n公平性：在交换结束后，要么每一方都得到他所期待的物品(或服务)，要么每一方都没有得到任何有意义的东西。公平性又分为强公平性和弱公平性。强公平性：在协议的任何阶段，参与协议的任何诚实的主体都不处于劣势。交换结束后，参与交换的各方或者得到自己想要得到的东西，或者都没有得到任何有用的东西。弱公平性：在协议执行的某个阶段，即使诚实的主体处于某种程度的不公平，在以后的争论中，诚实的主体可以向仲裁者提供协议中的证据恢复公平性。
5、公平交换协议的基本要求n终止性：在协议执行的任何时间，每个参加者可以单方面中止协议而不破坏公平性。n第三方可验证性：发生纠纷时第三方可以进行仲裁，对不诚实的一方可以进行制裁。同时，如果第三方不诚实使得该协议对Alice不公平，则Alice可以向仲裁者证明第三方的不公正行为。n无滥用性：在多方公平交换模型中，参与交换的任意子集在协议的任何时刻，都无法向第三者证明他们有能力中止(或完成)协议。同时签约想要以价格 X 卖股票可以,愿意以价格 X 买stock brokercustomer在股票交易市场，签约是交易的有效证明同时签约n带有仲裁者的同时签约(非面对面)n无仲裁者的同时签约(面对面)n无仲
6、裁者的同时签约(非面对面)n无仲裁者的同时签约(使用密码技术)带有仲裁者的同时签约(非面对面)nAlice和Bob想订立一个合约。他们已经同意了其中的措词，但每个人都想等对方签名后再签名。如果是面对面的，这很容易：两人一起签。如果距离远的，他们可以用一个仲裁者。n与仲裁员签订合同 Alice Trend Bob SignA(C)SignB(C)SignA(C),SignA(C)SignB(SignA(C),SignB(SignA(C)SignB(SignA(C)同时签约带有仲裁者的同时签约n(1)Alice签署合约的一份副本并发送给Trent。n(2)Bob签署合约的一份副本并发送给Trent
7、。n(3)Trent发送一份消息给Alice和Bob，指明彼此都已签约。n(4)Alice签署合约的两份副本并发送给Bob。n(5)Bob签署合约的这两份副本，自己留下一份，并把另一份发送给Alice。n(6)Alice和Bob都通知Trent他们每个人都有了一份有他们两人合签的合约副本。n(7)Trent撕毁在每一份上只有一个签名的两份合约副本。带有仲裁者的同时签约n这个协议奏效是因为Trent防止了双方中的某一方进行欺骗。如果在步骤(5)中Bob拒绝签约，Alice可以向Trent要求一份已经由Bob签署的合约副本。如果在步骤(4)中Alice拒绝签名，Bob也可以这么做。当在步骤(3)中
8、Trent指明他收到了两份合约，Alice和Bob知道彼此已受到和约的约束。如果Trent在步骤(1)和(2)中没有收到这两份合约，他便撕掉已收到的那份，则两方都不受合约约束。无仲裁者的同时签约(面对面)n如果Alice和Bob正面对面坐着，那么他们可以这样来签约：n(1)Alice签上她名字的第一个字母，并把合约递给Bob；n(2)Bob签上他名字的第一个字母，并把合约递给Alice；n(3)Alice签上她名字的第二个字母，并把合约递给Bob；n(4)Bob签上他名字的第二个字母，并把合约递给Alice；n(5)这样继续下去，直到Alice和Bob都签上他们的全名。无仲裁者的同时签约(面对
9、面)n如果忽视掉这个协议的一个明显问题(Alice的名字比Bob长)，这个协议照样有效。n在每一方都签了几个字母之后，或许可以让法官相信双方已签了合约，虽然如此，细节却是模糊的。当然在只签了第一个字母后他们确实不受约束，正如在签了全名之后他们理所当然受合约约束一样。在协议中哪一点上他们算是正式签约呢？在签了他们名字的一半之后？三分之二之后？四分之三之后？无仲裁者的同时签约(面对面)n因为Alice或Bob都不能指出她或他受约束的准确点，他们每一位至少有些担心她或他在整个协议上都受合约约束。Bob在任一点上都无法说：“你签了四个字母而我只签了三个，你受约束，但我不受。”Bob也没有理由不继续这个
10、协议。而且，他们继续得越久，法官裁决他们受合约约束的概率越大。另外，也不存在不继续执行这个协议的理由。毕竟他们都想签约，他们只是不想先于另一方签约。无仲裁者的同时签约(非面对面)n在这个协议中，Alice和Bob交换一系列下面这种形式的签名消息：“我同意我以概率p接受这个合约约束。”n消息的接方可以把它提交给法官，法官用概率p考虑被签署的合约。无仲裁者的同时签约(非面对面)nAlice和Bob就签约应当完成的日期达成一致意见。nAlice和Bob确定一个双方都愿意用的概率差。例如，Alice可以决定她不愿以超过Bob概率2%以上的概率受合约约束。叫Alice的概率差为a，叫Bob的概率差为b。
11、nAlice发送给Bob一份p=a的已签消息。nBob送给Alice一份p=a+b已签署的消息。n令p 为Alice在前一步中从Bob那里收到消息的概率。Alice发送给Bob一份p=p+a或1中较小的已签署消息。无仲裁者的同时签约(非面对面)n令p 为Bob在前一步中从Alice那里收到消息的概率。Bob发送给Alice一份p=p+b或1中较小的已签署消息。nAlice和Bob继续交替执行步骤(5)和步骤(6)，直到双方都收到p=1的消息，或者已通过在第(1)步中达成一致的日期。无仲裁者的同时签约(非面对面)n随着协议的进行，Alice和Bob都以越来越大的概率同意接受合约约束。例如，Ali
12、ce还定义她的的a为2%，Bob可以定义他的b为1%(如果他们选择较大的增量则更好；我们会在这里停留片刻)。Alice的第一份消息可能声明她以2%的概率受约束，Bob可能回答他以3%的概率接受约束。Alice的下一份消息可能声明她以5%的概率受约束，等等，直到双方都以100%的概率受约束。无仲裁者的同时签约(非面对面)n如果这个协议不能顺利完成，任何一方都可把合约拿给法官，并同时递上另一方的最后签的消息，法官在看合约之前在0或1之间随机选择一个。如果这个值小于另一方签名的概率，则双方都受合约约束。如果这个值大于那个概率，则双方都不受约束(法官接着保存这个值，以防需判定涉及同一合约的其它事件)。
13、这就是以概率p受合约约束的意思。不经意传输协议 1.Alice产生两个 public-key/private-key 密钥对。她把公钥发送给Bob。2.Bob 首先选择一个 DES 密钥，然后随机选择Alice一个公钥加密密钥并发送它。3.Alice 解密 Bob的密钥两次,每一次使用她的一个私钥进行解密，得到一DES密钥 和一无意义的随机密钥4.Alice用得到的两个密钥加密她的两条消息,一个使用真正的DES密钥，而另一个使用无意义的随机密钥，并将它们发送 Bob5.Bob 使用DES 密钥解密，一个他可以阅读，另一个是乱码(注：Alice爱丽丝不知道Bob能够读取哪一个)6.最后,Alic
14、e 必须把她的私钥给 Bob，以便Bob能确认Alice没有欺骗他，她没有在第4步用两个密钥加密发送相同的消息。无需仲裁者的同时签约(使用密码技术)n(1)Alice和Bob二者随机选择2 n个DES密钥，分成一对对的。n(2)Alice和Bob都产生n对消息，例如Ln和Rn：“这是我的第i个签名的左半部分”和：“这是我的第i个签名的右半部分。”标识符i从1取到n。每份消息可能也包含合约的数字签名以及时戳。如果另一方能产生一个单签名对的两半Li和Ri，那么就认为合约已被签署。无需仲裁者的同时签约(使用密码技术)n(3)Alice和Bob二者用每个DES密钥对加密他们的消息对，左半消息用密钥对中
15、的左密钥，右半消息用密钥对中的右密钥。n(4)Alice和Bob相互发送给对方2 n份加密消息，弄清哪份消息是哪对消息的哪一半。n(5)Alice和Bob利用每一对密钥的不经意传输协议相互送给对方，即Alice送给Bob或用于独立地加密n对消息中每一对左半消息的密钥；或用于加密右半消息的密钥。Bob也这样做。无需仲裁者的同时签约(使用密码技术)n(6)Alice和Bob用收到的密钥解密他们能解的那一半消息。他们确信解密消息是有效的。(验证)n(7)Alice和Bob都把所有2 n个DES密钥的第一个比特发送给对方。(验证)n(8)Alice和Bob对所有2 n个DES密钥的第二个比特、第三个比
16、特。重复步骤(7)，如此继续下去，直到所有DES密钥的所有比特都被传送出去。(验证)n(9)Alice和Bob解密剩余一半消息对，合约被签署。n(10)Alice和Bob交换在第(5)步的不经意传输中使用的私钥，并且各方验证对方没有欺骗。无需仲裁者的同时签约(使用密码技术)n假设Alice想要欺骗。在第（4）步和第（5）步中，Alice可以通过送给Bob一批毫无意义的比特字符串来破坏 这个协议。Bob能在第（6）步中发现这一点n如果Alice非常聪明，她可以正确地送出每对的一半，但送一 个毫无意义的字符串作为另一半。Bob只有50%的机会收到正确的一半，故Alice可以50%的概率进行欺骗。但
17、是，这只有在只有一对密钥的情况下起作用。如果有两对密钥，这类欺骗可在25%的概率成功。这就是n必须很大的原因。Alice必须正确地猜出n次 不经意传输协议的结果；她有2n分之一的机会成功。无需仲裁者的同时签约(使用密码技术)nAlice也可以在第（8）步中给Bob发送随机比特。也许Bob直到收到了全部密钥并试图解 密余下的一半消息时才知道Alice送给他的是随机比特。但是，Bob这边也有机会发现。他已经收到了密钥的一半，并且Alice不知道是哪一半。如果n足够大，Alice如果确实送 给他一个无意义的比特，则他能立即发现Alice在试图欺骗他。(利用不经意传输收到的密钥检查)n也许Alice将
18、继续执行第（8）步直到她有足够多的密钥比特使用穷举攻击，然后再停止 传送比特。DES有一个56比特长的密钥。如果她收到56比特中的40个比特，她只须试验2 16（65，536）个密钥便能读出这份消息-这个任务对计算机来说当然是轻而易举的。但 是Bob有同样多数量的她的密钥比特（或最坏是少一个比特），故他也可以读出消息。A lice除了继续这个协议外别无选择。无需仲裁者的同时签约(使用密码技术)n基本点是Alice必须公正地进行这个协议，因为要欺骗Bob的机会太小。在协议结束时，双方都有n个签名消息时，其中之一就足以作为一个有效的签名。n有一个Alice可以进行欺骗的办法；她可以在第（5）步中发
19、给Bob相同消息。Bob直到协 议结束都不能察觉这点，但是他可以使用协议副本让法官相信Alice的欺骗行为。(Bob可以通过不经意传输中选择L或R阻止)无需仲裁者的同时签约(使用密码技术)n这类协议有两个弱点。首先，如果一方比另一方有强大得多的计算能力，就会产生一个问题。例如，如果Alice使用穷举攻击的速度比Bob快，那么她能在第(8)步中较早地停止发送比特，并自己推算出Bob的密钥。Bob不能在一个合理的时间内同样做到这一步，将会很不幸。n其次，如果一方提前终止协议，也会产生一个问题。如果Alice突然终止协议，双方都面对同样的计算量，但Bob没有任何实际合法的追索权，例如，如果合约要求他
20、在一周内做一些事，而在Alice真正承诺前的某一时刻终止协议，使得Bob将不得不花费一年的计算量，那么就有了一个问题。数字证明邮件 n假设Alice要把一条消息送给Bob，但如果没有签名的收条，她就不让他读出。n(1)Alice用一个随机的DES密钥加密她的消息，并把它发送给Bob。n(2)Alice产生n对DES密钥。每对密钥的第一个密钥是随机产生的；每对密钥的第二个密钥是第一个密钥和消息加密密钥的异或。n(3)Alice用她的2n个密钥的每一个加密一份假消息。n(4)Alice把所有加密消息都发送给Bob，保证他知道哪些消息是哪一对的哪一半。n(5)Bob产生n对随机DES密钥。n(6)B
21、ob产生一对指明一个有效收条的消息。比较好的消息可以是“这是我收条的左半”和“这是我收条的右半”，再附加上某种类型的随机比特串。他做了n个收条对，每个都编上号。如同先前的协议一样，如果Alice能产生一个收条的两半(编号相同)和她的所有加密密钥，这个收条被认为是有效的。n(7)Bob用DES密钥对加密他的每一对消息，第i份消息用第i个密钥，左半消息用密钥对中的左密钥，右半消息用密钥对中的右密钥。n(8)Bob把他的消息对发送给Alice，保证Alice知道哪些消息是哪一对的哪一半。n(9)Alice和Bob利用不经意传输协议发送给对方每个密钥对。那就是说，对n对中的每一对而言，Alice或者送
22、给Bob用来加密左半消息的密钥，或者送给Bob用来加密右半消息的密钥。Bob也同样这么做。他们可以或者交替传送这些一半，或者一方发送n个，然后另一方再发送n个这都没有关系。现在Alice和Bob都有了每个密钥对中的一个密钥，但是都不知道对方有哪些一半。n(10)Alice和Bob都解密他们能解的那些一半，并保证解密消息是有效的。(检查)n(11)Alice和Bob送给对方所有2n个DES密钥中的第一个比特(如果他们担心窃听者可能会读到这个邮件消息，那么他们应当对相互的传输加密)。(检查)n(12)Alice和Bob对所有2n个DES密钥中的第二比特、第三比特都重复第(11)步，如此继续下去，直
23、到 所有DES密钥的所有比特都传送完。(检查)n(13)Alice和Bob解密消息对中的余下一半。Alice有了一张来自Bob的有效收条，而Bob能异或任一密钥对以得到原始消息加密密钥。n(14)Alice和Bob交换在不经意传输协议期间使用的私钥，同时每一方验证另一方没有进行欺骗。nBob的第（5）至第（8）步和Alice和Bob的第（9）至第（12）步都和签约协议相同。意 想不到的手法是Alice的所有假消息。它们给予Bob一些办法来检查第（10）步中Alice的 不经意传输的有效性，这可以迫使Alice在第（11）至第（13）步期间保持诚实。并且如 同同时签约协议一样，完成协议要求Ali
24、ce的一个消息对的左右两半。秘密的同时交换n假设Alice知道秘密A，Bob知道秘密B。如果Bob告诉Alice秘密B，Alice就告诉Bob秘密A；如果Alice告诉Bob秘密A，Bob就告诉Alice秘密B。他们都想知道对方的秘密，但是在谁先说出自己知道的秘密的问题上他们出现了矛盾。他们都担心在说出自己知道的秘密后，对方不再说出他知道的秘密。秘密的同时交换nAlice使用A作消息完成第（1）至第（4）步。Bob用B作他的消息完成类似的步骤。Alice和Bob在第（9）步中执行不经意传输，在第（10）步中解密他们能解密的那些一半消息，并在第（11）和第（12）步中处理完那些迭代。如果他们要防范Eve，他们应当加密他 们的消息。最后，Alice和Bob解密消息对余下的一半，并异或任一密钥对来得到原始消 息加密密钥。秘密的同时交换n这个协议使Alice和Bob可以同时交换秘密，但没有谈到所交换秘密的质量。Bob将得到Alice送给他的任何秘密。Alice可以允诺给Bob Minotaur迷宫的解法，但实际上送给他一张波士顿地铁系统交通图。
