计算机科学 ›› 2022, Vol. 49 ›› Issue (9): 355-360.doi: 10.11896/jsjkx.220100241

• 信息安全 • 上一篇    

保护隐私的汉明距离与编辑距离计算及应用

窦家维   

  1. 陕西师范大学数学与统计学院 西安 710119
  • 收稿日期:2022-01-26 修回日期:2022-06-08 出版日期:2022-09-15 发布日期:2022-09-09
  • 通讯作者: 窦家维(jiawei@snnu.edu.cn)
  • 基金资助:
    国家自然科学基金(61272435);陕西师范大学教学改革研究项目(22JG37)

Privacy-preserving Hamming and Edit Distance Computation and Applications

DOU Jia-wei   

  1. School of Mathematics and Statistics,Shaanxi Normal University,Xi'an 710119,China
  • Received:2022-01-26 Revised:2022-06-08 Online:2022-09-15 Published:2022-09-09
  • About author:DOU Jia-wei,born in 1963,Ph.D,associate professor.Her main research interests include applied mathematics,cryptography and information security.
  • Supported by:
    National Natural Science Foundation of China(61272435) and Teaching Reform Research Project of Shaanxi Normal University(22JG37).

摘要: 随着信息技术的快速发展,在保护数据隐私的条件下进行多方合作计算越来越普及,安全多方计算已成为解决这类问题的核心技术。在科学研究及实际应用中,人们常根据两个字符串之间的汉明/编辑距离度量其相似程度,研究汉明/编辑距离的保密计算具有重要意义。文中主要针对汉明距离与编辑距离的两方保密计算问题进行研究。首先将汉明距离的计算问题转化为向量内积计算问题,应用加密选择技巧以及Okamoto-Uchiyama(OU)密码系统设计保密计算协议。然后通过对参与者字符串中各字符进行统一编号的方法,将编辑距离的计算问题转化为判定隐私数据的差是否为0的问题,应用OU密码系统设计编辑距离保密计算协议。应用模拟范例严格证明了协议的安全性,分析了协议的计算复杂性,测试了协议的实际执行效率,并与目前已有相关结果进行了分析比较。理论分析和实验结果都表明了协议的高效性。

关键词: 安全多方计算, 汉明距离, 编辑距离, 半诚实模型, 模拟范例

Abstract: With the rapid development of information technology,privacy-preserving multiparty cooperative computation is becoming more and more popular.Secure multiparty computation is a key technology to address such problems.In scientific research and practical applications,people measure the similarity of two strings with Hamming(edit) distance.It is of great significance to study privacy-preserving Hamming(edit) distance computation.This paper studies privacy-preserving Hamming(edit) distance computation.First,we transform Hamming distance computation to inner product computation of vectors,and then use Okamoto-Uchiyama(OU) cryptosystem and encryption-and-choose technique to design protocol for Hamming distance.Second,we give each alphabet of a string a number,transform edit distance to determine whether the difference of the number of two alphabets is 0,and use OU cryptosystem to design a privacy-preserving edit distance computation protocol.The security of the protocol is strictly proved,the computational complexity of the protocol is analyzed,the actual implementation efficiency of the protocol is tested and compared with the existing results.Theoretical analysis and experimental results show that our protocols are efficient.

Key words: SMC, Hamming distance, Edit distance, Semi-honest model, Simulation paradigm

中图分类号: 

  • TP309.7
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!