nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Numerical Method for Comparison on Homomorphically Encrypted Numbers

verfasst von : Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, Keewoo Lee

Erschienen in: Advances in Cryptology – ASIACRYPT 2019

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

We propose a new method to compare numbers which are encrypted by Homomorphic Encryption (HE). Previously, comparison and min/max functions were evaluated using Boolean functions where input numbers are encrypted bit-wise. However, the bit-wise encryption methods require relatively expensive computations for basic arithmetic operations such as addition and multiplication.

In this paper, we introduce iterative algorithms that approximately compute the min/max and comparison operations of several numbers which are encrypted word-wise. From the concrete error analyses, we show that our min/max and comparison algorithms have \(\varTheta (\alpha )\) and \(\varTheta (\alpha \log \alpha )\) computational complexity to obtain approximate values within an error rate \(2^{-\alpha }\), while the previous minimax polynomial approximation method requires the exponential complexity \(\varTheta (2^{\alpha /2})\) and \(\varTheta (\sqrt{\alpha }\cdot 2^{\alpha /2})\), respectively. Our algorithms achieve (quasi-)optimality in terms of asymptotic computational complexity among polynomial approximations for min/max and comparison operations. The comparison algorithm is extended to several applications such as computing the top-k elements and counting numbers over the threshold in encrypted state.

Our method enables word-wise HEs to enjoy comparable performance in practice with bit-wise HEs for comparison operations while showing much better performance on polynomial operations. Computing an approximate maximum value of any two \(\ell \)-bit integers encrypted by HEAAN, up to error \(2^{\ell -10}\), takes only 1.14 ms in amortized running time, which is comparable to the result based on bit-wise HEs.

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 Algebraic XOR-RKA-Secure Pseudorandom Functions from Post-Zeroizing Multilinear Maps

Nächstes Kapitel Multi-Key Homomorphic Encryption from TFHE

Nur mit Berechtigung zugänglich

Albrecht, M.R.: A sage module for estimating the concrete security of learning with errors instances (2017). https://bitbucket.org/malb/lwe-estimator

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

Bernstein, S.: Sur la meilleure approximation de \(|\)x\(|\) par des polynomes de degrés donnés. Acta Math. 37(1), 1–57 (1914)MathSciNetCrossRef

Bos, J.W., Lauter, K., Loftus, J., Naehrig, M.: Improved security for a ring-based fully homomorphic encryption scheme. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 45–64. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-45239-0_4CrossRef

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

Bourse, F., Minelli, M., Minihold, M., Paillier, P.: Fast homomorphic evaluation of deep discretized neural networks. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 483–512. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_17CrossRef

Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 868–886. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_50CrossRef

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

Brown, K.: Probability of intersecting intervals. https://www.mathpages.com/home/kmath580/kmath580.htm

10.

Chatterjee, A., SenGupta, I.: Sorting of fully homomorphic encrypted cloud data: can partitioning be effective? IEEE Trans. Serv. Comput. (2017)

11.

Cheon, J.H., et al.: Toward a secure drone system: flying with real-time homomorphic authenticated encryption. IEEE Access 6, 24325–24339 (2018)CrossRef

12.

Cheon, J.H., Jeong, J., Lee, J., Lee, K.: Privacy-preserving computations of predictive medical models with minimax approximation and non-adjacent form. In: Brenner, M., et al. (eds.) FC 2017. LNCS, vol. 10323, pp. 53–74. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70278-0_4CrossRef

13.

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

14.

Cheon, J.H., Kim, D., Kim, Y., Song, Y.: Ensemble method for privacy-preserving logistic regression based on homomorphic encryption. IEEE Access 6, 46938–46948 (2018)CrossRef

15.

Cheon, J.H., Kim, D., Park, J.H.: Towards a practical clustering analysis over encrypted data. Cryptology ePrint Archive, Report 2019/465 (2019). https://eprint.iacr.org/2019/465

16.

Cheon, J.H., Kim, M., Kim, M.: Search-and-compute on encrypted data. In: Brenner, M., Christin, N., Johnson, B., Rohloff, K. (eds.) FC 2015. LNCS, vol. 8976, pp. 142–159. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48051-9_11CrossRef

