Public key encryption with keyword search secure against keyword guessing attacks without random oracle

The notion of public key encryption with keyword search (PEKS) was put forth by

Boneh et al. to enable a server to search from a collection of encrypted emails given

a “trapdoor” (i.e., an encrypted keyword) provided by the receiver. The nice property

in this scheme allows the server to search for a keyword, given the trapdoor.

Hence, the verifier can merely use an untrusted server, which makes this notion

very practical. Following Boneh et al.’s work, there have been subsequent works

that have been proposed to enhance this notion. Two important notions include the

so-called keyword guessing attack and secure channel free, proposed by Byun et al.

and Baek et al., respectively. The former realizes the fact that in practice, the space

of the keywords used is very limited, while the latter considers the removal of secure

channel between the receiver and the server to make PEKS practical. Unfortunately,

the existing construction of PEKS secure against keyword guessing attack is only

secure under the random oracle model, which does not reflect its security in the real

world. Furthermore, there is no complete definition that captures secure channel

free PEKS schemes that are secure against chosen keyword attack, chosen ciphertext

attack, and against keyword guessing attacks, even though these notions seem

to be the most practical application of PEKS primitives. In this paper, we make

the following contributions. First, we define the strongest model of PEKS which

is secure channel free and secure against chosen keyword attack, chosen ciphertext

attack, and keyword guessing attack. In particular, we present two important security

notions namely IND-SCF-CKCA and IND-KGA. The former is to capture an

inside adversary, while the latter is to capture an outside adversary. Intuitively, it

should be clear that IND-SCF-CKCA captures a more stringent attack compared to

IND-KGA. Second, we present a secure channel free PEKS scheme secure without

random oracle under the well known assumptions, namely DLP, DBDH, SXDH and

truncated q-ABDHE assumption. Our contributions fill the gap in the literature

and hence, making the notion of PEKS