In the last couple weeks I've become pretty well-acquainted with the recent work in this area. I also built a prototype order-preserving encryption scheme following the algorithms presented in 'Order-preserving Symmetric Encryption' by Boldyreva et al. I'll take a stab at explaining the method I just implemented, which requires some understanding of discrete probability and the hypergeometric distribution.
Let $M$ and $N$ be two positive integers such that $M < N$. Start by considering a random order-preserving injective function from $[M]$ to $[N]$, where $[M] = \{1, 2, ... , M\}$ and $[N] = \{1, 2, ... , N\}$. Now, choose $M$ elements of $[N]$ randomly and put them in order. Our injective function $f:[M] \to [N]$ is simply this ordered set. To encrypt $i \in [M]$, just output the $i$-th element of this list. Obviously we can't use this as a real encryption scheme, we might need to randomly generate billions of numbers! So how do we proceed?
We proceed by noticing that we don't need the whole function in advance. If we could figure out a way to only generate an element of the ordered set when we need it as a ciphertext, we'd be hunky dory. This is called lazily sampling the function. To lazily sample our proposed function, we first need to look at the range space a bit differently.
Let's stick with our random order-preserving injective function $f$, which we're thinking of as an ordered list of elements of the range. Think of an element of the range as 'marked' if it's in the list and 'unmarked' if it's not. Now think of all the elements of the range, marked and unmarked, as being balls in a giant bin. If we draw balls without replacement, the number $x$ of 'marked' balls we've drawn after $y$ samples can be characterized by the hypergeometric distribution. The HGD has PMF $$\frac{\binom{y}{x} \binom{N-y}{M-x}}{\binom{N}{M}}$$
If you don't know what a PMF is, don't sweat it. All we really need to understand is the connection between OPFs and the HGD, which is that we can figure out how many points of our OPF lie below a given point of the range by treating the range point as the number of 'samples' in a hypergeometric experiment where the number of marked balls is $M$ and unmarked balls is $N-M$.
Also important to know is that we can efficiently and deterministically sample the HGD, i.e. given $y$, $M$, $N$, and some random coins $cc$ we can always generate an $x$ that describes the number of marked balls in our sample of size $y$.
We're close, I promise. We have the groundwork laid, we just need to figure out how to get an encryption scheme out of this.
Our encryption scheme follows fairly naturally from the above. Given a plaintext $m \in [M]$ and a key $k$ we can lazily sample our OPF and produce a ciphertext $n \in [N]$ by recursively searching the domain and range like so:
Start with the entire domain $[M]$ and range $[N]$. Call $y \leftarrow \frac{N}{2}$ our range gap. Now using our key $k$ we generate some pseudorandom coins and give them to our HGD sampling routine along with $y$, $M$, and $N$. This gives us an $x \le y$ that describes the number of points of our order-preserving function less than $y$. Call this $x$ our domain gap. Now because the $m$-th point of our OPF is the ciphertext of $m$, we know that if $m \lt x$ we need to recur on the points of the domain less than or equal to $x$ and less than or equal to $y$. If $x \lt m$, we recur on the points of the domain greater than $x$ and $y$. When our domain only has one point remaining, we'll have as our range a set of points in which our ciphertext can reside. Pick a point of this set and output it.
So after all that, it's just a fancy binary search??? Kinda, yeah. If you want to know all the messy details and how to actually make it secure, read the original OPE paper or look at the CryptDB implementation. My java implementation will also be open-sourced sometime soon, so you might check that out as well.
Order-preserving encryption has several caveats. To know all the details, read the follow-up of Alexandra Boldyreva, Nathan Chenette and Adam O'Neill's Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions (in proceedings of CRYPTO 2011, or full paper here). It analyzes the security of a random OPF and characterizes its leakages. Their most glaringly problematic result has to do with an adversary's ability to guess approximately where the underlying plaintext of a ciphertext lives in the plaintext space. Intuitively, it says that certain attackers can learn half the bits of a plaintext given its ciphertext. For certain applications this trade of security for functionality is acceptable, but in any case it's important to know what you're getting when you use these schemes.
Post a comment if you want something clarified in the above, I'll try to make a cogent edit.
