Data Recovery on Encrypted Databases with k-Nearest Neighbor Query Leakage
Data Recovery on Encrypted Databases with k-Nearest Neighbor Query Leakage
复制标题
DOI：
10.1109/sp.2019.00015
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Evgenios M. Kornaropoulos;Charalampos Papamanthou;R. Tamassia
中科院分区：
文献类型：
--
作者：
Evgenios M. Kornaropoulos;Charalampos Papamanthou;R. Tamassia
Kellaris等人（CCS'16）和Lacharite等人（SP'18）最近的工作演示了支持范围查询等丰富查询的加密数据库的数据恢复攻击。在本文中，我们开发了第一个数据恢复攻击加密数据库支持一维k-最近邻（k-NN）查询，这是广泛应用于空间数据管理。我们的攻击利用了一个通用的k-NN查询泄漏配置文件：攻击者观察匹配记录的标识符。我们考虑无序的响应，其中泄漏是一个集合，和有序的响应，其中泄漏是按距离查询点排序的k元组。作为第一步，我们对精确重建进行了理论可行性研究，即，恢复加密数据库的精确明文值。对于有序响应，我们表明，如果攻击者有额外的访问一些辅助信息，通常是不可用的，在实践中，精确的重建是可行的。对于无序响应，我们证明了精确的重建是不可能的，由于无限数量的有效重建。下一步，我们提出实用且更真实的近似重建攻击，以恢复明文值的近似值。对于有序的响应，我们表明，在观察到足够的查询响应，攻击者可以近似客户端的加密数据库具有相当的准确性。对于无序响应，我们的特征在于一组有效的重建作为一个凸多面体在k维空间，并提出了一个严格的攻击，重建的明文数据库有界近似误差。由于多维空间数据可以通过Hilbert曲线映射到一维来有效地处理，我们展示了我们对隐私敏感的地理位置数据的近似重建攻击。我们在真实数据集上的实验表明，我们的攻击重建了明文值，相对误差在2.9%到0.003%之间。
Recent works by Kellaris et al. (CCS’16) and Lacharite et al. (SP’18) demonstrated attacks of data recovery for encrypted databases that support rich queries such as range queries. In this paper, we develop the first data recovery attacks on encrypted databases supporting one-dimensional k-nearest neighbor (k-NN) queries, which are widely used in spatial data management. Our attacks exploit a generic k-NN query leakage profile: the attacker observes the identifiers of matched records. We consider both unordered responses, where the leakage is a set, and ordered responses, where the leakage is a k-tuple ordered by distance from the query point. As a first step, we perform a theoretical feasibility study on exact reconstruction, i.e., recovery of the exact plaintext values of the encrypted database. For ordered responses, we show that exact reconstruction is feasible if the attacker has additional access to some auxiliary information that is normally not available in practice. For unordered responses, we prove that exact reconstruction is impossible due to the infinite number of valid reconstructions. As a next step, we propose practical and more realistic approximate reconstruction attacks so as to recover an approximation of the plaintext values. For ordered responses, we show that after observing enough query responses, the attacker can approximate the client’s encrypted database with considerable accuracy. For unordered responses we characterize the set of valid reconstructions as a convex polytope in a k-dimensional space and present a rigorous attack that reconstructs the plaintext database with bounded approximation error. As multidimensional spatial data can be efficiently processed by mapping it to one dimension via Hilbert curves, we demonstrate our approximate reconstruction attacks on privacy-sensitive geolocation data. Our experiments on real-world datasets show that our attacks reconstruct the plaintext values with relative error ranging from 2.9% to 0.003%.