# Order Preserving Encryption for Numeric Data Values

How can I ensure order of encrypted data i.e., Enc(m1) < Enc(m2) where m1 < m2, and all messages are integer values.

I have gone through Order Preserving Encryption discussed in Enabling Search over Encrypted Multimedia Databases.

According to the literature, for sorted data values (i.e., words), lower limit (l_w) and upper limit (U_w) are defined according to the frequency count of a word and estimated value (encoded value) is selected by Linear Spline Interpolation within the defined limits.

I am finding it hard to define lower and upper limits for the following data values. I want to encode the frequency with the range of [0 – 10,000] and DocCount with in [0 - 500]. However, I have only one data point (i.e., w_i) within each range (i.e., l_w_i to U_w_i), how can I find interpolant of the values.

DocCount    Word Frequency
10          1
8           2
6           3
5           4
3           5
2           6
1           7
0           8
0           9
0           10


Or

Is there any other way through which I can ensure order of the encrypted data. On StackOverFlow I was referred to homomorphic encryption – I am familiar with Pascal Paillier crypto system, any idea how can utilize it to preserve order among encrypted values.

-
you probably don't need the have the numerical encrypted values ordered, but it would suffice if you had some function f: f(E(m1), E(m2)) = m1<m2 –  Willem Hengeveld Mar 20 '12 at 17:49
If the list of messages is static, you could of course just prepend the indexnumber of the message to the encrypted message. –  Willem Hengeveld Mar 20 '12 at 17:51
I give an explanation of Boldyreva's OPE scheme in the accepted answer to this question: crypto.stackexchange.com/questions/3813/… –  pg1989 Aug 31 '13 at 16:28