基于局部敏感哈希的安全相似性查询方案

Secure Similarity Search Based on Locality Sensitive Hashing

随着云计算技术的不断发展,可搜索加密方案备受关注.传统的可搜索加密方案仅支持精确查询.然而,在实际应用中,相似性查询具有更好的应用前景.具体而言,当输入的查询项拼写错误时,相似性搜索方案依然能返回正确的查询结果.与此同时,现有的相似性可搜索加密方案会导致查询精确度降低.为了解决密文上相似性查询精确度不高的问题,本文提出了一种基于局部敏感哈希的安全相似性查询方案.首先,利用局部敏感哈希将原始数据量化为复合哈希关键字,使用量化结果和对称加密技术构建安全索引.然后,引入基于复合哈希关键字的度量机制,设计一种合理、高效的候选集定位策略;同时,优化候选集量化的方式,以便从候选集中选择出与查询项最相似的结果.查询时,使用以上定位方法与候选集选择方法可以同时保证查询效率和结果的精确度.本文从理论上证明了方案满足必要的安全要求.最后,将方案应用到真实数据集上,实验结果证明了方案的有效性,即查询的精确度明显提升.

With the continuous development of cloud computing technology, the searchable encryption scheme attracts much attention. The traditional searchable encryption schemes only handle exact query matching but not similarity matching. However, the similarity search has a better application prospect in practice. In particular, the similarity search scheme still returns the correct result when the input search term is misspelled. In the meantime, existing similarity searchable encryption schemes result in reduced search precision. In order to solve the problem that the precision of similarity search over encrypted data is not high, this study proposes a secure similarity search scheme based on locality sensitive hashing. Firstly, the locality sensitive hashing is used to quantize the original data into compound hash keywords, and the security index is constructed by using the quantitative results and symmetric encryption. Then, we introduce a metric based on compound hash keys to design a reasonable and efficient strategy to locate candidates. At the same time, we optimize the way of quantifying the candidate set so as to select the most similar result from the candidate set. Using the above method of locating and selecting a candidate set can ensure both the search efficiency and the precision of the result. This paper theoretically proves that the scheme meets the necessary security requirements. Finally, the scheme is applied to real datasets, the experimental results demonstrate the effectiveness of the scheme, namely the search precision has improved obviously.