On Private Information Retrieval Supporting Range Queries
On Private Information Retrieval Supporting Range Queries
复制标题
支持范围查询的私有信息检索
DOI：
10.1007/978-3-030-59013-0_33
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Matsuura Kanta
中科院分区：
文献类型：
--
作者：
Hayata Junichiro;Schuldt Jacob C. N.;Hanaoka Goichiro;Matsuura Kanta
私有信息检索（PIR）允许客户机从数据库检索数据，而无需数据库服务器了解正在检索的数据。尽管文献中提出了许多PIR方案，但几乎所有这些方案都侧重于单个数据库元素的检索，而没有考虑更灵活的检索查询，如基本范围查询。此外，虽然已经提出了旨在提供灵活和保护隐私的查询的面向实际的数据库方案，但据我们所知，还没有考虑对这些范围查询进行正式处理。在本文中，我们首先强调，在许多使用场景中，将标准PIR安全概念简单地扩展到范围查询是不够的，并提出了一个更强大的安全概念，旨在解决这个问题。然后，我们给出了一种满足我们更强的安全概念的PIR方案的简单通用结构，并提出了一种基于函数秘密共享的更有效的直接结构——前者在数据库大小中具有对数的轮复杂度，后者的轮复杂度是常数。之后，我们报告了我们直接施工的实际性能。最后，我们将结果扩展到多维数据库的情况下，并展示了支持多维范围查询的PIR方案的构建。我们的方案的通信复杂度是在最坏的情况下，即数据库的大小和查询检索到的元素的数量。
Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data are being retrieved. Although many PIR schemes have been proposed in the literature, almost all of these focus on retrieval of a single database element, and do not consider more flexible retrieval queries such as basic range queries. Furthermore, while practically-oriented database schemes aiming at providing flexible and privacy-preserving queries have been proposed, to the best of our knowledge, no formal treatment of range queries has been considered for these. In this paper, we firstly highlight that a simple extension of the standard PIR security notion to range queries is insufficient in many usage scenarios, and propose a stronger security notion aimed at addressing this. We then show a simple generic construction of a PIR scheme meeting our stronger security notion, and propose a more efficient direct construction based on function secret sharing—while the former has a round complexity logarithmic in the size of the database, the round complexity of the latter is constant. After that, we report on the practical performance of our direct construction. Finally, we extend the results to the case of multi-dimensional databases and show the construction of PIR scheme supporting multi-dimensional range queries. The communication round complexity of our scheme isin worst case, wherenis the size of database andkis the number of elements retrieved by the query.