Forward Secure Similarity Search Over Encrypted Data for Hamming Distance
Beining Wang, Kun He, Yingying Huang, Jing Chen, Chenbin Zhao, Ruiying Du · IEEE Transactions on Dependable and Secure Computing · 2024
Similarity search on encrypted data can identify similar data and handle misspelled keywords in a privacy-preserving manner and thus has received a lot of attention. However, existing schemes suffer from imprecise or predefined distance thresholds, which means that they do not always return the expected search results. Moreover, these schemes either do not consider document addition or lack forward security in this dynamic setting. In this article, we present a Similar Keyword Matching (SKM) framework that accurately calculates the Hamming distance between keywords through a new keyword representation called uni-pos-gram. Based on our framework, we propose a basic scheme for similarity search over encrypted data called SimSE that offers adjustable Hamming distance thresholds and an enhanced scheme called SimSE-F that provides forward security. Security analysis demonstrates that our schemes effectively safeguard the privacy of documents, indexes, and searches. Empirical experiments using real-world datasets demonstrate the efficiency and practical applicability of our schemes.