Editing ElGamal encryption (section)

== Security ==

The security of the ElGamal scheme depends on the properties of the underlying group <math>G</math> as well as any padding scheme used on the messages. If the [[computational Diffie–Hellman assumption]] (CDH) holds in the underlying cyclic group <math>G</math>, then the encryption function is [[one-way function|one-way]].<ref name=cryptutor>{{cite web
| url=https://crypto.cs.uiuc.edu/wiki/index.php/Elgamal_encryption_scheme
| title=Elgamal encryption scheme
| author= Mike Rosulek
| date=2008-12-13
| publisher=[[University of Illinois at Urbana-Champaign]]
| archive-url=https://web.archive.org/web/20160722005050/https://crypto.cs.uiuc.edu/wiki/index.php/Elgamal_encryption_scheme
| archive-date=2016-07-22
| url-status=dead}}</ref>

If the [[decisional Diffie–Hellman assumption]] (DDH) holds in <math>G</math>, then
ElGamal achieves [[semantic security]].<ref name=cryptutor/><ref>{{cite book
| first1=Yiannis
| last1=Tsiounis
| first2=Moti
| last2=Yung
| title=Public Key Cryptography
| chapter=On the security of ElGamal based encryption
| date=2006-05-24
| pages=117–134
| volume=1431
| doi=10.1007/BFb0054019
| isbn=978-3-540-69105-1
| series=Lecture Notes in Computer Science
}}
</ref> Semantic security is not implied by the computational Diffie–Hellman assumption alone. See [[Decisional Diffie–Hellman assumption]] for a discussion of groups where the assumption is believed to hold.

ElGamal encryption is unconditionally [[malleability (cryptography)|malleable]], and therefore is not secure under [[chosen ciphertext attack]]. For example, given an encryption <math>(c_1, c_2)</math> of some (possibly unknown) message <math>m</math>, one can easily construct a valid encryption <math>(c_1, 2 c_2)</math> of the message <math>2m</math>.

To achieve chosen-ciphertext security, the scheme must be further modified, or an appropriate padding scheme must be used. Depending on the modification, the DDH assumption may or may not be necessary.

Other schemes related to ElGamal which achieve security against chosen ciphertext attacks have also been proposed. The [[Cramer–Shoup cryptosystem]] is secure under chosen ciphertext attack assuming DDH holds for <math>G</math>. Its proof does not use the [[random oracle model]]. Another proposed scheme is [[Integrated Encryption Scheme|DHIES]],<ref name=DHIES>{{cite book
| first1=Michel
| last1=Abdalla
| first2=Mihir
| last2=Bellare
| first3=Phillip
| last3=Rogaway
| title=Topics in Cryptology — CT-RSA 2001
| chapter=The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES
| date=2001-01-01
| series=Lecture Notes in Computer Science
| volume=2020
| pages=143–158
| doi=10.1007/3-540-45353-9_12
| isbn=978-3-540-41898-6
| chapter-url=https://link.springer.com/chapter/10.1007/3-540-45353-9_12}}</ref> whose proof requires an assumption that is stronger than the DDH assumption.