I'm trying to create a protocol for comparing two El Gamal encrypted numbers (both numbers are encrypted with the same public key). However I'm having trouble with figuring out how to do this without using decryption at all.
My current approach for comparing $\mathcal{E}_{pk}(a)$ and $\mathcal{E}_{pk}(b)$ is to encrypt a random value: $\mathcal{E}_{pk}(r)$ and then calculating: $\mathcal{E}_{pk}(ar)$ and $\mathcal{E}_{pk}(br)$. By then decrypting both products and evaluating $\mathrm{max}(ar, br)$ it becomes possible to know which value is largest, without learning anything about $a$ or $b$ (with some caveats of course). However this does involve decrypting two values, which of course requires a private key. As such this approach is not ideal.
Is it possible to do this without having to use decryption?
Edit: As per request, I'll expand a little bit on what it is I'm trying to do.
I have an encrypted database on a server. The database is really nothing more than an encrypted key/value store. In this database multiple users have stored multiple records each encrypted with their own public key.
I now want to add the functionality that a user can search their own records. My idea was that the user sends their encrypted query (for example: "All my records with a value greater than $a$", where $a$ is some encrypted value) to the server.
The server then retrieves all the records belonging to the user performing the query and for each record performs a homomorphic comparison $\mathrm{compare}(\mathcal{E}_{Pk}(a),\ \mathcal{E}_{Pk}(v_i))$ (where: $v_i$ is the value of record $i$) to find all the records which have a value greater than $a$.
Lastly the server sends all the encrypted records back to the user whom will then be able to decrypt and view them.