字符串模式匹配的安全多方计算
|
摘要
安全多方计算是近年来国际密码学界研究的热点问题之一,是信息社会隐私保护的核心技术.很多研究者已经对其进行了深入研究,并提出了各种各样的具有实际应用背景的安全多方计算问题以及它们的解决方案.本文研究字符串模式匹配的安全多方计算问题.保密地判断字符串模式匹配问题是安全多方计算的一个重要组成部分,在信息检索、信息过滤、入侵检测、病毒检测、计算生物学等方面有重要的意义,同时在拍卖,招标等其他商业领域也有广泛的应用前景.为了保密地判断两个字符串是否模式匹配,本文首先借助Goldwasser-Micali异或同态加密算法设计了判断两个字符串是否相等的协议;然后基于BMH算法提出了高效的字符串模式匹配协议;最后将字符串模式匹配问题转化成集合成员判定问题,设计了保密性更好,计算复杂性和通信复杂性更低的新协议.利用模拟范例对以上协议做出了安全性分析,并证明了协议是正确的.同时给出了以上协议计算复杂性和通信复杂性的理论分析,通过真实数据集实验验证了以上协议的高效性.
Secure multiparty computation is a research focus in the international cryptographic community and a key privacy preserving technique in cyberspace. A variety of SMC problems and relative solutions have been presented in public literatures. This paper studies an SMC problem of privacy-preserving string matching. As an important case of secure multi-party computation, it has important theoretical significance and broad applications in auction, bidding and some other electronic commerce activities. To privately determine whether two strings match, based on the XOR homomorphism of Goldwasser-Micali probabilistic encryption algorithm, we first present a protocol to determine whether two strings are equal. Then we propose a protocol to privately determine whether two strings match based on BMH algorithm with higher efficiency. Finally, we design a more efficient and more secure protocol by changing two strings matching problem into set-inclusion problem. In addition, we prove that these protocols are secure using simulation paradigm in the semi-honest model and analyze their correctness. We also analyze the computational complexities and communication complexities of the proposed protocols and show that these protocols are efficient.
Secure multiparty computation is a research focus in the international cryptographic community and a key privacy preserving technique in cyberspace. A variety of SMC problems and relative solutions have been presented in public literatures. This paper studies an SMC problem of privacy-preserving string matching. As an important case of secure multi-party computation, it has important theoretical significance and broad applications in auction, bidding and some other electronic commerce activities. To privately determine whether two strings match, based on the XOR homomorphism of Goldwasser-Micali probabilistic encryption algorithm, we first present a protocol to determine whether two strings are equal. Then we propose a protocol to privately determine whether two strings match based on BMH algorithm with higher efficiency. Finally, we design a more efficient and more secure protocol by changing two strings matching problem into set-inclusion problem. In addition, we prove that these protocols are secure using simulation paradigm in the semi-honest model and analyze their correctness. We also analyze the computational complexities and communication complexities of the proposed protocols and show that these protocols are efficient.
引文
[1]GOLDWASSER S.Multi party computations:past and present[C].In:Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing.ACM,1997:1–6.
[2]GOLDREICH O.Secure multi-party computation(working draft)[OL].http://www.wisdom.weizmann.ac.ilhomeoded public-html foc.html,2002
[3]FREEDMAN M J,NISSIM K,PINKAS B.Efficient private matching and set intersection[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:1–19.
[4]LYNN B,PRABHAKARAN M,SAHAI A.Positive results and techniques for obfuscation[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:20–39.
[5]AGGARWAL G,MISHRA N,PINKAS B.Secure computation of the k th-ranked element[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:40–55.
[6]FITZI M,HOLENSTEIN T,WULLSCHLEGER J.Multi-party computation with hybrid security[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:419–438.
[7]ISHAI Y,KUSHILEVITZ E.On the hardness of information-theoretic multiparty computation[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:439–455.
[8]GOLLE P,JUELS A.Dining cryptographers revisited[C].In:Advances in Cryptology—Eurocrypt 2004.Springer Berlin Heidelberg,2004:456–473.
[9]YAO A.Protocols for secure computations[C].In:23rd Annual Symposium on Foundations of Computer Science,1982.IEEE,1982:160–164.
[10]Goldreich O,Micali S,Wigderson A.How to play any mental game[C].In:Proceedings of the nineteenth annual ACM symposium on Theory of computing.ACM,1987:218–229.
[11]LINin H Y,TZENG W G.An efficient solution to the millionaires’problem based on homomorphic encryption[C].In:International Conference on Applied Cryptography and Network Security.Springer Berlin Heidelberg,2005:456–466.
[12]LI S D,WANG D S.Efficient secure multiparty computation based on homomorphic encryption[J].Dianzi Xuebao(Acta Electronica Sinica),2013,41(4):798–803.
[13]SHEIKH R,MISHRA D K,KUMAR B.Secure multiparty computation:from millionaires problem to anonymizer[J].Information Security Journal:A Global Perspective,2011,20(1):25–33.
[14]GRIGORIEV D,SHPILRAIN V.Yao’s Millionaires’problem and decoy-based public key encryption by classical physics[J].International Journal of Foundations of Computer Science,2014,25(04):409–417.
[15]LINDELL Y,PINKAS B.Privacy preserving data mining[J].Journal of Cryptology,2002,15(3):177–206.
[16]CACHIN C.Efficient private bidding and auctions with an oblivious third party[C].In:Proceedings of the 6th ACM Conference on Computer and Communications Security.ACM,1999:120–127.
[17]ATALLAH M J,DU W.Secure multi-party computational geometry[C].In:Workshop on Algorithms and Data Structures.Springer Berlin Heidelberg,2001:165–179.
[18]DU W,ATALLAH M J.Secure multi-party computation problems and their applications:a review and open problems[C].In:Proceedings of the 2001 Workshop on New Security Paradigms.ACM,2001:13–22.
[19]LI S D,WU C Y,WANG D S,et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401–413.
[20]LI S D,DAI Y G,WANG D S,et al.A secure multi-party computation solution to intersection problems of sets and rectangles[J].Progress in Natural Science,2006,16(5):538–545.
[21]LUO Y,SHI L,ZHANG C,et al.Privacy-preserving protocols for string matching[C].In:2010 4th International Conference on Network and System Security(NSS).IEEE,2010:481–485.
[22]MOHASSEL P,NIKSEFAT S,SADEGHIAN S,et al.An efficient protocol for oblivious DFA evaluation andapplications[C].In:Cryptographers’Track at the RSA Conference.Springer Berlin Heidelberg,2012:398–415.
[23]YASUDA M,SHIMOYAMA T,KOGURE J,et al.Secure pattern matching using somewhat homomorphic encryption[C].In:Proceedings of the 2013 ACM Workshop on Cloud Computing Security Workshop.ACM,2013:65–76.
[24]HAZAY C,TOFT T.Computationally secure pattern matching in the presence of malicious adversaries[C].In:International Conference on the Theory and Application of Cryptology and Information Security.Springer Berlin Heidelberg,2010:195–212.
[25]GOLDWASSER S,MICALI S.Probabilistic encryption[J].Journal of Computer and System Sciences,1984,270–299.
[26]LINDELL Y.How to simulate it-A tutorial on the simulation proof technique[R].IACR Cryptology e Print Archive,2016:46,2016.
[27]GOLDREICH O.Foundations of Cryptography:Volume 2,Basic Applications[M].Cambridge University Press,2004.
[28]LI S D,SI T G,DAI Y Q.Secure multi-party computation of set-inclusion and graph-inclusion[J].Journal of Computer Research and Development,2005,42(10):1647–1653.李顺东,司天歌,戴一奇.集合包含与几何包含的多方保密计算[J].计算机研究与发展,2005,42(10):1647–1653.
[2]GOLDREICH O.Secure multi-party computation(working draft)[OL].http://www.wisdom.weizmann.ac.ilhomeoded public-html foc.html,2002
[3]FREEDMAN M J,NISSIM K,PINKAS B.Efficient private matching and set intersection[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:1–19.
[4]LYNN B,PRABHAKARAN M,SAHAI A.Positive results and techniques for obfuscation[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:20–39.
[5]AGGARWAL G,MISHRA N,PINKAS B.Secure computation of the k th-ranked element[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:40–55.
[6]FITZI M,HOLENSTEIN T,WULLSCHLEGER J.Multi-party computation with hybrid security[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:419–438.
[7]ISHAI Y,KUSHILEVITZ E.On the hardness of information-theoretic multiparty computation[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:439–455.
[8]GOLLE P,JUELS A.Dining cryptographers revisited[C].In:Advances in Cryptology—Eurocrypt 2004.Springer Berlin Heidelberg,2004:456–473.
[9]YAO A.Protocols for secure computations[C].In:23rd Annual Symposium on Foundations of Computer Science,1982.IEEE,1982:160–164.
[10]Goldreich O,Micali S,Wigderson A.How to play any mental game[C].In:Proceedings of the nineteenth annual ACM symposium on Theory of computing.ACM,1987:218–229.
[11]LINin H Y,TZENG W G.An efficient solution to the millionaires’problem based on homomorphic encryption[C].In:International Conference on Applied Cryptography and Network Security.Springer Berlin Heidelberg,2005:456–466.
[12]LI S D,WANG D S.Efficient secure multiparty computation based on homomorphic encryption[J].Dianzi Xuebao(Acta Electronica Sinica),2013,41(4):798–803.
[13]SHEIKH R,MISHRA D K,KUMAR B.Secure multiparty computation:from millionaires problem to anonymizer[J].Information Security Journal:A Global Perspective,2011,20(1):25–33.
[14]GRIGORIEV D,SHPILRAIN V.Yao’s Millionaires’problem and decoy-based public key encryption by classical physics[J].International Journal of Foundations of Computer Science,2014,25(04):409–417.
[15]LINDELL Y,PINKAS B.Privacy preserving data mining[J].Journal of Cryptology,2002,15(3):177–206.
[16]CACHIN C.Efficient private bidding and auctions with an oblivious third party[C].In:Proceedings of the 6th ACM Conference on Computer and Communications Security.ACM,1999:120–127.
[17]ATALLAH M J,DU W.Secure multi-party computational geometry[C].In:Workshop on Algorithms and Data Structures.Springer Berlin Heidelberg,2001:165–179.
[18]DU W,ATALLAH M J.Secure multi-party computation problems and their applications:a review and open problems[C].In:Proceedings of the 2001 Workshop on New Security Paradigms.ACM,2001:13–22.
[19]LI S D,WU C Y,WANG D S,et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401–413.
[20]LI S D,DAI Y G,WANG D S,et al.A secure multi-party computation solution to intersection problems of sets and rectangles[J].Progress in Natural Science,2006,16(5):538–545.
[21]LUO Y,SHI L,ZHANG C,et al.Privacy-preserving protocols for string matching[C].In:2010 4th International Conference on Network and System Security(NSS).IEEE,2010:481–485.
[22]MOHASSEL P,NIKSEFAT S,SADEGHIAN S,et al.An efficient protocol for oblivious DFA evaluation andapplications[C].In:Cryptographers’Track at the RSA Conference.Springer Berlin Heidelberg,2012:398–415.
[23]YASUDA M,SHIMOYAMA T,KOGURE J,et al.Secure pattern matching using somewhat homomorphic encryption[C].In:Proceedings of the 2013 ACM Workshop on Cloud Computing Security Workshop.ACM,2013:65–76.
[24]HAZAY C,TOFT T.Computationally secure pattern matching in the presence of malicious adversaries[C].In:International Conference on the Theory and Application of Cryptology and Information Security.Springer Berlin Heidelberg,2010:195–212.
[25]GOLDWASSER S,MICALI S.Probabilistic encryption[J].Journal of Computer and System Sciences,1984,270–299.
[26]LINDELL Y.How to simulate it-A tutorial on the simulation proof technique[R].IACR Cryptology e Print Archive,2016:46,2016.
[27]GOLDREICH O.Foundations of Cryptography:Volume 2,Basic Applications[M].Cambridge University Press,2004.
[28]LI S D,SI T G,DAI Y Q.Secure multi-party computation of set-inclusion and graph-inclusion[J].Journal of Computer Research and Development,2005,42(10):1647–1653.李顺东,司天歌,戴一奇.集合包含与几何包含的多方保密计算[J].计算机研究与发展,2005,42(10):1647–1653.