Are RSA and Elgamal partially homomorphic techniques? which one is better if one want to use it for practical purpose? and is there some FHE technique which can be used practically?
2
-
$\begingroup$ Not sure why people voted to close as "opinion-based", there is a clear winner between RSA and ElGamal for most realistic applications. $\endgroup$– mikeazoCommented Dec 3, 2014 at 16:51
-
1$\begingroup$ I would expect that close vote to be due to the 2nd question on FHE. I've seen many demonstrations of FHE - calling these practical all depend on what you need, which the Shalki didn't even attempt to quantify. $\endgroup$– Thomas M. DuBuissonCommented Dec 3, 2014 at 17:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
10
Yes ElGamal and RSA (without padding) are both partially homomorphic (wrt. mulitiplication). I can not think of any applications that uses the homomorphic properties of these schemes in practice. However, in terms of efficiency they are probably about equal. Evaluating the homomorphism involves just one multiplication for RSA and two for ElGamal. As for security, ElGamal is the way to go. ElGamal at least provides semantic security which unpadded RSA does not.
Wrt. FHE: the known constructions of FHE are still quite computationally heavy. However, since the first construction in 2009 a lot has happened to make FHE more efficient. At this point it is conceivable to run FHE in practice although it would be very very slow. In this paper researches evaluated the AES circuit using FHE for example. Whether or not it would be practical to use for any given application of course heavily depends on the application.
-
$\begingroup$ Nitpick: In case of ElGamal it requires two multiplications. I agree that a only a homomorphism w.r.t. multiplication is not really attractive for applications and textbook RSA is insecure. Additively homomoprhic ElGamal (aka "exponent ElGamal") such as Paillier, however, has numerous applications and ElGamal is semanitcally secure if the DDH in the respective group/subgroup is hard. A problem with exponent ElGamal however is, that you either have to use trapdoor discrete log groups or encryption invloves solving dlogs (which, however, can be practical if the message space is not too large). $\endgroup$– DrLecterCommented Dec 2, 2014 at 8:46
-
$\begingroup$ Thank you, I edited the answer to about ElGamal. However, I did not state that a homomorphism wrt. multiplication is unattractive. It may be very useful, I don't know. I just said I do not know of any application that uses it in practice. $\endgroup$– Guut BoyCommented Dec 2, 2014 at 8:59
-
$\begingroup$ True, actually the "is not attractive" is not an absolute statement, but from my point of view not attractive. $\endgroup$– DrLecterCommented Dec 2, 2014 at 9:07
-
$\begingroup$ what about the homomorphic encryption using LWE approach given by Brakerski and Vaikuntanathan? $\endgroup$ Commented Dec 2, 2014 at 9:50
-
$\begingroup$ What would you like to know about it? $\endgroup$– Guut BoyCommented Dec 2, 2014 at 9:56