Paper 2020/091

Enabling Faster Operations for Deeper Circuits in Full RNS Variants of FV-like Somewhat Homomorphic Encryption

Jonathan Takeshita, Matthew Schoenbauer, Ryan Karl, and Taeho Jung


Though Fully Homomorphic Encryption (FHE) has been realized, most practical implementations utilize leveled Somewhat Homomorphic Encryption (SHE) schemes, which have limits on the multiplicative depth of the circuits they can evaluate and avoid computationally intensive bootstrapping. Many SHE schemes exist, among which those based on Ring Learning With Error (RLWE) with operations on large polynomial rings are popular. Of these, variants allowing operations to occur fully in Residue Number Systems (RNS) have been constructed. This optimization allows homomorphic operations directly on RNS components without needing to reconstruct numbers from their RNS representation, making SHE implementations faster and highly parallel. In this paper, we present a set of optimizations to a popular RNS variant of the B/FV encryption scheme that allow for the use of significantly larger ciphertext moduli (e.g., thousands of bits) without increased overhead due to excessive numbers of RNS components or computational overhead, as well as computational optimizations. This allows for the use of larger ciphertext moduli, which leads to a higher multiplicative depth with the same computational overhead. Our experiments show that our optimizations yield runtime improvements of up to 4.48 for decryption and 14.68 for homomorphic multiplication for large ciphertext moduli.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Fully Homomorphic EncryptionBFV SchemeRNS VariantPerformance Optimization
Contact author(s)
jtakeshi @ nd edu
mschoenb @ nd edu
rkarl @ nd edu
tjung @ nd edu
2020-02-04: received
Short URL
Creative Commons Attribution


      author = {Jonathan Takeshita and Matthew Schoenbauer and Ryan Karl and Taeho Jung},
      title = {Enabling Faster Operations for Deeper Circuits in Full {RNS} Variants of {FV}-like Somewhat Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/091},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.