Oblivious Query Processing
Oblivious Query Processing
复制标题
不经意的查询处理
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
R. Kaushik
中科院分区：
文献类型：
--
作者：
A. Arasu;R. Kaushik
出于对云安全的担忧，人们对能够存储加密数据并支持对其进行查询的数据库系统越来越感兴趣。此类系统的一种常见架构是使用诸如加密协处理器之类的可信组件进行查询处理，该组件用于安全地解密数据并以明文形式进行计算。可信组件的内存有限，因此大多数（输入和中间）数据在不可信存储中保持加密状态，并根据“需求”移动到可信组件中。
在这种情况下，即使采用了强加密，来自不可信存储的数据访问模式也有可能泄露敏感信息；实际上，所有使用可信组件对加密数据进行查询处理的现有系统都存在这一漏洞。在本文中，我们对安全查询处理进行了首次正式研究，在这种情况下，一个完全了解查询（文本）并观察查询执行的对手除了数据库上查询的结果大小之外，对底层数据库一无所知。我们引入了一个更简单的概念，即无感知查询处理，并正式证明一个查询若允许安全查询处理当且仅当它允许无感知查询处理。我们针对涉及选择、连接、分组和聚合的一类丰富的数据库查询提出了无感知查询处理算法。对于我们的算法未处理的查询，我们提供了一些初步证据，表明通过从两个通常被认为是困难的、经过充分研究的简单问题进行归约，设计无感知（因而是安全的）算法是困难的。我们对无感知查询处理的研究还揭示了与数据库连接理论的有趣联系。
Motivated by cloud security concerns, there is an increasing interest in database systems that can store and support queries over encrypted data. A common architecture for such systems is to use a trusted component such as a cryptographic co-processor for query processing that is used to securely decrypt data and perform computations in plaintext. The trusted component has limited memory, so most of the (input and intermediate) data is kept encrypted in an untrusted storage and moved to the trusted component on ``demand.'
In this setting, even with strong encryption, the data access pattern from untrusted storage has the potential to reveal sensitive information; indeed, all existing systems that use a trusted component for query processing over encrypted data have this vulnerability. In this paper, we undertake the first formal study of secure query processing, where an adversary having full knowledge of the query (text) and observing the query execution learns nothing about the underlying database other than the result size of the query on the database. We introduce a simpler notion, oblivious query processing, and show formally that a query admits secure query processing iff it admits oblivious query processing. We present oblivious query processing algorithms for a rich class of database queries involving selections, joins, grouping and aggregation. For queries not handled by our algorithms, we provide some initial evidence that designing oblivious (and therefore secure) algorithms would be hard via reductions from two simple, well-studied problems that are generally believed to be hard. Our study of oblivious query processing also reveals interesting connections to database join theory.