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

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
homomorphic encryptionefficient polynomial evaluationring lwe
Contact author(s)
sergiu carpov @ cea fr
History
2018-06-26: received
Short URL
https://ia.cr/2018/626
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/626,
      author = {Sergiu Carpov and Oana Stan},
      title = {Efficient Evaluation of Low Degree Multivariate Polynomials in Ring-LWE Homomorphic Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2018/626},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/626}},
      url = {https://eprint.iacr.org/2018/626}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.