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?


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

  • 1
    $\begingroup$ 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"). $\endgroup$
    – lamba
    Sep 5 at 15:37
  • $\begingroup$ Thanks for both of your explanations. It works in this way. $\endgroup$
    – alexander
    Sep 6 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.