Cryptology ePrint Archive: Report 2018/117

An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

Shai Halevi and Yuriy Polyakov and Victor Shoup

Abstract: We present an optimized implementation of the Fan-Vercauteren variant of the scale-invariant homomorphic encryption scheme of Brakerski. 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 they do not introduce any additional noise. We implement our optimizations in the PALISADE library and evaluate the runtime performance for the range of multiplicative depths from 1 to 50. Our results show that the homomorphic multiplication for the depth-20 setting can be executed in 63 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.

Category / Keywords: implementation / implementation, lattice techniques, public-key cryptography, quantum cryptography, homomorphic encryption, Residue Number System

Date: received 31 Jan 2018, last revised 31 Jan 2018

Contact author: polyakov at njit edu

Available format(s): PDF | BibTeX Citation

Version: 20180131:202555 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]