I'm looking into multiplication-homomorphic schemes now and basically I see that there are 3 options: RSA, Boneh-Goh-Nissim and ElGamal.

RSA was proved to be insecure unless message is randomly padded, which action breaks the homomorphic property of the scheme.

Boneh-Goh-Nissim allows for one multiplication, but the decryption process is done through Pollard's lambda algorithm, which is basically guessing, i.e., there's no upper boundary on decryption time - looks dodgy for serious use.

ElGamal is great but the message expansion ratio is just crazy. If we use a 1024 bit key (512 was already broken), a 4 byte integer blows up to 256 bytes when encrypted. 64 times is harsh if we intend to encrypt GBs of plaintext data. Haven't yet tested the performance myself, but I guess that would suffer a lot too.

So the question is - are there other options I might take a look at?

  • $\begingroup$ You could get an upper boundary on decryption time. $\;$ $\endgroup$
    – user991
    Jun 6, 2014 at 9:52
  • $\begingroup$ Agreed, I was not completely correct. As far as I understand, worst case scenario is equivalent to brute force, which of course will end in a finite time. Is that right? $\endgroup$
    – bazzilic
    Jun 6, 2014 at 10:07

1 Answer 1


Well, there seem to be some restrictions you have:

  • numbers are 32 bit integers
  • (several) GB of total data
  • expansion factor matters

Well, standard ElGamal is probably already close to the best you can get. Maybe ElGamal over elliptic curves would work, which have shorter representations at similar security levels (but then the operations on points are homomorphic, and the function from integers to points will most likely not preserve this property). But in general, it's not going to be any better: Trapdoor functions need this kind of size for each element. And if the original element is just 32 bit, there is this kind of expansion.

  • $\begingroup$ 32 bit integers are a typical thing. Well, nowadays a 64 bit integer becomes more and more common too. I'll take a look at ElGamal over elliptic curves, thanks for the idea! $\endgroup$
    – bazzilic
    Jun 9, 2014 at 5:45
  • $\begingroup$ Well, in common programming languages 32 and 64 bit are common. But in cryptographic protocols, the basic size of numbers are chosen such that it's not possible to try out every possible number. And 32 bit are really easy to search through, 64 bit are manageable today. $\endgroup$
    – tylo
    Jun 10, 2014 at 11:09
  • $\begingroup$ I understand that, I'm saying that still plaintext values are usually no bigger than 64 bits. Btw, do you have a link to a paper on homomorphic ElGamal over elliptic curves? I didn't find it myself. $\endgroup$
    – bazzilic
    Jun 10, 2014 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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