Paper 2016/510

A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes

Jean-Claude Bajard, Julien Eynard, Anwar Hasan, and Vincent Zucca

Abstract

Since Gentry's breakthrough work in 2009, homomorphic cryptography has received a widespread attention. Implementation of a fully homomorphic cryptographic scheme is however still highly expensive. Somewhat Homomorphic Encryption (SHE) schemes, on the other hand, allow only a limited number of arithmetical operations in the encrypted domain, but are more practical. Many SHE schemes have been proposed, among which the most competitive ones rely on (Ring-) Learning With Error (RLWE) and operations occur on high-degree polynomials with large coefficients. This work focuses in particular on the Chinese Remainder Theorem representation (a.k.a. Residue Number Systems) applied to large coefficients. In SHE schemes like that of Fan and Vercauteren (FV), such a representation remains hardly compatible with procedures involving coefficient-wise division and rounding required in decryption and homomorphic multiplication. This paper suggests a way to entirely eliminate the need for multi-precision arithmetic, and presents techniques to enable a full RNS implementation of FV-like schemes. For dimensions between $2^{11}$ and $2^{15}$, we report speed-ups from $5\times$ to $20\times$ for decryption, and from $2\times$ to $4\times$ for multiplication.

Note: Extended version of published version.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Selected Areas in Cryptography (SAC 2016)
Keywords
Lattice-based CryptographyHomomorphic EncryptionFVResidue Number SystemsSoftware Implementation
Contact author(s)
eynard julien @ wanadoo fr
History
2016-11-22: revised
2016-05-25: received
See all versions
Short URL
https://ia.cr/2016/510
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/510,
      author = {Jean-Claude Bajard and Julien Eynard and Anwar Hasan and Vincent Zucca},
      title = {A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2016/510},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/510}},
      url = {https://eprint.iacr.org/2016/510}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.