International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On CCA1-Security of Elgamal And Damg{\aa}rd's Elgamal

Authors:
Helger Lipmaa
Download:
URL: http://eprint.iacr.org/2008/234
Search ePrint
Search Google
Abstract: We establish the complete complexity landscape surrounding CCA1-security of Elgamal and Damg{\aa}rd's Elgamal (DEG). Denote by $X^{Y[i]}$ the assumption that the adversary, given a non-adaptive oracle access to the $Y$ oracle with $i$ free variables cannot break the assumption $X$. We show that the CCA1-security of Elgamal is equivalent to the $DDH^{CDH[1]}$ assumption. We then give a simple alternative to Gj{\o}steen's proof that DEG cryptosystem is CCA1-secure under the $DDH^{DDH[2]}$ assumption. We also provide several separations. We show that $DDH$ cannot be reduced to $DDH^{CDH[1]}$ in the generic group model. We give an irreduction showing that $DDH$ cannot be reduced to $DDEG^{CDEG[2]}$ (unless $\DDH$ is easy), $DDEG^{CDEG[2]}$ cannot be reduced to $DDH^{DDH[2]}$ (unless $DDEG^{CDEG[2]}$ is easy) and $DDH^{DDH[2]}$ cannot be reduced to the $DDH^{CDH[1]}$(unless $DDH^{DDH[2]}$ is easy). All those irreductions are optimal in the sense that they show that if assumption $X$ can be reduced to $Y$ in polynomial time then $X$ has to be solvable in polynomial time itself and thus \emph{both} assumptions are broken.
BibTeX
@misc{eprint-2008-18106,
  title={On CCA1-Security of Elgamal And Damg{\aa}rd's Elgamal},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography/CCA1-security, DEG cryptosystem, DDH, Elgamal cryptosystem, irreduction},
  url={http://eprint.iacr.org/2008/234},
  note={Manuscript h.lipmaa@cs.ucl.ac.uk 14152 received 22 May 2008, last revised 30 Sep 2008},
  author={Helger Lipmaa},
  year=2008
}