4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user1387682
    Mar 19, 2017 at 22:48
  • $\begingroup$ 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 $\endgroup$
    – user1387682
    Jun 5, 2017 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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