17.

Chialva, D., Dooms, A.: Conditionals in homomorphic encryption and machine learning applications. Cryptology ePrint Archive, Report 2018/1032 (2018). https://eprint.iacr.org/2018/1032

18.

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_1CrossRefMATH

19.

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 377–408. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_14CrossRef

20.

Costache, A., Smart, N.P.: Which ring based somewhat homomorphic encryption scheme is best? In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 325–340. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29485-8_19CrossRef

21.

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 and Applied Homomorphic Cryptography, pp. 1–12. ACM (2018)

22.

van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_2CrossRef

23.

Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 617–640. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_24CrossRefMATH

24.

Emmadi, N., Gauravaram, P., Narumanchi, H., Syed, H.: Updates on sorting of fully homomorphic encrypted data. In: 2015 International Conference on Cloud Computing Research and Innovation (ICCCRI), pp. 19–24. IEEE (2015)

25.

Eremenko, A., Yuditskii, P.: Uniform approximation of sgn(x) by polynomials and entire functions. J. d’Analyse Mathématique 101(1), 313–324 (2007)MathSciNetCrossRef

26.

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

27.

Gentry, C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University (2009). http://crypto.stanford.edu/craig

28.

Gentry, C., Halevi, S., Smart, N.P.: Better bootstrapping in fully homomorphic encryption. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 1–16. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_1CrossRef

29.

Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5CrossRef

30.

Gilad-Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: Cryptonets: applying neural networks to encrypted data with high throughput and accuracy. In: International Conference on Machine Learning (2016)

31.

Goldschmidt, R.E.: Applications of division by convergence. Ph.D. thesis, Massachusetts Institute of Technology (1964)

32.

Halevi, S., Shoup, V.: Bootstrapping for HElib. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 641–670. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_25CrossRef

33.

Jackson, D.: The Theory of Approximation, vol. 11. American Mathematical Society (1930)

34.

Jäschke, A., Armknecht, F.: Unsupervised machine learning on encrypted data. In: Cid, C., Jacobson Jr., M. (eds.) SAC 2018. LNCS, pp. 453–478. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7_21CrossRef

35.

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), 83 (2018)CrossRef

36.

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

37.

Kocabas, O., Soyata, T.: Utilizing homomorphic encryption to implement secure and private medical cloud computing. In: 2015 IEEE 8th International Conference on Cloud Computing (CLOUD), pp. 540–547. IEEE (2015)

38.

Pachón, R., Trefethen, L.N.: Barycentric-Remez algorithms for best polynomial approximation in the chebfun system. BIT Numer. Math. 49(4), 721 (2009)MathSciNetCrossRef

39.

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

40.

Phillips, G.M.: Best approximation. In: Phillips, G.M. (ed.) Interpolation and Approximation by Polynomials. CBM, pp. 49–118. Springer, New York (2003). https://doi.org/10.1007/0-387-21682-0_2CrossRef

41.

Powell, M.J.D.: Approximation Theory and Methods. Cambridge University Press, Cambridge (1981)CrossRef

42.

Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks and privacy homomorphisms. Found. Secur. Comput. 4(11), 169–180 (1978)MathSciNet

43.

Togan, M., Morogan, L., Plesca, C.: Comparison-based applications for fully homomorphic encrypted data. In: Proceedings of the Romanian Academy-Series A: Mathematics, Physics, Technical Sciences, Information Science, vol. 16, p. 329 (2015)

44.

Wilkes, M.V.: The Preparation of Programs for an Electronic Digital Computer: with Special Reference to the EDSAC and the Use of a Library of Subroutines. Addison-Wesley Press (1951)

Titel: Numerical Method for Comparison on Homomorphically Encrypted Numbers
verfasst von: Jung Hee Cheon
Dongwoo Kim
Duhyeong Kim
Hun Hee Lee
Keewoo Lee
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2019
Print ISBN: 978-3-030-34620-1

Electronic ISBN: 978-3-030-34621-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-34621-8_15

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