Comparing two encrypted numbers using El Gamal without using decryption

Question

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.

Answer 1

I believe you're having trouble with achieving your goal, because it actually goes against the security property of ElGamal:

I don't know how deep your cryptography background is, but the security of ElGamal is IND-CPA. It basically states, the attacker chooses two messages, gets back the encryption of one of the message, and he has to choose which message it was and retrns 0 or 1. If IND-CPA holds, then there is no stragety better than guessing that one bit(with negligible difference).

If you have an operation for comparison without decryption, then the above security game is easy: The attacker can encrypt both messages. And he could also encrypt an intermediate value and use the comparison to immediately find out which one it was.

About your general idea, using the multiplicative homomorphic property:

• Kep in mind, that you are operating modulo some number. Formally, it's a finite field. But there is no comparison of elements in finite fields. The only way to achieve that, would be to limit the size of the numbers somehow, that you never trigger the modulo operation. That means, you have to keep the products below the modulus, otherwise the simple formula $a < b \Leftrightarrow ar < br$ is not valid any more. At least in general, without some additional constraints, e.g. that $a$ and $b$ are close together.
• But then, anyone who sees $ar$ and $br$ can also compute $gcd(ar,br)$. That is divisible by $r$, and if $a,b$ are coprime, it is exactly $r$. It's easy to get $a$ and $b$ then.

So for the purpose of security, this step is exactly the same as giving $a$ and $b$ directly for comparison.

---

To your acutal question:

There are a few things, which you could use. But they are constructs of scientific papers, not something that you can find fully implemented in libraries:

• Order preserving encryption, e.g. see this question or Order-Preserving Symmetric Encryption, Boldyreva et al., 2009
• searchable encryption, see this question or our tag for it, or Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions, Curtmola et al., 2006

Order-preserving encryption preserves elements order, so the comparison of the plaintext is just comparing the ciphertexts. However, this comes at a cost: The ciphertexts are usually quite a bit larger than the plaintexts. Searchable encryption is a powerful construction, which could be adapted for your comparison case.

But with ElGamal, you're not going to be able to achieve that without decryption and comparing the plaintext.