Algorithmic Acceleration of B/FV-like Somewhat Homomorphic Encryption for Compute-Enabled RAM

Jonathan Takeshita; Dayane Reis; Ting Gong; Michael Niemier; X.  Sharon Hu; Taeho Jung

Paper 2020/1223

Algorithmic Acceleration of B/FV-like Somewhat Homomorphic Encryption for Compute-Enabled RAM

Jonathan Takeshita, Dayane Reis, Ting Gong, Michael Niemier, X. Sharon Hu, and Taeho Jung

Abstract

Somewhat Homomorphic Encryption (SHE) allows arbitrary computation with nite multiplicative depths to be performed on encrypted data, but its overhead is high due to memory transfer incurred by large ciphertexts. Recent research has recognized the shortcomings of general-purpose computing for high-performance SHE, and has begun to pioneer the use of hardware-based SHE acceleration with hardware including FPGAs, GPUs, and Compute-Enabled RAM (CE-RAM). CERAM is well-suited for SHE, as it is not limited by the separation between memory and processing that bottlenecks other hardware. Further, CE-RAM does not move data between dierent processing elements. Recent research has shown the high eectiveness of CE-RAM for SHE as compared to highly-optimized CPU and FPGA implementations. However, algorithmic optimization for the implementation on CE-RAM is underexplored. In this work, we examine the eect of existing algorithmic optimizations upon a CE-RAM implementation of the B/FV scheme, and further introduce novel optimization techniques for the Full RNS Variant of B/FV. Our experiments show speedups of up to 784x for homomorphic multiplication, 143x for decryption, and 330x for encryption against a CPU implementation. We also compare our approach to similar work in CE-RAM, FPGA, and GPU acceleration, and note general improvement over existing work. In particular, for homomorphic multiplication we see speedups of 506.5x against CE-RAM, 66.85x against FPGA, and 30.8x against GPU as compared to existing work in hardware acceleration of B/FV.

Note: Corrected typos in Algorithms 5 and 6.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Minor revision. Selected Areas in Cryptography (SAC) 2020
Keywords: Somewhat Homomorphic Encryption B FV scheme Full RNS Variant Compute-Enabled RAM
Contact author(s): tjung @ nd edu
jtakeshi @ nd edu
History: 2021-05-17: last of 2 revisions; 2020-10-06: received; See all versions
Short URL: https://ia.cr/2020/1223
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1223,
      author = {Jonathan Takeshita and Dayane Reis and Ting Gong and Michael Niemier and X.  Sharon Hu and Taeho Jung},
      title = {Algorithmic Acceleration of B/{FV}-like Somewhat Homomorphic Encryption for Compute-Enabled {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1223},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1223}
}