Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

2 Answers 2

up vote 3 down vote accepted

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?

share|improve this answer
add comment

You definitely cannot get semantic security defined by Goldwasser and Micali; however, you can get some weaker form of security notion. Boldyreva et al. has motivated more on this in their first paper on Order Preserving Encyption. They have a follow up paper with more security analysis and an alternative scheme. I guess both of them solves the issue that you are trying to handle. They have a fairly detailed introduction in which they outline few of the key ideas, so if you don't care about minute details, that might be enough!

I am not sure how homomorphic encryption can be used to handle this scenario. I hardly doubt that FHE can be of any use here!

share|improve this answer
    
FHE cannot be used to achieve OPE, but definitely applications of OPE can be realized using FHE . I mean if OPE allows one to perform sort, compare etc , its trivial in FHE to execute such circuits on encrypted data . –  sashank Aug 31 '13 at 16:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.