On the CCAl-Security of Elgamal and Damgard's Elgamal

摘要

It is known that there exists a reduction from the CCA1-security of Damgard'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 CCAl-security of the Elgamal cryptosystem is equivalent to another assumption ddh~(dsdh), while we show that ddh~(dsdh) is insufficient for El-gamal's CCAl-security. Finally, we prove a generic-group model lower bound Ω(q~(1/3)) for the hardest considered assumption ddh~(dsdh), where q is the largest prime factor of the group order.