  At CCS 2015 Naveed et al. presented first attacks on efficiently searchable
encryption, such as deterministic and order-preserving encryption. These
plaintext guessing attacks have been further improved in subsequent work, e.g.
by Grubbs et al. in 2016. Such cryptanalysis is crucially important to sharpen
our understanding of the implications of security models. In this paper we
present an efficiently searchable, encrypted data structure that is provably
secure against these and even more powerful chosen plaintext attacks. Our data
structure supports logarithmic-time search with linear space complexity. The
indices of our data structure can be used to search by standard comparisons and
hence allow easy retrofitting to existing database management systems. We
implemented our scheme and show that its search time overhead is only 10
milliseconds compared to non-secure search.
