Paper 2018/1083

Private Stateful Information Retrieval

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM-CCS-2018
Private information retrieval
Contact author(s)
kwlyeo @ google com
2018-11-09: received
Short URL
Creative Commons Attribution


      author = {Sarvar Patel and Giuseppe Persiano and Kevin Yeo},
      title = {Private Stateful Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1083},
      year = {2018},
      doi = {10.1145/3243734.3243821},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.