Cryptology ePrint Archive: Report 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.

Category / Keywords: CCA1-security, DEG cryptosystem, Elgamal cryptosystem, generic group model, irreduction

Publication Info: Inscrypt 2010

Date: received 22 May 2008, last revised 7 Sep 2011

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Note: This corresponds to the published version

Version: 20110907:122145 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]