LPN Encryption Homomorphism

Question

Trying to understand the LPN encryption in this paper: https://eprint.iacr.org/2021/120.pdf. From Definitions 4 and 5, ciphertext is $c=C\cdot s\oplus e\oplus G\cdot m$ and the paper says the LPN encryption scheme is both message homomorphic and key homomorphic, where $s$ is the secret key, $C$ and $G$ are two matrices.

But, I did not understand why it is homomorphic.

Suppose two ciphertexts with same secret key $s$: $c_1=C\cdot s\oplus e_1\oplus G\cdot m_1$ and $c_2=C\cdot s\oplus e_2\oplus G\cdot m_2$. XOR of these two ciphertext gives $c_1\oplus c_2=e_1\oplus e_2\oplus G\cdot (m_1\oplus m_2)$. This is not an encryption of $m_1\oplus m_2$. Also, $e_1\oplus e_2$ cannot guarantee correct decryption, isn't it?

Answer 1

$C$ is not a fixed matrix, it is the encryption randomness (given in the ciphertext). Hence, two ciphertexts with the same secret key $s$ will have different matrices $C$:

$c_1 = (C_1, C_1\cdot s \oplus e_1 \oplus G\cdot m_1)$

$c_2 = (C_2, C_2\cdot s \oplus e_2 \oplus G\cdot m_2)$

Then if you XOR them,

$c_1 \oplus c_2 = (C_1\oplus C_2, (C_1\oplus C_2)\cdot s \oplus (e_1 \oplus e_2) \oplus G\cdot (m_1\oplus m_2))$,

which is indeed a valid encryption of $m_1 \oplus m_2$, except that the noise rate is twice higher. For an appropriate choice of parameters, you can find an efficiently decodable code $G$ which can correct up to $\mathsf{HW}(e_1\oplus e_2)$ errors, yet have LPN security using noise of weight $\mathsf{HW}(e_1)$.

Keep in mind, though, that this is a very limited form of additive homomorphism: the ciphertext cannot be rerandomized, and the noise accumulates very fast if you do more operations (the noise weight grows linearly). You can only add a few ciphertexts before making decryption impossible.