More Web Proxy on the site http://driver.im/

Article

Improved Bootstrapping for Approximate Homomorphic Encryption

Authors:

Ilaria Chillotti,

Yongsoo SongAuthors Info & Claims

Advances in Cryptology – EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part II

Pages 34 - 54

https://doi.org/10.1007/978-3-030-17656-3_2

Published: 19 May 2019 Publication History

Abstract

Since Cheon et al. introduced a homomorphic encryption scheme for approximate arithmetic (Asiacrypt ’17), it has been recognized as suitable for important real-life usecases of homomorphic encryption, including training of machine learning models over encrypted data. A follow up work by Cheon et al. (Eurocrypt ’18) described an approximate bootstrapping procedure for the scheme. In this work, we improve upon the previous bootstrapping result. We improve the amortized bootstrapping time per plaintext slot by two orders of magnitude, from

\sim

1 s to

\sim

0.01 s. To achieve this result, we adopt a smart level-collapsing technique for evaluating DFT-like linear transforms on a ciphertext. Also, we replace the Taylor approximation of the sine function with a more accurate and numerically stable Chebyshev approximation, and design a modified version of the Paterson-Stockmeyer algorithm for fast evaluation of Chebyshev polynomials over encrypted data.

References

[1]

HEAAN with Faster Multiplication (2018). https://github.com/snucrypto/HEAAN/releases/tag/2.1

[2]

Bajard J-C, Eynard J, Hasan MA, and Zucca V Avanzi R and Heys H A full RNS variant of FV like somewhat homomorphic encryption schemes Selected Areas in Cryptography – SAC 2016 2017 Cham Springer 423-442

[3]

Beckermann, B.: On the numerical condition of polynomial bases: estimates for the condition number of Vandermonde, Krylov and Hankel matrices. Ph.D. thesis, Verlag nicht ermittelbar (1997)

[4]

Bonte C, Bootland C, Bos JW, Castryck W, Iliashenko I, and Vercauteren F Fischer W and Homma N Faster homomorphic function evaluation using non-integral base encoding Cryptographic Hardware and Embedded Systems – CHES 2017 2017 Cham Springer 579-600

[5]

Boura, C., Gama, N., Georgieva, M.: Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning. Cryptology ePrint Archive, Report 2018/758 (2018). https://eprint.iacr.org/2018/758

[6]

Bourse F, Minelli M, Minihold M, and Paillier P Shacham H and Boldyreva A Fast homomorphic evaluation of deep discretized neural networks Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 483-512

Digital Library

[7]

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of ITCS, pp. 309–325. ACM (2012)

[8]

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 97–106. IEEE Computer Society (2011)

[9]

Brakerski Z and Vaikuntanathan V Rogaway P Fully homomorphic encryption from ring-LWE and security for key dependent messages Advances in Cryptology – CRYPTO 2011 2011 Heidelberg Springer 505-524

[10]

Chen H et al. Logistic regression over encrypted data from fully homomorphic encryption BMC Med. Genomics 2018 11 4 81

[11]

Chen H and Han K Nielsen JB and Rijmen V Homomorphic lower digits removal and improved FHE bootstrapping Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 315-337

[12]

Chen, H., Laine, K., Rindal, P.: Fast private set intersection from homomorphic encryption. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1243–1255. ACM (2017)

[13]

Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: Implementation of boostrapping for HEAAN (2017). https://github.com/kimandrik/HEAANBOOT

[14]

Cheon JH, Han K, Kim A, Kim M, and Song Y Nielsen JB and Rijmen V Bootstrapping for approximate homomorphic encryption Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 360-384

[15]

Cheon JH, Han K, Kim A, Kim M, and Song Y Cid C and Jacobson M Jr A full RNS variant of approximate homomorphic encryption Selected Areas in Cryptography – SAC 2018 2018 Cham Springer 347-368

Digital Library

[16]

Cheon JH, Kim A, Kim M, and Song Y Takagi T and Peyrin T Homomorphic encryption for arithmetic of approximate numbers Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 409-437

[17]

Chillotti I, Gama N, Georgieva M, and Izabachène M Cheon JH and Takagi T Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 3-33

[18]

Chillotti I, Gama N, Georgieva M, and Izabachène M Takagi T and Peyrin T Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 377-408

[19]

Crawford, J.L., Gentry, C., Halevi, S., Platt, D., Shoup, V.: Doing real work with FHE: the case of logistic regression. In: Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pp. 1–12. ACM (2018)

[20]

Ducas L and Micciancio D Oswald E and Fischlin M FHEW: bootstrapping homomorphic encryption in less than a second Advances in Cryptology – EUROCRYPT 2015 2015 Heidelberg Springer 617-640

[21]

Ehlich H and Zeller K Auswertung der normen von interpolationsoperatoren Math. Ann. 1966 164 2 105-112

