Does ElGamal Encryption create a different key for each block sent?

Question

I ask about ElGamal algorithm. Is ElGamal algorithm used new key for each encryption process. in other word it should we use new key for each chunk? For example, if we have message that has four block each block less than $P$. Where $P$ is the prime number used in ElGamal. How many keys should be used to encrypt this message?

Answer 1

If you have the setting of $G$ being a prime order $p$ group (written multiplicatively) generated by $g$ and your public-secret key pair is $(pk,sk)=(y=g^x,x)$, then encrypting a single message $m\in Z_p$ amounts to choosing $k\in_R Z_p$ and computing $(c_1,c_2)=(g^k,my^k)$.

If you have a message $m=(m_1,\ldots,m_l) \in Z_p^l$, then the ciphertext would be $((g^{k_1},m_1y^{k_1}),\ldots,(g^{k_l},m_ly^{k_l}))$ with the $k_i$'s being distinct (but the public key $y$ is the same, since it is intended for one receiver).

Observe, that when using the same $k$ for two messages, say $m_1$ and $m_2$, then you can infer non-trivial information about the messages from the ciphertexts $(g^k,m_1y^k)$ and $(g^k,m_2y^k)$, since computing $m_1y^k(m_2y^k)^{-1}$ gives you $m_1(m_2)^{-1}$. Consequently, choosing a fresh randomizer $k_i$ for every block is essential.

Nevertheless, if you have to encrypt multiple blocks in practice, you would use KEM/DEM style hybrid encryption for the sake of more efficiency.

A side note: if you encrypt a message $m\in Z_p$ under distinct public-keys $y_1,\ldots,y_n$, then you can re-use the randomness $k$. This means, that instead of choosing $k_1,\ldots,k_n \in_R Z_p$ and sending $((g^{k_1},my_1^{k_1}),\ldots,(g^{k_n},my_n^{k_n}))$, you can choose $k\in_R Z_p$ and send $(g^k,my_1^k,\ldots,my_n^k)$ which saves you computation and bandwidth. You may look here for a general treatment of this so called randomness re-use in multi-recipient encryption: journal paper or the previous paper versions paper1, paper2 for further details.