Order-Preserving Encryption (OPE) and leakage

Question

I recently came across OPE and Order-Revealing Encryption (ORE), but I didn't exactly got the idea why they are important. What's exactly important about them? Are they actually used in practice? My recent interest is leakage-resilient cryptography, and I saw there are some papers on leakage in OPE and ORE, but why is leakage important in OPE and ORE?

Answer 1

I do work in this area. OPE and ORE are important primarily because of their tremendous utility in building systems which can perform some computation on encrypted data. Contrary to general-purpose solutions like fully-homomorphic encryption, OPE and ORE can be used to provide drop-in (with no code change) security in applications like databases. They can do this with only a small decrease in efficiency of the application.

OPE and ORE are used in practice. Companies like CipherCloud and Skyhigh Networks deploy encryption software for cloud applications like Salesforce that use OPE heavily. Other major tech companies are also looking at OPE and ORE, though I can't say which ones for confidentiality reasons.

The 'but' (in cryptography there's always a 'but') is that all practical OPE and ORE schemes leak some information about the plaintext. This may seem obvious - to have order-preserving encryption you kind of need to, you know, preserve order. The hitch is that most actual deployable OPE and ORE schemes leak more than just the order of the plaintexts, and in some sense this is unavoidable because of a well-known impossibility result by Boldyreva et al. Further, nobody in the research community really knows how bad this leakage even is for real applications of OPE and ORE - we have precise simulation-based proofs which bound the leakage, but these proofs assume uniformly-distributed plaintexts. It seems like most use cases of OPE and ORE do not involve uniformly-distributed values, though. Extending and generalizing these analyses is a major (and important) open question right now.

I should note that when research papers talk about the "leakage" of OPE, it's not quite the same "leakage" discussed in leakage-resilient cryptography (LRC). LRC is attempting to provide a formal framework for reasoning about the effect of side-channel attacks which leak bits of the secret key, but in analyses of OPE and ORE the key is assumed to be fully hidden from the adversary.

Answer 2

If you know the order of the plaintext just possessing the correspondent ciphertext, then you can perform sorting, interval querying, and all the sort of algorithms based on neighborhoods on the ciphertext domain. This is why those schemes are used in practice.

To see another example of the use of OPE, take a look at the cryptoDB: Queries of type "SELECT * FROM table WHERE some_column <= some_value" are possible over an encrypted database because of the OPE schemes used there.

The other answer said that homomorphic encryption (HE) solutions are (far) less efficient and harder to deploy. That is surely true. But besides that, the main difference here is that the results of the comparisons are known by anyone that compares the ciphertexts using OPE or ORE, while in the HE scenario, given two ciphertexts, it would be possible to execute a circuit that compares them, but the result would be also a ciphertext, therefore, only the private key holder (usually the data owner) would know this result. This is why HE does not leak the order.

And since you asked about other things those kinds of schemes may leak, I add the following:

1. If they are deterministic (as OPE schemes are), then they leak plaintext equality.

That means that given two ciphertexts, one could know if they are the encryption of the same plaintext or not. Therefore, it leaks the frequency of the plaintexts.

2. They may leak the relative distance between plaintexts.

That means that given two ciphertexts, one could know how distant their correspondent plaintexts are one of the other. In particular, one can have an idea of how many possible plaintexts you have by looking at the smaller and at the greater ciphertext and finding out the distance of their correspondent plaintexts.

3. They may leak the approximate location of the plaintext.

That means that given one ciphertext $c$ corresponding to a plaintext $m$, one could find some interval $[a, b]$ such $a \le m \le b$. This is the notion modeled by the Window One-Wayness (WOW) security definition (a window is an interval where a plaintext may lie in)

Answer 3

If you want to know more about leakage in Order Preserving Encryption (OPE) and Order Revealing Encryption (ORE) Scheme, you can find some interesting findings in two papers:

• What Else is Revealed by Order-Revealing Encryption?, 2016 ACM SIGSAC.
• Leakage-Abuse Attacks against Order-Revealing Encryption, 2017 IEEE S&P

In the first paper they explain how in the attack they perform the inter-column correlation-based attacks combined with a sorting attack on multiple columns.

In the second they perform the frequency statistics of plain-text attack (using available data-sets from the Internet (knowing approximately the domain (e.g health) and trying to guess which plain-text matches which cipher-text from DB).