Is it secure to use order preserving encryption in practice?

Question

When I read papers, I often see the comments, "order-preserving encryption is deterministic and it is not IND-CPA secure", or in general "it is not secure enough to be implemented in practice". So I am wondering if these comments are correct especially from the practical implementation's point of view. I know a lot of works based on OPE. If it is not that secure in real world, can I think of these works as be more theoretical than practical?

Answer 1

Timely question, since attacks on the order preserving encryption in CryptDB were recently in the news. Quoting the research paper (pdf), there are two attacks they use on OPE:

• sorting attack: is an attack that decrypts OPE-encrypted columns. This folklore attack is very simple but, as we show, very powerful in practice. It is applicable to columns that are “dense”in the sense that every element of the message space appears in the encrypted column. While this may seem like a relatively strong assumption, we show that it holds for many real-world datasets.
• cumulative attack: is a new attack we introduce that decrypts OPE-encrypted columns. This attack is applicable even to low-density columns and also makes use of combinatorial optimization techniques.

In practice they were able to decrypt fields with a relatively small range possible values with very high confidence.

The response from the developers was that:

OPE encryption should be used for “high-entropy values” where the order does not reveal much

I would not think there are many circumstances where that would be the case and yet both privacy and ordering (rather than e.g. deterministic encryption only) is needed, but there are probably some. E.g. some very exact timestamp might fit the bill in some circumstances, if finding the approximate value would not be a problem but the exact value would.

So practical applications where it is secure may be limited but they probably exist.