# Multiplication-homomorphic schemes

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?

-
You could get an upper boundary on decryption time. $\;$ –  Ricky Demer Jun 6 at 9:52
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? –  bazzilic Jun 6 at 10:07