Cryptology ePrint Archive: Report 2007/073

Public Key Encryption that Allows PIR Queries

Dan Boneh and Eyal Kushilevitz and Rafail Ostrovsky and William E. Skeith III

Abstract: Consider the following problem: Alice wishes to maintain her email using a storage-provider Bob (such as a Yahoo! or hotmail e-mail account). This storage-provider should provide for Alice the ability to collect, retrieve, search and delete emails but, at the same time, should learn neither the content of messages sent from the senders to Alice (with Bob as an intermediary), nor the search criteria used by Alice. A trivial solution is that messages will be sent to Bob in encrypted form and Alice, whenever she wants to search for some message, will ask Bob to send her a copy of the entire database of encrypted emails. This however is highly inefficient. We will be interested in solutions that are communication-efficient and, at the same time, respect the privacy of Alice. In this paper, we show how to create a public-key encryption scheme for Alice that allows PIR searching over encrypted documents. Our solution provides a theoretical solution to an open problem posed by Boneh, DiCrescenzo, Ostrovsky and Persiano on ``Public-key Encryption with Keyword Search'', providing the first scheme that does not reveal any partial information regarding user's search (including the access pattern) in the public-key setting and with non-trivially small communication complexity. The main technique of our solution also allows for Single-Database PIR writing with sub-linear communication complexity, which we consider of independent interest.

Category / Keywords: cryptographic protocols / Searching on encrypted data, Database security, Public-key Encryption with special properties, Private Information Retrieval

Date: received 23 Feb 2007

Contact author: wskeith at math ucla edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20070228:111413 (All versions of this report)

Short URL: ia.cr/2007/073

Discussion forum: Show discussion | Start new discussion