1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Also, have you looked through these search results? $\endgroup$ – mikeazo Oct 14 '16 at 12:07
  • $\begingroup$ I've chosen El Gamal because it is the only homomorphic scheme supported by Bouncycastle. As for the search results, I had already seen a few of them, I will need some time to evaluate all of them though. $\endgroup$ – user1870238 Oct 14 '16 at 12:24
  • $\begingroup$ Do you actually need the "additive" homomorphic nature of ElGamal, or is the only operation you need to perform comparison? $\endgroup$ – mikeazo Oct 14 '16 at 13:51
  • $\begingroup$ Wait, El Gamal is multiplicatively homomorphic, right? As in: E(a) * E(b) = E(a*b). (en.wikipedia.org/wiki/Homomorphic_encryption#ElGamal) As for whether I only need to do comparison, I guess so. Though, is it even possible to do secure comparison without homomorphic properties? $\endgroup$ – user1870238 Oct 14 '16 at 14:15
  • $\begingroup$ Homomorphic properties are something entirely different than comparisons. Actually, comparisons in pretty much any public-key cryptosystem doe not work. In those algebraic structures, comparisons (just like with integers) do not exist. $\endgroup$ – tylo Oct 14 '16 at 14:19
1
$\begingroup$

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 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.

$\endgroup$
  • 1
    $\begingroup$ "But they are constructs of scientific papers, not something that you can find fully implemented in libraries". It might be good to mention some of the encrypted DBs that are out there (and open source) that support range queries. Like ZeroDB, and CryptDB. $\endgroup$ – mikeazo Oct 14 '16 at 14:45
  • $\begingroup$ At least CryptDB is referenced in the question-link for searchable encryption. But you are right in the sense that there are constructions beyond the scientific scope, with the goal to achieve this functionality. But I don't know how much provable security or proper cryptanalyis there is, espcially for the inner parts of their "onion stragety for encryption" (not sure that's the right term) . $\endgroup$ – tylo Oct 14 '16 at 17:26
  • $\begingroup$ yeah, I haven't dove too deep into the provable aspect or cryptanalysis of these. There are also likely other application layer issues that could be run into. $\endgroup$ – mikeazo Oct 14 '16 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.