nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Bootstrapping Bits with CKKS

verfasst von : Youngjin Bae, Jung Hee Cheon, Jaehyung Kim, Damien Stehlé

Erschienen in: Advances in Cryptology – EUROCRYPT 2024

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Cheon–Kim–Kim–Song (CKKS) fully homomorphic encryption scheme is designed to efficiently perform computations on real numbers in an encrypted state. Recently, Drucker et al [J. Cryptol.] proposed an efficient strategy to use CKKS in a black-box manner to perform computations on binary data.

In this work, we introduce several CKKS bootstrapping algorithms designed specifically for ciphertexts encoding binary data. Crucially, the new CKKS bootstrapping algorithms enable to bootstrap ciphertexts containing the binary data in the most significant bits. First, this allows to decrease the moduli used in bootstrapping, saving a larger share of the modulus budget for non-bootstrapping operations. In particular, we obtain full-slot bootstrapping in ring degree \(2^{14}\) for the first time. Second, the ciphertext format is compatible with the one used in the DM/CGGI fully homomorphic encryption schemes. Interestingly, we may combine our CKKS bootstrapping algorithms for bits with the fast ring packing technique from Bae et al [CRYPTO’23]. This leads to a new bootstrapping algorithm for DM/CGGI that outperforms the state-of-the-art approaches when the number of bootstraps to be performed simultaneously is in the low hundreds.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Fully Homomorphic Encryption Beyond IND-CCA1 Security: Integrity Through Verifiability

Nächstes Kapitel Concurrently Secure Blind Schnorr Signatures

We note that the \(h_1\) noise-reducing function is run after every binary gate in [DMPS24], which is over-conservative as noted in [ADE+23]; a saving of a factor 3.4 can be obtained by calling the \(h_1\) function less frequently and using complex bootstrapping.

This is actually intrinsic. The number of slots s modulo 2 is exactly the number of distinct factors modulo 2 of the cyclotomic polynomial and the degrees of these factors are all equal. Assume N is the degree of the cyclotomic polynomial, and d the degree of the factors: the number of distinct factors is \(s \le N/d\). We also have \(s \le 2^d\), the number of polynomials modulo 2 of degree \(<d\). The second bound implies that \(d \ge \log _2 (s)\) and the first one then gives \(s \cdot \log _2 (s) \le N\).

As far as we are aware of, it has not been formally described so far in an article, but it is used in [EPF22, Cry22].

For the sake of comparison, \(\textsf{BinBoot}\) for \(\textsf{Param14}\) and real bootstrapping (optimized for latency), takes \(84.8\,\mu \)s per gate which is 4.82x slower than \(\textsf{Param16}\) with complex bootstrapping (optimized for throughput).

One may need \(\le 30\) bits primes for lazy modular reductions (see [Har14]). To be compatible with this technique, we may use slightly smaller primes for \(\textsf{Param14}\) and \(\textsf{Param16}\) for Tables 5 and 7.

[ADE+23]

Aharoni, E., Drucker, N., Ezov, G., Kushnir, E., Shaul, H., Soceanu, O.: E2E near-standard and practical authenticated transciphering. Cryptology ePrint Archive, Paper 2023/1040 (2023)

[APS15]

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. (2015). Software available at https://github.com/malb/lattice-estimator (commit fd4a460)

[BBB+22]

Al Badawi, A., et al.: OpenFHE: open-source fully homomorphic encryption library. Cryptology ePrint Archive, Paper 2022/915 (2022). Software available at https://github.com/openfheorg/openfhe-development (commit 4ebb28e)

[BCC+22]

Bae, Y., Cheon, J.H., Cho, W., Kim, J., Kim, T.: META-BTS: bootstrapping precision beyond the limit. In: CCS (2022)

[BCK+23]

Bae, Y., Cheon, J.H., Kim, J., Park, J.H., Stehlé, D.: HERMES: efficient ring packing using MLWE ciphertexts and application to transciphering. In: CRYPTO (2023)

[BGGJ20]

Boura, C., Gama, N., Georgieva, M., Jetchev, D.: CHIMERA: combining ring-LWE-based fully homomorphic encryption schemes. J. Math. Cryptol. (2020)

[BGV12]

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: ITCS (2012)

[BIP+22]

Bonte, C., Iliashenko, I., Park, J., Pereira, H.V.L., Smart, N.P.: FINAL: faster FHE instantiated with NTRU and LWE. In: ASIACRYPT (2022)

