Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2022 (EUROCRYPT 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13275))

Abstract

While it is well known that the sawtooth function has a point-wise convergent Fourier series, the rate of convergence is not the best possible for the application of approximating the mod function in small intervals around multiples of the modulus. We show a different sine series, such that the sine series of order n has error \(O(\epsilon ^{2n+1})\) for approximating the mod function in \(\epsilon \)-sized intervals around multiples of the modulus. Moreover, the resulting polynomial, after Taylor series approximation of the sine function, has small coefficients, and the whole polynomial can be computed at a precision that is only slightly larger than \(-(2n+1)\log \epsilon \), the precision of approximation being sought. This polynomial can then be used to approximate the mod function to almost arbitrary precision, and hence allows practical CKKS-HE bootstrapping with arbitrary precision. We validate our approach by an implementation and obtain 100 bit precision bootstrapping as well as improvements over prior work even at lower precision.

N. Manohar—Work done while this author was at the University of California, Los Angeles.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 99.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 129.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The source code is available upon request.

References

  1. HEAAN. https://github.com/snucrypto/HEAAN

  2. Albrecht, M.R.: On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 103–129. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_4

    Chapter  Google Scholar 

  3. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of Learning with Errors. J. Math. Cryptol. 9(3), 169–203 (2015). http://www.degruyter.com/view/j/jmc.2015.9.issue-3/jmc-2015-0016/jmc-2015-0016.xml

  4. Bergamaschi, F., Halevi, S., Halevi, T.T., Hunt, H.: Homomorphic training of 30,000 logistic regression models. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (eds.) ACNS 2019. LNCS, vol. 11464, pp. 592–611. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21568-2_29

    Chapter  Google Scholar 

  5. Bossuat, J.-P., Mouchet, C., Troncoso-Pastoriza, J., Hubaux, J.-P.: Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 587–617. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_21

    Chapter  Google Scholar 

  6. 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_2

    Chapter  Google Scholar 

  7. 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_14

    Chapter  Google Scholar 

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

    Google Scholar 

  9. 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_15

    Chapter  Google Scholar 

  10. Curtis, B.R., Player, R.: On the feasibility and impact of standardising sparse-secret LWE parameter sets for homomorphic encryption. In: Brenner, M., Lepoint, T., Rohloff, K. (eds.) Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC@CCS 2019, London, UK, 11–15 November 2019, pp. 1–10. ACM (2019). https://doi.org/10.1145/3338469.3358940

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

    Article  Google Scholar 

  12. Han, K., Ki, D.: Better bootstrapping for approximate homomorphic encryption. In: Jarecki, S. (ed.) CT-RSA 2020. LNCS, vol. 12006, pp. 364–390. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-40186-3_16

    Chapter  Google Scholar 

  13. Jutla, C.S., Manohar, N.: Modular Lagrange Interpolation of the Mod Function for Bootstrapping of Approximate HE. Cryptology ePrint Archive, Report 2020/1355 (2020). https://eprint.iacr.org/2020/1355

  14. Kim, A., Papadimitriou, A., Polyakov, Y.: Approximate Homomorphic Encryption with Reduced Approximation Error. IACR Cryptol. ePrint Arch, p. 1118 (2020). https://eprint.iacr.org/2020/1118

  15. Kim, A., Song, Y., Kim, M., Lee, K., Cheon, J.H.: Logistic regression model training based on the approximate homomorphic encryption. BMC Med. Genom. 11(4), 83 (2018). https://doi.org/10.1186/s12920-018-0401-7

  16. Kim, M., et al.: Ultra-Fast Homomorphic Encryption Models enable Secure Outsourcing of Genotype Imputation. bioRxiv (2020)

    Google Scholar 

  17. 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). http://www.ncbi.nlm.nih.gov/pubmed/29666041

  18. 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: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 618–647. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_22

    Chapter  Google Scholar 

  19. Masters, O., et al.: Towards a homomorphic machine learning big data pipeline for the financial services sector. In: RWC (2020)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  21. Remez, E., G.: Sur la determination des polynomes d’approximation de degre’ donnee’. Comm. of the Kharkov Math. Soc. 10(196), 41–63 (1934)

    Google Scholar 

  22. Sav, S., et al.: POSEIDON: Privacy-Preserving Federated Neural Network Learning (2020)

    Google Scholar 

