Recetly while studying about cryptographic primtives, I have come across below line in wiki : http://en.wikipedia.org/wiki/ElGamal_encryption

Encryption under ElGamal requires two exponentiations; however, these exponentiations are independent of the message and can be computed ahead of time if need be.

Does "if need be" in the sentence refering to a static key? or is he saying that we can compute an ephemeral key prior to encryption and send to receiver, then later send the encrypted ciphertext at some other time.

If he is not refering to ephemeral key, I still want to know, are there any times we can really implement such a process using ephemeral.


I use the notation from the linked Wiki page.

What this means is, assuming one potential receiver's public key $h$, that you can choose $y_1,\ldots,y_k$ offline and compute offline the values $(g^{y_1},h^{y_1}),\ldots,(g^{y_1},h^{y_1})$ and store them. Observe, that these values have nothing to do with the messages you want to encrypt (which are not yet known at this point in time).

Then, when you want to encrypt some message $m$ and send it encrypted to the holder of the public key $h$, you simply take an item from the stored list, say the $i$'th entry, set the ciphertext as $(c_1,c_2)=(g^{y_i},m\cdot g^{y_i})$ and send it. Observe, that now this only costs a single multiplication of one of the pre-computed values with the message $m$.

After having sent this ciphertext, you remove the $i$'th entry from the list.

  • $\begingroup$ @smslce I did not say that this is a good idea. You will have to securely store the pre-computed list as the knowledge allows simple decryption by an attacker without the secret key. Yes, you have to know the receiver in advance, but you could pre-compute lists for all potential receivers. $\endgroup$ – DrLecter Jan 26 '14 at 16:08
  • $\begingroup$ But, we choose our receiver only at the time we want to send a message but not prior to it, isn't that the concept of ephemeral keys. Also I think wiki's method could be problematic at two situations. 1. If there are "n" number of users, we have to store n entries. What if "n" is too large. 2. Also how much sure we can, that our receiver would stick to the same public key, after we go offline. $\endgroup$ – smslce Jan 26 '14 at 16:10
  • $\begingroup$ @smslce 1) yes, clearly. 2) this approach only makes sense if you know the receivers and their public keys (you should have an authentic copy of the receivers public key and typically public keys have a validity period in the order of years). $\endgroup$ – DrLecter Jan 26 '14 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.