Paper 2013/720

Outsourced Symmetric Private Information Retrieval

Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel Rosu, and Michael Steiner


In the setting of searchable symmetric encryption (SSE), a data owner D outsources a database (or document/file collection) to a remote server E in encrypted form such that D can later search the collection at E while hiding information about the database and queries from E. Leakage to E is to be confined to well-defined forms of data-access and query patterns while preventing disclosure of explicit data and query plaintext values. Recently, Cash et al presented a protocol, OXT, which can run arbitrary Boolean queries in the SSE setting and which is remarkably efficient even for very large databases. In this paper we investigate a richer setting in which the data owner D outsources its data to a server E but D is now interested to allow clients (third parties) to search the database such that clients learn the information D authorizes them to learn but nothing else while E still does not learn about the data or queried values as in the basic SSE setting. Furthermore, motivated by a wide range of applications, we extend this model and requirements to a setting where, similarly to private information retrieval, the client's queried values need to be hidden also from the data owner D even though the latter still needs to authorize the query. Finally, we consider the scenario in which authorization can be enforced by the data owner D without D learning the policy, a setting that arises in court-issued search warrants. We extend the OXT protocol of Cash et al to support arbitrary Boolean queries in all of the above models while withstanding adversarial non-colluding servers (D and E) and arbitrarily malicious clients, and while preserving the remarkable performance of the protocol.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision.CCS’13, November 4–8, 2013, Berlin, Germany
searchable encryptionprivate information retrieval
Contact author(s)
stanislawjarecki @ gmail com
2013-11-04: received
Short URL
Creative Commons Attribution


      author = {Stanislaw Jarecki and Charanjit Jutla and Hugo Krawczyk and Marcel Rosu and Michael Steiner},
      title = {Outsourced Symmetric Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2013/720},
      year = {2013},
      doi = {10.1145/2508859.2516730},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.