The ciphertext $c$ corresponding to plaintext $m$ is given by $c= mK + w$. $K$ is the invertible matrix and w is the uniformly distributed random vector.

If $w$ is changed during every encryption, will this affine Hill cipher satisfy IND-CPA?

If $w$ is generated using a PRNG and this type of encryption is used as homomorphic encryption keeping $K$ same, will it still provide IND-CPA?

During decryption, $w$ should be subtracted from ciphertext first and multiplied with the inverse of $K$. For decryption, the key for the PRNG (LFSR based) can be used.

$(m1 + m2) = [(c1 + c2) - (w1 + w2)]K^{-1}$

  • 1
    $\begingroup$ Yes, because this essentially is a one-time-pad in this case. $\endgroup$
    – SEJPM
    Commented Dec 2, 2017 at 12:56
  • 1
    $\begingroup$ No, because the definition of IND-CPA does not allow changing the key between encryptions. $\endgroup$
    – fkraiem
    Commented Dec 2, 2017 at 13:05

1 Answer 1


Let $G:\{0,1\}^{r+l}\to\{0,1\}^*$ be some pseudorandom generator, let $K\in\text{GL}(\mathbb K,d\times d)$ be any invertible matrix over some field $\mathbb K$ and let $k\in\{0,1\}^{r+l}$ be the secret key for $G$ and $f:\{0,1\}^*\to \mathbb K^d$ be some bijective function mapping the PRG outputs to vectors, then $E_{K,k}(m):=m\cdot K+f(G(k))$.

This scheme is deterministic, that is given the same keys and the same message, it will always return the same encryption and thus cannot be CPA-secure.

However, we can easily modify the above scheme to make it CPA-secure. Let $G,K,f$ be as above and let $k\in\{0,1\}^r$. Define $E_{K,k}':=n\stackrel{\$}{\gets}\{0,1\}^l;n\parallel m\cdot K+f(G(k\parallel n))$, where $\stackrel{\$}{\gets}$ means that $n$ is sampled uniformly at random from $\{0,1\}^l$.

Essentially for every encryption we generate a nonce $n$, append it to the ciphertext and then use combination of the nonce and the key to generate the random bitstream. This is how stream ciphers work, but we are using vector-addition instead of XOR. Actually one could make appropriate choices for $f,K$ to turn this into a classic stream cipher by picking $K=\mathbb F_2$ and $f$ mapping bitstrings to vectors of the same strings. The bijectivity of $f$ is needed to preserve the uniformly random distribution of the output elements to make it an appropriate "pad". As for why $K$ is there, I don't know, it doesn't serve any purpose for the security in this scheme.


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.