A Somewhat Homomorphic Encryption Scheme based on Multivariate Polynomial Evaluation
This work addresses the need for secure homomorphic encryption schemes, which is crucial for privacy-preserving computations in fields like cloud computing and data analysis, though it appears incremental as it builds on existing concepts like Learning with Errors.
The authors tackled the problem of constructing a symmetric key homomorphic encryption scheme by proposing one based on multivariate polynomial evaluation over finite fields, which supports addition and multiplication operations, and they reduced its semantic security to the hardness of a new generalization of the Learning with Errors problem called the Hidden Subspace Membership problem.
We propose a symmetric key homomorphic encryption scheme based on the evaluation of multivariate polynomials over a finite field. The proposed scheme is somewhat homomorphic with respect to addition and multiplication. Further, we define a generalization of the Learning with Errors problem called the Hidden Subspace Membership problem and show that the semantic security of the proposed scheme can be reduced to the hardness of this problem.