4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Mar 20, 2012 at 17:49
  • $\begingroup$ If the list of messages is static, you could of course just prepend the indexnumber of the message to the encrypted message. $\endgroup$ Mar 20, 2012 at 17:51
  • 1
    $\begingroup$ I give an explanation of Boldyreva's OPE scheme in the accepted answer to this question: crypto.stackexchange.com/questions/3813/… $\endgroup$
    – pg1989
    Aug 31, 2013 at 16:28

2 Answers 2

3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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 . $\endgroup$
    – sashank
    Aug 31, 2013 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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