# Semantic security IND-CPA of Affine Hill Cipher

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 multiply with inverse of K. For decryption, the key for the PRNG (LFSR based) can be used.

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

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

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))$.
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.