Paper 2018/117

An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

Shai Halevi, Yuriy Polyakov, and Victor Shoup

Abstract

We present an optimized implementation of the Fan-Vercauteren variant of Brakerski's scale-invariant homomorphic encryption scheme. Our algorithmic improvements focus on optimizing decryption and homomorphic multiplication in the Residue Number System (RNS), using the Chinese Remainder Theorem (CRT) to represent and manipulate the large coefficients in the ciphertext polynomials. In particular, we propose efficient procedures for scaling and CRT basis extension that do not require translating the numbers to standard (positional) representation. Compared to the previously proposed RNS design due to Bajard et al., our procedures are simpler and faster, and introduce a lower amount of noise. We implement our optimizations in the PALISADE library and evaluate the runtime performance for the range of multiplicative depths from 1 to 100. For example, homomorphic multiplication for a depth-20 setting can be executed in 62 ms on a modern server system, which is already practical for some outsourced-computing applications. Our algorithmic improvements can also be applied to other scale-invariant homomorphic encryption schemes, such as YASHE.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Major revision. CT-RSA 2019
DOI
10.1007/978-3-030-12612-4_5
Keywords
implementationlattice techniquespublic-key cryptographyquantum cryptographyhomomorphic encryptionResidue Number System
Contact author(s)
polyakov @ njit edu
History
2019-03-06: last of 4 revisions
2018-01-31: received
See all versions
Short URL
https://ia.cr/2018/117
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/117,
      author = {Shai Halevi and Yuriy Polyakov and Victor Shoup},
      title = {An Improved RNS Variant of the BFV Homomorphic Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2018/117},
      year = {2018},
      doi = {10.1007/978-3-030-12612-4_5},
      note = {\url{https://eprint.iacr.org/2018/117}},
      url = {https://eprint.iacr.org/2018/117}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.