I'm curious on the following question: let $\mathbb{F}_{2^n}$ be a finite field which is an extension of $\mathbb{F}_2$ with order of $n$, is there an encoding scheme $e:=\mathbb{F}_{2^n}\rightarrow \mathcal{C}$ for some domain $\mathcal{C}$ and satisfies linear homomorphic, i.e. $$\forall x_1,x_2\in \mathbb{F}_{2^n}, e(c_1x_1+c_2x_2)=c_1e(x_1)+c_2e(x_2),$$where $c_1,c_2\in\mathbb{F}_{2^n}$ are some constants.

A naive idea is that we regard $s\in \mathbb{F}_{2^n}$ as a binary vector and encrypt the bits one by one, then we can do the arithmetic operation on $\mathbb{F}_{2^n}$ in the bit level over the cipher vector (which only require additive homomorphic over $\mathbb{F}_2$). However, this will have a huge cipher space i.e. $c*n$ where $c$ is the security parameter makes the bit level encryption secure.

My question is:

Can we do better than the naive approach above? Or, is there any existed results on this topic?

  • $\begingroup$ Is an encoding scheme the same thing of an encrypting scheme? $\endgroup$ – Hilder Vitor Lima Pereira Jun 16 '16 at 14:26
  • $\begingroup$ @Vitor Yes, it's an encryption scheme. $\endgroup$ – Paul Jun 16 '16 at 23:18
  • $\begingroup$ I may be missing something, but, since a field is commutative, $e(cx) = e(xc)$, and so, for the equality you put there, it would be equal to $xe(c)$ and that is exposing the plaintext. $\endgroup$ – Hilder Vitor Lima Pereira Jun 17 '16 at 1:54
  • $\begingroup$ @Vitor I edited the question to make it more clear, what I need is actually the additive and constant multiplicative homomorphic encryption over $\mathbb{F}_{2^n}$. $\endgroup$ – Paul Jun 17 '16 at 2:01
  • $\begingroup$ This does not work. Your cipher function is always a multiplication by a constant. To see this, set $x_2=0$ and $x_1=1$. Now the equation will be $e(c_1) = e(c_1 1) = c_1 e(1)$ for arbitrary $c_1$. $\endgroup$ – user27950 Jun 17 '16 at 4: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.