I am on cryptography course and there is a homework question to show that Hill cipher doesn't have perfect security.

So assume we have an cryptosystem $(P,C,K)$, where $P = C = \mathbb Z_{26}^N$ and $K$ is the set of invertible $N \times N$-matrices modulo $26$. Now we also have some probability distribution on $P$ and also some distribution on $K$.

A cryptosystem has perfect secrecy if $p(x) = p(x|y), \forall x\in P \wedge y\in C.$

Now, one option I considered is that according to Bayes rule, if system has perfect secrecy, the cardinalities of these sets $P,C,K$ must fulfill $|K| \ge |C| \ge |P|$. But this seems to be the case, so I can't use that.

The $p(x)$ is whatever the original distribution says it is. Now $p(x|y)$ cannot be the same as $p(x)$ for this homework to make sense. $$p(x|y) = \frac{p(y|x) p(x)}{p(y)}$$ $p(y) = \sum p(k) p(d_k(y))$, so probability that key used was $k \in K$ times the probability of decrypted message being $d_k(y)$. I would think $p(d_k(y))$ is same as $p(x)$, as $x$ is $y$ encrypted and as we sum over all the keys, for any key there is some $y \in C$ which maps back to a given $x \in P$, this is same as $p(x).$

Thus $p(x|y) = p(y|x)$. I would think that as we know $x$, and every key maps every plaintext to different cryptotext, they would have same distribution, so $p(x|y) = p(y|x) = p(x)$.

So we have perfect secrecy.

Now, what am I not getting here? I am sure I do something wrong, but help would be welcome.


1 Answer 1


One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages. So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large....

Another possibility you might be missing is the consequences of the fact that you are working modulo $26$. I think you need to calculate out $p(y|x)$ carefully. You might start by considering what happens when $N=1$. Can you calculate the value of $p(y|x)$ and $p(x|y)$, for all possible values of $x,y$? Maybe write a program to do it, or do the case analysis so you don't have to consider $26\times 26$ cases exhaustively. I think you'll find that is enough to let you figure out what's going on.

I don't want to say more, because this is an exercise, and should solve your own exercise.

  • $\begingroup$ Well, I did some calculations. If we have plaintext {0,0,0...}, then no matter what key we use, the cryptotext is also {0,0,0...}. So p(0,0,0...) = 1/something, but p(0,0,0...|y) = 0 or 1, depending on the y... So they are not same. Am I correct? $\endgroup$
    – Valtteri
    Commented Feb 4, 2014 at 21:13
  • $\begingroup$ @Valtteri, well done! $\endgroup$
    – D.W.
    Commented Feb 4, 2014 at 22:34

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.