[BMTPH21]

Bossuat, J.-P., Mouchet, C., Troncoso-Pastoriza, J., Hubaux, J.-P.: Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys. In: EUROCRYPT (2021)

[BP23]

Al Badawi, A., Polyakov, Y.: Demystifying bootstrapping in fully homomorphic encryption. Cryptology ePrint Archive, Paper 2023/149 (2023)

[Bra12]

Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: CRYPTO (2012)

[BTPH22]

Bossuat, J.-P., Troncoso-Pastoriza, J., Hubaux, J.-P.: Bootstrapping for approximate homomorphic encryption with negligible failure-probability by using sparse-secret encapsulation. In: ACNS (2022)

[CCS19]

Chen, H., Chillotti, I., Song, Y.: Improved bootstrapping for approximate homomorphic encryption. In: EUROCRYPT (2019)

[CDKS21]

Chen, H., Dai, W., Kim, M., Song, Y.: Efficient homomorphic conversion between (ring) LWE ciphertexts. In: ACNS (2021)

[CGGI16a]

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: ASIACRYPT (2016)

[CGGI16b]

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: fast fully homomorphic encryption library (version 1.1) (2016). Software available at https://tfhe.github.io/tfhe/

[CGGI17]

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In: ASIACRYPT (2017)

[CHK+18a]

Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: Bootstrapping for approximate homomorphic encryption. In: EUROCRYPT (2018)

[CHK+18b]

Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: A full RNS variant of approximate homomorphic encryption. In: SAC (2018)

[CHK+21]

Cho, J., et al.: Transciphering framework for approximate homomorphic encryption. In: ASIACRYPT (2021)

[CIM19]

Carpov, S., Izabachène, M., Mollimard, V.: New techniques for multi-value input homomorphic evaluation and applications. In: CT-RSA (2019)

[CJL+20]

Chillotti, I., Joye, M., Ligier, D., Orfila, J.-B., Tap, S.: Concrete: concrete operates on ciphertexts rapidly by extending TFHE. In: WAHC (2020)

[CJP21]

Chillotti, I., Joye, M., Paillier, P.: Programmable bootstrapping enables efficient homomorphic inference of deep neural networks. In: CSCML (2021)

[CKK20]

Cheon, J.H., Kim, D., Kim, D.: Efficient homomorphic comparison methods with optimal complexity. In: ASIACRYPT (2020)

[CKKS17]

Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: ASIACRYPT (2017)

[CLOT21]

Chillotti, I., Ligier, D., Orfila, J.-B., Tap, S.: Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE. In: ASIACRYPT (2021)

[Cry22]

CryptoLab. HEaaN library (2022). https://www.cryptolab.co.kr/en/products-en/heaan-he/

[DM15]

Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: EUROCRYPT (2015)

[DMPS24]

Drucker, N., Moshkowich, G., Pelleg, T., Shaul, H.: BLEACH: cleaning errors in discrete computations over CKKS. J. Cryptol. (2024)

[EPF22]

EPFL-LDS, Tune Insight SA. Lattigo v4 (2022). https://github.com/tuneinsight/lattigo

[FV12]

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

[GBA21]

Guimarães, A., Borin, E., Aranha, D.F.: Revisiting the functional bootstrap in TFHE. IACR Trans. Cryptogr. Hardw. Embed. Syst. (2021)

[GHPS13]

Gentry, C., Halevi, S., Peikert, C., Smart, N.P.: Field switching in BGV-style homomorphic encryption. J. Comput. Secur. (2013)

[GPL23]

Guimarães, A., Pereira, H.V.L., Van Leeuwen, B.: Amortized bootstrapping revisited: simpler, asymptotically-faster, implemented. Cryptology ePrint Archive, Paper 2023/14 (2023)

[Har14]

Harvey, D.: Faster arithmetic for number-theoretic transforms. J. Symb. Comput. (2014)

[HK20]

Han, K., Ki, D.: Better bootstrapping for approximate homomorphic encryption. In: CT-RSA (2020)

[HS14]

Halevi, S., Shoup, V.: Algorithms in HElib. In: CRYPTO (2014)

[JM20]

Jutla, C.S., Manohar, N.: Modular Lagrange interpolation of the mod function for bootstrapping of approximate HE. Cryptology ePrint Archive, Paper 2020/1355 (2020)

[JM22]

