11-02-2013, 09:36 AM
pCloud: A Distributed System for Practical PIR
Abstract
Computational Private Information Retrieval (cPIR) protocols allow a client to retrieve one bit from a database, without the server inferring any information about the queried bit. These protocols are too costly in practice because they invoke complex arithmetic operations for every bit of the database. In this paper, we present pCloud, a distributed system that constitutes the first attempt toward practical cPIR. Our approach assumes a disk-based architecture that retrieves one page with a single query. Using a striping technique, we distribute the database to a number of cooperative peers, and leverage their computational resources to process cPIR queries in parallel. We implemented pCloud on the PlanetLab network, and experimented extensively with several system parameters. Our results indicate that pCloud reduces considerably the query response time compared to the traditional client/server model, and has a very low communication overhead. Additionally, it scales well with an increasing number of peers, achieving a linear
speedup.
INTRODUCTION
CONSIDER an n-bit database DB ¼ fx1; x2; . . . ; xng. A Private Information Retrieval (PIR) protocol allows a client to retrieve bit xi, while keeping the value of the
index i secret from the server. PIR can also retrieve blocks of data (e.g., an ‘-bit record) by viewing the database as n=‘ elements, each with size ‘ bits. The ability to hide the
information that a user is interested in (from both the server and other clients) has some very appealing applications. For instance, an investor in the stock market may be
unwilling to disclose a trading strategy to other parties. Additionally, browsing privately through a patent or pharmaceutical database may conceal critical information
about a company’s new product. In the context of locationbased services, PIR may be utilized to hide the location of a user that is, otherwise, revealed through a spatial query
[15]. Finally, PIR has been considered as a building block in the Pynchon Gate [24], a system for receiving pseudonymously addressed e-mail. Given the vast number of applications that may benefit from private queries, PIR has received a lot of attention in
the cryptography community. Single-server PIR is a family of protocols that assume a nonreplicated database stored at a single site. These protocols, also known as computational PIR (cPIR), utilize certain cryptographic assumptions to ensure
privacy. Fig. 1 illustrates the operation of a generic cPIR scheme.
CONCLUSIONS
PIR is an important field with several practical applications. However, despite the extensive cryptography literature, there is very limited work on databases due to the prohibitive cost of PIR on data sets with realistic sizes. In order to tackle this cost, we leverage the computational resources of a peer-to-peer cloud. Specifically, the proposed pCloud solution embeds a state-of-the-art PIR protocol in a distributed environment, by utilizing a novel striping technique. pCloud can retrieve arbitrarily large blocks of information with a single query. We present a comprehensive solution that includes a data placement policy, result retrieval, and authentication mechanisms. We implement our system in PlanetLab and perform an extensive set of experiments, which confirm the effectiveness and practicality of our scheme.