Single-Server Private Information Retrieval with Sublinear Amortized Time
Single-Server Private Information Retrieval with Sublinear Amortized Time
复制标题
DOI：
10.1007/978-3-031-07085-3_1
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Henry Corrigan-Gibbs;Alexandra Henzinger;Dmitry Kogan
中科院分区：
文献类型：
--
作者：
Henry Corrigan-Gibbs;Alexandra Henzinger;Dmitry Kogan
我们在单服务器设置中构建新的私人信息检索协议。我们的方案允许客户端私下从服务器获取一系列数据库记录，而服务器以与数据库大小呈次线性关系的平均时间回答每个查询。具体来说，我们引入了第一个单服务器私人信息检索方案，该方案具有次线性摊销服务器时间，需要次线性额外存储，并允许客户端自适应地进行查询。我们的协议仅依赖于标准密码学假设（决策 Diffie-Hellman、二次余数、错误学习等）。它们的工作原理是让客户端首先从服务器获取有关数据库内容的小“提示”。生成此提示需要与数据库大小成线性关系的服务器时间。此后，客户端可以使用提示向服务器发出有限数量的自适应查询，服务器在亚线性时间内回答这些查询，从而产生亚线性摊销成本。最后，我们给出下限，证明我们最有效的方案在服务器在线时间和客户端存储之间实现的权衡方面是最佳的。
We construct new private-information-retrieval protocols in the single-server setting. Our schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size. Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small “hint” about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sublinear time—yielding sublinear amortized cost. Finally, we give lower bounds proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage.