eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2017/825

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

Syed Mahbub Hafiz and Ryan Henry


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 24th ACM Conference on Computer and Communications Security (CCS 2017)
Private information retrievalexpressive queriesbatch codesbatch queriesramp schemesefficiency
Contact author(s)
henry @ indiana edu
2017-08-31: received
Short URL
Creative Commons Attribution


      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.