2
$\begingroup$

I am trying to find out some disadvantages of ElGamal cryptography but I'm not able to figure out what's wrong with the algorithm. The only one I found is that a known-plain text attack is possible in ElGamal if the same $r$ is used twice during encryption.

Are there any other disadvantages of ElGamal encryption?

$\endgroup$
5
  • $\begingroup$ What about malleability, ciphertext expansion ? Or are you comparing it to something specific ? $\endgroup$
    – Ruggero
    Feb 27, 2015 at 12:45
  • 1
    $\begingroup$ Upsides compared with (EC)IES style schemes: None for normal encryption. Downsides: 1) Weak security proof (DDH) 2) Annoying to implement, since you need to be able to encode as group elements 3) malleable 4) The limited message size means that you typically still need to implement hybrid encryption. $\endgroup$ Feb 27, 2015 at 13:51
  • 1
    $\begingroup$ Well, are you referring to ElGamal only over $\mathbb{Z}_p$, or the general construction on arbitrary groups? And the disadvantages compared to what? Compared to no encryption, it has security advantages but the disadvantage of additional computations. Compared to encryption schemes with pairings.... it does not support pairings. ElGamal in general is homomorphic aka malleable, and it depends on the DDH assumption (and is only usable in groups, where DDH is hard). If this is an advantage or a disadvantage depends on your requirements. $\endgroup$
    – tylo
    Feb 27, 2015 at 13:59
  • 1
    $\begingroup$ Its main disadvantages are: 1) security requiring a safe prime number makes generation of large-enough keys super-long. 2) the data encrypted with it is twice the size of the same data encrypted with RSA (and in its sister signature algorithm, BTW, the signature of some data is twice as long as the same data signed with DSA). ElGamal is slow and uncanny, and it has no big advantages compared to other algorithms that I know of. $\endgroup$
    – Mints97
    Feb 27, 2015 at 19:04
  • 1
    $\begingroup$ @tylo or Mints Could you please construct an answer out of your comments? If everybody starts just commenting instead of answering (as CodesInChaos often does) then nothing gets actually answered in the end. $\endgroup$
    – Maarten Bodewes
    Mar 2, 2015 at 10:57

1 Answer 1

1
$\begingroup$

ElGamal is a scheme, that can be applied to any kind of group structure. The only requirement is that DDH has to be hard (e.g. not $(\mathbb{Z}_p,+)$).

If you use the most common construction with multiplicative groups $(\mathbb{Z}_p^*,\cdot)$, then you need larger groups, due to attacks like index calculus.

If you use elliptic curves, you can use smaller groups instead, because algorithms like index calculus are not known.

Elliptic curves with pairings are not suitable to be used, because in that case the DDH problem is not hard. Therefore, you can not design protocols with efficiently computable pairings.

One property of ElGamal is, that it is (semi-)homomorphic w.r.t. the group operation. If you see that as an unwelcome property, you can also call that malleable. If you consider this property useful or a security risk, depends on your point of view and your actual goal.

$\endgroup$

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.