CryptoDB
On CCA1-Security of Elgamal And Damg{\aa}rd's Elgamal
Authors: | |
---|---|
Download: | |
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 }