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 '18 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 '18 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 '18 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 '18 at 13:57

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

| improve this answer | |
  • $\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 '18 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$ – Changyu Dong Jul 20 '18 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$ – Florian Bourse Aug 9 '18 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.

| improve this answer | |
  • $\begingroup$ Can you give a reference please to a simple FHE scheme that has this "vectorization" property you mentioned? $\endgroup$ – Daniel Jul 20 '18 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$ – Weikeng Chen Jul 20 '18 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$ – Weikeng Chen Jul 20 '18 at 1:44
  • $\begingroup$ Note: if in your use case, the potential additions needed are unbounded, then this construction may not be satisfactory. $\endgroup$ – Weikeng Chen Jul 20 '18 at 1:45

Your Answer

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

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