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

Helger Lipmaa. On the CCA1-Security of Elgamal and Damgård's Elgamal. In Xuejia Lai, Moti Yung and Dongdai Lin, editors, Inscrypt 2010, volume 6584 of Lecture Notes in Computer Science, pages 18--35, Shanghai, China, October 20--23, 2010. Springer, Heidelberg.

File: [.pdf (230 KB)] pdf recommended.

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 ( ^3\sqrt{q})$ for the hardest considered assumption $DDH^{CSDH}$, where $q$ is the largest prime factor of the group order.

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

Slides:

Comment: Note that [Bellare, Palacio, Asiacrypt 2004] proved that DEG is IND-CCA1 secure under a knowledge assumption. This somehow didn't make it to the related work

Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>gmail.com.