Paper 2019/1375

New ideas to build noise-free homomorphic cryptosystems

Gérald Gavin and Sandrine Tainturier

Abstract

We design a very simple private-key encryption scheme whose decryption function is a rational function. This scheme is not born naturally homomorphic. To get homomorphic properties, a nonlinear additive homomorphic operator is specifically developed. The security analysis is based on symmetry considerations and we prove some formal results under the factoring assumption. In particular, we prove IND-CPA security in the generic ring model. Even if our security proof is not complete, we think that it is convincing and that the technical tools considered in this paper are interesting by themselves. Moreover, the factoring assumption is just needed to ensure 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. As motivating perspectives, we then propose to develop a simple multiplicative operator. To achieve this, randomness is added in our construction giving hope to remove the factoring assumption in order to get a pure multivariate encryption scheme.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Homomorphic cryptosystemMultivariate encryption schemeGeneric ring model
Contact author(s)
gerald gavin @ univ-lyon1 fr
History
2019-12-02: revised
2019-12-01: received
See all versions
Short URL
https://ia.cr/2019/1375
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1375,
      author = {Gérald Gavin and Sandrine Tainturier},
      title = {New ideas to build noise-free homomorphic cryptosystems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1375},
      year = {2019},
      url = {https://eprint.iacr.org/2019/1375}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.