公平交换协议ppt课件.ppt

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