1982年にElGamalが考案した公開鍵暗号。
公開鍵は(p,g,y)。秘密鍵はx。
を暗号化する。
暗号文は。
を復号する。
巡回群Gとして楕円曲線で定義される素数位数の巡回群を選ぶ場合がある。この場合、楕円曲線ElGamalと呼ばれる(→楕円曲線暗号, ECC)。
直感的に言えば、によってDiffie-Hellman鍵交換を行い、その鍵を用いて平文をマスクしている。
暗号解読はCDH問題(Computational Diffie-Hellman問題)と等価である*1。CDH問題とは位数が素数pの群Gとその生成元g, , を入力として, を計算する問題。
*リスト:リスト::数学関連
*1:暗号を解読できればCDH問題が解けるし、CDH問題が解ければ暗号を解読できる