PEKS schemes have first been formalized and constructed by Boneh et al.. But with one exception, no known construction of a PEKS scheme supports the decryption of ciphertexts. That is, known constructions allow to *test* for a certain message, but they do not allow to *retrieve* the message, even when having the full secret key. Besides being somewhat unnatural for an encryption scheme, this ``no-decryption''-property also limits the applicability of a PEKS scheme. The one exception, a PEKS scheme with decryption due to Fuhr and Paillier, is formulated in the random oracle model, and inherently relies on the statistical properties of the random oracle. In fact, Fuhr and Paillier leave it as an open problem to construct a PEKS scheme with decryption in the standard model.
In this paper, we construct the first PEKS scheme with decryption (PEKSD scheme) in the standard model. Our sole assumption is an anonymous IBE scheme. We explain the technical difficulties that arise with previous attempts to build a PEKS scheme with decryption and how we overcome these difficulties. Technically, we isolate a vital additional property of IBE schemes (a property we call *well-addressedness* and which states that a ciphertext is tied to an identity and will be rejected when trying to decrypt with respect to any other identity) and show how to generically achieve it.
Our construction of a PEKSD scheme from an anonymous IBE scheme provides a natural example of a *non-shielding* construction (in which the decryption algorithm queries the encryption algorithm). Gertner et al. have shown that an IND-CCA secure public key encryption scheme cannot be constructed and proven from an IND-CPA secure scheme in a black-box and *shielding* way. However, our results give evidence that encryption queries in the decryption algorithm may well prove useful in a security reduction.
Category / Keywords: public-key cryptography / searchable encryption, public-key encryption, identity-based encryption Date: received 1 Oct 2008, last revised 23 Oct 2008 Contact author: Dennis Hofheinz at cwi nl Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Changes since initial upload: Fixed the definition of the PEKSD trapdoor. Added discussion on privacy-preserving trapdoors. Version: 20081023:063922 (All versions of this report) Discussion forum: Show discussion | Start new discussion