基于电路计算的理性安全多方求和协议
|
摘要
安全求和协议作为安全多方计算的一种实例,在分布式数据挖掘、统计分析和电子选举等领域有着非常广泛的应用.但是传统协议在求和过程中存在计算不公平的问题.针对这个问题,本文结合博弈论和密码算法,提出了一种基于电路计算的理性安全多方求和协议.首先对参与者在求和过程中的策略和效益进行了分析和设计,构建了安全多方求和电路计算的概率效用模型;然后利用改进之后的偏向0的投币协议所产生的随机字符串隐藏多方求和计算结果;最后参与者通过逐步释放的方法揭示最后的计算结果,同时不会泄露参与者自身的隐私输入.本文所设计的协议不需要拥有大多数诚实参与者这个强条件,可以有效验证成员欺诈行为、消除参与者在多方求和计算过程中的合谋动机,从而保证每个成员在标准点对点通信网络下能够公平地获得求和结果.
The secure sum protocol is given as an example of secure multiparty computation, which has numerous applications such as data mining, statistical analysis, and electronic election. However,traditional secure sum protocols cannot guarantee the fairness. To address this problem, this study proposes a rational secure sum protocol based on circuit evaluation, combining game theory, and cryptography. To begin with, strategies of participants are designed and the model of probabilistic payoffs for circuit computation is developed. Besides, a random string generated by the improved coin flips protocol biased to 0 is used to mask the result. Finally, participants reveal the output by using a method of gradual release. Meanwhile, this method will not reveal participants' private inputs. The protocol does not need to have the strong conditions of most honest participants, and can effectively verify the members' deceit. Therefore, every participant has no incentive to conspire, and the protocol can guarantee that every participant can obtain the correct sum in standard point-to-point communication networks.
The secure sum protocol is given as an example of secure multiparty computation, which has numerous applications such as data mining, statistical analysis, and electronic election. However,traditional secure sum protocols cannot guarantee the fairness. To address this problem, this study proposes a rational secure sum protocol based on circuit evaluation, combining game theory, and cryptography. To begin with, strategies of participants are designed and the model of probabilistic payoffs for circuit computation is developed. Besides, a random string generated by the improved coin flips protocol biased to 0 is used to mask the result. Finally, participants reveal the output by using a method of gradual release. Meanwhile, this method will not reveal participants' private inputs. The protocol does not need to have the strong conditions of most honest participants, and can effectively verify the members' deceit. Therefore, every participant has no incentive to conspire, and the protocol can guarantee that every participant can obtain the correct sum in standard point-to-point communication networks.
引文
[1]CLIFTON C,KANTARCIOGLU M,VAIDYA J,et al.Tools for privacy preserving distributed data mining[J].ACM SIGKDD Explorations Newsletter,2002,4(2):28-34.[DOI:10.1145/772862.772867]
[2]SCHNEIER B.Applied Cryptography:Protocols,Algorithms,and Source Code in C[M].New York,John Wiley&Sons,Inc.1996:115-135.
[3]KANTARCIOGLU M,CLIFTON C.Privacy-preserving distributed mining of association rules on horizontally partitioned data[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1026-1037.[DOI:10.1109/TKDE.2004.45]
[4]SHEPARD S,KRESMAN R,DUNNING L.Data mining and collusion resistance[C].In:Proceedings of the World Congress on Engineering 2009,Vol.1.London,UK,2009:283-288.
[5]MEHNAZ S,BELLALA G,BERTINO E.A secure sum protocol and its application to privacy-preserving multiparty analytics[C].In:Proceedings of the 22nd ACM on Symposium on Access Control Models and Technologies.ACM,2017:219-230.[DOI:10.1145/3078861.3078869]
[6]LIU W,WANG Y B,FAN W Q.An novel protocol for the quantum secure multi-party summation based on twoparticle bell states[J].International Journal of Theoretical Physics,2017,56(9):2783-2791.[DOI:10.1007/s10773-017-3442-3]
[7]JUNG T,LI X Y,WAN M.Collusion-tolerable privacy-preserving sum and product calculation without secure channel[J].IEEE Transactions on Dependable and Secure Computing,2015,12(1):45-57.[DOI:10.1109/TD-SC.2014.2309134]
[8]ASHOURI-TALOUKI M,BARAANI-DASTJERDI A.Cryptographic collusion-resistant protocols for secure sum[J].International Journal of Electronic Security and Digital Forensics,2017,9(1):19-34.[DOI:10.1504/I-JESDF.2017.10002631]
[9]GORDON S D,HAZAY C,KATZ J,et al.Complete fairness in secure two-party computation[J].Journal of the ACM(JACM),2011,58(6):24.[DOI:10.1145/1374376.1374436]
[10]ZHANG E,CAI Y Q.Rational secure two-party computation protocol[J].Journal of Computer Research and Development,2013,50(7):1409-1417.[DOI:10.7544/issn1000-1239.2013.20111614]张恩,蔡永泉.理性的安全两方计算协议[J].计算机研究与发展,2013,50(7):1409-1417.[DOI:10.7544/issn1000-1239.2013.20111614]
[11]LINDELL Y.Fast cut-and-choose based protocols for malicious and covert adversaries[C].In:Advances in Cryptology-CRYPTO 2013,Part II.Springer Berlin Heidelberg,2013:1-17.[DOI:10.1007/978-3-642-40084-1_1]
[12]ASHAROV G,LINDELL Y,RABIN T.A full characterization of functions that imply fair coin tossing and ramifications to fairness[C].In:Theory of Cryptography-TCC 2013.Springer Berlin Heidelberg,2013:243-262.[DOI:10.1007/978-3-642-36594-2_14]
[13]AGRAWAL S,PRABHAKARAN M.On fair exchange,fair coins and fair sampling[C].In:Advances in Cryptology-CRYPTO 2013,Part I.Springer Berlin Heidelberg,2013:259-276.[DOI:10.1007/978-3-642-40041-4_15]
[14]TIAN Y L,PENG C G,Ma J F,el at.Universally composable secure multiparty computation protocol with fairness[J].Journal on Communications,2014,2(5):54-62.[DOI:10.3969/j.issn.1000-436x.2014.02.008]田有亮,彭长根,马建峰,等.通用可组合公平安全多方计算协议[J].通信学报,2014,35(2):54-62.[DOI:10.3969/j.issn.1000-436x.2014.02.008]
[15]ZHANG E,LI F,NIU B,et al.Server-aided private set intersection based on reputation[J].Information Sciences,2017,387:180-194.[DOI:10.1016/j.ins.2016.09.056]
[16]KARGUPTA H,DAS K,LIU K.A game theoretic approach toward multi-party privacy-preserving distributed data mining[R].Technical Report TR-CS_01_07,Department of Computer Science and Electrical Engineering,University of Maryland-Baltimore County.Baltimore,MD,USA.
[17]WANG Y L,XU Q L.Survey on rational secure multi-party computation[J].Journal of Cryptologic Research,2014,1(5):481-490.[DOI:10.13868/j.cnki.jcr.000045]王伊蕾,徐秋亮.理性安全多方计算研究[J].密码学报,2014,1(5):481-490.[DOI:10.13868/j.cnki.jcr.000045]
[18]GOLDREICH O.Foundations of Cryptography-Vol.II,Basic Applications[M].New York,Cambridge University Press,2009:693-723.[DOI:10.1017/CBO9780511721656]
[19]BEAVER D,GOLDWASSER S.Multiparty computation with faulty majority[C].in:Proceedings of the 30th Annual Symposium on Foundations of Computer Science(SFCS’89).ACM,1989:468-473.[DOI:10.1109/SFC-S.1989.63520]
[2]SCHNEIER B.Applied Cryptography:Protocols,Algorithms,and Source Code in C[M].New York,John Wiley&Sons,Inc.1996:115-135.
[3]KANTARCIOGLU M,CLIFTON C.Privacy-preserving distributed mining of association rules on horizontally partitioned data[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1026-1037.[DOI:10.1109/TKDE.2004.45]
[4]SHEPARD S,KRESMAN R,DUNNING L.Data mining and collusion resistance[C].In:Proceedings of the World Congress on Engineering 2009,Vol.1.London,UK,2009:283-288.
[5]MEHNAZ S,BELLALA G,BERTINO E.A secure sum protocol and its application to privacy-preserving multiparty analytics[C].In:Proceedings of the 22nd ACM on Symposium on Access Control Models and Technologies.ACM,2017:219-230.[DOI:10.1145/3078861.3078869]
[6]LIU W,WANG Y B,FAN W Q.An novel protocol for the quantum secure multi-party summation based on twoparticle bell states[J].International Journal of Theoretical Physics,2017,56(9):2783-2791.[DOI:10.1007/s10773-017-3442-3]
[7]JUNG T,LI X Y,WAN M.Collusion-tolerable privacy-preserving sum and product calculation without secure channel[J].IEEE Transactions on Dependable and Secure Computing,2015,12(1):45-57.[DOI:10.1109/TD-SC.2014.2309134]
[8]ASHOURI-TALOUKI M,BARAANI-DASTJERDI A.Cryptographic collusion-resistant protocols for secure sum[J].International Journal of Electronic Security and Digital Forensics,2017,9(1):19-34.[DOI:10.1504/I-JESDF.2017.10002631]
[9]GORDON S D,HAZAY C,KATZ J,et al.Complete fairness in secure two-party computation[J].Journal of the ACM(JACM),2011,58(6):24.[DOI:10.1145/1374376.1374436]
[10]ZHANG E,CAI Y Q.Rational secure two-party computation protocol[J].Journal of Computer Research and Development,2013,50(7):1409-1417.[DOI:10.7544/issn1000-1239.2013.20111614]张恩,蔡永泉.理性的安全两方计算协议[J].计算机研究与发展,2013,50(7):1409-1417.[DOI:10.7544/issn1000-1239.2013.20111614]
[11]LINDELL Y.Fast cut-and-choose based protocols for malicious and covert adversaries[C].In:Advances in Cryptology-CRYPTO 2013,Part II.Springer Berlin Heidelberg,2013:1-17.[DOI:10.1007/978-3-642-40084-1_1]
[12]ASHAROV G,LINDELL Y,RABIN T.A full characterization of functions that imply fair coin tossing and ramifications to fairness[C].In:Theory of Cryptography-TCC 2013.Springer Berlin Heidelberg,2013:243-262.[DOI:10.1007/978-3-642-36594-2_14]
[13]AGRAWAL S,PRABHAKARAN M.On fair exchange,fair coins and fair sampling[C].In:Advances in Cryptology-CRYPTO 2013,Part I.Springer Berlin Heidelberg,2013:259-276.[DOI:10.1007/978-3-642-40041-4_15]
[14]TIAN Y L,PENG C G,Ma J F,el at.Universally composable secure multiparty computation protocol with fairness[J].Journal on Communications,2014,2(5):54-62.[DOI:10.3969/j.issn.1000-436x.2014.02.008]田有亮,彭长根,马建峰,等.通用可组合公平安全多方计算协议[J].通信学报,2014,35(2):54-62.[DOI:10.3969/j.issn.1000-436x.2014.02.008]
[15]ZHANG E,LI F,NIU B,et al.Server-aided private set intersection based on reputation[J].Information Sciences,2017,387:180-194.[DOI:10.1016/j.ins.2016.09.056]
[16]KARGUPTA H,DAS K,LIU K.A game theoretic approach toward multi-party privacy-preserving distributed data mining[R].Technical Report TR-CS_01_07,Department of Computer Science and Electrical Engineering,University of Maryland-Baltimore County.Baltimore,MD,USA.
[17]WANG Y L,XU Q L.Survey on rational secure multi-party computation[J].Journal of Cryptologic Research,2014,1(5):481-490.[DOI:10.13868/j.cnki.jcr.000045]王伊蕾,徐秋亮.理性安全多方计算研究[J].密码学报,2014,1(5):481-490.[DOI:10.13868/j.cnki.jcr.000045]
[18]GOLDREICH O.Foundations of Cryptography-Vol.II,Basic Applications[M].New York,Cambridge University Press,2009:693-723.[DOI:10.1017/CBO9780511721656]
[19]BEAVER D,GOLDWASSER S.Multiparty computation with faulty majority[C].in:Proceedings of the 30th Annual Symposium on Foundations of Computer Science(SFCS’89).ACM,1989:468-473.[DOI:10.1109/SFC-S.1989.63520]