# Example of partial homomorphic encryption over $\mathbb{F}_{2^k}$?

I'm looking for a partial additive homomorphic encryption over $\mathbb{F}_{2^k}$.

I know that, I can take an additive homomorphic encryption over $\mathbb{F}_2$ and just concatenate each bit that we encrypted. (as suggested at :Additive homomorphic encryption over small fields)

But it seems very inefficiently, when $k$ is not a constant.

All the other encryption schemes that I saw work over $Z_{pq}^*$ and some variants.

Thanks.

I think you are making a classical mistake: $\mathbb{Z}_{2^k}$ is not $\mathbb{F}_{2^k}$. Concatenating $k$ ciphertexts homomorphic over $\mathbb{Z}_{2}$ gives an encryption scheme homomorphic over $\mathbb{Z}_{2}^k \approx \mathbb{F}_{2^k}$, but this is not $\mathbb{Z}_{2^k}$ - intuitively, $\mathbb{Z}_{a} \times \mathbb{Z}_{b} \approx \mathbb{Z}_{ab}$ only when $a$ and $b$ are coprime.

So, if what you want is really an additively homomorphic encryption scheme over $\mathbb{Z}_{2^k}$, there is one: this paper describes an extension of the Goldwasser-Micali encryption scheme which does exactly this.

If, however, you need an encryption scheme over $\mathbb{F}_{2^k}$, then there is not really any alternatives to concatenating encryptions over $\mathbb{Z}_{2}$, except using an appropriate scheme based on LWE - but I'm not sure whether this would improve a lot over the "naive" solution, I do not have a good knowledge of lattice-based cryptography.

• You are right, I have just did that classical mistake :(. Thanks for the first citation and the mention for the LWE encryption , but unfortunately I'm looking forward the scheme over $F_{2^k}$, So I will change the question respectably. Mar 19, 2017 at 22:48
• One more related question over the concatenating encryptions in $F_{2^k}$. In a setting of two players: suppose that Player 1 wants to compute f(ab), where he holds $f(a)$ and $f(b);a,b∈F_{2^k}$. Player 1 doesn't have the private key. But he can use the help of Player 2 who posses the private key and also he Player 1 needs to prevent from Player 2 to know the values aa nor bb. Is it possible to implement this scheme with your suggestion? Thanks Jun 5, 2017 at 18:42