Symmetric Searchable Encryption for Database Applications

This paper proposes an efficient symmetric searchable encryption to achieve indistinguishability of indexes and trapdoors. Previous symmetric searchable encryptions are either insecure because their trapdoor generation algorithms are not probabilistic or inefficient because of the heavy cost due to pairing-based computation. Our searchable encryption is the first that satisfies both requirements of efficiency and indistinguishablity (security). Furthermore, we introduce a limitation of the latest definition of indistinguishability for searchable encryption when each cell in the database is encrypted. We hereby define a new game for database usage and show that our scheme is provably secure in this new game.