Fair Secure Two-Party Computation Protocol Based on Game Theory
-
摘要: 针对传统安全两方计算无法实现完全公平性的问题,结合博弈论方法,将参与者看作是理性的,提出了理性安全两方计算协议。首先,在扩展式博弈框架下,给出安全两方计算的博弈模型;其次,根据博弈模型描述,给出理性安全两方计算理想函数FRPCP以及理性安全两方计算协议RPCP;最后对协议的安全性、公平性及纳什均衡进行了分析。分析结果表明,在混合模型下,协议RPCP能安全地实现理想函数FRPCP,并且在BDH困难假设下,协议RPCP中各理性参与者的最佳策略是选择合作,当博弈达到纳什均衡时,参与者双方能公平地获得计算结果。Abstract: Since complete fairness cannot be achieved in traditional two-party computation, a rational two-party computation protocol, based on game theory, was proposed, which regards player as rational. At first, the game model of secure two-party computation was put forward in the extensive game framework. Secondly, according to the description of game model, the ideal function FRPCP of rational secure two-party computation and rational two-party computation protocol RPCP were presented. Finally, the security, fairness and Nash Equilibrium of protocol was analyzed. The analysis results show that the protocol RPCP can realize ideal function FRPCP safely in the hybrid model; meanwhile, under the Bilinear Diffie-Hellman (BDH) assumption, the best strategy of the rational players is to choose cooperation; and when the game achieves Nash Equilibrium, all players can obtain the right results fairly.
-
Key words:
- secure two-party computation /
- extensive game /
- Nash Equilibrium /
- fairness
-
YAO A C. Protocols for secure computation[C]//Proc. of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS). Los Alamitos: IEEE Computer Society Press, 1982: 160-164. GOLDREICH O, MICALI S, WIGDERSON A. How to play any mental game[C]//Proc. of the 19th Annual ACM Symposium on Theory of Computing (STOC). New York: ACM Press, 1987: 218-229. GOLDWASSER S. Multi-party computation: past and present[C]//Proc. of the 16th Annual ACM Symposium on Principles of Distributed Computing. New York: ACM Press, 1997: 21-24 GOLDREICH O. Foundations of cryptography: volume 2, basic applications[M]. Cambridge: Cambridge University Press, 2004: 79-92. BLAKE I F, KOLESNIKOV V. Strong condition oblivious transfer and computing on intervals[G]//Proc. of Advances in Cryptology. Berlin: Springer, 2004: 515-529. 李顺东,戴一奇,游启友. 姚氏百万富翁问题的高效解决方案[J]. 电子学报,2005,33(5): 769-773. LI Shundong, DAI Yiqi, YOU Qiyou. An efficient solution to Yao' millionaires' problem[J]. Acta Electronica Sinica, 2005, 33(5): 769-773. LIN H Y, TZENG W G. An efficient solution to the millionaires problem based on homomorphic encryption[C]//In ASIA crypto logy 2005. Berlin: Springer, 2005: 456-466. LINDELL Y, PINKAS B. A proof of Yao's protocol for secure two-party computation[J]. Journal of Cryptology, 2009, 22(5): 161-188. 唐春明,石桂花,姚正安. 排序问题的安全多方计算协议[J]. 中国科学:信息科学,2011,41(7): 789-797. TANG Chunming, SHI Guihua, YAO Zheng'an. Secure multi-party computation protocol for sequencing problem[J]. Scientia Sinica Informationis, 2011, 41(7): 789-797. 田有亮,彭长根,马建峰,等. 通用可组合公平安全多方计算协议[J]. 通信学报,2014,35(2): 54-62. TIAN Youliang, PENG Changgen, MA Jianfeng, et al. Universally composable secure multiparty computation protocol with fairness[J]. Journal on Communications, 2014, 35(2): 54-62. CLEVE R. Limits on the security of coin flips when half the processors are faulty[C]// In 18th Annual ACM Symposium on Theory of Computing. Berkeley:, 1986: 364-369. GORDON D, HAZAY C, KATZ J, et al. Complete fairness in secure two-party computation[C]//Proc of the 40th Annual ACM Symposium on Theory of Computing (STOC). New York: ACM Press, 2008: 413-422. HALPERN J, TEAGUE V. Rational secret sharing and multiparty computation[C]//Proc of the 36th Annual ACM Symposium on Theory of Computing(STOC). New York: ACM Press, 2004: 623-632. KOL G, NAOR M. Games for exchanging information[C]//Proc. of the 40th Annual ACM Symposium on Theory of Computing(STOC). New York: ACM, 2008: 423-432. ABRAHAM I, DOLEV D, GONEN R, et al. Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation[C]//Proc. of the 25th ACM symposium on Principles of distributed computing(PODC'06). New York: ACM, 2006: 53-62. LYSYANSKAYA A, TRIANDOPOULOS N. Rationality and adversarial behavior in multiparty computation[G]//Proc. the 26th Annual Cryptology. Berlin: Springer, 2006: 180-197. ASHAROV G, CANETTI R, HAZAY C. Towards a game theoretic view of secure computation[G]//Proc. of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2011: 426-445. GROCE A, KATZ J. Fair computation with rational player[G]//Proc. of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 81-98. 张恩,蔡永泉. 理性的安全两方计算协议[J]. 计算机研究与发展,2013,50(7): 1409-1417. ZHANG En, CAI Yongquan. Rational secure two-party computation protocol[J]. Journal of Computer Research and Development, 2013, 50(7): 1409-1417. 王伊蕾,郑志华,王皓,等. 满足可计算序贯均衡的理性公平计算[J]. 计算机研究与发展,2014,51(7): 1527-1537. WANG Yilei, ZHENG Zhihua, WANG Hao, et al. Rational fair computation with computational sequential equilibrium[J]. Journal of Computer Research and Development, 2014, 51(7): 1527-1537. OSBORNE M, RUBINSTEIN A. A course in game theory[M]. Cambridge: MIT Press, 2004: 10-15. KATZ J. Bridging game theory and cryptography:recent results and future directions[G]//Proc. of the 5th Theory of Cryptography Conf(TCC 2008). Berlin: Springer, 2008: 251-25.
点击查看大图
计量
- 文章访问数: 552
- HTML全文浏览量: 69
- PDF下载量: 167
- 被引次数: 0