MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption
Cloud computing has made it easier for individuals and companies to get access to large compute and memory resources. However, it has also raised privacy concerns about the data that users share with the remote cloud servers. Fully homomorphic encryption (FHE) offers a solution to this problem by en...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM|56th Annual IEEE/ACM International Symposium on Microarchitecture
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153275 |
| _version_ | 1826212456296349696 |
|---|---|
| author | Agrawal, Rashmi De Castro, Leo Juvekar, Chiraag Chandrakasan, Anantha Vaikuntanathan, Vinod Joshi, Ajay |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Agrawal, Rashmi De Castro, Leo Juvekar, Chiraag Chandrakasan, Anantha Vaikuntanathan, Vinod Joshi, Ajay |
| author_sort | Agrawal, Rashmi |
| collection | MIT |
| description | Cloud computing has made it easier for individuals and companies to get access to large compute and memory resources. However, it has also raised privacy concerns about the data that users share with the remote cloud servers. Fully homomorphic encryption (FHE) offers a solution to this problem by enabling computations over encrypted data. Unfortunately, all known constructions of FHE require a noise term for security, and this noise grows during computation. To perform unlimited computations on the encrypted data, we need to perform a periodic noise reduction step known as bootstrapping. This bootstrapping operation is memory-bound as it requires several GBs of data. This leads to orders of magnitude increase in the time required for operating on encrypted data as compared to unencrypted data.
In this work, we first present an in-depth analysis of the bootstrapping operation in the CKKS FHE scheme. Similar to other existing works, we observe that CKKS bootstrapping exhibits a low arithmetic intensity (< 1 Op/byte). We then propose memory-aware design (MAD) techniques to accelerate the bootstrapping operation of the CKKS FHE scheme. Our proposed MAD techniques are agnostic of the underlying compute platform and can be equally applied to GPUs, CPUs, FPGAs, and ASICs. Our MAD techniques make use of several caching optimizations that enable maximal data reuse and perform reordering of operations to reduce the amount of data that needs to be transferred to/from the main memory. In addition, our MAD techniques include several algorithmic optimizations that reduce the number of data access pattern switches and the expensive NTT operations. Applying our MAD optimizations for FHE improves bootstrapping arithmetic intensity by 3 ×. For Logistic Regression (LR) training, by leveraging our MAD optimizations, the existing GPU design can get up to 3.5 × improvement in performance for the same on-chip memory size. Similarly, the existing ASIC designs can get up to 27 × and 57 × improvement in performance for LR training and ResNet-20 inference, respectively, while reducing the on-chip memory requirement by 16 ×, which proportionally reduces the cost of the solution. |
| first_indexed | 2024-09-23T15:22:12Z |
| format | Article |
| id | mit-1721.1/153275 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:22:12Z |
| publishDate | 2024 |
| publisher | ACM|56th Annual IEEE/ACM International Symposium on Microarchitecture |
| record_format | dspace |
| spelling | mit-1721.1/1532752024-07-11T19:07:54Z MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption Agrawal, Rashmi De Castro, Leo Juvekar, Chiraag Chandrakasan, Anantha Vaikuntanathan, Vinod Joshi, Ajay Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cloud computing has made it easier for individuals and companies to get access to large compute and memory resources. However, it has also raised privacy concerns about the data that users share with the remote cloud servers. Fully homomorphic encryption (FHE) offers a solution to this problem by enabling computations over encrypted data. Unfortunately, all known constructions of FHE require a noise term for security, and this noise grows during computation. To perform unlimited computations on the encrypted data, we need to perform a periodic noise reduction step known as bootstrapping. This bootstrapping operation is memory-bound as it requires several GBs of data. This leads to orders of magnitude increase in the time required for operating on encrypted data as compared to unencrypted data. In this work, we first present an in-depth analysis of the bootstrapping operation in the CKKS FHE scheme. Similar to other existing works, we observe that CKKS bootstrapping exhibits a low arithmetic intensity (< 1 Op/byte). We then propose memory-aware design (MAD) techniques to accelerate the bootstrapping operation of the CKKS FHE scheme. Our proposed MAD techniques are agnostic of the underlying compute platform and can be equally applied to GPUs, CPUs, FPGAs, and ASICs. Our MAD techniques make use of several caching optimizations that enable maximal data reuse and perform reordering of operations to reduce the amount of data that needs to be transferred to/from the main memory. In addition, our MAD techniques include several algorithmic optimizations that reduce the number of data access pattern switches and the expensive NTT operations. Applying our MAD optimizations for FHE improves bootstrapping arithmetic intensity by 3 ×. For Logistic Regression (LR) training, by leveraging our MAD optimizations, the existing GPU design can get up to 3.5 × improvement in performance for the same on-chip memory size. Similarly, the existing ASIC designs can get up to 27 × and 57 × improvement in performance for LR training and ResNet-20 inference, respectively, while reducing the on-chip memory requirement by 16 ×, which proportionally reduces the cost of the solution. 2024-01-03T20:27:09Z 2024-01-03T20:27:09Z 2023-10-28 2024-01-01T08:47:40Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0329-4 https://hdl.handle.net/1721.1/153275 Agrawal, Rashmi, De Castro, Leo, Juvekar, Chiraag, Chandrakasan, Anantha, Vaikuntanathan, Vinod et al. 2023. "MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption." PUBLISHER_POLICY PUBLISHER_POLICY en https://doi.org/10.1145/3613424.3614302 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The author(s) application/pdf ACM|56th Annual IEEE/ACM International Symposium on Microarchitecture |
| spellingShingle | Agrawal, Rashmi De Castro, Leo Juvekar, Chiraag Chandrakasan, Anantha Vaikuntanathan, Vinod Joshi, Ajay MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption |
| title | MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption |
| title_full | MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption |
| title_fullStr | MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption |
| title_full_unstemmed | MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption |
| title_short | MAD: Memory-Aware Design Techniques for Accelerating Fully Homomorphic Encryption |
| title_sort | mad memory aware design techniques for accelerating fully homomorphic encryption |
| url | https://hdl.handle.net/1721.1/153275 |
| work_keys_str_mv | AT agrawalrashmi madmemoryawaredesigntechniquesforacceleratingfullyhomomorphicencryption AT decastroleo madmemoryawaredesigntechniquesforacceleratingfullyhomomorphicencryption AT juvekarchiraag madmemoryawaredesigntechniquesforacceleratingfullyhomomorphicencryption AT chandrakasananantha madmemoryawaredesigntechniquesforacceleratingfullyhomomorphicencryption AT vaikuntanathanvinod madmemoryawaredesigntechniquesforacceleratingfullyhomomorphicencryption AT joshiajay madmemoryawaredesigntechniquesforacceleratingfullyhomomorphicencryption |