Hill cipher is not perfectly secure

Question

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.

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.