Security of the iterated Hill Cipher

I can understand that the basic Hill Cipher is susceptible to known plaintext attacks, but suppose the Hill Cipher is modified into the Iterated Hill Cipher. For a plaintext $x_0=m_0$ and an initialization vector $x_{-1}=u_0$ we have,

$$x_{i+1}=Ax_{i}-x_{i-1}$$

for $0\leq i< k$. So our private key consist of the triplet $(A,\,u_0,\,k)$ where $A$ is an invertible matrix. The ciphertext will be the tuple, $c=(x_{k},\,x_{k-1})$. This is the idea behind the Iterated Hill Cipher given in Symmetric-Key Homomorphic Encryption for Encrypted Data Processing (paywall).

Then there are lots of research papers which try to employ Latin Squares and Magic Squares for $A$. Here are some:

So my question is: why do people try to use Quasi-groups (Latin Squares) and Magic squares for the Hill Cipher? Does it improve the security?

• Note: the first two papers are behind a paywall. May 30 '14 at 14:29

The question was changed, so here is my updated answer.

This scheme is not secure against known-plaintext attacks. It is no better than an ordinary Hill cipher.

If you iterate the recurrence relation you listed, we find that

$$x_k = Bx_0 - Cx_{-1}$$

and

$$x_{k-1} = Cx_0 - Dx_{-1}$$

where $B,C,D$ are matrices given by $B=f(A)$, $C=g(A)$, $D=h(A)$, and $f(\cdot),g(\cdot),h(\cdot)$ are publicly known polynomials that depend only upon $k$. (For instance, for $k=4$, we have $B=f(A)=A^4 - 3A^2 + \text{Id}$, $C=g(A) = A^3 - 2A$, $D = h(A) = A^2 - \text{Id}$.)

It immediately follows that this scheme is insecure against known-plaintext attack. Each known plaintext pair gives you $m_0$ (the message), $u_0$ (the initialization vector), $x_k$, and $x_{k-1}$ (from the ciphertext), so we know $x_{-1},x_0,x_{k-1},x_k$.

Therefore, each known plaintext gives us two linear equations, with the unknowns being the elements of $B,C,D$. If the matrix is $n\times n$, then after $1.5n$ known plaintext pairs, we have enough information that we can probably recover all of $B,C,D$, and then the scheme is broken.

In fact, I expect this scheme might even be breakable via a ciphertext-only attack. I think we always have $C^2 = BD + \text{Id}$. Therefore,

$$Cx_k = BCx_0 - C^2 x_{-1}$$ $$Bx_{k-1} = BCx_0 - BD x_{-1}$$

so

$$Bx_{k-1} - Cx_k = x_{-1}.$$

Note that in a ciphertext-only attack, $x_{-1},x_{k-1},x_k$ are all known (from the initialization vector and the ciphertext). Therefore, each ciphertext gives us a linear equation on the unknowns $B,C$. After observing $2n$ ciphertexts, we should be able to solve for the matrices $B,C$. Then deriving $D$ is easy, and we will be able to decrypt.

Therefore, it looks like there is even a ciphertext-only attack on this scheme. Caveat: I haven't validated this ciphertext-only attack carefully, so check the details yourself. I might have made a mistake somewhere.

So why do those three papers still study Hill ciphers? I don't know, that would be an excellent question for the authors of those papers! Only they will know what was going through their minds. I wasn't able to read the first two papers (due to the paywall), but I took a quick look at the third paper, and I do not think there is a good reason to study these ciphers.

Keep in mind that there are a lot of papers out there, and quality varies widely. Just because a paper has been published doesn't mean it is any good. You will do better by sticking to conferences and journals that are well-reputed; once you start wandering off into obscure conferences and journals that are not well-regarded among cryptographers, the quality might vary tremendously. Similarly, if you find a crypto paper published in a conference that is not dedicated to cryptography, you might also want to be a bit cautious or skeptical. My suspicion is that the three papers you have found just aren't very good, and so there is not much more to say.

Your proposed scheme is not secure.

If $A$ is public, given $x_{i+1},x_i$ you can compute $x_{i-1}$ via the equation

$$x_{i-1} = Ax_i - x_{i+1}.$$

Everything on the right-hand side is known. Thus, an eavesdropper can start with $x_k,x_{k-1}$ and iteratively compute $x_{k-2},x_{k-3},\dots,x_1,x_0$. Once the eavesdropper has computed $x_0$, he knows the message $m_0$.

Another way to see that your proposed scheme is insecure is that there is no secret key. There is no secret known to the recipient that is not also known to the eavesdropper. Thus, if the recipient can decrypt, surely so can an eavesdropper.

So, your scheme is trivially broken under ciphertext-only attack. It is even worse than an ordinary Hill cipher. The attacker doesn't even need known plaintext.

• I think "public key" in the question is either a typo or a misunderstanding. The linked paper refers to $A$ as the secret key. Change "public" to "private" or "secret" and the question makes sense.
– otus
May 31 '14 at 10:27
• @LinearAlgebra, OK, I've edited my answer to show how to break the revised scheme, given your updated question.
– D.W.
May 31 '14 at 18:49