Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data
Open Access
- 15 January 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 12, 11850-11864
Abstract
Homomorphic encryption (HE) enables third-party servers to perform computations on encrypted user data while preserving privacy. Although conceptually attractive, the speed of software implementations of HE is almost impractical. To address this challenge, various domain-specific architectures have been proposed to accelerate homomorphic evaluation, but efficiency remains a bottleneck. In this paper, we propose a homomorphic evaluation accelerator with heterogeneous reconfigurable modular computing units (RCUs) for the Brakerski/Fan-Vercauteren (BFV) scheme. RCUs leverage operator abstraction to efficiently perform basic sub-operations of homomorphic evaluation such as residue number system (RNS) conversion, number theoretic transform (NTT), and other modular computations. By combining these sub-operations, complex homomorphic evaluation operations like multiplication, rotation, and addition are efficiently executed. To address the high demand for data access and improve memory efficiency, we design a coordinate-based address encoding strategy that enables in-place and conflict-free data access. Furthermore, specific optimizations are performed on the core sub-operations such as NTT and automorphism. The proposed architecture is implemented on Xilinx Virtex-7 and UltraScale+ FPGA platforms and evaluated for polynomials of length 4096. Compared to state-of-the-art accelerators with the same parameter set, our accelerator achieves the following advantages: $1)\,\,2.04\times $ to $3.33\times $ reduction in the area-time product (ATP) for the key sub-operation NTT, $2)\,\,1.08\times $ to $7.42\times $ reduction in latency for homomorphic multiplication with higher area efficiency, and 3) support for a wider range of homomorphic evaluation operations, including rotation, compared to other BFV-based accelerators.
Keywords
Funding Information
- Joint Funds of the National Natural Science Foundation of China (U21B2032)
- National Natural Science Foundation of China (62104098)
- Natural Science Foundation of Jiangsu Province for Youth (BK20210178)
- National Key Research and Development Program of China (2021YFB3600104)
This publication has 42 references indexed in Scilit:
- High-Performance Ideal Lattice-Based Cryptography on 8-Bit ATxmega Microcontrollers2015
- (Leveled) Fully Homomorphic Encryption without BootstrappingACM Transactions on Computation Theory, 2014
- Compact Ring-LWE Cryptoprocessor2014
- Fully Homomorphic Encryption with Polylog Overhead2012
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP2012
- On Ideal Lattices and Learning with Errors over Rings2010
- Fully homomorphic encryption using ideal lattices2009
- Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor2000
- The Fast Fourier Transform in a Finite FieldMathematics of Computation, 1971
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965