An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

Shai Halevi, Yuriy Polyakov, Victor Shoup

Research output: Chapter in Book/Report/Conference proceedingConference contribution

92 Scopus citations


We present an optimized variant of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme and its efficient implementation in PALISADE. 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. These improvements are based on our original general-purpose techniques for CRT basis extension and scaling that can be applied to many other lattice-based cryptographic primitives. Our variant is simpler and significantly more efficient than the RNS variant proposed by Bajard et al. both in terms of noise growth and the computational complexity of the underlying CRT basis extension and scaling procedures.

Original languageEnglish (US)
Title of host publicationTopics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings
EditorsMitsuru Matsui
PublisherSpringer Verlag
Number of pages23
ISBN (Print)9783030126117
StatePublished - 2019
EventCryptographers Track at the RSA Conference 2019, CT-RSA 2019 - San Francisco, United States
Duration: Mar 4 2019Mar 8 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11405 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceCryptographers Track at the RSA Conference 2019, CT-RSA 2019
Country/TerritoryUnited States
CitySan Francisco

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Homomorphic encryption
  • Lattice-based cryptography
  • Post-quantum cryptography
  • Residue number systems
  • Software implementation


Dive into the research topics of 'An Improved RNS Variant of the BFV Homomorphic Encryption Scheme'. Together they form a unique fingerprint.

Cite this