# LPN Encryption Homomorphism

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?

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

• Just to add to this answer, the way the referenced paper (eprint.iacr.org/2021/120.pdf) uses the LPN homomorphism is to fix the $C$ for every garbled gate and row but use different keys so that the encryption scheme becomes key and message homomorphic (see Equation 8 under Section 5.1, $C$ is derived from "nonce"). Sep 5 at 15:37
• Thanks for both of your explanations. It works in this way. Sep 6 at 1:57