Cryptology ePrint Archive: Report 2016/897

An efficient somewhat homomorphic encryption scheme based on factorization

Gérald Gavin

Abstract: Surprisingly, most of existing provably secure FHE or SWHE schemes are lattice-based constructions. It is legitimate to question whether there is a mysterious link between homomorphic encryptions and lattices. This paper can be seen as a first (partial) negative answer to this question. We propose a very simple private-key (partially) homomorphic encryption scheme whose security relies on factorization. This encryption scheme deals with a secret multivariate rational function $\phi_D$ defined over $\mathbb{Z}_n$, $n$ being an RSA-modulus. An encryption of $x$ is simply a vector $c$ such that $\phi_D(c)=x+\textsf{noise}$. To get homomorphic properties, nonlinear operators are specifically developed. We first prove IND-CPA security in the generic ring model assuming the hardness of factoring. We then extend this model in order to integrate lattice-based cryptanalysis and we reduce the security of our scheme (in this extended model) to an algebraic condition. This condition is extensively discussed for several choices of parameters. Some of these choices lead to competitive performance with respect to other existing homomorphic encryptions. While quantum computers are not only dreams anymore, designing factorization-based cryptographic schemes might appear as irrelevant. But, it is important to notice that, in our scheme, the factorization of $n$ is not required to decrypt. The factoring assumption simply ensures that solving nonlinear equations or finding non-null polynomials with many roots is difficult. Consequently, the ideas behind our construction could be re-used in rings satisfying these properties.

Category / Keywords: public-key cryptography / homomorphic encryption scheme

Original Publication (with major differences): CANS 2016 (to appear)

Date: received 14 Sep 2016, last revised 14 Sep 2016

Contact author: gavin at univ-lyon1 fr

Available format(s): PDF | BibTeX Citation

Version: 20160914:115346 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]