Secure KNN Queries over Encrypted Data: Dimensionality Is Not Always a Curse
Secure KNN Queries over Encrypted Data: Dimensionality Is Not Always a Curse
复制标题
DOI：
10.1109/icde.2017.91
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Xinyu Lei;A. Liu;Rui Li-
中科院分区：
文献类型：
--
作者：
Xinyu Lei;A. Liu;Rui Li-
移动的设备中快速增长的位置相关应用正在制造过多的地理空间数据。将地理空间数据存储外包给强大的云是一种经济的方法。然而，保护数据用户的位置隐私免受不可信云的侵害，同时在加密数据上提供高效的位置感知查询处理是相互冲突的。作为一个步骤，以调和这种冲突，我们研究了安全的k最近邻（SkNN）查询处理加密的地理空间数据在云计算。我们设计了二维SkNN（2DSkNN），一个方案实现了强可证明安全性和高效率。我们的方法采用局部敏感哈希（LSH）在一个维度增加的方式。这是LSH的一个反直觉的杠杆作用，因为LSH的传统用法是减少数据维度并解决所谓的“维度灾难”问题。我们表明，通过LSH增加数据维数确实有助于解决2DSkNN问题。通过基于LSH的邻域编码和两层无前缀编码，我们将邻近度测试转化为带停止条件的连续关键字查询，这可以很好地解决任何现有的对称可搜索加密（SSE）方案。我们证明了2DSkNN在随机预言模型中实现了选择关键字攻击下的自适应不可否认性（IND 2-CKA）。一个原型实现和真实世界和合成数据集上的实验证实了2DSkNN的高实用性。
The fast increasing location-dependent applications in mobile devices are manufacturing a plethora of geospatial data. Outsourcing geospatial data storage to a powerful cloud is an economical approach. However, safeguarding data users' location privacy against the untrusted cloud while providing efficient location-aware query processing over encrypted data are in conflict with each other. As a step to reconcile such conflict, we study secure k nearest neighbor (SkNN) queries processing over encrypted geospatial data in cloud computing. We design 2D SkNN (2DSkNN), a scheme achieves both strong provable security and high-efficiency. Our approach employs locality sensitive hashing (LSH) in a dimensional-increased manner. This is a counter-intuitive leverage of LSH since the traditional usage of LSH is to reduce the data dimensionality and solve the so-called "curse of dimensionality" problem. We show that increasing the data dimensionality via LSH is indeed helpful to tackle 2DSkNN problem. By LSH-based neighbor region encoding and two-tier prefix-free encoding, we turn the proximity test to be sequential keywords query with a stop condition, which can be well addressed by any existing symmetric searchable encryption (SSE) scheme. We show that 2DSkNN achieves adaptive indistinguishability under chosen-keyword attack (IND2-CKA) secure in the random oracle model. A prototype implementation and experiments on both real-world and synthetic datasets confirm the high practicality of 2DSkNN.