Helger Lipmaa's publications

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.


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.


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


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