Date Added: Aug 2012
This paper presents a new security notion, called Perfect Keyword Privacy (PKP), for non-interactive Public-Key Encryption with Keyword Search (PEKS). Although the conventional security notion for PEKS guarantees that a searchable ciphertext leaks no information about keywords, it gives no guarantee concerning leakage of a keyword from the trapdoor. PKP is a notion for overcoming this fatal deficiency. Since the trapdoor has verification functionality, the popular concept of "Indistinguishability" is inadequate for capturing the notion of keyword privacy from the trapdoor. Hence, the authors' formalization of PKP depends on the idea of formalizing a perfectly one-way hash function. They also present IND-PKP security as a useful notion for showing that a given PEKS scheme has PKP.