可证明平安的理性拜托计算协议

委托计算是指计算能力相对较弱或资源受 限的委托方将函数 F 的计算任务委托给不信任的 计算方，计算方将返回一个计算结果及计算结果的 正确性证明给委托方。委托方通过执行验证协议来 验证返回结果的正确性，并且委托方验证该证明的 工作量比计算函数 F 的开销要小得多，否则将失去 委托计算的意义。委托计算一直受到学者的广泛研 究，主要有基于复杂性理论构造方案和基于密码技 术构造方案。基于复杂性理论构造方案主要应用的 工具是交互式证明系统、PCP（probabilistic checking of proofs）定理等，Chung 等在随机语 言模型下对非交互式委托计算进行研究，给出了有 效的解决方法。基于密码技术构造方案主要应用的 工具有全同态加密、基于属性加密、混淆电路等，Gennaro 等利用文献的混淆电路构造了非 交互式的委托计算方案，该方案有效地解决了基于 计算理论方案的困难性问题。 理性委托计算属于理性密码学的研究范围，针对 理性密码协议的研究领域，大多学者较多地关注利用 博弈论方法来解决秘密共享、安全多方计算等问题， 涉及理性委托计算的研究尚少。理性委托计算结合博 弈论与委托计算的思想，协议中参与者都是理性的， 而不是诚实的或是恶意的，且协议中通过效用函数来 保证计算结果的正确性。传统的委托计算协议中，通 常假设参与者要么是诚实的，要么是恶意的，但实际 应用中，参与者大多是理性的，因此理性委托计算的 研究成为当前的研究热点。Azar 等根据适当的评分 规则，提出了一种理性证明系统，该系统中参与者既 不是诚实的，也不是恶意的，而是理性的；随后 Azar 等又利用 Utility Gaps 的思想构造了一种超有效的 理性证明系统；Guo 等通过对理性证明系统的研 究，解决了证明者计算能力受限的理性证明系统问 题；Tian 等从理性的角度分析了安全通信问题， 并提出了贝叶斯理性秘密共享方案；随后 Chen 等从复杂性理论的角度研究了当存在多个证明者时，理 性证明系统的理性证明问题。 关于理性委托计算的安全性问题是研究者最 为关心的，如何利用效用函数构建安全可靠的理性 委托计算协议更是当前的研究需求。Kilian 等提出了证明者使用 Merkle 树向验证者发送对整个 证明的短承诺的有效论证，证明者可以交互式地打开验证者的请求。Micali’s CS Proof可以获得 非交互式解决方案，该解决方案根据随机 oracle 应用承诺字符串来选择要打开的请求，消除涉及 参数的交互。在最近的研究中，更多研究者较为 关注非交互式协议，并且可以在标准模型中给予 证明。 本文结合混淆电路和全同态加密技术提出了 一种可证明安全的理性委托计算方案，该方案保证 了所有理性参与者都得到最优的利益，保证委托计 算输入和输出的隐私性。

1) 通过分析参与者的行为策略及参与者选择 行为策略而得到的效用，设计了理性委托计算博弈 模型。

2) 根据构建的委托计算博弈模型中纳什均衡 需求，以及理性委托计算的安全需求，设计了可证 明安全的理性委托计算安全模型。

3) 利用随机化混淆电路可重用的优点与全 同态加密技术，保证了理性参与者结果的正确性 及委托计算输入和输出隐私，从而构建了安全的 理性委托计算协议。

4) 对协议的安全性与性能进行分析，证明了 协议的安全性与输入输出隐私性，保证了所有参 与者在协议中能获得利益的最大化即达到唯一 纳什均衡。