Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data
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...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10400455/ |
| _version_ | 1827374227219546112 |
|---|---|
| author | Wenqing Song Sirui Shen Congwei Xu Yilin Wang Xinyu Wang Yuxiang Fu Li Li Zhonghai Lu |
| author_facet | Wenqing Song Sirui Shen Congwei Xu Yilin Wang Xinyu Wang Yuxiang Fu Li Li Zhonghai Lu |
| author_sort | Wenqing Song |
| collection | DOAJ |
| description | 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: <inline-formula> <tex-math notation="LaTeX">$1)\,\,2.04\times $ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$3.33\times $ </tex-math></inline-formula> reduction in the area-time product (ATP) for the key sub-operation NTT, <inline-formula> <tex-math notation="LaTeX">$2)\,\,1.08\times $ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$7.42\times $ </tex-math></inline-formula> 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. |
| first_indexed | 2024-03-08T11:30:53Z |
| format | Article |
| id | doaj.art-3c7a270c0d8e492cbb56e98fa3e543c0 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-08T11:30:53Z |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-3c7a270c0d8e492cbb56e98fa3e543c02024-01-26T00:01:32ZengIEEEIEEE Access2169-35362024-01-0112118501186410.1109/ACCESS.2024.335427510400455Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted DataWenqing Song0https://orcid.org/0000-0002-8806-8717Sirui Shen1Congwei Xu2Yilin Wang3Xinyu Wang4Yuxiang Fu5https://orcid.org/0000-0003-1351-5460Li Li6https://orcid.org/0000-0002-1047-6067Zhonghai Lu7https://orcid.org/0000-0003-0061-3475School of Electronic Science and Engineering, Nanjing University, Nanjing, ChinaCentrum Wiskunde & Informatica (CWI Amsterdam), Amsterdam, The NetherlandsSchool of Electronic Science and Engineering, Nanjing University, Nanjing, ChinaSchool of Electronic Science and Engineering, Nanjing University, Nanjing, ChinaSchool of Electronic Science and Engineering, Nanjing University, Nanjing, ChinaSchool of Integrated Circuit, Nanjing University, Nanjing, ChinaSchool of Electronic Science and Engineering, Nanjing University, Nanjing, ChinaSchool of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Kista, Stockholm, SwedenHomomorphic 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: <inline-formula> <tex-math notation="LaTeX">$1)\,\,2.04\times $ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$3.33\times $ </tex-math></inline-formula> reduction in the area-time product (ATP) for the key sub-operation NTT, <inline-formula> <tex-math notation="LaTeX">$2)\,\,1.08\times $ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$7.42\times $ </tex-math></inline-formula> 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.https://ieeexplore.ieee.org/document/10400455/BFVhardware accelerationhomomorphic encryptionnumber theoretic transform |
| spellingShingle | Wenqing Song Sirui Shen Congwei Xu Yilin Wang Xinyu Wang Yuxiang Fu Li Li Zhonghai Lu Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data IEEE Access BFV hardware acceleration homomorphic encryption number theoretic transform |
| title | Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data |
| title_full | Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data |
| title_fullStr | Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data |
| title_full_unstemmed | Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data |
| title_short | Heterogeneous Reconfigurable Accelerator for Homomorphic Evaluation on Encrypted Data |
| title_sort | heterogeneous reconfigurable accelerator for homomorphic evaluation on encrypted data |
| topic | BFV hardware acceleration homomorphic encryption number theoretic transform |
| url | https://ieeexplore.ieee.org/document/10400455/ |
| work_keys_str_mv | AT wenqingsong heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata AT siruishen heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata AT congweixu heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata AT yilinwang heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata AT xinyuwang heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata AT yuxiangfu heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata AT lili heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata AT zhonghailu heterogeneousreconfigurableacceleratorforhomomorphicevaluationonencrypteddata |