Witness-based searchable encryption

We put forward a new cryptographic primitive called witness-based searchable encryption (WBSE), namely if w and x satisfy a witness relation, an encryption of (m, w) could be tested by a trapdoor of (m′, x) whether the keyword m′ is equal to m. The benefit of this primitive is to solve the challenging problem of keyword guessing attack in public-key searchable encryption. We construct a WBSE scheme in a generic way using smooth projective hash function (SPHF) as a building block and prove its WB-IND-CCA ciphertext security, WB-IND-TD trapdoor security and EUFT-CIA trapdoor unforgeability. Thanks to an efficient SPHF instantiation from Decisional Diffie-Hellman (DDH) assumption, we obtain an efficient WBSE instance without any pairing operation.