Paper 2007/073

Public Key Encryption that Allows PIR Queries

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


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Searching on encrypted dataDatabase securityPrivate Information Retrieval
Contact author(s)
wskeith @ math ucla edu
2007-02-28: received
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Eyal Kushilevitz and Rafail Ostrovsky and William E.  Skeith III},
      title = {Public Key Encryption that Allows PIR Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2007/073},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.