[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3470496.3527393acmconferencesArticle/Chapter ViewAbstractPublication PagesiscaConference Proceedingsconference-collections
research-article
Open access

CraterLake: a hardware accelerator for efficient unbounded computation on encrypted data

Published: 11 June 2022 Publication History

Abstract

Fully Homomorphic Encryption (FHE) enables offloading computation to untrusted servers with cryptographic privacy. Despite its attractive security, FHE is not yet widely adopted due to its prohibitive overheads, about 10,000X over unencrypted computation. Recent FHE accelerators have made strides to bridge this performance gap. Unfortunately, prior accelerators only work well for simple programs, but become inefficient for complex programs, which bring additional costs and challenges.
We present CraterLake, the first FHE accelerator that enables FHE programs of unbounded size (i.e., unbounded multiplicative depth). Such computations require very large ciphertexts (tens of MBs each) and different algorithms that prior work does not support well. To tackle this challenge, CraterLake introduces a new hardware architecture that efficiently scales to very large cipher-texts, novel functional units to accelerate key kernels, and new algorithms and compiler techniques to reduce data movement.
We evaluate CraterLake on deep FHE programs, including deep neural networks like ResNet and LSTMs, where prior work takes minutes to hours per inference on a CPU. CraterLake outperforms a CPU by gmean 4,600X and the best prior FHE accelerator by 11.2X under similar area and power budgets. These speeds enable realtime performance on unbounded FHE programs for the first time.

References

[1]
2020. HEAAN software library. https://github.com/snucrypto/HEAAN.
[2]
2020. Lattigo. https://github.com/ldsec/lattigo.
[3]
Ahmad Qaisar Ahmad Al Badawi, Yuriy Polyakov, Khin Mi Mi Aung, Bharadwaj Veeravalli, and Kurt Rohloff. 2021. Implementation and performance evaluation of RNS variants of the BFV homomorphic encryption scheme. IEEE Transactions on Emerging Topics in Computing 9, 2 (2021).
[4]
Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. 2018. Homomorphic Encryption Security Standard. Technical Report. HomomorphicEncryption.org.
[5]
Martin R Albrecht, Benjamin R Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W Postlethwaite, Fernando Virdia, and Thomas Wunderer. 2018. Estimate all the {LWE, NTRU } schemes!. In Proceedings of the International Conference on Security and Cryptography for Networks (SCN).
[6]
Krste Asanovic. 1998. Vector Microprocessors. Ph.D. Dissertation. EECS Department, University of California, Berkeley.
[7]
Jean-Claude Bajard, Julien Eynard, M Anwar Hasan, and Vincent Zucca. 2016. A full RNS variant of FV-like somewhat homomorphic encryption schemes. In Proceedings of the International Conference on Selected Areas in Cryptography (SAC).
[8]
Laszlo A. Belady. 1966. A study of replacement algorithms for a virtual-storage computer. IBM Systems journal 5, 2 (1966).
[9]
Fabrice Benhamouda, Tancrede Lepoint, Claire Mathieu, and Hang Zhou. 2017. Optimization of bootstrapping in circuits. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).
[10]
Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche, Ronny Van Keer, and Benoît Viguier. 2018. KangarooTwelve: Fast hashing based on Keccak. In Proceedings of the 16th International Conference on Applied Cryptography and Network Security (ACNS).
[11]
Jean-Philippe Bossuat, Christian Mouchet, Juan Troncoso-Pastoriza, and Jean-Pierre Hubaux. 2021. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT).
[12]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT) 6, 3 (2014).
[13]
Alon Brutzkus, Ran Gilad-Bachrach, and Oren Elisha. 2019. Low latency privacy preserving inference. In Proceedings of the International Conference on Machine Learning (ICML).
[14]
Hao Chen, Ilaria Chillotti, and Yongsoo Song. 2019. Improved bootstrapping for approximate homomorphic encryption. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT).
[15]
Hao Chen, Kim Laine, and Peter Rindal. 2017. Fast Private Set Intersection from Homomorphic Encryption. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS).
[16]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic encryption for arithmetic of approximate numbers. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT).
[17]
Jack Choquette, Wishwesh Gandhi, Olivier Giroux, Nick Stam, and Ronny Krashinsky. 2021. NVIDIA A100 Tensor Core GPU: Performance and innovation. IEEE Micro 41, 2 (2021).
[18]
David Bruce Cousins, John Golusky, Kurt Rohloff, and Daniel Sumorok. 2014. An FPGA co-processor implementation of Homomorphic Encryption. In Proceedings of the IEEE Conference on High Performance Extreme Computing (HPEC).
[19]
David Bruce Cousins, Kurt Rohloff, Chris Peikert, and Rick Schantz. 2012. An update on SIPHER (Scalable Implementation of Primitives for Homomorphic EncRyption) - FPGA implementation using Simulink. In Proceedings of the IEEE Conference on High Performance Extreme Computing (HPEC).
[20]
D. B. Cousins, K. Rohloff, and D. Sumorok. 2017. Designing an FPGA-Accelerated Homomorphic Encryption Co-Processor. IEEE Transactions on Emerging Topics in Computing 5, 2 (2017).
[21]
Sal Dasgupta, Teja Singh, Ashish Jain, Samuel Naffziger, Deepesh John, Chetan Bisht, and Pradeep Jayaraman. 2020. Radeon RX 5700 Series: The AMD 7nm Energy-Efficient High-Performance GPUs. In Proceedings of the IEEE International Solid-State Circuits Conference (ISSCC).
[22]
Roshan Dathathri, Blagovesta Kostova, Olli Saarikivi, Wei Dai, Kim Laine, and Madan Musuvathi. 2020. EVA: An encrypted vector arithmetic language and compiler for efficient homomorphic computation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).
[23]
Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz. 2019. CHET: An optimizing compiler for fully-homomorphic neural-network inferencing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).
[24]
Yarkin Doröz, Erding Öztürk, and Berk Sunar. 2015. Accelerating fully homomorphic encryption in hardware. IEEE Trans. Comput. 64, 6 (2015).
[25]
Axel Feldmann, Nikola Samardzic, Aleksandar Krastev, Srini Devadas, Ron Dreslinski, Christopher Peikert, and Daniel Sanchez. 2021. F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption. In Proceedings of the 54th annual IEEE/ACM international symposium on Microarchitecture (MICRO-54).
[26]
Harvey L Garner. 1959. The residue number system. In Papers presented at the the March 3--5, 1959, Western Joint Computer Conference.
[27]
Craig Gentry and Shai Halevi. 2019. Compressible FHE with Applications to PIR. In Proceedings of the Theory of Cryptography Conference (TCC).
[28]
Craig Gentry, Shai Halevi, and Nigel P Smart. 2012. Homomorphic evaluation of the AES circuit. In Proceedings of the 32nd Annual Cryptology Conference (CRYPTO).
[29]
Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Proceedings of the 33rd Annual Cryptology Conference (CRYPTO).
[30]
Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2016. CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy. In Proceedings of the International Conference on Machine Learning (ICML).
[31]
Shai Halevi and Victor Shoup. 2018. Faster homomorphic linear transformations in HElib. In Proceedings of the 38th Annual International Cryptology Conference (CRYPTO).
[32]
Shai Halevi and Victor Shoup. 2020. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Report 2020/1481.
[33]
Shai Halevi and Victor Shoup. 2020. HElib design principles. Technical Report.
[34]
Shai Halevi and Victor Shoup. 2021. Bootstrapping for HElib. Journal of Cryptology 34, 1 (2021).
[35]
Kyoohyung Han, Seungwan Hong, Jung Hee Cheon, and Daejun Park. 2018. Efficient Logistic Regression on Large Encrypted Data. Cryptology ePrint Archive, Report 2018/662.
[36]
Kyoohyung Han, Seungwan Hong, Jung Hee Cheon, and Daejun Park. 2019. Logistic regression on homomorphic encrypted data at scale. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33.
[37]
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, Quoc V. Le, and Adam Hartwig. 2019. Searching for MobileNetV3. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV).
[38]
Qijing Huang, Aravind Kalaiah, Minwoo Kang, James Demmel, Grace Dinh, John Wawrzynek, Thomas Norell, and Yakun Sophia Shao. 2021. CoSA: Scheduling by constrained optimization for spatial accelerators. In Proceedings of the 48th annual International Symposium on Computer Architecture (ISCA-48).
[39]
Malika Izabachène, Renaud Sirdey, and Martin Zuber. 2019. Practical fully homomorphic encryption for fully masked neural networks. In Proceedings of the International Conference on Cryptology and Network Security (CANS).
[40]
Jyun-Neng Ji and Ming-Der Shieh. 2019. Efficient comparison and swap on fully homomorphic encrypted data. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS).
[41]
Norman P Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, et al. 2017. In-datacenter performance analysis of a tensor processing unit. In Proceedings of the 44th annual International Symposium on Computer Architecture (ISCA-44).
[42]
Wonkyung Jung, Sangpyo Kim, Jung Ho Ahn, Jung Hee Cheon, and Younho Lee. 2021. Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with GPUs. IACR Transactions on Cryptographic Hardware and Embedded Systems (CHES) (2021).
[43]
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. 2018. GAZELLE: A low latency framework for secure neural network inference. In Proceedings of the 27th USENIX Security Symposium (USENIX Security 18).
[44]
Miran Kim, Yongsoo Song, Baiyu Li, and Daniele Micciancio. 2020. Semi-parallel logistic regression for GWAS on encrypted data. BMC Medical Genomics 13, 7 (2020).
[45]
Alex Krizhevsky. 2009. Learning multiple layers of features from tiny images. Technical Report. University of Toronto.
[46]
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. 1998. Gradient-based learning applied to document recognition. Proc. IEEE 86, 11 (1998).
[47]
Junghyun Lee, Eunsang Lee, Joon-Woo Lee, Yongjune Kim, Young-Sik Kim, and Jong-Seon No. 2021. Precise approximation of convolutional neural networks for homomorphically encrypted data. arXiv preprint arXiv:2105.10879 (2021).
[48]
Joon-Woo Lee, HyungChul Kang, Yongwoo Lee, Woosuk Choi, Jieun Eom, Maxim Deryabin, Eunsang Lee, Junghyun Lee, Donghoon Yoo, Young-Sik Kim, et al. 2021. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. arXiv preprint arXiv:2106.07229 (2021).
[49]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On ideal lattices and learning with errors over rings. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT).
[50]
Ahmet Can Mert, Erdinç Öztürk, and Erkay Savaş. 2019. Design and implementation of encryption/decryption architectures for BFV homomorphic encryption scheme. IEEE Transactions on Very Large Scale Integration (VLSI) Systems (2019).
[51]
Vincent Migliore, Cédric Seguin, Maria Mendez Real, Vianney Lapotre, Arnaud Tisserand, Caroline Fontaine, Guy Gogniat, and Russell Tessier. 2017. A High-Speed Accelerator for Homomorphic Encryption using the Karatsuba Algorithm. ACM Transactiosn on Embedded Computer Systems (TECS) 16, 5s (2017).
[52]
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. 2020. Delphi: A cryptographic inference service for neural networks. In Proceedings of the 29th USENIX Security Symposium (USENIX Security 20).
[53]
Christian Mouchet, Jean-Philippe Bossuat, Juan Troncoso-Pastoriza, and J Hubaux. 2020. Lattigo: A multiparty homomorphic encryption library in Go. In 8th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC).
[54]
NVIDIA. 2021. NVIDIA DGX Station A100 system architecture. https://images.nvidia.com/aem-dam/Solutions/Data-Center/nvidia-dgx-station-a100-system-architecture-white-paper.pdf.
[55]
Angshuman Parashar, Priyanka Raina, Yakun Sophia Shao, Yu-Hsin Chen, Victor A Ying, Anurag Mukkara, Rangharajan Venkatesan, Brucek Khailany, Stephen W Keckler, and Joel Emer. 2019. Timeloop: A systematic approach to DNN accelerator evaluation. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS).
[56]
Michael Pellauer, Yakun Sophia Shao, Jason Clemons, Neal Crago, Kartik Hegde, Rangharajan Venkatesan, Stephen W Keckler, Christopher W Fletcher, and Joel Emer. 2019. Buffets: An efficient and composable storage idiom for explicit decoupled data orchestration. In Proceedings of the 24th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XXIV).
[57]
Robert Podschwadt and Daniel Takabi. 2020. Classification of encrypted word embeddings using recurrent neural networks. In Workshop on Privacy in Natural Language Processing (PrivateNLP @ WSDM).
[58]
Rambus Inc. 2020. White paper: HBM2E and GDDR6: Memory Solutions for AI.
[59]
Brandon Reagen, Wooseok Choi, Yeongil Ko, Vincent Lee, Gu-Yeon Wei, Hsien-Hsin S Lee, and David Brooks. 2021. Cheetah: Optimizations and methods for privacy preserving inference via homomorphic encryption. In Proceedings of the 27th IEEE international symposium on High Performance Computer Architecture (HPCA-27).
[60]
M Sadegh Riazi, Kim Laine, Blake Pelton, and Wei Dai. 2020. HEAX: An architecture for computing on encrypted data. In Proceedings of the 25th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XXV).
[61]
Sujoy Sinha Roy, Furkan Turan, Kimmo Järvinen, Frederik Vercauteren, and Ingrid Verbauwhede. 2019. FPGA-Based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data. In Proceedings of the 25th IEEE international symposium on High Performance Computer Architecture (HPCA-25).
[62]
Richard M Russell. 1978. The CRAY-1 computer system. Commun. ACM 21, 1 (1978).
[63]
Furkan Turan, Sujoy Roy, and Ingrid Verbauwhede. 2020. HEAWS: An accelerator for homomorphic encryption on the Amazon AWS FPGA. IEEE Trans. Comput. (2020).
[64]
McKenzie van der Hagen and Brandon Lucia. 2022. Client-optimized algorithms and acceleration for encrypted compute offloading. In Proceedings of the 27th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XXVII).
[65]
Wei Wang, Zhilu Chen, and Xinming Huang. 2014. Accelerating leveled fully homomorphic encryption using GPU. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS).
[66]
Wei Wang, Yin Hu, Lianmu Chen, Xinming Huang, and Berk Sunar. 2012. Accelerating fully homomorphic encryption using GPU. In Proceedings fo the IEEE conference on High Performance Extreme Computing (HPEC).
[67]
Wei Wang, Yin Hu, Lianmu Chen, Xinming Huang, and Berk Sunar. 2013. Exploring the feasibility of fully homomorphic encryption. IEEE Trans. Comput. 64, 3 (2013).
[68]
Xuan Yang, Mingyu Gao, Qiaoyi Liu, Jeff Setter, Jing Pu, Ankita Nayak, Steven Bell, Kaidi Cao, Heonjae Ha, Priyanka Raina, et al. 2020. Interstellar: Using Halide's scheduling language to analyze DNN accelerators. In Proceedings of the 25th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XXV).
[69]
Geoffrey Yeap, S. S. Lin, Y. M. Chen, H. L. Shang, P. W. Wang, H. C. Lin, Y. C. Peng, J. Y. Sheu, M. Wang, X. Chen, B. R. Yang, C. P. Lin, F. C. Yang, Y. K. Leung, D. W. Lin, et al. 2019. 5nm CMOS Production Technology Platform featuring full-fledged EUV, and High Mobility Channel FinFETs with densest 0.021um2 SRAM cells for Mobile SoC and High Performance Computing Applications. In Proceedings of the 2019 IEEE International Electron Devices Meeting (IEDM).

