International Association
for Cryptologic Research

In this work, we generalize the paradigm of hash proof system (HPS) proposed by Cramer and Shoup~\\cite{CS2002}.

In the central of our generalization, we lift subset membership problem to distribution distinguish problem.

Our generalized HPS clarifies and encompass all the known public-key encryption (PKE) schemes

that essentially implement the idea of hash proof system.

Moreover, besides 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 anonymous HPS.

We then extend our generalization to the identity-based setting.

Concretely, we generalize the paradigm of identity-based hash proof system (IB-HPS)

proposed by Boneh~\\textit{et al.}~\\cite{BGH2007} and Alwen~\\textit{et al.}~\\cite{Alwen2010},

and introduce anonymity for it. As an interesting application of anonymous IB-HPS,

we consider security for public-key encryption with keyword search (PEKS) in the presence of token-leakage,

and provide a generic construction of leakage-resilient secure PEKS from leakage-resilient anonymous IBE,

which in turn is based on anonymous IB-HPS.