Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (9): 355-360.doi: 10.11896/jsjkx.220100241

• Information Security • Previous Articles    

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).

PDF (PC)

685

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

CLC Number: 

  • 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] SUN Guo-zi, LYU Jian-wei, LI Hua-kang. MeTCa:Multi-entity Trusted Confirmation Algorithm Based on Edit Distance [J]. Computer Science, 2020, 47(12): 327-331.
[2] XIANG Ying-zhuo, TAN Ju-xian, HAN Jie-si, SHI Hao. Survey of Graph Matching Algorithms [J]. Computer Science, 2018, 45(6): 27-31.
[3] XU Zhou-bo, ZHANG Kun, NING Li-hua and GU Tian-long. Summary of Graph Edit Distance [J]. Computer Science, 2018, 45(4): 11-18.
[4] TAN En-min and FAN Yu-xiang. Optimization Method of Low Power Test Vectors Based on Hamming Sorting for X Bits Padding [J]. Computer Science, 2018, 45(2): 249-253.
[5] ZHANG Run-liang and NIU Zhi-xian. Sequential Verification Algorithm to Compute Edit Distance Based on Edit Operation Sequence [J]. Computer Science, 2016, 43(Z6): 51-54.
[6] YANG Yan-lin, YE Feng, LV Xin, YU Lin and LIU Xuan. DTW Clustering-based Similarity Mining Method for Hydrological Time Series [J]. Computer Science, 2016, 43(2): 245-249.
[7] LI Jing-yu, ZHANG Yang-sen and CHEN Ruo-yu. User Query Intention Oriented Hierarchical Sentence Similarity Computation [J]. Computer Science, 2015, 42(1): 227-231.
[8] XIANG Lin-hong,ZHANG Ju,SUN Qi-long and ZHAO Xue-ling. Medical Data Similarity Algorithm Analysis Based on Relative-IDF [J]. Computer Science, 2014, 41(Z6): 417-420.
[9] WU Sheng-feng, WU Yue and XU Shi-yi. Study on Quasi-perfect Maximum Distance Pseudo Random Testing [J]. Computer Science, 2014, 41(5): 50-54.
[10] . Simulation Platform for Differential Power Analysis Attack on DES [J]. Computer Science, 2012, 39(2): 59-60.
[11] LIU Hui-ying,WANG Tao,ZHAO Xin-jie,ZHOU Lin. Research on Correlation Power Analysis Attack against PRESENT [J]. Computer Science, 2011, 38(11): 40-42.
[12] LI Lang,LI Ren-fa,LI Jing,WU Ke-shou. Differential Power Analysis Attacks on SMS4 [J]. Computer Science, 2010, 37(7): 39-41.
[13] ZHANG Shi-fang,LIU San-yang,ZHAI Ren-he. Method of Grey Relational Analysis for MADM Problem with Intuitionistic Trapezoidal Fuzzy Numbers [J]. Computer Science, 2010, 37(11): 214-216.
[14] XU Guo-liang,TAN Qing-ping. Quality Assessment for Halftone Image Based on Non-ideal Printer Model [J]. Computer Science, 2010, 37(10): 228-232.
[15] ZHU Jing-fen XU Shi yi （School of Computer Engineering and Science, Shanghai University, Shanghai 200072 ,China）. [J]. Computer Science, 2009, 36(5): 133-137.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.