Document Open Access Logo

Ring Packing and Amortized FHEW Bootstrapping

Authors Daniele Miccianco, Jessica Sorrell

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.100.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Daniele Miccianco
  • Department of Computer Science and Engineering, University of California - San Diego, CA, USA
Jessica Sorrell
  • Department of Computer Science and Engineering, University of California - San Diego, CA, USA

Funding

Research supported in part by the Defense Advanced Research Project Agency (DARPA) and the U.S. Army Research Office under the SafeWare program, and the National Science Foundation (NSF) under grant CNS-1528068. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect reflect the views, position or policy of the Government.

Cite As Get BibTex

Daniele Miccianco and Jessica Sorrell. Ring Packing and Amortized FHEW Bootstrapping. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 100:1-100:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.100

Abstract

The FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) offers very fast homomorphic NAND-gate computations (on encrypted data) and a relatively fast refreshing procedure that allows to homomorphically evaluate arbitrary NAND boolean circuits. Unfortunately, the refreshing procedure needs to be executed after every single NAND computation, and each refreshing operates on a single encrypted bit, greatly decreasing the overall throughput of the scheme. We give a new refreshing procedure that simultaneously refreshes n FHEW ciphertexts, at a cost comparable to a single-bit FHEW refreshing operation. As a result, the cost of each refreshing is amortized over n encrypted bits, improving the throughput for the homomorphic evaluation of boolean circuits roughly by a factor n.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
Keywords
  • homomorphic encryption
  • bootstrapping
  • lattice-based cryptography

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jacob Alperin-Sheriff and Chris Peikert. Practical bootstrapping in quasilinear time. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 1-20. Springer, Heidelberg, August 2013. URL: http://dx.doi.org/10.1007/978-3-642-40041-4_1.
  2. Jacob Alperin-Sheriff and Chris Peikert. Faster bootstrapping with polynomial error. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 297-314. Springer, Heidelberg, August 2014. URL: http://dx.doi.org/10.1007/978-3-662-44371-2_17.
  3. Jean-François Biasse and Luis Ruiz. FHEW with efficient multibit bootstrapping. In Kristin E. Lauter and Francisco Rodríguez-Henríquez, editors, Progress in Cryptology - LATINCRYPT 2015: 4th International Conference on Cryptology and Information Security in Latin America, volume 9230 of Lecture Notes in Computer Science, pages 119-135. Springer, Heidelberg, August 2015. URL: http://dx.doi.org/10.1007/978-3-319-22174-8_7.
  4. Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 868-886. Springer, Heidelberg, August 2012. Google Scholar
  5. Zvika Brakerski, Craig Gentry, and Shai Halevi. Packed ciphertexts in LWE-based homomorphic encryption. In Kaoru Kurosawa and Goichiro Hanaoka, editors, PKC 2013: 16th International Conference on Theory and Practice of Public Key Cryptography, volume 7778 of Lecture Notes in Computer Science, pages 1-13. Springer, Heidelberg, February / March 2013. URL: http://dx.doi.org/10.1007/978-3-642-36362-7_1.
  6. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012: 3rd Innovations in Theoretical Computer Science, pages 309-325. Association for Computing Machinery, January 2012. Google Scholar
  7. Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th Annual ACM Symposium on Theory of Computing, pages 575-584. ACM Press, June 2013. Google Scholar
  8. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) dollarbackslashmathsfLWEdollar. SIAM J. Comput., 43(2):831-871, 2014. URL: https://doi.org/10.1137/120868669, URL: http://dx.doi.org/10.1137/120868669.
  9. Zvika Brakerski and Vinod Vaikuntanathan. Lattice-based FHE as secure as PKE. In Moni Naor, editor, ITCS 2014: 5th Innovations in Theoretical Computer Science, pages 1-12. Association for Computing Machinery, January 2014. Google Scholar
  10. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016, Part I, volume 10031 of Lecture Notes in Computer Science, pages 3-33. Springer, Heidelberg, December 2016. URL: http://dx.doi.org/10.1007/978-3-662-53887-6_1.
  11. Léo Ducas and Daniele Micciancio. Improved short lattice signatures in the standard model. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 335-352. Springer, Heidelberg, August 2014. URL: http://dx.doi.org/10.1007/978-3-662-44371-2_19.
  12. Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping homomorphic encryption in less than a second. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 617-640. Springer, Heidelberg, April 2015. URL: http://dx.doi.org/10.1007/978-3-662-46800-5_24.
  13. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st Annual ACM Symposium on Theory of Computing, pages 169-178. ACM Press, May / June 2009. Google Scholar
  14. Craig Gentry and Shai Halevi. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In Rafail Ostrovsky, editor, 52nd Annual Symposium on Foundations of Computer Science, pages 107-109. IEEE Computer Society Press, October 2011. Google Scholar
  15. Craig Gentry, Shai Halevi, Chris Peikert, and Nigel P. Smart. Ring switching in BGV-style homomorphic encryption. In Ivan Visconti and Roberto De Prisco, editors, SCN 12: 8th International Conference on Security in Communication Networks, volume 7485 of Lecture Notes in Computer Science, pages 19-37. Springer, Heidelberg, September 2012. Google Scholar
  16. Craig Gentry, Shai Halevi, and Nigel P. Smart. Better bootstrapping in fully homomorphic encryption. In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, PKC 2012: 15th International Conference on Theory and Practice of Public Key Cryptography, volume 7293 of Lecture Notes in Computer Science, pages 1-16. Springer, Heidelberg, May 2012. Google Scholar
  17. Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully homomorphic encryption with polylog overhead. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 465-482. Springer, Heidelberg, April 2012. Google Scholar
  18. Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic evaluation of the AES circuit. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 850-867. Springer, Heidelberg, August 2012. Google Scholar
  19. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75-92. Springer, Heidelberg, August 2013. URL: http://dx.doi.org/10.1007/978-3-642-40041-4_5.
  20. Shai Halevi and Victor Shoup. Algorithms in HElib. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 554-571. Springer, Heidelberg, August 2014. URL: http://dx.doi.org/10.1007/978-3-662-44371-2_31.
  21. Shai Halevi and Victor Shoup. Bootstrapping for HElib. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 641-670. Springer, Heidelberg, April 2015. URL: http://dx.doi.org/10.1007/978-3-662-46800-5_25.
  22. Henri J. Nussbaumer. Fast polynomial transform methods for multidimensional dfts. In IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '80, Denver, Colorado, April 9-11, 1980, pages 235-237. IEEE, 1980. URL: https://doi.org/10.1109/ICASSP.1980.1170902, URL: http://dx.doi.org/10.1109/ICASSP.1980.1170902.
  23. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th Annual ACM Symposium on Theory of Computing, pages 84-93. ACM Press, May 2005. Google Scholar
  24. Nigel P. Smart and Frederik Vercauteren. Fully homomorphic SIMD operations. Des. Codes Cryptography, 71(1):57-81, 2014. URL: https://doi.org/10.1007/s10623-012-9720-4, URL: http://dx.doi.org/10.1007/s10623-012-9720-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact