5
$\begingroup$

If we have a (possibly imperfect) cryptosystem that generates ciphertext $C$ from plaintext $P$ and key $K$, we have:

$H(C, P, K) = H(C | P, K) + H(P, K)$

where $H$ is entropy.

My question is why following is true:

$H(C | P, K) = 0$

It seems because each key and plaintext uniquely define a ciphertext but I want to prove this mathematically (theories in entropy).

$\endgroup$
2
  • 3
    $\begingroup$ Your question might be more useful to other readers if you add an explanation for the symbols used. $\endgroup$ Mar 8, 2023 at 19:54
  • $\begingroup$ Edited to explain symbols. Two partial answers below could be merged. $\endgroup$
    – ctwardy
    Mar 21, 2023 at 14:39

2 Answers 2

4
$\begingroup$

It is not true for all cryptosystems. Most modern cryptographic systems support probabilistic encryption where there can be many ciphertexts associated with a single key-plaintext pair. This is particularly important where we wish schemes to have indistinguishability under chosen plaintext attacks (IND-CPA) for example.

$\endgroup$
3
$\begingroup$

Take the definition of the conditional entropy,

$H(C|P,K) = - \sum_{c \ \in \ C \\ m \ \in \ P \\ k \ \in \ K} p(c, m, k) \log\left(\frac{p(c,m,k)}{p(m,k)}\right)$

(maybe this is clearer on the Wikipedia, sorry for my rubbish formatting skills) then notice that, if $c$ is totally conditioned on $(m, k)$ - because, like you said, each ciphertext corresponds to a unique plaintext-key pair with a bijective mapping - then it must be that $p(c,m,k) = p(m,k)$. Consequently, the fraction inside the logarithm evaluates to $1$ always, and so the logarithm evaluates to $0$, always. Then each term in the sum is $0$ and the over all conditional entropy is $0$, as you expect for a distribution where $(m,k)$ totally defines $c$.

As mentioned above, for probabilistic encryption, where a nonce or IV is used, this wouldn't be the case, because there would be more inputs to define $c$, so the entropy of those inputs would 'filter through' to $c$ leading to non-zero conditional entropy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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