Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

Efficient Homomorphic Comparison Methods with Optimal Complexity

verfasst von : Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim

Erschienen in: Advances in Cryptology – ASIACRYPT 2020

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Comparison of two numbers is one of the most frequently used operations, but it has been a challenging task to efficiently compute the comparison function in homomorphic encryption (HE) which basically supports addition and multiplication. Recently, Cheon et al. (Asiacrypt 2019) introduced a new approximate representation of the comparison function with a rational function, and showed that this rational function can be evaluated by an iterative algorithm. Due to this iterative feature, their method achieves a logarithmic computational complexity compared to previous polynomial approximation methods; however, the computational complexity is still not optimal, and the algorithm is quite slow for large-bit inputs in HE implementation.
In this work, we propose new comparison methods with optimal asymptotic complexity based on composite polynomial approximation. The main idea is to systematically design a constant-degree polynomial f by identifying the core properties to make a composite polynomial \(f\circ f \circ \cdots \circ f\) get close to the sign function (equivalent to the comparison function) as the number of compositions increases. We additionally introduce an acceleration method applying a mixed polynomial composition \(f\circ \cdots \circ f\circ g \circ \cdots \circ g\) for some other polynomial g with different properties instead of \(f\circ f \circ \cdots \circ f\). Utilizing the devised polynomials f and g, our new comparison algorithms only require \(\varTheta (\log (1/\epsilon )) + \varTheta (\log \alpha )\) computational complexity to obtain an approximate comparison result of \(a,b\in [0,1]\) satisfying \(|a-b|\ge \epsilon \) within \(2^{-\alpha }\) error.
The asymptotic optimality results in substantial performance enhancement: our comparison algorithm on 16-bit encrypted integers for \(\alpha = 16\) takes 1.22 ms in amortized running time based on an approximate HE scheme HEAAN, which is 18 times faster than the previous work.

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 Privacy-Preserving Pattern Matching on Encrypted Data
Nächstes Kapitel Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
In fact, this line of work in numerical analysis aims to compute the matrix sign function [36] which is a more general object than the sign function in our context. An inverse operation is not much more costly than a multiplication in their (asymptotic) cost analysis and experiments, which is a crucial difference from HE which requires an additional costly polynomial approximation for inverse [12].
 
2
The complexity notations in \(D_n\) and \(C_n\) only depend on n, not \(\alpha \) and \(\epsilon \).
 
3
It does not mean the “convergence” to L(2, 1) as \(n\rightarrow \infty \), since the equation \(TD_n = L\left( \frac{\log n + O(1)}{\log c_n}, \frac{\log n + O(1)}{\log (n+1)}\right) \) only holds when \(n=O(1)\) with respect to \(\alpha \) and \(1/\epsilon \).
 
4
In every iteration of Algorithm 2, the minimax approximate polynomial \(g_{min}\) of \((1-\frac{\tau }{2})\cdot \text {sgn}(x)\) over \([-1,\delta _0]\cup [\delta _0,1]\) satisfies Prop I & IV. Prop I is trivial, and \(g_{min}([\delta _0,1]) \subset [1-\tau , 1]\) by Lemma 1. Since \(g_{min}(\delta _0) > 1-\tau \ge \delta _0\) and \(g_{min}\) is concave & increasing in \([0,\delta _0]\), it holds that \(x< g_{min}(x) < 1\) for \(x \in (0,\delta _0]\).
 
5
If \(g(x) = g_{n,\tau }^{conv}(x)\) on some \(x \in (0, \delta _0)\), it is the point of intersection in \((0, \delta _g)\), and proof continues.
 
6
It does not mean the “convergence” to L(1, 1) as \(n\rightarrow \infty \), since n should be O(1) with respect to \(\alpha \) and \(1/\epsilon \).
 
