Homomorphic (encrypted) comparison to an integer

Question

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])$)

Answer 1

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).