FrodoPIR：Simple, Scalable, Single-Server Private Information Retrieval - Alex Davidson.pdf
免费下载
FrodoPIR: Simple, Scalable, Single-Server Private
Information Retrieval
Alex Davidson, Gon¸calo Pestana, Sof´ıa Celi
Brave Software
Abstract. We design FrodoPIR — a highly configurable, stateful, single-
server Private Information Retrieval (PIR) scheme that involves an of-
fline phase that is completely client-independent. Coupled with small
online overheads, it leads to much smaller amortized financial costs on
the server-side than previous approaches. In terms of performance for a
database of 1 million 1KB elements, FrodoPIR requires < 1 second for
responding to a client query, has a server response size blow-up factor
of < 3.6×, and financial costs are ∼ $1 for answering 100, 000 client
queries. Our experimental analysis is built upon a simple, non-optimized
Rust implementation, illustrating that FrodoPIR is particularly suitable
for deployments that involve large numbers of clients.
1 Introduction
A Private Information Retrieval (PIR) scheme provides the ability for clients to
retrieve items from an online database, without revealing anything about their
queries to the untrusted host server(s). Applications of practical PIR schemes
include: anonymous communication [7, 61], anonymous media streaming [47],
privacy-preserving ad-delivery [45, 68, 63], private location discovery [37], pri-
vate contact discovery [16], password-checking [3], and SafeBrowsing [54]. PIR
schemes are split into those that are information-theoretically secure, but require
the database to be shared between multiple non-colluding servers [5, 26, 9, 11,
31, 10, 12, 75, 36, 35, 28, 40, 72, 58]; and those that are computationally-secure
against a single untrusted server [3, 31, 6, 21, 24, 38, 55, 56, 1, 64, 65, 62, 59].
Multi-server PIR constructions are typically more efficient than single-server
schemes. However, finding non-colluding servers to jointly fulfill the PIR func-
tionality can be unrealistic and burdensome. To avoid such problems, devel-
oping practical single-server PIR schemes is a desirable goal. The most effi-
cient single-server PIR schemes are based on fully homomorphic encryption
(FHE), with security derived from the ring learning with errors (RLWE) as-
sumption [1, 6, 62, 3, 64, 59]. Unfortunately, these schemes incur computational,
bandwidth, and consequent financial overheads for answering client queries on
standard, cloud-based infrastructure that would make them expensive to run at
scale. Even the most efficient require several seconds to process a single query
on a database of 1 million 1KB elements.
To drive down online and financial costs, a recent line of work of single-
server PIR moves large proportions of the expensive online computation and
communication to an offline phase [62, 65, 30] (a technique that also applies in the
two-server model [31, 58]). In this model, the client and server prepare an offline
internal state to be used for making online queries. Such schemes are referred
to as offline-online or stateful, as opposed to online-only or stateless. Many
works [62, 65, 30] have focused on developing PIR schemes with efficient online
phases. The recent work of Corrigan-Gibbs et al. [30], for example, produces a
stateful single-server PIR scheme with sublinear efficiency costs.
A key difficulty that has gone unsolved is that either the computation or
the communication costs induced during the offline phase scale linearly in the
number of clients that will make queries [62, 30, 65]. Moreover, previous schemes
require each individual client to make large numbers of queries (e.g.
√
m for m
DB elements) to ensure that the amortized costs remain sublinear. Ultimately,
this still results in significant financial costs for any server that plans to run a PIR
service in standard cloud-based infrastructure and that will answer queries from
large numbers of clients. As a consequence, single-server PIR remains unusable
in many real-world applications.
Our results. We build FrodoPIR: a stateful PIR scheme that is built directly
upon the learning with errors (LWE) problem only, rather than using RLWE and
FHE-based technologies. Similarly to FrodoKEM with respect to lattice-based
key exchange [17], we show that — counter to accepted intuition — eschewing
ring lattice structures can lead to flexible and practically efficient PIR schemes.
The main benefit of FrodoPIR is that the offline phase of the protocol is performed
by the server alone, completely independent of the number of clients or queries
that will be made. This results in low amortized computation overheads, and an
offline client download size that is a tiny fraction of the entire server database.
Our results highlight that the current bottleneck for deploying practical state-
ful PIR schemes is heavily related to the per-client scalability of the offline
preprocessing phase. Previous schemes have optimized primarily for per-client
asymptotics, which we show do not necessarily translate into financially cheap
real-world systems. To this end, FrodoPIR represents an initial exploration in de-
veloping stateful PIR schemes that are suitable for large, real-world deployments,
where lowering financial costs for server-side operators is of paramount impor-
tance. On top of this, FrodoPIR is significantly simpler than previous schemes,
making no use of FHE techniques and requiring only modular arithmetic that
can be implemented using standard 32-bit unsigned integer instructions. Our
formal contributions are as follows:
1. A stateful single-server PIR scheme, known as FrodoPIR, with security de-
rived from LWE.
2. A simple, open-source Rust implementation — containing only a few hundred
lines of code.
1
3. Experimental analysis that illustrates that FrodoPIR is cheaper to run in
large multi-client deployments than all previous single-server PIR schemes.
1
https://github.com/brave-experiments/frodo-pir
2
of 42
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论