Paper 2018/1083

Private Stateful Information Retrieval

Sarvar Patel, Giuseppe Persiano, and Kevin Yeo

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM-CCS-2018
DOI
10.1145/3243734.3243821
Keywords
Private information retrieval
Contact author(s)
kwlyeo @ google com
History
2018-11-09: received
Short URL
https://ia.cr/2018/1083
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1083,
      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{https://eprint.iacr.org/2018/1083}},
      url = {https://eprint.iacr.org/2018/1083}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.