1
$\begingroup$

I've read on differential cryptanalysis where it traces the differences on the changes of ciphertexts of the same plaintext, except for some bits.

However, I wonder is the differential cryptanalysis is applicable to CPA secure cryptos like El-Gamal?

Thanks in advance.

$\endgroup$
6
$\begingroup$

Differential cryptanalysis is a tool which is used to analyze symmetric primitives such as block ciphers and cryptographic hash functions. So it is applicable to CPA secure symmetric encryption schemes.

ElGamal, however, is an asymmetric encryption scheme. Its CPA security essentially relies on the decisional Diffie-Hellman assumption in some group $\mathbb{G}$. Roughly speaking, under this assumption, the adversary can not distinguish the ElGamal ciphertext $C = (C_1, C_2)$ from a random element in $\mathbb{G} \times \mathbb{G}$.

Generally speaking, in the asymmetric setting, security is typically proven by showing that an adversary against some security property would imply an adversary against some underlying hardness assumption (e.g., DDH in the case of ElGamal). That is, as long as the underlying assumption holds, also the cryptosystem is secure. Therefore, one does usually not apply custom attack techniques to the cryptosystem itself, but rather analyzes the underlying hardness assumption. In contrast, in the symmetric setting, the security of the cryptosystem can typically not be reduced to breaking some underlying assumption, which is why one directly analyzes the cryptosystem regarding potential "weaknesses". Differential cryptanalisis is one such tool.

$\endgroup$
  • $\begingroup$ Thanks for the answer. So, as far as I understand, because the El-Gamal uses random ephemeral keys at each stage, there is no meaning to obtain the cipher-texts for plaint-text which differs in at most 1 bit for example. Am I right? $\endgroup$ – Ali Shakiba Jan 2 '18 at 14:15
  • 1
    $\begingroup$ I've edited the answer to additionally address the question from the comment. Please let me know if everything is clear now. $\endgroup$ – dade Jan 2 '18 at 14:44

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.