Paper 2024/021

Designing homomorphic encryptions with rational functions

Abstract

New ideas to build homomorphic encryption schemes based on rational functions have been recently proposed. The starting point is a private-key encryption scheme whose secret key is a rational function $\phi/\phi'$. By construction, such a scheme is not homomorphic. To get homomorphic properties, nonlinear homomorphic operators are derived from the secret key. In this paper, we adopt the same approach to build HE. We obtain a multivariate encryption scheme in the sense that the knowledge of the CPA attacker can be turned into an over-defined system of nonlinear equations (contrarily to LWE-based encryptions). The factoring assumption is introduced in order to make a large class of algebraic attacks (based on Groebner bases) irrelevant. We extensively analyze the security of our scheme against algebraic attacks. In particular, we exhibit the fundamental role played by symmetry in these attacks. We also formally show that some of these attacks are exponential-time. While we did not propose a formal security proof relying on a classical cryptographic assumption, we hopefully provide convincing evidence for security.