Querying for Queries: Indexes of Queries for Efficient and Expressive IT-PIR.
Syed Mahbub Hafiz, Ryan Henry · IACR Cryptology ePrint Archive · 2017
We propose indexes of queries, a novel mechanism for supporting efficient, expressive, and information-theoretically private single-round queries over multi-server databases. Our approach decouples way that users construct their requests for data from physical layout of 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 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 protocol in ubiquitous vector-matrix model for PIR, though 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 new techniques can greatly improve not only utility for private information retrievers but also efficiency for private information retrievers and servers alike.