Private Stateful Information Retrieval

By Sarvar Patel, Giuseppe Persiano, Kevin Yeo. 2018

77 citations recorded by the source corpus.

Private information retrieval (PIR) is a fundamental tool for preserving query privacy when accessing outsourced data. All previous PIR constructions have significant costs preventing widespread use. In this work, we present private stateful information retrieval (PSIR), an extension of PIR, allowing clients to be stateful and maintain information between multiple queries. Our design of the PSIR primitive maintains three important properties of PIR: multiple clients may simultaneously query without complex concurrency primitives, query privacy should be maintained if the server colludes with other clients, and new clients should be able to enroll into the system by exclusively interacting with the server. We present a PSIR framework that reduces an online query to performing one single-server PIR on a sub-linear number of database records. All other operations beyond the single-server PIR consist of cryptographic hashes or plaintext operations. In practice, the dominating costs of resources occur due to the public-key operations involved with PIR. By reducing the input database to PIR, we are able to limit expensive computation and avoid transmitting large ciphertexts. We show that various instantiations of PSIR reduce server CPU by up to 10x and online network costs by up to 10x over the previous best PIR construction.

Subfields: Artificial Intelligence, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “[319] shows how the latter side information can be obtained and a practical hybrid (computational and information theoretic) PIR scheme on a single server was implemented and validated.”
Secure Federated Submodel Learning (2019, methodology): “To avoid downloading the full matrix, Private Information Retrieval (PIR) [13]–[15] can be applied, which exactly matches our problem settings, including the read-only mode and the privacy preservation requirement of the retrieved elements.”
Communication-Computation Trade-offs in PIR (2019, background): “Another work [56] introduces the notion of private stateful information retrieval where clients store some state over multiple queries.”
Private Information Retrieval With Side Information (2017, methodology): “The work of [34] builds up on the Partition and Code scheme to design a computationally efficient single-server PIR scheme with computational privacy guarantees.”