Order Preserving Encryption for Numeric Data Values How can I ensure order of encrypted data i.e., Enc(m1) &lt; Enc(m2) where m1 &lt; 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.
To answer your second question, Paillier and other CPA-secure homomorphic encryption schemes cannot provide order-preserving encryption. The security of these schemes rely on using a random factor during encryption to ensure their ciphertexts are distributed randomly in the ciphertext space. OPE must use a weaker notion of security than CPA. 

In terms of your first question, I don't know enough about the data structure behind OPE to follow what you are asking. I know OPE is an available option in CryptDB so maybe they have automated the process of defining the limits you are asking about?