Cryptology ePrint Archive: Report 2018/626

Efficient Evaluation of Low Degree Multivariate Polynomials in Ring-LWE Homomorphic Encryption Schemes

Sergiu Carpov and Oana Stan

Abstract: Homomorphic encryption schemes allow to perform computations over encrypted data. In schemes based on RLWE assumption the plaintext data is a ring polynomial. In many use cases of homomorphic encryption only the degree-0 coefficient of this polynomial is used to encrypt data. In this context any computation on encrypted data can be performed. It is trickier to perform generic computations when more than one coefficient per ciphertext is used.

In this paper we introduce a method to efficiently evaluate low-degree multivariate polynomials over encrypted data. The main idea is to encode several messages in the coefficients of a plaintext space polynomial. Using ring homomorphism operations and multiplications between ciphertexts, we compute multivariate monomials up to a given degree. Afterwards, using ciphertext additions we evaluate the input multivariate polynomial. We perform extensive experimentations of the proposed evaluation method. As example, evaluating an arbitrary multivariate degree-3 polynomial with 100 variables over Boolean space takes under 13 seconds.

Category / Keywords: implementation / homomorphic encryption, efficient polynomial evaluation, ring lwe

Date: received 22 Jun 2018

Contact author: sergiu carpov at cea fr

Available format(s): PDF | BibTeX Citation

Version: 20180626:145446 (All versions of this report)

Short URL: ia.cr/2018/626


[ Cryptology ePrint archive ]