How does order-preserving encryption work?

Question

Order-preserving encryption (OPE) is, apparently, a method of encrypting data so that it's possible to make efficient inequality comparisons on the encrypted items without decrypting them.

I've been coming across this term in various places (including here) lately, but I have no idea how such encryption schemes are supposed to work. Any obvious methods I can think of to allow such comparisons on encrypted data would result in catastrophic security failure.

Certainly, I assume that OPE must involve some kind of security tradeoff compared to traditional encryption, but given that it seems to be actively studied and used, it seems that it must be possible to implement in a way that retains at least some level of useful security. I just don't see how.

Given that a quick Google search didn't turn up any convenient Wikipedia articles or other popular summaries of OPE, I figured I'd try asking for one here before diving into the academic literature. (At worst, I may try to answer my own question later, if nobody else beats me to it.)

So, to summarize, my question is: How does order-preserving encryption work, and what security properties does it provide?

Answer 1

There are a number of ways to do this.

The simplest way is to simply add a number to it. Given a key of X, it would show:

A>B
A+X>B+X

Of course, this isn't a very complex method by any means, but more complex formula could be used to give the same result. Generally speaking, they simply need to preserve the sign, which there are a multitude of methods of ensuring that it works, using some sort of a polynomial approach. Logarithm to a particular base could be another such example, as well as combinations of logarithms and the like.

For some more advanced methods, take a look at this paper, which goes into quite a bit of detail as to different methods.