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?


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$ – Alexey Ustinov Feb 15 '18 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, privacy policy and cookie policy

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