Thanks for the reply. I indeed was thinking of just comparing the encrypted bits.
That requires that encrypting X always produces the same bits. Reading on ElGamal on Wikipedia learnt me that it does not guarantee that; it also doubles messages in size, as you thought. That will thwart this attack for any reasonable size of the encoded messages.
One could do the comparison inside the crypto system, but that would not help either, as one cannot check the outcome of such a comparison.
That requires that encrypting X always produces the same bits. Reading on ElGamal on Wikipedia learnt me that it does not guarantee that; it also doubles messages in size, as you thought. That will thwart this attack for any reasonable size of the encoded messages.
One could do the comparison inside the crypto system, but that would not help either, as one cannot check the outcome of such a comparison.