计算机科学 ›› 2022, Vol. 49 ›› Issue (9): 355-360.doi: 10.11896/jsjkx.220100241
• 信息安全 • 上一篇
窦家维
DOU Jia-wei
摘要： 随着信息技术的快速发展,在保护数据隐私的条件下进行多方合作计算越来越普及,安全多方计算已成为解决这类问题的核心技术。在科学研究及实际应用中,人们常根据两个字符串之间的汉明/编辑距离度量其相似程度,研究汉明/编辑距离的保密计算具有重要意义。文中主要针对汉明距离与编辑距离的两方保密计算问题进行研究。首先将汉明距离的计算问题转化为向量内积计算问题,应用加密选择技巧以及Okamoto-Uchiyama(OU)密码系统设计保密计算协议。然后通过对参与者字符串中各字符进行统一编号的方法,将编辑距离的计算问题转化为判定隐私数据的差是否为0的问题,应用OU密码系统设计编辑距离保密计算协议。应用模拟范例严格证明了协议的安全性,分析了协议的计算复杂性,测试了协议的实际执行效率,并与目前已有相关结果进行了分析比较。理论分析和实验结果都表明了协议的高效性。
中图分类号:
| [1]YAO A C.Protocols for secure computations [C]//The 23rd Annual Symposium on Foundations of Computer Science.New York:ACM Press,1982:160-164. [2]GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game[C]//The 19th Annual ACM Symposium on Theory of computing.New York:ACM Press,1987:218-229. [3]BEN-OR M,GOLDWASSER S,WIGDERSON A.Completeness theorems for non-cryptographic fault-tolerant distributed computation(extended abstract) [C]//Proceedings of the STOC.New York:ACM Press,1988:1-10. [4]YANG X Y,LI S D,KANG J.Private substitution and its applications in private scientific computation [J].Chinese Journal of Computers,2018,41(5):1132-1142. [5]FAGIN R,NAOR M,WINKLER P.Comparing informationwithout leaking it [J].Communications of the ACM,1996,39(5):77-85. [6]LIU C,ZHU L H,HE X J,et al.Enabling privacy-preserving shortest distance queries on encrypted graph data [J].IEEE Transaction on Dependable Secure Computing,2021,18(1):192-204. [7]WU X T,WU T T,KHAN M,et al.Game theory based correlated privacy preserving analysis in big data [J].IEEE Transactions on Big Data,2021,7(4):643-656. [8]LEE A S,JUN S P.Privacy-preserving data mining for open government data from heterogeneous sources [J].Government Information Quarterly,2021,38(1):101544. [9]LI Y,ZHOU Y P,JOLFAEI A,et al.Privacy-preserving federated learning framework based on chained secure multiparty computing [J].IEEE Internet Things Journal,2021,8(8):6178-6186. [10]FREEDMAN M J,HAZAY C,NISSIM K,et al.Efficient set intersection with simulation-based security [J].Journal of Cryptology,2016,29(1):115-155. [11]ZHU X J,AYDAY E,VITENBERG R.A privacy-preserving framework for outsourcing location-based services to the cloud[J].IEEE Transactions on Dependable Secure Computing,2021,18(1):384-399. [12]DING X F,WANG Z,ZHOU P,et al.Efficient and privacy-preserving multi-party skyline queries over encrypted data [J].IEEE Transactions on Information Forensics Security,2021,16:4589-4604. [13]FEIGENBAUM J,ISHAI Y,MALKIN T,et al.Secure multiparty computation of approximations [J].ACM Transaction on Algorithms,2006,2(3):435-472. [14]BRINGER J,CHABANNE H,PATEY A.Shade:Secure hamming distance computation from oblivious transfer[C]//Proceedings of the International Conference on Financial Cryptography and Data Security.Berlin:Springer,2013:164-176. [15]KULKARNI R,NAMBOODIRI A.Secure hamming distancebased biometric authentication[C]//Proceedings of The International Conference on Biometrics.Piscataway:IEEE Press,2013:1-6. [16]YASUDA M.Secure Hamming distance computation for bio-metrics using ideal-lattice and ring-LWE homomorphic encryption[J].Information Security Journal:A Global Perspective.2017,26(2):85-103. [17]MA M Y,XU Y,LIU Z.Privacy preserving Hamming distance computing problem of DNA sequences[J].Journal of Computer Applications,2019,39(9):2636-2640. [18]JARROUS A,PINKAS B.Secure computation of functionalities based on hamming distance and its application to computing document similarity [J].International Journal of Applied Cryptography,2013,3(1):21-46. [19]OKAMOTO T,UCHIYAMA S.A new public-key cryptosystem as secure as factoring[C]//Proceedings of the EUROCRYPT.Berlin:Springer,1998:308-318. [20]BOUDOT F,SCHOENMAKERS B,TRAORE J.A fair andefficient solution to the socialist millionaires' problem [J].Discrete Application Mathematics,2001,111(1/2):23-36. |
| [1] | 汤凌韬, 王迪, 张鲁飞, 刘盛云. 基于安全多方计算和差分隐私的联邦学习方案 Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy 计算机科学, 2022, 49(9): 297-305. https://doi.org/10.11896/jsjkx.210800108 |
| [2] | 王健. 基于隐私保护的反向传播神经网络学习算法 Back-propagation Neural Network Learning Algorithm Based on Privacy Preserving 计算机科学, 2022, 49(6A): 575-580. https://doi.org/10.11896/jsjkx.211100155 |
| [3] | 卫宏儒, 李思月, 郭涌浩. 基于智能合约的秘密重建协议 Secret Reconstruction Protocol Based on Smart Contract 计算机科学, 2022, 49(6A): 469-473. https://doi.org/10.11896/jsjkx.210700033 |
| [4] | 王勤, 魏立斐, 刘纪海, 张蕾. 基于云服务器辅助的多方隐私交集计算协议 Private Set Intersection Protocols Among Multi-party with Cloud Server Aided 计算机科学, 2021, 48(10): 301-307. https://doi.org/10.11896/jsjkx.210300308 |
| [5] | 孙国梓, 吕建伟, 李华康. 基于编辑距离的多实体可信确认算法 MeTCa:Multi-entity Trusted Confirmation Algorithm Based on Edit Distance 计算机科学, 2020, 47(12): 327-331. https://doi.org/10.11896/jsjkx.191100176 |
| [6] | 李艳斌, 刘瑜, 李木舟, 吴韧韬, 王鹏达. MASCOT协议的参与方自适应变体 Participant-adaptive Variant of MASCOT 计算机科学, 2020, 47(11A): 380-387. https://doi.org/10.11896/jsjkx.200400091 |
| [7] | 王童, 马文平, 罗维. 基于区块链的信息共享及安全多方计算模型 Information Sharing and Secure Multi-party Computing Model Based on Blockchain 计算机科学, 2019, 46(9): 162-168. https://doi.org/10.11896/j.issn.1002-137X.2019.09.023 |
| [8] | 项英倬, 谭菊仙, 韩杰思, 石浩. 图匹配技术研究 Survey of Graph Matching Algorithms 计算机科学, 2018, 45(6): 27-31. https://doi.org/10.11896/j.issn.1002-137X.2018.06.004 |
| [9] | 徐周波,张鵾,宁黎华,古天龙. 图编辑距离概述 Summary of Graph Edit Distance 计算机科学, 2018, 45(4): 11-18. https://doi.org/10.11896/j.issn.1002-137X.2018.04.002 |
| [10] | 王伟,陈志高,孟宪凯,李伟. 基于熵的音频指纹检索技术研究与实现 Research and Implementation of Identifying Music through Performances Using Entropy Based Audio-fingerprint 计算机科学, 2017, 44(Z6): 551-556. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.123 |
| [11] | 张润梁,牛之贤. 基于基本操作序列的编辑距离顺序验证 Sequential Verification Algorithm to Compute Edit Distance Based on Edit Operation Sequence 计算机科学, 2016, 43(Z6): 51-54. https://doi.org/10.11896/j.issn.1002-137X.2016.6A.011 |
| [12] | 徐周波,俞强生,古天龙,宁黎华. 基于符号EVBDD的安全多方计算 Secure Multi-party Computation Based on Symbolic Edge-valued Binary Decision Diagram 计算机科学, 2016, 43(4): 127-133. https://doi.org/10.11896/j.issn.1002-137X.2016.04.026 |
| [13] | 杨艳林,叶枫,吕鑫,余霖,刘璇. 一种基于DTW聚类的水文时间序列相似性挖掘方法 DTW Clustering-based Similarity Mining Method for Hydrological Time Series 计算机科学, 2016, 43(2): 245-249. https://doi.org/10.11896/j.issn.1002-137X.2016.02.051 |
| [14] | 唐璇,仲红,石润华,崔杰. 基于编码和同态加密的高效SMP方案 Efficient Solution to SMP Based on Coding and Homomorphic Encryption 计算机科学, 2016, 43(1): 181-185. https://doi.org/10.11896/j.issn.1002-137X.2016.01.041 |
| [15] | 李景玉,张仰森,陈若愚. 面向用户查询意图的句子相似度分层计算 User Query Intention Oriented Hierarchical Sentence Similarity Computation 计算机科学, 2015, 42(1): 227-231. https://doi.org/10.11896/j.issn.1002-137X.2015.01.050 |
|
||
首页