## 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`.