Security analysis of a “one-time pad” type hill cipher

Suppose the Hill cipher were modified to something like a one-time pad cipher, where Alice wants to send a message to Bob, and she chooses a key matrix randomly everytime a new message is sent (and the inverse of the key matrix is sent to Bob by other means everytime - just as in the one-time pad). Would this yield perfect secrecy or at least $\mathsf{IND-CCA}$?

Any thoughts on how to proceed with the security analysis of this?

-

Expand the equation system corresponding to the matrix multiplication:

$c_j = \sum_{i=0}^{n-1}k_{i,j}p_i$

In other words, each element of the cipher text corresponds to the sum of the cipher text elements of an OTP encryption of the input plain text. If the matrix is never reused, it should be fairly easy to go from here. You are basically using $n$ one time pads to encrypt the message instead of a single one. - Almost, since the $k_{i,j}$ values of the matrix have to be selected in such way that the determinant is not zero (presuming a prime field is used for the arithmetic operations). The next step is therefore to observe what this constraint means: If the diagonal is selected at random, the other matrix elements might be selected in such way that the determinant is non-zero.

-
If the $p_i$ are all zeroes, what are the $c_j$? Is that compatible with OTP-level security? –  fgrieu Mar 4 '12 at 11:51
Thanks, that is correct. This could be considered to be an encoding issue. Let the alphabet be such that the first character (zero) is never used in any plain text. This means that the cipher text alphabet contains one more character than the plain text alphabet contains, which not necessarily is any more problematic than it would be to Base64 encode an OTP cipher text. The problem is rather to define this deterministic step in such way that it can be applied to the random function you are trying to distinguish the hill cipher from. –  Henrick Hellström Mar 4 '12 at 12:05
Now, assuming we work $\bmod{27}$ and $p_j\ne 0$, what is $c_j\bmod 3$ if all $p_i\equiv 0 \pmod 3$? Again, is that compatible with OTP-like security? –  fgrieu Mar 4 '12 at 12:44
We don't work mod 27. According to the wikipedia article linked to in the question, the alphabet is typically expanded to a prime number of elements to avoid what you describe. –  Henrick Hellström Mar 4 '12 at 12:50
Yes, restricting a key to encode a single vector, removing 0 from the source alphabet, and using a prime modulus, I believe the Hill cipher becomes as secure as the OTP (this is easy to prove if, in addition, the matrix is restricted to be diagonal). Nitpick: the Wikipedia article does not state that using a prime modulus is typical or improves security (the rationale given is easier choice of key). –  fgrieu Mar 4 '12 at 15:45