International Association
for Cryptologic Research

In the past decade, much progress has been made on proposing encryption schemes with multi-user security. However, no known work aims at constructing a Public-key Encryption with Keyword Search (PEKS) scheme that is secure in multi-user setting. PEKS is a well-known primitive to solve the problem of searching over encrypted data. In this paper, we fill the gap. For more realistic multi-user scenario, we consider a strong security notion. Specifically, the adversary can adaptively corrupt some users' secret keys, and can adaptively request searchable ciphertexts of related keywords under different public keys as well as trapdoors of related keywords under different secret keys. We present two multi-user PEKS schemes both under simple assumptions in the standard model to achieve this strong security notion. \text{\qquad}Technically, our first scheme is a variation of the Lewko-Waters identity-based encryption scheme, and our second scheme is a variation of the Wee identity-based encryption scheme. However, we need to prove that the presented public key encryption schemes are secure in the multi-user, multi-challenge setting under adaptive corruptions. We modify the dual system encryption methodology to meet the goal. In particular, the security loss is constant.