Exponential ElGamal decryption optimizations

[seresistvanandras]

Currently, the verifier naively brute forces the exponential ElGamal ciphertext to recover the underlying plaintext. This has a linear complexity. We could either (depending on the application and the assumptions about the clients computational/storage complexity):

1. Use lookup tables to read off the plaintext as it was done in this paper. Some of the lookup tables here have MB, even GB size, which might be intolerable in certain applications. So caution is required here.
2. Use Shank's Baby step Giant step algorithm or Pollard's rho algorithm to recover the plaintext, i.e., the discrete logarithm of g^m, where m is the message. This would have square root complexity in the size of the range.