As for the PQC algorithm Saber.PKE based on M-LWR, I wonder whether it supports homomorphic addition operation. According to my related work, the error of this algorithm can be written as $e_S = ||s^{\prime T}e-e^{\prime T}s +e_r||$, this fomula satisfies$e_S \mod p < p/4$. By parameters selecting, whether we could control the noise with the condition $e_S \ll p/4$, then we can use Saber.PKE for homomorphic addition operation.

After the research on Saber.PKE, although it supports additional homomorphic operations, there is only a support for addition modulo 2. In other words, below formula works: $D(E(m_1)+E(m_2)) = m_1 \oplus m_2, \forall \ m_1,m_2 \in \{0,1\}$. So the next question is can this algorithm used for integers homomorphic addition operation rather the XOR operation?


1 Answer 1


If you don't use the full/proper Saber.KEM, i.e., skip the FO transform step and use Saber.PKE directly, then you can get homomorphism.

Otherwise no. Saber.KEM is designed to be an IND-CCA2 scheme, which means the ciphertext is authenticated. Being authenticated means the ciphertext is not malleable, any attempt to change it to another ciphertext will cause the authentication procedure to fail. This is due to the Fujisaki-Okamono (FO) transform.

  • $\begingroup$ The question asks Saber.PKE, which is the building block used in companion with the FO transformation. It's homomorphic. I've edited the question to make this part clear hope you don't mind. $\endgroup$
    – DannyNiu
    Jul 4, 2022 at 2:59
  • $\begingroup$ Thank u so much, there is a need for the building block Saber.PKE in my project only, I would appreciate it if you could give more details in additional homomorphism in Saber.PKE, such as how to control the noise bound and how to realize the bit homomorphic addition. $\endgroup$
    – R YS
    Jul 4, 2022 at 5:47

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.