Cryptology ePrint Archive: Report 2013/720

Outsourced Symmetric Private Information Retrieval

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

Abstract: 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.

Category / Keywords: cryptographic protocols / searchable encryption, private information retrieval

Original Publication (with major differences): CCS’13, November 4–8, 2013, Berlin, Germany

Date: received 3 Nov 2013

Contact author: stanislawjarecki at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20131104:040004 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]