HALO: Loop-aware Bootstrapping Management for Fully Homomorphic Encryption
Authors: 
Seonyoung Cheon, Yongwoo Lee, Hoyun Youm, Dongkwan Kim, Sungwoo Yun, Kunmo Jeong, Dongyoon Lee, Hanjun KimAuthors Info & Claims
Pages 572 - 585
Abstract
Thanks to the computation ability on encrypted data, fully homomorphic encryption (FHE) is an attractive solution for privacy-preserving computation. Despite its advantages, FHE suffers from limited applicability in small programs because repeated FHE multiplications deplete the level of a ciphertext, which is finite. Bootstrapping reinitializes the level, thus allowing support for larger programs. However, its high computational overhead and the risk of level underflow require sophisticated bootstrapping placement, thereby increasing the programming burden. Although a recently proposed compiler automatizes the bootstrapping placement, its applicability is still limited due to lack of loop support.
This work proposes the first loop-aware bootstrapping management compiler, called HALO, which optimizes bootstrapping placement in an FHE program with a loop. To correctly support bootstrapping-enabled loops, HALO matches encryption types and levels between live-in and loop-carried ciphertexts in the loops. To reduce the bootstrapping overheads, HALO decreases the number of bootstrapping within a loop body by packing the loop-carried variables to a single ciphertext, reduces wasted levels in a short loop body by unrolling the loop, and optimizes the bootstrapping latency by adjusting the target level of bootstrapping as needed. For seven machine learning programs with flat and nested loops, HALO shows 27% performance speedup compared to the state-of-the-art compiler that places bootstrapping operations on fully unrolled loops. In addition, HALO reduces the compilation time and code size by geometric means of 209.12x and 11.0x compared to the compiler, respectively.
References
[1]
''Lattigo v4,'' Online: https://github.com/tuneinsight/lattigo, Aug. 2022, ePFL-LDS, Tune Insight SA.
[2]
R. Agrawal, J. H. Ahn, F. Bergamaschi, R. Cammarota, J. H. Cheon, F. D. M. de Souza, H. Gong, M. Kang, D. Kim, J. Kim, H. de Lassus, J. H. Park, M. Steiner, and W. Wang, ''High-precision rns-ckks on fixed but smaller word-size architectures: theory and application,'' in Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, ser.WAHC '23. Association for Computing Machinery, 2023.
[3]
A. Al Badawi, J. Bates, F. Bergamaschi, D. B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee et al., ''Openfhe: Opensource fully homomorphic encryption library,'' in Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2022, pp. 53--63.
[4]
D.W. Archer, J. M. Calderón Trilla, J. Dagit, A. Malozemoff, Y. Polyakov, K. Rohloff, and G. Ryan, ''Ramparts: A programmer-friendly system for building homomorphic encryption applications,'' in Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, ser.WAHC'19. Association for Computing Machinery, 2019. [Online]. Available: https://doi.org/10.1145/3338469.3358945
[5]
S. Bian, Z. Zhao, Z. Zhang, R. Mao, K. Suenaga, Y. Jin, Z. Guan, and J. Liu, ''Heir: A unified representation for cross-scheme compilation of fully homomorphic computation.''
[6]
F. Boemer, A. Costache, R. Cammarota, and C. Wierzynski, ''ngraphhe2: A high-throughput framework for neural network inference on encrypted data,'' in Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2019, pp. 45--56.
[7]
F. Boemer, Y. Lao, R. Cammarota, and C. Wierzynski, ''ngraph-he: a graph compiler for deep learning on homomorphically encrypted data,'' in Proceedings of the 16th ACM International Conference on Computing Frontiers, 2019, pp. 3--13.
[8]
J.-P. Bossuat, C. Mouchet, J. Troncoso-Pastoriza, and J.-P. Hubaux, ''Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys,'' in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2021, pp. 587--617.
[9]
Z. Brakerski, C. Gentry, and S. Halevi, ''Packed Ciphertexts in LWEBased Homomorphic Encryption,'' in Public-Key Cryptography - PKC 2013, K. Kurosawa and G. Hanaoka, Eds. Springer, 2013.
[10]
Z. Brakerski, C. Gentry, and V. Vaikuntanathan, ''(leveled) fully homomorphic encryption without bootstrapping,'' in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ser. ITCS '12. New York, NY, USA: Association for Computing Machinery, 2012, pp. 309--325. [Online]. Available: https://doi.org/10.1145/2090236.2090262
[11]
J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song, ''A full rns variant of approximate homomorphic encryption,'' in Selected Areas in Cryptography -- SAC 2018, C. Cid and M. J. Jacobson Jr., Eds. Springer International Publishing, 2018.
[12]
J. H. Cheon, A. Kim, M. Kim, and Y. Song, ''Homomorphic encryption for arithmetic of approximate numbers,'' in Advances in Cryptology--ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3--7, 2017, Proceedings, Part I 23. Springer, 2017, pp. 409--437.
[13]
S. Cheon, Y. Lee, D. Kim, J. M. Lee, S. Jung, T. Kim, D. Lee, and H. Kim, ''{DaCapo}: Automatic bootstrapping management for efficient fully homomorphic encryption,'' in 33rd USENIX Security Symposium (USENIX Security 24), 2024, pp. 6993--7010.
[14]
E. Chielle, O. Mazonka, H. Gamil, N. G. Tsoutsos, and M. Maniatakos, ''E3: A framework for compiling c programs with encrypted operands,'' Cryptology ePrint Archive, Report 2018/1013, 2018, https://ia.cr/2018/1013.
[15]
I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, ''Tfhe: Fast fully homomorphic encryption over the torus,'' Journal of Cryptology, no. 1, pp. 34--91, 2020, https://doi.org/10.1007/s00145-019-09319-x.
[16]
--, ''TFHE: Fast fully homomorphic encryption library,'' August 2016, https://tfhe.github.io/tfhe/.
[17]
S. Chowdhary, W. Dai, K. Laine, and O. Saarikivi, ''Eva improved: Compiler and extension library for ckks,'' in Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography, ser. WAHC '21. New York, NY, USA: Association for Computing Machinery, 2021. [Online]. Available: https://doi.org/10.1145/3474366.3486929
[18]
''Cingulata,'' https://github.com/CEA-LIST/Cingulata, 2020.
[19]
M. Cowan, D. Dangwal, A. Alaghi, C. Trippel, V. T. Lee, and B. Reagen, ''Porcupine: A synthesizing compiler for vectorized homomorphic encryption,'' in Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2021, pp. 375--389.
[20]
E. Crockett, C. Peikert, and C. Sharp, ''Alchemy: A language and compiler for homomorphic encryption made easy,'' in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018, pp. 1020--1037.
[21]
B. Dai, Weiand Sunar, ''cuhe: A homomorphic encryption accelerator library,'' in Cryptography and Information Security in the Balkans, E. Pasalic and L. R. Knudsen, Eds. Cham: Springer International Publishing, 2016, pp. 169--186.
[22]
R. Dathathri, B. Kostova, O. Saarikivi, W. Dai, K. Laine, and M. Musuvathi, ''EVA: An encrypted vector arithmetic language and compiler for efficient homomorphic computation,'' in Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2020. [Online]. Available: https://doi.org/10.1145/3385412.3386023
[23]
R. Dathathri, O. Saarikivi, H. Chen, K. Laine, K. Lauter, S. Maleki, M. Musuvathi, and T. Mytkowicz, ''CHET: An Optimizing Compiler for Fully-homomorphic Neural-network Inferencing,'' in Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2019. [Online]. Available: http://doi.acm.org/10.1145/3314221.3314628
[24]
L. Ducas and D. Micciancio, ''Fhew: bootstrapping homomorphic encryption in less than a second,'' in Annual international conference on the theory and applications of cryptographic techniques. Springer, 2015.
[25]
J. Fan and F. Vercauteren, ''Somewhat practical fully homomorphic encryption,'' Cryptology ePrint Archive, Report 2012/144, 2012, https://eprint.iacr.org/2012/144.
[26]
R. A. Fisher, ''The use of multiple measurements in taxonomic problems,'' Annals of eugenics, 1936.
[27]
''FullRNS-HEAAN,'' https://github.com/KyoohyungHan/FullRNSHEAAN, 2018.
[28]
C. Gentry, ''Fully homomorphic encryption using ideal lattices,'' in Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 169--178.
[29]
S. Gorantala, R. Springer, S. Purser-Haskell, W. Lam, R. Wilson, A. Ali, E. P. Astor, I. Zukerman, S. Ruth, C. Dibak et al., ''A general purpose transpiler for fully homomorphic encryption,'' arXiv preprint arXiv:2106.07893, 2021.
[30]
C. Gouert, D. Mouris, and N. Tsoutsos, ''Sok: New insights into fully homomorphic encryption libraries via standardized benchmarks,'' Proceedings on privacy enhancing technologies, 2023.
[31]
K. Han and D. Ki, ''Better bootstrapping for approximate homomorphic encryption,'' in Cryptographers' Track at the RSA Conference. Springer, 2020, pp. 364--390.
[32]
''HEAAN Open-Source HE Library,'' https://github.com/snucrypto/HEAAN, 2020.
[33]
''HElib Open-Source HE Library,'' https://github.com/homenc/HElib, 2020.
[34]
Z. Huang, W.-j. Lu, C. Hong, and J. Ding, ''Cheetah: Lean and fast secure {Two-Party} deep neural network inference,'' in 31st USENIX Security Symposium (USENIX Security 22), 2022, pp. 809--826.
[35]
W. Jung, S. Kim, J. H. Ahn, J. H. Cheon, and Y. Lee, ''Over 100x faster bootstrapping in fully homomorphic encryption through memorycentric optimization with gpus,'' IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 114--148, 2021.
[36]
C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, ''{GAZELLE}: A low latency framework for secure neural network inference,'' in 27th {USENIX} Security Symposium ({USENIX} Security 18), 2018, pp. 1651--1669.
[37]
D. Kim, J. Park, J. Kim, S. Kim, and J. H. Ahn, ''Hyphen: A hybrid packing method and optimizations for homomorphic encryption-based neural networks,'' arXiv preprint arXiv:2302.02407, 2023.
[38]
D. Kim, Y. Lee, S. Cheon, H. Choi, J. Lee, H. Youm, D. Lee, and H. Kim, ''Privacy set: Privacy-authority-aware compiler for homomorphic encryption on edge-cloud system,'' IEEE Internet of Things Journal, vol. 11, no. 21, pp. 35 167--35 184, 2024.
[39]
C. Lattner, M. Amini, U. Bondhugula, A. Cohen, A. Davis, J. Pienaar, R. Riddle, T. Shpeisman, N. Vasilache, and O. Zinenko, ''Mlir: Scaling compiler infrastructure for domain specific computation,'' in 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). IEEE, 2021, pp. 2--14.
[40]
E. Lee, J.-W. Lee, J. Lee, Y.-S. Kim, Y. Kim, J.-S. No, and W. Choi, ''Lowcomplexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions,'' in International Conference on Machine Learning. PMLR, 2022, pp. 12 403--12 422.
[41]
E. Lee, J.-W. Lee, J.-S. No, and Y.-S. Kim, ''Minimax approximation of sign function by composite polynomial for homomorphic comparison,'' IEEE Transactions on Dependable and Secure Computing, vol. 19, no. 6, pp. 3711--3727, 2021.
[42]
J.-W. Lee, H. Kang, Y. Lee, W. Choi, J. Eom, M. Deryabin, E. Lee, J. Lee, D. Yoo, Y.-S. Kim et al., ''Privacy-preserving machine learning with fully homomorphic encryption for deep neural network,'' IEEE Access, 2022.
[43]
J.-W. Lee, E. Lee, Y.-S. Kim, and J.-S. No, ''Rotation key reduction for client-server systems of deep neural network on fully homomorphic encryption,'' in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2023, pp. 36--68.
[44]
Y. Lee, S. Cheon, D. Kim, D. Lee, and H. Kim, ''{ELASM}:{Error-Latency-Aware} scale management for fully homomorphic encryption,'' in 32nd USENIX Security Symposium (USENIX Security 23), 2023, pp. 4697--4714.
[45]
--, ''Performance-aware scale analysis with reserve for homomorphic encryption,'' in Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1, 2024, pp. 302--317.
[46]
Y. Lee, S. Heo, S. Cheon, S. Jeong, C. Kim, E. Kim, D. Lee, and H. Kim, ''HECATE: Performance-Aware Scale Optimization for Homomoprhic Encryption Compiler,'' in 2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2022.
[47]
Y. Lee, J. Seo, Y. Nam, J. Chae, and J. H. Cheon, ''Heaan-stat: A privacypreserving statistical analysis toolkit for large-scale numerical, ordinal, and categorical data,'' IEEE Transactions on Dependable and Secure Computing, 2024.
[48]
V. Lyubashevsky, C. Peikert, and O. Regev, ''On ideal lattices and learning with errors over rings,'' in Advances in Cryptology -- EUROCRYPT 2010, H. Gilbert, Ed. Berlin, Heidelberg: Springer, 2010.
[49]
R. Malik, K. Sheth, and M. Kulkarni, ''Coyote: A compiler for vectorizing encrypted arithmetic circuits,'' in Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, 2023, pp. 118--133.
[50]
C. Marcolla, V. Sucasas, M. Manzano, R. Bassoli, F. H. P. Fitzek, and N. Aaraj, ''Survey on fully homomorphic encryption, theory, and applications,'' Proceedings of the IEEE, 2022.
[51]
P. Mishra, R. Lehmkuhl, A. Srinivasan, W. Zheng, and R. A. Popa, ''Delphi: a cryptographic inference system for neural networks,'' in Proceedings of the 2020 Workshop on Privacy-Preserving Machine Learning in Practice, 2020, pp. 27--30.
[52]
M. Paindavoine and B. Vialla, ''Minimizing the number of bootstrappings in fully homomorphic encryption,'' in Selected Areas in Cryptography--SAC 2015: 22nd International Conference, Sackville, NB, Canada, August 12--14, 2015, Revised Selected Papers 22. Springer, 2016, pp. 25--43.
[53]
''PALISADE Lattice Cryptography Library,'' https://palisade-crypto.org/, Oct. 2020.
[54]
J. Park, D. Kim, J. Kim, S. Kim, W. Jung, J. H. Cheon, and J. H. Ahn, ''Toward practical privacy-preserving convolutional neural networks exploiting fully homomorphic encryption,'' 2023.
[55]
S. Park, W. Song, S. Nam, H. Kim, J. Shin, and J. Lee, ''HEaaN.MLIR: An optimizing compiler for fast ring-based homomorphic encryption,'' no. PLDI, 2023.
[56]
D. Rathee, M. Rathee, N. Kumar, N. Chandran, D. Gupta, A. Rastogi, and R. Sharma, ''Cryptflow2: Practical 2-party secure inference,'' in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, pp. 325--342.
[57]
''Microsoft SEAL (release 4.1),'' https://github.com/Microsoft/SEAL, Jan. 2023, microsoft Research, Redmond, WA.
[58]
T. van Elsloo, G. Patrini, and H. Ivey-Law, ''Sealion: a framework for neural network inference on encrypted data,'' 2019.
[59]
A. Viand, P. Jattke, M. Haller, and A. Hithnawi, ''HECO: Fully homomorphic encryption compiler,'' in 32nd USENIX Security Symposium (USENIX Security 23), 2023.
[60]
A. Viand, P. Jattke, and A. Hithnawi, ''Sok: Fully homomorphic encryption compilers,'' in 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021, pp. 1092--1108.
[61]
A. Viand and H. Shafagh, ''Marble: Making fully homomorphic encryption accessible to all,'' in Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, ser. WAHC '18. Association for Computing Machinery, 2018.
[62]
M. O. S. N. Wolberg, William and W. Street, ''Breast Cancer Wisconsin (Diagnostic),'' UCI Machine Learning Repository, 1995.
[63]
Zama, ''Concrete: TFHE Compiler that converts python programs into FHE equivalent,'' 2022, https://github.com/zama-ai/concrete.
[64]
--, ''TFHE-rs: A Pure Rust Implementation of the TFHE Scheme for Boolean and Integer Arithmetics Over Encrypted Data,'' 2022, https://github.com/zama-ai/tfhe-rs.
[65]
A. Sah Özcan and E. Savas, ''HEonGPU: a GPU-based fully homomorphic encryption library 1.0,'' Cryptology ePrint Archive, Paper 2024/1543, 2024. [Online]. Available: https://eprint.iacr.org/2024/1543
Index Terms
- HALO: Loop-aware Bootstrapping Management for Fully Homomorphic Encryption
Recommendations
(Leveled) fully homomorphic encryption without bootstrapping
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science ConferenceWe present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic ...
Fully Homomorphic Encryption Beyond IND-CCA1 Security: Integrity Through Verifiability
Advances in Cryptology – EUROCRYPT 2024AbstractWe focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond . Towards this, we propose a new notion, called security against verified ...
CCA-Secure Keyed-Fully Homomorphic Encryption
Proceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 9614To simultaneously achieve CCA security and homomorphic property for encryption, Emura et al. introduced a new cryptographic primitive named keyed-homomorphic encryption, in which homomorphic ciphertext manipulations can only be performed by someone ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2025
1177 pages
ISBN:9798400706981
DOI:10.1145/3669940
- General Chairs:
- Lieven Eeckhout,
- Georgios Smaragdakis,
- Katai Liang,
- Program Chairs:
- Adrian Sampson,
- Martha Kim,
- Christopher J. Rossbach
Copyright © 2025.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 March 2025
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ASPLOS '25: 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems
March 30 - April 3, 2025
Rotterdam, Netherlands
Acceptance Rates
Overall Acceptance Rate 535 of 2,713 submissions, 20%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025