Keyword guessing attacks on secure searchable public key encryption schemes with a designated tester

The first searchable public key encryption scheme with designated testers (dPEKS) known to be secure against keyword guessing attacks was due to Rhee et al. [H.S. Rhee, W. Susilo, and H.J. Kim, Secure searchable public key encryption scheme against keyword guessing attacks, IEICE Electron. Express 6(5) (2009), pp. 237-243]. Recently, some dPEKS schemes, including the Rhee et al. scheme, were found to be vulnerable to keyword guessing attacks by a malicious server. However, the Rhee et al. dPEKS scheme and its improved variants are still known to be secure against keyword guessing attack by the outsider attacker to date. In this paper, we present a keyword guessing attack by the outsider attacker on the existing dPEKS schemes. We first describe the attack scenario which is possible in the current nature of the Internet and public key encryption with keyword search applications, e.g. email routing. We then demonstrate the detailed attack steps on the Rhee et al. scheme as an attack instance. We emphasize that our attack is generic and it equally applies to all existing dPEKS schemes that claim to be secure against keyword guessing attacks by the outsider attacker.