Paper 2017/825

Querying for Queries: Indexes of Queries for Efficient and Expressive IT-PIR

Syed Mahbub Hafiz and Ryan Henry

Abstract

We propose indexes of queries, a novel mechanism for supporting efficient, expressive, and information-theoretically private single-round queries over multi-server PIR databases. Our approach decouples the way that users construct their requests for data from the physical layout of the remote data store, thereby enabling users to fetch data using "contextual" queries that specify which data they seek, as opposed to "positional" queries that specify where those data happen to reside. For example, an open-access eprint repository could employ indexes of queries to let researchers fetch academic articles via PIR queries such as for "this year's 5 most cited papers about PIR" or "the 3 most recently posted papers about PIR". Our basic approach is compatible with any PIR protocol in the ubiquitous "vector-matrix" model for PIR, though the most sophisticated and useful of our constructions rely on some nice algebraic properties of Goldberg's IT-PIR protocol (Oakland 2007). We have implemented our techniques as an extension to Percy++, an open-source implementation of Goldberg's IT-PIR protocol. Our experiments indicate that the new techniques can greatly improve not only utility for private information retrievers but also efficiency for private information retrievers and servers alike.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. 24th ACM Conference on Computer and Communications Security (CCS 2017)
DOI
10.1145/3133956.3134008
Keywords
Private information retrievalexpressive queriesbatch codesbatch queriesramp schemesefficiency
Contact author(s)
henry @ indiana edu
History
2017-08-31: received
Short URL
https://ia.cr/2017/825
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/825,
      author = {Syed Mahbub Hafiz and Ryan Henry},
      title = {Querying for Queries: Indexes of Queries for Efficient and Expressive IT-PIR},
      howpublished = {Cryptology ePrint Archive, Paper 2017/825},
      year = {2017},
      doi = {10.1145/3133956.3134008},
      note = {\url{https://eprint.iacr.org/2017/825}},
      url = {https://eprint.iacr.org/2017/825}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.