Fully homomorphic encryption with polynomials

Question

I have read some texts concerning fully homomorphic encryption but didn't find the following simple idea.

Let $p$ be a prime. We choose secret key $x_0$ in the interval $1\le x_0<p$. Let $\mathrm{Enc}(m)$ be a polynomial $P(x)=a_{p-2}x^{p-2}+\ldots+a_1x+a_0$ with random $a_{p-2},\ldots,a_1$ and $a_0$ such that $P(x_0)=m$; $\mathrm{Dec}(P):=P(x_0)$ (everything is modulo $p$). This construction gives FHE because $(P_1P_2)(x_0)=P_1(x_0)P_2(x_0) \bmod(x^{p-1}-1)$ and $(P_1+P_2)(x_0)=P_1(x_0)+P_2(x_0).$

Is this idea reasonable or I missed some pitfalls?

Answer 1

I missed some pitfalls?

The most obvious one is that the secret key $x_0$ is recoverable with a single known plaintext/ciphertext pair. That is, if we know both $m$ and $Enc(m) = a_{p-2}x^{p-2} +\ ... \ + a_1 x + a_0$, then we know that $x_0$ is a root of the polynomial $$a_{p-2}x^{p-2} +\ ...\ +\ a_1 x + (a_0 - m)$$ Roots of polynomials modulo $p$ can be efficiently recovered; this will give us the value $x_0$ (and possibly a few other false hits).

The other practical issue is that your ciphertexts consists of $p-1$ values; unless $p$ is tiny (e.g. no more than $2^{40}$), then you have impractically large ciphertexts.

Answer 2

This idea was considered in Combinatorial cryptosystems galore! by M. Fellows and N. Koblitz (1994).