4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ In reality , it depends on what data type you want to apply OPE for ? if it is salary , age and such low entropy fields, it may not be suggested $\endgroup$ – sashank Sep 18 '15 at 10:14
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Just adding to @otus. Order-preserving encryption should only be used as a secondary measure, and when there is no other option. It is important to be aware that it is not secure, but it does give you something when there's nothing else you can do. (By nothing else to do, I mean that it's either this or not encrypt at all, due to application constraints). $\endgroup$ – Yehuda Lindell Sep 18 '15 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.