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?


2 Answers 2


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.

  • $\begingroup$ Thanks! At least it will work as instructional counterexample. $\endgroup$ Commented Feb 15, 2018 at 0:24

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


Your Answer

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

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