Cited By

View all
  • (2024)High-throughput and fully-pipelined ciphertext multiplier for homomorphic encryptionIEICE Electronics Express10.1587/elex.21.2023062821:6(20230628-20230628)Online publication date: 25-Mar-2024
  • (2024)Practical solutions in fully homomorphic encryption: a survey analyzing existing acceleration methodsCybersecurity10.1186/s42400-023-00187-47:1Online publication date: 1-Mar-2024
  • (2024)Private pathological assessment via machine learning and homomorphic encryptionBioData Mining10.1186/s13040-024-00379-917:1Online publication date: 10-Sep-2024
  • Show More Cited By

Index Terms

  1. CraterLake: a hardware accelerator for efficient unbounded computation on encrypted data

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ISCA '22: Proceedings of the 49th Annual International Symposium on Computer Architecture
      June 2022
      1097 pages
      ISBN:9781450386104
      DOI:10.1145/3470496
      This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike International 4.0 License.

      Sponsors

      In-Cooperation

      • IEEE CS TCAA: IEEE CS technical committee on architectural acoustics

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 11 June 2022

      Check for updates

      Author Tags

      1. fully homomorphic encryption
      2. hardware acceleration

      Qualifiers

      • Research-article

      Funding Sources

      • DARPA
      • Wistron Corporation

      Conference

      ISCA '22
      Sponsor:

      Acceptance Rates

      ISCA '22 Paper Acceptance Rate 67 of 400 submissions, 17%;
      Overall Acceptance Rate 543 of 3,203 submissions, 17%

      Upcoming Conference

      ISCA '25

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)1,533
      • Downloads (Last 6 weeks)205
      Reflects downloads up to 16 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)High-throughput and fully-pipelined ciphertext multiplier for homomorphic encryptionIEICE Electronics Express10.1587/elex.21.2023062821:6(20230628-20230628)Online publication date: 25-Mar-2024
      • (2024)Practical solutions in fully homomorphic encryption: a survey analyzing existing acceleration methodsCybersecurity10.1186/s42400-023-00187-47:1Online publication date: 1-Mar-2024
      • (2024)Private pathological assessment via machine learning and homomorphic encryptionBioData Mining10.1186/s13040-024-00379-917:1Online publication date: 10-Sep-2024
      • (2024)vFHE: Verifiable Fully Homomorphic EncryptionProceedings of the 12th Workshop on Encrypted Computing & Applied Homomorphic Cryptography10.1145/3689945.3694806(11-22)Online publication date: 19-Nov-2024
      • (2024)ProgramGalois: A Programmable Generator of Radix-4 Discrete Galois Transformation Architecture for Lattice-Based CryptographyACM Transactions on Reconfigurable Technology and Systems10.1145/368943717:4(1-32)Online publication date: 24-Aug-2024
      • (2024)SoK: Fully Homomorphic Encryption AcceleratorsACM Computing Surveys10.1145/367695556:12(1-32)Online publication date: 5-Jul-2024
      • (2024)NeuJeans: Private Neural Network Inference with Joint Optimization of Convolution and FHE BootstrappingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690375(4361-4375)Online publication date: 2-Dec-2024
      • (2024)Rhombus: Fast Homomorphic Matrix-Vector Multiplication for Secure Two-Party InferenceProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690281(2490-2504)Online publication date: 2-Dec-2024
      • (2024)SZKP: A Scalable Accelerator Architecture for Zero-Knowledge ProofsProceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques10.1145/3656019.3676898(271-283)Online publication date: 14-Oct-2024
      • (2024)BoostCom: Towards Efficient Universal Fully Homomorphic Encryption by Boosting the Word-wise ComparisonsProceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques10.1145/3656019.3676893(121-132)Online publication date: 14-Oct-2024
      • Show More Cited By

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Login options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media