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

Helger Lipmaa

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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-security DEG cryptosystem Elgamal cryptosystem generic group model irreduction
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: 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}
}