Download references

Acknowledgements

Nathan Manohar is supported in part from a Simons Investigator Award, DARPA SIEVE award, NTT Research, NSF Frontier Award 1413955, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, and an Okawa Foundation Research Grant. This material is based upon work supported by the Defense Advanced Research Projects Agency through Award HR00112020024.

Author information

Authors and Affiliations

  1. IBM T. J. Watson Research Center, Yorktown Heights, NY, USA

    Charanjit S. Jutla & Nathan Manohar

Authors
  1. Charanjit S. Jutla
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nathan Manohar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Charanjit S. Jutla .

Editor information

Editors and Affiliations

  1. University of Haifa, Haifa, Haifa, Israel

    Orr Dunkelman

  2. University of Warsaw, Warsaw, Poland

    Stefan Dziembowski

A Proof of Lemma 5

A Proof of Lemma 5

Lemma 5 (restated). For any \(k \ge 0\), any \(\mathbf{a}\) of length \(n>0\), and an independent formal variable t,

$$ \sum _{j=0}^{k} h_j(\mathbf{a})t^j \, = \ \prod _{i=1}^{n} \sum _{j=0}^{k} (ta_i)^j \text{ mod } t^{k+1}. $$

Proof

We prove this lemma by induction over n. The base case for \(n=1\) follows as \(h_j(a) = a^j\) for every j in [0..k]. Suppose the lemma holds for \(n-1\). Then, let \(\mathbf{a}'\) be truncation of \(\mathbf{a}\) to its first \(n-1\) components. We have, modulo \(t^{k+1}\),

$$\begin{aligned} \prod _{i=1}^{n} \sum _{j=0}^{k} (ta_i)^j \,&= \ \sum _{z=0}^{k} (ta_n)^z \;*\; \prod _{i=1}^{n-1} \sum _{j=0}^{k} (ta_i)^j \\&= \ \sum _{z=0}^{k} t^za_n^z \;*\; \sum _{j=0}^{k} h_j(\mathbf{a}')t^j \\&= \ \sum _{j=0}^{k} \sum _{z=0}^{k} a_n^z * h_j(\mathbf{a}')t^{j+z} \\&= \ \sum _{z=0}^{k} \sum _{j=0}^{k} a_n^z * h_j(\mathbf{a}')t^{j+z} \\&= \ \sum _{z=0}^{k} \sum _{j=0}^{k-z} a_n^z * h_j(\mathbf{a}')t^{j+z} \\&= \ \sum _{z=0}^{k} \sum _{j'=z}^{k} a_n^z * h_{j'-z}(\mathbf{a}')t^{j'} \\&= \ \sum _{z=0}^{k} \sum _{k \ge j';\, j' \ge z} a_n^z * h_{j'-z}(\mathbf{a}')t^{j'} \\&= \ \sum _{z \le k;\, j' \le k;\, z\ge 0;\, z \le j'} a_n^z * h_{j'-z}(\mathbf{a}')t^{j'} \\&= \ \sum _{j'=0}^{k} \sum _{z=0}^{j'} a_n^z * h_{j'-z}(\mathbf{a}')t^{j'} \\&= \ \sum _{j'=0}^{k} h_{j'}(\mathbf{a})t^{j'} \end{aligned}$$

Rights and permissions

Reprints and permissions

Copyright information

© 2022 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Jutla, C.S., Manohar, N. (2022). Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE. In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13275. Springer, Cham. https://doi.org/10.1007/978-3-031-06944-4_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-06944-4_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-06943-7

  • Online ISBN: 978-3-031-06944-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation