I am aware of Goldwasser-Micali cryptosystem, which is additively homomorphic over $\Bbb Z_2$. Are there other schemes that satisfy this property?

Note: If one is willing to involve advanced tools like lattices one could get something stronger like FHE. I am looking for a simple cryptosystem not involving lattices or similar tools.

  • 1
    $\begingroup$ I think DGHV scheme fit into this. See this eprint.iacr.org/2009/616.pdf $\endgroup$
    – vivek
    Jul 16, 2018 at 4:07
  • $\begingroup$ @vivek Thanks a lot, I'll take a look at it. However, at first glance it seems this is not exactly what I'm looking for since it still uses sort of advanced tools like adding noise and so on, and also it's not clear to me that it works for $\Bbb Z_2$ only. $\endgroup$
    – Daniel
    Jul 16, 2018 at 6:17
  • $\begingroup$ Then RSA and Paillier schemes are also shows homomorphism. RSA being multiplicative homomorphic and paillier scheme is additive homomorphic. you can check the wiki pages of these schemes. $\endgroup$
    – vivek
    Jul 16, 2018 at 11:03
  • $\begingroup$ @vivek Thanks, but I'm explicitly looking for additively homomorphic schemes over $\Bbb Z_2$. The schemes you mentioned do not satisfy this. $\endgroup$
    – Daniel
    Jul 16, 2018 at 13:57

2 Answers 2


Any additively homomorphic encryption scheme (with a large enough message space), e.g. Paillier. To do so, let the message space of the homomorphic encryption scheme be $\mathcal{M}$, you encode your message space $Z_2$ as follows:

  • choose an even number from $\mathcal{M}$ to represent 0, and an odd number to represent 1. One obvious choice would be simply 0 and 1. Let's call the two $m_0$ $m_1$ respectively

To encrypt, you encrypt $m_0$ or $m_1$ (all other messages are not allowed) using the homomorphic encryption scheme as usual.

To do homomorphic operations, you do the homomorphic operations as usual.

To decrypt, you decrypt as usual, then take mod 2 on the result to get your final result.

Here the parity of the values encodes messages in $Z_2$: even corresponding to 0, and odd corresponding to 1. We know

  • odd+odd $\rightarrow$ even (1+1=0 mod 2)
  • odd+even $\rightarrow$ odd (1+0=1 mod 2)
  • even+even $\rightarrow$ even (0+0=0 mod 2)
  • even+odd $\rightarrow$ odd (0+1=1 mod 2)

Thus it is correct.

The message space needs to be large enough so you can do enough number of addition operations without overflow (0 and 1 is actually the best choice to maximize the number of operations you can do).

  • $\begingroup$ Thanks for the answer, but I don't think this is a good solution since the proposed scheme lacks of circuit privacy, i.e. ciphertexts generated via homomorphic operations are clearly distinguishable from "fresh" ciphertexts $\endgroup$
    – Daniel
    Jul 20, 2018 at 0:11
  • $\begingroup$ If circuit privacy is a concern, you can add a large enough even number to the homomorphic evaluated result after you evaluated the circuit. $\endgroup$ Jul 20, 2018 at 7:27
  • $\begingroup$ This works if the message space has even order. If the order is odd, you have to be careful not overflowing, which could be tricky. $\endgroup$ Aug 9, 2018 at 9:39

Let me add to @vivek's comment. Fully homomorphic encryption (based on lattices) is surely one of the solutions.

It is a very advanced tool, yet could be super simple and not slow.

In current FHE, a ciphertext has many slots. Each slot is independent.

If you use a lot of slots, each slot is in $\mathbb{Z}_2$, then you have a ciphertext that contains several $\mathbb{Z}_2$ additively homomorphic (i.e., XOR homomorphic) slots.

It would be useful if you are going to encrypt a lot of bits, each in an independent $\mathbb{Z}_2$ field.

By choosing proper noise level (which can be small since addition does not dramatically increase the noise), it might be sufficient in your use case.

  • $\begingroup$ Can you give a reference please to a simple FHE scheme that has this "vectorization" property you mentioned? $\endgroup$
    – Daniel
    Jul 20, 2018 at 0:09
  • $\begingroup$ Please compile shaih/Helib on GitHub (github.com/shaih/HElib). By default, the test program compiled from src/Test_General.cpp exactly implements what I said. $\endgroup$ Jul 20, 2018 at 1:42
  • $\begingroup$ The main difference in your case is that you don't use the multiplications. So, if you can estimate the number of additions that you will need, this is an okay solution. $\endgroup$ Jul 20, 2018 at 1:44
  • $\begingroup$ Note: if in your use case, the potential additions needed are unbounded, then this construction may not be satisfactory. $\endgroup$ Jul 20, 2018 at 1:45

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.