Team for Research in
Ubiquitous Secure Technology

Citation
"Public Key Encryption That Allows PIR Queries". D. Boneh, E. Kushilevitz, R. Ostrovsky, and W. Skeith (eds.), Crypto, 2007.

Abstract
We 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 is the first to reveal no partial information regarding the user's search (including the access pattern) in the public-key setting and with non-trivially small communication complexity. This provides a theoretical solution to a problem posed by Boneh, DiCrescenzo, Ostrovsky and Persiano on ``Public-key Encryption with Keyword Search.'' The main technique of our solution also allows for Single-Database PIR writing with sub-linear communication complexity, which we consider of independent inter est.

Electronic downloads

• http://crypto.stanford.edu/~dabo/abstracts/rafisearch.html

• HTML

   <a
  href="http://www.truststc.org/pubs/590.html"
  ><i>Public Key Encryption That Allows PIR
  Queries</i></a>, D. Boneh, E. Kushilevitz, R.
  Ostrovsky, and W. Skeith (eds.), Crypto, 2007.

• Plain text

   "Public Key Encryption That Allows PIR Queries".
  D. Boneh, E. Kushilevitz, R. Ostrovsky, and W. Skeith
  (eds.), Crypto, 2007.

• BibTeX

  @proceedings{BonehKushilevitzOstrovskySkeith07_PublicKeyEncryptionThatAllowsPIRQueries,
      title = {Public Key Encryption That Allows PIR Queries},
      editor = {D. Boneh, E. Kushilevitz, R. Ostrovsky, and W.
                Skeith},
      organization = {Crypto},
      year = {2007},
      abstract = {We 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 is the first to reveal no
                partial information regarding the user's search
                (including the access pattern) in the public-key
                setting and with non-trivially small communication
                complexity. This provides a theoretical solution
                to a problem posed by Boneh, DiCrescenzo,
                Ostrovsky and Persiano on ``Public-key Encryption
                with Keyword Search.'' The main technique of our
                solution also allows for Single-Database PIR
                writing with sub-linear communication complexity,
                which we consider of independent inter est. },
      URL = {http://www.truststc.org/pubs/590.html}
  }
  

Posted by Jessica Gamble on 13 Mar 2009.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.