# How does order-preserving encryption work?

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?

-

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.

Start by considering a random order-preserving injective function from $M$ to $N$, $|M| < |N|$. W.l.o.g. we can consider $M$ the set $\{1, 2, ... , M\}$ and $N$ likewise. 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{max(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.

-
Thanks for this excellent answer! I felt that it deserved more than just an accept and an upvote, so you'll be getting an extra 50 rep bounty on top of that in a day or so. –  Ilmari Karonen Jun 23 '13 at 7:41
Thanks :) It's funny, before I really committed to learning this stuff I found this question hoping it would have a really comprehensive answer so I wouldn't have to do the heavy lifting. Now it does, haha. –  pg1989 Jun 23 '13 at 23:52
@pg1989 are you planing to make public your prototype implementation of the OPE scheme? –  curious Aug 6 '13 at 11:37
You don't need all the values. Really you just need the bit length of strings in the domain and range, since that determines the number of unique values in either (for an n-bit string there are $2^n$ values, etc. etc.) –  pg1989 Oct 28 '13 at 19:00
My code will be available soon –  pg1989 Oct 28 '13 at 21:50

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.

-
That approach is not secure if the same key is being used for all values. Suppose $c_1=OPE(a)=a+x$ and $c_2=OPE(b)=b+x$. Then the attacker obtains k=c2-c1 = a-b. So he knows that $a$ will in a range $[a-b,OPE(a)]$ . If $X$ is not big enough then the attacker with brute force can try all values in the range. –  curious Apr 19 '13 at 11:08