On the Limits of Privacy Provided by Order-Preserving Encryption

The value of cloud services lies in operating on client's data, which often conflicts with clients' data privacy needs. Reconciling these contradictory requirements is an important research and engineering problem, whose efficient solution would have a far-reaching business impact. Generic theoretical approaches, such as fully-homomorphic encryption, are inefficient. Ad-hoc approaches, such as order-preserving encryption (OPE), provide solutions to a limited class of problems (e.g., evaluating encrypted range queries). Security achieved in real systems, even if an "ideal OPE" is employed, is hard to evaluate, and is often only illusory, since ability to order ciphertexts may reveal a lot about the underlying plaintexts. We concentrate on a typical application of OPE, encrypted searcheable webmail service. We describe information leakage due to OPE in this setting and discuss approaches to minimizing its impact. The main avenue of privacy improvement is appropriately limiting the type of interaction webmail server should be allowed.