I'm looking for an additive homomorphic encryption that the addition operator (+) in its plaintext space be the same as addition operator in its ciphertext space. (Schemes like Paillier do addition in plaintext space by multiplication in ciphertext space).

Does anybody know such a scheme?

  • $\begingroup$ exactly I mean: D(E(m1)+E(m2)) = m1 + m2 $\endgroup$ – user26343 Aug 25 '15 at 7:26
  • 2
    $\begingroup$ I think certain lattice based encryption schemes are additively homomorphic in this sense. This includes (but is not limited to) some of the suggestions for fully homomorphic encryption schemes, although those will probably be overkill if you are just looking for additive homomorphism. A cant think of any concrete schemes right now though. $\endgroup$ – Guut Boy Aug 25 '15 at 8:34
  • 1
    $\begingroup$ NTRU should to the job. $\endgroup$ – SEJPM Aug 25 '15 at 11:16
  • $\begingroup$ On the other hand, if you want $D\hspace{.03 in}(E(m_1)\hspace{-0.04 in}+\hspace{-0.04 in}E(m_2)\hspace{-0.04 in}+\hspace{-0.04 in}E(m_3)+...\hspace{-0.05 in}+E(m_{\hspace{.02 in}n-1})\hspace{-0.04 in}+\hspace{-0.04 in}E(m_{\hspace{.02 in}n})) \: = \: m_1\hspace{-0.06 in}+\hspace{-0.04 in}m_2\hspace{-0.04 in}+\hspace{-0.04 in}m_3+...\hspace{-0.04 in}+m_{\hspace{.02 in}n-1}\hspace{-0.05 in}+\hspace{-0.04 in}m_{\hspace{.02 in}n} \hspace{1.17 in}$ for all $n$, then things will probably be more difficult. $\;\;\;\;$ $\endgroup$ – user991 Aug 26 '15 at 0:33
  • $\begingroup$ From an asymptotic point of view I think the lattice schemes work for n = poly(k), for security parameter k. So, if you need more than that you are going super poly-time, and then you can just break the encryption and encrypt the result ... oh, the wonders of asymptotics. $\endgroup$ – Guut Boy Aug 26 '15 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.