Literatur
1.
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef
2.
Andrievskii, V.: Polynomial approximation of piecewise analytic functions on a compact subset of the real line. J. Approx. Theory 161(2), 634–644 (2009)MathSciNetCrossRef
3.
Armknecht, F., et al.: A guide to fully homomorphic encryption. Cryptology ePrint Archive, Report 2015/1192 (2015)
4.
Bajard, J.-C., Martins, P., Sousa, L., Zucca, V.: Improving the efficiency of SVM classification with FHE. IEEE Trans. Inf. Forensics Secur. 15, 1709–1722 (2019)CrossRef
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. Accepted to Number-Theoretic Methods in Cryptology (NuTMiC) (2019)
6.
7.
Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of ITCS, pp. 309–325. ACM (2012)
8.
9.
Cheon, J.H., et al.: Toward a secure drone system: flying with real-time homomorphic authenticated encryption. IEEE Access 6, 24325–24339 (2018)CrossRef
10.
11.
12.
13.
14.
Chialva, D., Dooms, A.: Conditionals in homomorphic encryption and machine learning applications. Cryptology ePrint Archive, Report 2018/1032 (2018)
15.
16.
17.
Comaniciu, D., Meer, P.: Mean shift: a robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell. 24(5), 603–619 (2002)CrossRef
18.
Cordero, A., Soleymani, F., Torregrosa, J.R., Ullah, M.Z.: Numerically stable improved Chebyshev-Halley type schemes for matrix sign function. J. Comput. Appl. Math. 318, 189–198 (2017)MathSciNetCrossRef
19.
Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20(3), 273–297 (1995)MATH
20.
Crawford, J.L., Gentry, C., Halevi, S., Platt, D., Shoup, V.: Doing real work with FHE: the case of logistic regression (2018)
21.
Curtis, B.R., Player, R.: On the feasibility and impact of standardising sparse-secret LWE parameter sets for homomorphic encryption. In: Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pp. 1–10 (2019)
22.
23.
Eremenko, A., Yuditskii, P.: Uniform approximation of sgn x by polynomials and entire functions. Journal d’Analyse Mathématique 101(1), 313–324 (2007)MathSciNetCrossRef
24.
Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive, 2012:144 (2012)
25.
Friedman, J.H.: Greedy function approximation: a gradient boosting machine. Ann. Stat. 29, 1189–1232 (2001)MathSciNetCrossRef
26.
27.
28.
29.
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)
30.
Goldschmidt, R.E.: Applications of division by convergence. Ph.D. thesis, Massachusetts Institute of Technology (1964)
31.
Han, K., Hong, S., Cheon, J.H., Park, D.: Logistic regression on homomorphic encrypted data at scale. In: The AAAI Conference on Innovative Applications of Artificial Intelligence (2019)
32.
Han, K., Ki, D.: Better bootstrapping for approximate homomorphic encryption. Cryptology ePrint Archive, Report 2019/688 (2019). To Appear in CT-RSA 2020
33.
Hartigan, J.A., Wong, M.A.: Algorithm as 136: a k-means clustering algorithm. J. Royal Stat. Soc. Ser. C (Appl. Stat.) 28(1), 100–108 (1979)
34.
Higham, N.J.: Functions of matrices: theory and computation. SIAM (2008)
35.
36.
37.
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
38.
Kim, D., Son, Y., Kim, D., Kim, A., Hong, S., Cheon, J.H.: Privacy-preserving approximate GWAS computation based on homomorphic encryption. Cryptology ePrint Archive, Report 2019/152 (2019)
39.
Kim, M., Song, Y., Li, B., Micciancio, D.: Semi-parallel logistic regression for GWAS on encrypted data. Cryptology ePrint Archive, Report 2019/294 (2019)
40.
41.
42.
Nakatsukasa, Y., Bai, Z., Gygi, F.: Optimizing Halley’s iteration for computing the matrix polar decomposition. SIAM J. Matrix Anal. Appl. 31(5), 2700–2720 (2010)MathSciNetCrossRef
43.
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
44.
Saff, E., Totik, V.: Polynomial approximation of piecewise analytic functions. J. London Math. Soc. 2(3), 487–498 (1989)MathSciNetCrossRef
45.
46.
Soheili, A.R., Toutounian, F., Soleymani, F.: A fast convergent numerical method for matrix sign function with application in SDEs. J. Comput. Appl. Math. 282, 167–178 (2015)MathSciNetCrossRef
47.
Tan, B.H.M., Lee, H.T., Wang, H., Ren, S.Q., Khin, A.M.M.: Efficient private comparison queries over encrypted databases using fully homomorphic encryption with finite fields. IEEE Trans. Dependable Secure Comput. (2020)
48.
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)
Metadaten
Titel
Efficient Homomorphic Comparison Methods with Optimal Complexity
verfasst von
Jung Hee Cheon
Dongwoo Kim
Duhyeong Kim
Copyright-Jahr
2020
Buch
Advances in Cryptology – ASIACRYPT 2020

Print ISBN: 978-3-030-64833-6

Electronic ISBN: 978-3-030-64834-3

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-64834-3_8

Premium Partner

    Bildnachweise