[22]

Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive 2012:144 (2012)

[23]

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 169–178. ACM (2009)

[24]

Gentry C, Halevi S, and Smart NP Fischlin M, Buchmann J, and Manulis M Better bootstrapping in fully homomorphic encryption Public Key Cryptography – PKC 2012 2012 Heidelberg Springer 1-16

Digital Library

[25]

Gilad-Bachrach, R., et al.: CryptoNets: applying neural networks to encrypted data with high throughput and accuracy. In: International Conference on Machine Learning, pp. 201–210 (2016)

[26]

Giroux A Approximation of entire functions over bounded domains J. Approx. Theory 1980 28 1 45-53

[27]

Halevi S and Shoup V Garay JA and Gennaro R Algorithms in HElib Advances in Cryptology – CRYPTO 2014 2014 Heidelberg Springer 554-571

[28]

Halevi S and Shoup V Oswald E and Fischlin M Bootstrapping for HElib Advances in Cryptology – EUROCRYPT 2015 2015 Heidelberg Springer 641-670

[29]

Han, K., Hong, S., Cheon, J.H., Park, D.: Efficient logistic regression on large encrypted data. Cryptology ePrint Archive, Report 2018/662 (2018). https://eprint.iacr.org/2018/662

[30]

Kim A, Song Y, Kim M, Lee K, and Cheon JH Logistic regression model training based on the approximate homomorphic encryption BMC Med. Genomics 2018 11 4 83

[31]

Paterson MS and Stockmeyer LJ On the number of nonscalar multiplications necessary to evaluate polynomials SIAM J. Comput. 1973 2 1 60-66

Digital Library

Cited By

Cho WHanrot GKim TPark MStehlé DLuo BLiao XXu JKirda ELie D(2024)Fast and Accurate Homomorphic Softmax EvaluationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670369(4391-4404)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670369
Chen MChen YZong RLi ZJiang Z(2024)F-FHEW: High-Precision Approximate Homomorphic Encryption with Batch BootstrappingInformation Security and Privacy10.1007/978-981-97-5025-2_7(121-140)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_7
Huang TMa SWang AWang X(2024)Approximate Methods for the Computation of Step Functions in Homomorphic EncryptionInformation Security and Privacy10.1007/978-981-97-5025-2_12(217-237)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_12
Show More Cited By

Recommendations

(Leveled) fully homomorphic encryption without bootstrapping
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference

We 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 2024
Abstract
We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond $CCA1$ . Towards this, we propose a new notion, called security against verified ...
A Hybrid Scheme of Public-Key Encryption and Somewhat Homomorphic Encryption
We introduce a hybrid homomorphic encryption that combines public-key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce the storage requirements of most somewhat or fully homomorphic encryption (FHE) applications. In this model, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part II

May 2019

786 pages

ISBN:978-3-030-17655-6

DOI:10.1007/978-3-030-17656-3

Editors:
Yuval Ishai
Technion, Haifa, Israel
,
Vincent Rijmen
COSIC Group, KU Leuven, Heverlee, Belgium

© International Association for Cryptologic Research 2019.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 19 May 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cho WHanrot GKim TPark MStehlé DLuo BLiao XXu JKirda ELie D(2024)Fast and Accurate Homomorphic Softmax EvaluationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670369(4391-4404)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670369
Chen MChen YZong RLi ZJiang Z(2024)F-FHEW: High-Precision Approximate Homomorphic Encryption with Batch BootstrappingInformation Security and Privacy10.1007/978-981-97-5025-2_7(121-140)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_7
Huang TMa SWang AWang X(2024)Approximate Methods for the Computation of Step Functions in Homomorphic EncryptionInformation Security and Privacy10.1007/978-981-97-5025-2_12(217-237)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_12
Cheon JCho WKim JStehlé DMeng WJensen CCremers CKirda E(2023)Homomorphic Multiple Precision Multiplication for CKKS and Reduced Modulus ConsumptionProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623086(696-710)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623086
Bian SZhang ZPan HMao RZhao ZJin YGuan ZMeng WJensen CCremers CKirda E(2023)HE3DB: An Efficient and Elastic Encrypted Database Via Arithmetic-And-Logic Fully Homomorphic EncryptionProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616608(2930-2944)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616608
Li BMicciancio D(2021)On the Security of Homomorphic Encryption on Approximate NumbersAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77870-5_23(648-677)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77870-5_23
Lee JLee ELee YKim YNo J(2021)High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine FunctionAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77870-5_22(618-647)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77870-5_22
Bossuat JMouchet CTroncoso-Pastoriza JHubaux J(2021)Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse KeysAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77870-5_21(587-617)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-77870-5_21

View Options

View options

Media

Figures

Other

Tables

View Table of Contents