Paper 2008/234

On the CCA1-Security of Elgamal and Damgård's Elgamal

Helger Lipmaa

Abstract

It is known that there exists a reduction from the CCA1-security of Damgård's Elgamal (DEG) cryptosystem to what we call the $\DDH^{\DSDH}$ assumption. We show that $\DDH^{\DSDH}$ is unnecessary for DEG-CCA1, while DDH is insufficient for DEG-CCA1. We also show that CCA1-security of the Elgamal cryptosystem is equivalent to another assumption $\DDH^{\CSDH}$, while we show that $\DDH^{\DSDH}$ is insufficient for Elgamal's CCA1-security. Finally, we prove a generic-group model lower bound $\Omega (\sqrt[3]{q})$ for the hardest considered assumption $\DDH^{\CSDH}$, where $q$ is the largest prime factor of the group order.

Note: This corresponds to the published version

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Inscrypt 2010
Keywords
CCA1-securityDEG cryptosystemElgamal cryptosystemgeneric group modelirreduction
Contact author(s)
helger lipmaa @ gmail com
History
2011-09-07: last of 4 revisions
2008-05-26: received
See all versions
Short URL
https://ia.cr/2008/234
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/234,
      author = {Helger Lipmaa},
      title = {On the CCA1-Security of Elgamal and Damgård's Elgamal},
      howpublished = {Cryptology ePrint Archive, Paper 2008/234},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/234}},
      url = {https://eprint.iacr.org/2008/234}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.