2
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ If the $p_i$ are all zeroes, what are the $c_j$? Is that compatible with OTP-level security? $\endgroup$
    – fgrieu ♦
    Mar 4, 2012 at 11:51
  • $\begingroup$ 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. $\endgroup$
    – Henrick Hellström
    Mar 4, 2012 at 12:05
  • $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Mar 4, 2012 at 12:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Henrick Hellström
    Mar 4, 2012 at 12:50
  • 1
    $\begingroup$ 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). $\endgroup$
    – fgrieu ♦
    Mar 4, 2012 at 15:45

Your Answer

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

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