Jutla, C.S., Manohar, N.: Sine series approximation of the mod function for bootstrapping of approximate HE. In: EUROCRYPT (2022)

[KLSS23]

Kim, M., Lee, D., Seo, J., Song, Y.: Accelerating HE operations from key decomposition technique. In: CRYPTO (2023)

[Klu22]

Kluczniak, K.: NTRU-\(\nu \)-um: secure fully homomorphic encryption from NTRU with small modulus. In: CCS (2022)

[KS23]

Kluczniak, K., Schild, L.: FDFB: full domain functional bootstrapping towards practical fully homomorphic encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst. (2023)

[KSS24]

Kim, J., Seo, J., Song, Y.: Simpler and faster BFV bootstrapping for arbitrary plaintext modulus from CKKS. Cryptology ePrint Archive, Paper 2024/109 (2024)

[LHH+21]

Lu, W.-J., Huang, Z., Hong, C., Ma, Y., Qu, H.: PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption. In: S &P (2021)

[LLK+22]

Lee, Y., Lee, J.-W., Kim, Y.-S., Kim, Y., No, J.-S., Kang, H.: High-precision bootstrapping for approximate homomorphic encryption by error variance minimization. In: EUROCRYPT (2022)

[LLKN20]

Lee, Y., Lee, J.-W., Kim, Y.-S., No, J.-S.: Near-optimal polynomial for modulus reduction using L2-norm for approximate homomorphic encryption. IEEE Access (2020)

[LLL+21]

Lee, J.-W., Lee, E., Lee, Y., Kim, Y.-S., No, J.-S.: High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function. In: UROCRYPT (2021)

[LMK+23]

Lee, Y., et al.: Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption. In: EUROCRYPT (2023)

[LMSS23]

Lee, C., Min, S., Seo, J., Song, Y.: Faster TFHE bootstrapping with block binary keys. In: AsiaCCS (2023)

[LPR10]

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: EUROCRYPT (2010)

[LW23a]

Liu, F.-H., Wang, H.: Batch bootstrapping I: a new framework for SIMD bootstrapping in polynomial modulus. In: EUROCRYPT (2023)

[LW23b]

Liu, F.-H., Wang, H.: Batch bootstrapping II: bootstrapping in polynomial modulus only requires \(\widetilde{O}(1)\) FHE multiplications in amortization. In: EUROCRYPT (2023)

[LW23c]

Liu, Z., Wang, Y.: Amortized functional bootstrapping in less than 7 ms, with \(\tilde{O}(1)\) polynomial multiplications. In: ASIACRYPT (2023)

[LW24]

Liu, Z., Wang, Y.: Relaxed functional bootstrapping: a new perspective on BGV/BFV bootstrapping. Cryptology ePrint Archive, Paper 2024/172 (2024)

[MHWW24]

Ma, S., Huang, T., Wang, A., Wang, X.: Accelerating BGV bootstrapping for large \(p\) using null polynomials over \(\mathbb{Z}_{p^e}\). Cryptology ePrint Archive, Paper 2024/115, to appear in the proceedings of EUROCRYPT’24 (2024)

[MKMS23]

De Micheli, G., Kim, D., Micciancio, D., Suhl, A.: Faster amortized FHEW bootstrapping using ring automorphisms. Cryptology ePrint Archive, Paper 2023/112 (2023)

[MS18]

Micciancio, D., Sorrell, J.: Ring packing and amortized FHEW bootstrapping. In: ICALP (2018)

[Reg05]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)

[SSTX09]

Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: ASIACRYPT (2009)

[TCBS23]

Trama, D., Clet, P.-E., Boudguiga, A., Sirdey, R.: At last! a homomorphic AES evaluation in less than 30 seconds by means of TFHE. Cryptology ePrint Archive, Paper 2023/1020 (2023)

[XZD+23]

Xiang, B., Zhang, J., Deng, Y., Dai, Y., Feng, D.: Fast blind rotation for bootstrapping FHEs. In: CRYPTO (2023)

Titel: Bootstrapping Bits with CKKS
verfasst von: Youngjin Bae
Jung Hee Cheon
Jaehyung Kim
Damien Stehlé
Verlag: Springer Nature Switzerland
Buch: Advances in Cryptology – EUROCRYPT 2024
Print ISBN: 978-3-031-58722-1

Electronic ISBN: 978-3-031-58723-8

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58723-8_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner