Constructing PEKS schemes secure against keyword guessing attacks is possible?

Abstract

Byun et al. suggested keyword guessing attacks and showed that some PEKS (public-key encryption with keyword search) schemes are not secure to keyword guessing attacks, when the number of possible keywords is bounded by some polynomial. Abdalla et al. showed that robust PEKS schemes should satisfy consistency which ensures the PEKS schemes fulfil their functions. In the paper, we show a negative result about the open problem to construct secure PEKS schemes against keyword guessing attacks. Our result shows that consistency implies insecurity to keyword guessing attacks in PEKS. This means that constructing secure and consistent PEKS schemes against keyword guessing attacks is impossible, when the number of possible keywords is bounded by some polynomial. © 2008 Elsevier B.V. All rights reserved.