Efficient Oblivious Query Processing for Range and kNN Queries
Efficient Oblivious Query Processing for Range and kNN Queries
复制标题
DOI：
10.1109/tkde.2021.3060757
复制
发表时间：
2021-02
影响因子：
8.9
通讯作者：
Zhao Chang;Dong Xie;Feifei Li;J. M. Phillips;R. Balasubramonian
中科院分区：
文献类型：
--
作者：
Zhao Chang;Dong Xie;Feifei Li;J. M. Phillips;R. Balasubramonian
越来越多的个人和公司采用云服务提供商作为主要数据和 IT 基础设施平台。数据的远程访问不可避免地带来信任问题。为了确保云上敏感信息的安全和私密，数据加密是必要的。然而，攻击者仍然可以通过观察数据访问模式来了解有关加密数据的有价值的信息。为了解决这个问题，Oblivious RAM（ORAM）被提出来完全隐藏访问模式。然而，大多数 ORAM 结构都很昂贵，并且不适合部署在数据库中以支持大数据的查询处理。此外，ORAM 同步处理查询，因此不能为并发查询处理提供高吞吐量。在本文中，我们设计了一个实用的不经意查询处理框架，以实现云数据库上的高效查询处理。特别是，我们专注于以高吞吐量异步并发处理多个范围和 $k$kNN 查询。关键思想是将索引集成到 ORAM 中，ORAM 利用了一套优化技术（例如，不经意的批处理和缓存）。我们的不经意查询处理框架的有效性和效率是通过对大型数据集的广泛评估来证明的。与其他基线相比，我们的构建显示出一个数量级的加速。
Increasingly, individuals and companies adopt a cloud service provider as a primary data and IT infrastructure platform. The remote access of the data inevitably brings the issue of trust. Data encryption is necessary to keep sensitive information secure and private on the cloud. Yet adversaries can still learn valuable information regarding encrypted data by observing data access patterns. To solve such problem, Oblivious RAMs (ORAMs) are proposed to completely hide access patterns. However, most ORAM constructions are expensive and not suitable to deploy in a database for supporting query processing over large data. Furthermore, an ORAM processes queries synchronously, hence, does not provide high throughput for concurrent query processing. In this article, we design a practical oblivious query processing framework to enable efficient query processing over a cloud database. In particular, we focus on processing multiple range and $k$kNN queries asynchronously and concurrently with high throughput. The key idea is to integrate indices into ORAM which leverages a suite of optimization techniques (e.g., oblivious batch processing and caching). The effectiveness and efficiency of our oblivious query processing framework is demonstrated through extensive evaluations over large datasets. Our construction shows an order of magnitude speedup in comparison with other baselines.