nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Better Bootstrapping for Approximate Homomorphic Encryption

verfasst von : Kyoohyung Han, Dohyeong Ki

Erschienen in: Topics in Cryptology – CT-RSA 2020

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

After Cheon et al. (Asiacrypt’ 17) proposed an approximate homomorphic encryption scheme, HEAAN, for operations between encrypted real (or complex) numbers, the scheme is widely used in a variety of fields with needs on privacy-preserving in data analysis. After that, a bootstrapping method for HEAAN is proposed by Cheon et al. (Eurocrypt’ 18) with modulus reduction being replaced by a sine function. In this paper, we generalize the Full-RNS variant of HEAAN proposed by Cheon et al. (SAC, 19) to reduce the number of temporary moduli used in key-switching. As a result, our scheme can support more depth computations without bootstrapping while ensuring the same level of security.

We also propose a new polynomial approximation method to evaluate a sine function in an encrypted state, which is specialized for the bootstrapping for HEAAN. Our method considers a ratio between the size of a plaintext and the size of a ciphertext modulus. Consequently, it requires a smaller number of non-scalar multiplications, which is about half of the Chebyshev method.

With our variant of the Full-RNS scheme and a new sine evaluation method, we firstly implement bootstrapping for a Full-RNS variant of approximate homomorphic encryption scheme. Our method enables bootstrapping for a plaintext in the space \({\mathbb {C}}^{16384}\) to be completed in 52 s while preserving 11 bit precision of each slot.

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 Faster Homomorphic Encryption is not Enough: Improved Heuristic for Multiplicative Depth Minimization of Boolean Circuits

Nächstes Kapitel Improved Secure Integer Comparison via Homomorphic Encryption

Nur mit Berechtigung zugänglich

After version 3.2, they use one temporary modulus instead of bit-decomposition as in [17].

In practice, \(p_i\)’s are chosen to have maximum sizes within the word size (<64 bits). On the other hand, sizes of \(q_j\)’s are depend on the precision of applications, and usually they are 40–45 bits.

In the case of SEAL v3.2, they use the bit-decomposition technique with the RNS-decomposition to reduce the noise growth. But, this method also has a drawback. It increases the length of the public key vector for key-switching further, which is directly related to the complexity of the process.

In Step 1, inverse NTT transform is needed for the next step (modulus raising).

Here, SEAL v.3.3 and HEAAN-RNS indicate the scheme corresponding to each paper and library.

Previous method uses a sine function and double angle formula for a sine function needs both \(\cos (t)\) and \(\sin (t)\) to compute \(\sin (2t)\).

The code for finding an approximate polynomial for the cosine function can be found at [15].

In fact, they use the nodes \(t_i = K \cos \left( {i\pi /n}\right) \) for \(0 \le i \le n\) instead of nodes \(t_i = K \cos \left( (2i-1)\pi / (2n+2) \right) \) for \(1 \le i \le n+1\). But, there is no big difference.

Here, SEAL v.3.3 and HEAAN-RNS indicate the schemes corresponding to each library and paper.

\(|t-\sin {t}|<O(t^3)\) for t near the origin.

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef

Bajard, J.-C., Eynard, J., Hasan, M.A., Zucca, V.: A full RNS variant of FV like somewhat homomorphic encryption schemes. In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 423–442. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5_23CrossRef

Boemer, F., Lao, Y., Wierzynski, C.: nGraph-HE: a graph compiler for deep learning on homomorphically encrypted data. arXiv preprint arXiv:1810.10121 (2018)

Carpov, S., Gama, N., Georgieva, M., Troncoso-Pastoriza, J.R.: Privacy-preserving semi-parallel logistic regression training with Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2019/101 (2019). https://eprint.iacr.org/2019/101

Chen, H., Chillotti, I., Song, Y.: Improved bootstrapping for approximate homomorphic encryption. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 34–54. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_2CrossRef

Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: A full RNS variant of approximate homomorphic encryption. In: Cid, C., Jacobson Jr., M. (eds.) SAC 2018. LNCS, vol. 11349, pp. 347–368. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7_16CrossRef

Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: Bootstrapping for approximate homomorphic encryption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 360–384. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_14CrossRef

Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 409–437. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_15CrossRef

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, vol. 9, pp. 169–178 (2009)

10.

Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 850–867. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_49CrossRef

11.

Halevi, S., Polyakov, Y., Shoup, V.: An improved RNS variant of the BFV homomorphic encryption scheme. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 83–105. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_5CrossRef

12.

Han, K., Hhan, M., Cheon, J.H.: Improved homomorphic discrete Fourier transforms and FHE bootstrapping. IEEE Access 7, 57361–57370 (2019)CrossRef

13.

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

14.

Jiang, Y., Wang, C., Wu, Z., Du, X., Wang, S.: Privacy-preserving biomedical data dissemination via a hybrid approach. In: AMIA Annual Symposium Proceedings, vol. 2018, p. 1176. American Medical Informatics Association (2018)

15.

Ki, D.: (2019). https://github.com/DohyeongKi/better-homomorphic-sine-evaluation

16.

Kim, A., Song, Y., Kim, M., Lee, K., Cheon, J.H.: Logistic regression model training based on the approximate homomorphic encryption. BMC Med. Genomics 11(4) (2018). Article number: 83

17.

Kim, M., Song, Y., Li, B., Micciancio, D.: Semi-parallel logistic regression for GWAS on encrypted data. Cryptology ePrint Archive, Report 2019/294 (2019). https://eprint.iacr.org/2019/294

18.

Kim, M., Song, Y., Wang, S., Xia, Y., Jiang, X.: Secure logistic regression based on homomorphic encryption: Design and evaluation. JMIR Med. Inform. 6(2), e19 (2018)CrossRef

19.

Paterson, M.S., Stockmeyer, L.J.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60–66 (1973)MathSciNetCrossRef

Titel: Better Bootstrapping for Approximate Homomorphic Encryption
verfasst von: Kyoohyung Han
Dohyeong Ki
Verlag: Springer International Publishing
Buch: Topics in Cryptology – CT-RSA 2020
Print ISBN: 978-3-030-40185-6

Electronic ISBN: 978-3-030-40186-3

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-40186-3_16

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"