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