You are looking at a specific version 20160914:115346 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. CANS 2016 (to appear)
Keywords
homomorphic encryption scheme
Contact author(s)
gavin @ univ-lyon1 fr
History
2016-09-14: received
Short URL
https://ia.cr/2016/897
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.