[ElGamal85] A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms

Authors: Taher ElGamal | Venue: IEEE Transactions on Information Theory 1985 | Source

Abstract

A new signature scheme is proposed, together with an implementation of the Diffie-Hellman key distribution scheme that achieves a public key cryptosystem. The security of both systems relies on the difficulty of computing discrete logarithms over finite fields. The encryption scheme works as follows: to encrypt a message $m$ under public key $y=g^x$, choose random $r$ and send $(g^r,m\cdot y^r)$; decryption uses the secret key $x$ to recover $y^r=g^{rx}$ and thereby $m$. This construction is CPA-secure under the Decisional Diffie-Hellman (DDH) assumption, making it the first concrete PKE scheme provably based on a group-theoretic assumption. The ElGamal signature scheme was also influential, though it is not EUF-CMA secure without additional modifications (cf. DSA).

BibTeX

Copy

@Inproceedings{C:ElGamal84,
  author = {Taher {ElGamal}},
  title = {A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms},
  pages = {10--18},
  editor = {G. R. Blakley and David Chaum},
  booktitle = {Advances in Cryptology -- {CRYPTO}'84},
  volume = {196},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~19--23},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {1984},
  doi = {10.1007/3-540-39568-7_2},
}