I\'m looking into multiplication-homomorphic schemes now and basically I see tha

Question

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?

Explanation / Answer

Well, there seem to be some restrictions you have:

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.