2011 | OriginalPaper | Chapter
On the CCA1-Security of Elgamal and Damgård’s Elgamal
Author : Helger Lipmaa
Published in: Information Security and Cryptology
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
It is known that there exists a reduction from the CCA1-security of Damgård’s Elgamal (DEG) cryptosystem to what we call the
$\textrm{ddh}^{\textrm{dsdh}}$
assumption. We show that
$\textrm{ddh}^{\textrm{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
$\textrm{ddh}^{\textrm{csdh}}$
, while we show that
$\textrm{ddh}^{\textrm{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
$\textrm{ddh}^{\textrm{csdh}}$
, where
q
is the largest prime factor of the group order.