AbstractIn this work, we generalize the paradigm of the hash proof system (HPS) proposed by Cramer and Shoup (EUROCRYPT 2002). In the center of our generalization, we lift a subset membership problem to a distribution‐distinguishing problem. Our generalized HPS clarifies and encompasses all the known public‐key encryption (PKE) schemes that essentially implement the idea of an HPS. Moreover, besides the existing smoothness property, we introduce an additional property named anonymity for HPS. As a natural application, we consider anonymity for PKE in the presence of key leakage and provide a generic construction of leakage‐resilient anonymous PKE from an anonymous HPS. We then extend our generalization to the identity‐based setting. Concretely, we generalize the paradigm of the identity‐based HPS (IB‐HPS) proposed by Boneh et al. (FOCS 2007) and Alwen et al. (EUROCRYPT 2010) and introduce anonymity for it. As an interesting application of the anonymous IB‐HPS, we consider security for PKE with keyword search (PEKS) in the presence of token leakage and provide a generic construction of leakage‐resilient secure PEKS from leakage‐resilient anonymous identity‐based encryption, which in turn is based on anonymous IB‐HPS. Copyright © 2013 John Wiley & Sons, Ltd.