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.

When working with an additive homomorphic encryption scheme (say Pallier's), is there an efficient way to get the encrypted value of a comparison test to an integer value (I realise that an unencrypted comparison test would make the encryption scheme worthless)?

I know there are (rather costly in number of rounds and broadcast complexity) methods to compare two encrypted values, that is: given $Enc(x)$ and $Enc(y)$, obtain $Enc([x < y])$, which decodes to $1$ or $0$.

If we do not necessarily need $y$ to be private, but are instead willing to use a public integer value $d$ (presumably of the form $2^k$), are there any faster methods (in number of rounds) to get $Enc([x < d])$?

Edit 1: it is worth mentioning that, in this instance, $Enc(x)$ is itself obtained from homomorphic operations, so any method relying on having a binary decomposition of $Enc(x)$ would not be applicable (or more exactly: would require a costly pre-treatment protocol to binary-decompose the input)...

Edit 2: While I am definitely interested in hearing any generic answers to this problem (if they exist), my personal case can accommodate the following relaxations (by order of acceptability):

  • $y$ very small relative to the size of the modulo field (say, less than 3 bits).
  • $x$ small (say, less than 8 bits).
  • a secure comparison protocol not relying on pure homomorphic operations (e.g. requiring communication rounds).
  • if nothing better: testing for inequality ($Enc([x ≠ y])$)
share|improve this question
    
It would be good to know when you require the comparison. For initial encryptions or after performing homomorphic operations on the ciphertexts? For the former, if you produce a ciphertext and want to prove that the encrypted message falls into a specific interval, you can use encryption + commitment to encrypted message + zero-knowledge proof that ciphertext and commitment contain the same message and that the value in the commitment lies in a specific known interval (this works for instance for Paillier as well as for "exponential" - additive homomorphic - ElGamal). –  DrLecter Nov 13 '13 at 8:24
    
Sorry, just realised after posting: this would be after performing homomorphic operations (e.g. on the result of a series of multiplications between cyphertexts)... Which I guess rules out many method relying on a binary-decomposed input. –  Dave Nov 13 '13 at 8:28
    
Ok. The problem is that you then can no longer assume that you have knowledge about the encrypted message (which is also reqired by the methods you have cited). Do you have a certain application in mind? Should this comparison be done by some specific (trusted) entity or should it be in public? For the latter I do not see that much hope, as any algorithm that can do this efficiently, can be used to break the IND-CPA security of the encryption scheme (choose two messages of different integer size, get the challenge ciphertext, check for the integer size and win the game). –  DrLecter Nov 13 '13 at 9:09
1  
Comparison should be done in private by the party holding the encrypted values. The end goal is to count the number of values (obtained from previous homomorphic computations) that fall under a certain threshold (can be predetermined and public), without complete knowledge of the individual values and without the other party learning that count. A decent fallback would be a way to count for non-zero values. All this, on a rather large number of values. You are right: the paper I linked does require binary-decomposed inputs, but I believe there are protocols to do that (at quite a cost). –  Dave Nov 14 '13 at 0:20
    
I think I may have found a solution that uses one round (and only a few exponentiations) to compute the above. I may be missing something obvious, so any comment is welcome. –  Dave Nov 14 '13 at 5:24
add comment

1 Answer 1

up vote 2 down vote accepted

I may have found an answer (welcoming any comment on whether I missed something) which works, given certain size restrictions on the input $x$ and $y$:

Say, party A has Enc(x) and Enc(y):

  1. A flips a coin: b in {-1, 1}

  2. A computes: $Enc(c) = (Enc(y) Enc(-x))^{b*r} Enc(-r') = Enc(b*r*(y-x)-r')$ where (r, r') are a pair of random obfuscating values such that:

    • $r' < r$

    • the distribution of the random variable $r(y-x)-r'$ does not reveal anything about $(y-x)$ (see Edit 2 below).

    • $log_2(n) > log_2(max(x,y)) + log_2(r) + 2$

  3. A sends Enc(c) to the other party B

  4. B sends back Enc(d) = Enc([c > 0])

    • If b = 1, Enc([y > x]) = Enc(d)

    • If b = -1, Enc([y > x]) = Enc(-d)Enc(1)

Am I missing an obvious flaw?

Edit: To avoid modulo problems, $c$ should obviously be smaller than n. Which should be guaranteed by enforcing the conditions on $r$, $r'$ listed above.

Also: negative values refer to the upper range of [0, n-1], as detailed in section 2 of this paper.

Edit 2: The main attack vector would be in the possibility to identify a specific distribution of $c' = r(y-x) - r'$, revealing information on $(y-x)$ (and particularly whether $x = y$). I initially blindly assumed (based on this paper) that $c'$ had to follow a uniform distribution, but this actually does not seem to be a direct requirement.

Section 3.3 of this paper notes that, for $x$ and $y$ in domain $\mathcal{D}_a = [l_a,h_a]$, if $r$ is picked in domain $\mathcal{D}_r = [1, (h_a-l_a)^2]$ and $r'$ from $[0, r]$ (both uniform), then the probability of accidentally revealing $a = b$ is $p \approx \frac{\ln h_r}{h_r}$. This is negligible for e.g. $h_r = 64$ ($p < 2^{-58}$), which still can fit the modulo limit, given a typically secure $n$ (e.g. 512 bits).

This can be made even more difficult by choosing a distribution at random to pick $r$ and $r'$ from.

Same paper discusses a (seemingly tighter) bound on $r, r'$ to prevent wraparound (haven't checked it yet, but it would not really affect the above).

share|improve this answer
    
I believe the flaw is that this is not a homomorphic comparison, since it $\hspace{2.14 in}$ needs the private key holder to participate. $\:$ –  Ricky Demer Nov 14 '13 at 5:44
    
@D.W.: Basing the obfuscation idea on 2.1.1 of this paper, I realise that all operations here are mod n, but that's a very large n (presumably larger than c) with the condition: log2(n) > max(l(x),l(y) + l(r) + 2 (which I've now added above). Do you see a way this would be different from the paper above? | RickyDemer: granted. But it's a one-round protocol and I haven't seen any better so far (it seems likely that pure homomorphic comparison is simply not possible, based on what I've read so far). –  Dave Nov 14 '13 at 6:18
    
I have added to my answer the constraint that must be applied to the values: $log_2(n) > max(l(x),l(y)) + l(r) + 2$. This means that, for reasonably "small" values of $x, y$, you still have a large margin for the length of $r, r'$. My ballpark estimate would be that for input roughly half the bit-length of $n$, obfuscation should be still safe. There is definitely a limitation here, but it merely depend on how large $n$ is chosen and seems reasonable to me (my particular application would have $x, y$ under 8-bit, so definitely fine). –  Dave Nov 14 '13 at 6:59
    
@D.W.: For the sake of closure, I am going to go ahead and accept my own answer as I doubt anybody else will contribute at this point and it may be the closest I get to a solution to this question. But first, I would really like to hear your opinion on whether the requirements I spelt out satisfyingly address your concerns. –  Dave Nov 15 '13 at 16:06
1  
OK, much better! Now I believe that this should work. +1. Thank you for your patience with all my questions and doubts. –  D.W. Nov 16 '13 at 7:37
show 4 more comments

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.