Homomorphic (encrypted) comparison to an integer
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):


A flips a coin: b in {-1, 1}
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' &lt; 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) &gt; log_2(max(x,y)) + log_2(r) + 2$

A sends Enc(c) to the other party B
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 &lt; 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).