Efficient Methods for Simultaneous Homomorphic Inversion
Authors
Jean Belo Klamti, M. Anwarul Hasan, Koray Karabina
Jean Belo Klamti
National Research Council Canada, Ottawa, Ontario, Canada
jeanbelo dot klamti at nrc-cnrc dot gc dot ca
jeanbelo dot klamti at nrc-cnrc dot gc dot ca
M. Anwarul Hasan
University of Waterloo, Waterloo, Ontario, Canada
ahasan at uwaterloo dot ca
ahasan at uwaterloo dot ca
Koray Karabina
National Research Council Canada, Ottawa, Ontario, Canada
University of Waterloo, Waterloo, Ontario, Canada
koray dot karabina at nrc-cnrc dot gc dot ca
University of Waterloo, Waterloo, Ontario, Canada
koray dot karabina at nrc-cnrc dot gc dot ca
Keywords:
Fully homomorphic encryption
Homomorphic inversion
Goldschmidt inversion
Montgomery's trick.
Abstract
Efficient implementation of some privacy-preserving algorithms and applications rely on efficient implementation of homomorphic inversion. For example, a recently proposed homomorphic image filtering algorithm and the privacy-preserving body mass index (BMI) calculations repetitively use homomorphic inversion. In this paper, inspired by Montgomery's trick to perform simultaneous plaintext inversion, we tackle the simultaneous homomorphic inversion problem to compute s inverses simultaneously over ciphertexts. The advantage of Montgomery's trick for plaintext arithmetic is well-known. We first observe that the advantage can quickly vanish when homomorphic encryption is employed because of the increased depth of the circuits. Therefore, we propose three algorithms (Montgomery's trick and two other variants) that reduce the number of homomorphic inversions from s to 1 and that offer different levels of trade-offs between the number of multiplications and the circuit depth. We provide a theoretical complexity analysis of our algorithms and implement them using the CKKS scheme in the OpenFHE library. Our experiments show that, for some cases, the run time of homomorphic s-inversion can be improved up to 35 percent while in some other cases, regular inversion seems to outperform Montgomery-based inversion algorithms.
References
[ABBB+22]
Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. OpenFHE: Open-source fully homomorphic encryption library. In Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 53–63, New York, NY, USA. 2022. Association for Computing Machinery. DOI: 10.1145/3560827.3563379
[ASP14]
Jacob Alperin-Sheriff and Chris Peikert. Faster bootstrapping with polynomial error. In Advances in Cryptology–CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I 34, pages 297–314. 2014. Springer. DOI: https://doi.org/10.1007/978-3-662-44371-2_17
[Ben94]
Josh Benaloh. Dense probabilistic encryption. In Proceedings of the Workshop on Selected Areas of Cryptography, pages 120–128. 1994.
[BGN05]
Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts. In Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005. Proceedings 2, pages 325–341. 2005. Springer. DOI: https://doi.org/10.1007/978-3-540-30576-7_18
[BGV14]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014. DOI: https://doi.org/10.1145/2090236.2090262
[BLLN13]
Joppe W Bos, Kristin Lauter, Jake Loftus, and Michael Naehrig. Improved security for a ring-based fully homomorphic encryption scheme. In Cryptography and Coding: 14th IMA International Conference, IMACC 2013, Oxford, UK, December 17-19, 2013. Proceedings 14, pages 45–64. 2013. Springer. DOI: https://doi.org/10.1007/978-3-642-45239-0_4
[Bra12]
Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In Advances in Cryptology–CRYPTO 2012: 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, pages 868–886. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_50
[Bra18]
Zvika Brakerski. Fundamentals of fully homomorphic encryption - a survey. In Electronic Colloquium on Computational Complexity (ECCC), volume 25, pages 125. 2018. DOI: https://doi.org/10.1145/3335741.3335762
[BV11a]
Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 97–106. 2011. IEEE. DOI: 10.1109/FOCS.2011.12
[BV11b]
Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Annual Cryptology Conference, pages 505–524. 2011. Springer. DOI: 10.1007/978-3-642-22792-9_29
[BV14]
Zvika Brakerski and Vinod Vaikuntanathan. Lattice-based FHE as secure as PKE. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pages 1–12. 2014. DOI: 10.1145/2554797.2554799
[CCK+13]
Jung Hee Cheon, Jean-Sébastien Coron, Jinsu Kim, Moon Sung Lee, Tancrede Lepoint, Mehdi Tibouchi, and Aaram Yun. Batch fully homomorphic encryption over the integers. In Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32, pages 315–335. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_20
[CDPR16]
Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals in cyclotomic rings. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 559–585. 2016. Springer. DOI: 10.1007/978-3-662-49896-5_20
[CDSM15]
Gizem Selcan Cetin, Yarkin Doroz, Berk Sunar, and William J. Martin. Arithmetic using word-wise homomorphic encryption. https://eprint.iacr.org/2015/1195. Cryptology ePrint Archive, Paper 2015/1195. 2015.
[CGGI20]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91, 2020. DOI: 10.1007/s00145-019-09319-x
[Che54]
Pafnuty Lvovich Chebyshev. Memoires des savants etrangers présentés á l'académie de Saint-Pétersbourg. Ch. Théorie des mécanismes connus sous le nom de parallélogrammes, 7:539–586, 1854.
[CKK+19]
Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, and Keewoo Lee. Numerical method for comparison on homomorphically encrypted numbers. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, pages 415–445, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-34621-8_15
[CKKS17]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, pages 409–437, Cham. 2017. Springer International Publishing. DOI: 10.1007/978-3-319-70694-8_15
[CLT14]
Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Scale-invariant fully homomorphic encryption over the integers. In Public-Key Cryptography–PKC 2014: 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings 17, pages 311–328. 2014. Springer. DOI: 10.1007/978-3-642-54631-0_18
[CMNT11]
Jean-Sébastien Coron, Avradip Mandal, David Naccache, and Mehdi Tibouchi. Fully homomorphic encryption over the integers with shorter public keys. In Annual Cryptology Conference, pages 487–504. 2011. Springer. DOI: 10.1007/978-3-642-22792-9_28
[CN12]
Yuanmi Chen and Phong Q Nguyen. Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 502–519. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_30
[CNT12]
Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi. Public key compression and modulus switching for fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 446–464. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_27
[CS15]
Jung Hee Cheon and Damien Stehlé. Fully homomophic encryption over the integers revisited. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 513–536. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_20
[CSY22]
Jung Hee Cheon, Yongha Son, and Donggeon Yhee. Practical FHE parameters against lattice attacks. J. Korean Math. Soc, 59(1):35–51, 2022. DOI: 10.4134/JKMS.j200650
[DM15]
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, pages 617–640, Berlin, Heidelberg. 2015. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-46800-5_24
[DS20]
Yarkın Doröz and Berk Sunar. Flattening NTRU for evaluation key free homomorphic encryption. Journal of Mathematical Cryptology, 14(1):66–83, 2020. DOI: doi:10.1515/jmc-2015-0052
[ElG85]
Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on Information Theory, 31(4):469–472, 1985. DOI: 10.1109/TIT.1985.1057074
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. https://eprint.iacr.org/2012/144. Cryptology ePrint Archive, Paper 2012/144. 2012.
[Gal02]
Steven D Galbraith. Elliptic curve Paillier schemes. Journal of Cryptology, 15:129–138, 2002. DOI: 10.1007/s00145-001-0015-6
[Gen09]
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pages 169–178, New York, NY, USA. 2009. Association for Computing Machinery. DOI: 10.1145/1536414.1536440
[GH11]
Craig Gentry and Shai Halevi. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 107–109. 2011. IEEE. DOI: 10.1109/FOCS.2011.94
[GM82]
Shafi Goldwasser and Silvio Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 365–377. 1982. DOI: 10.1145/800070.802212
[Gol64]
Robert E. Goldschmidt. Applications of division by convergence. PhD thesis, Massachusetts Institute of Technology, 1964.
[GSW13]
Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pages 75–92. 2013. Springer. DOI: 10.1007/978-3-642-40041-4_5
[Har08]
David G. Harris. Simultaneous field divisions: an extension of Montgomery's trick. https://eprint.iacr.org/2008/199. Cryptology ePrint Archive, Paper 2008/199. 2008.
[IIMP22a]
Ilia Iliashenko, Malika Izabachène, Axel Mertens, and Hilder Vitor Lima Pereira. Homomorphically counting elements with the same property. Proceedings on Privacy Enhancing Technologies, 4:670–683, 2022. DOI: https://doi.org/10.56553/popets-2022-0127
[IIMP22b]
Ilia Iliashenko, Malika Izabachène, Axel Mertens, and Hilder VL Pereira. Homomorphically counting elements with the same property. [Online; accessed 30-May-2024]. https://www.youtube.com/watch?v=P2XdA758JUo. 2022.
[KGV15]
Alhassan Khedr, Glenn Gulak, and Vinod Vaikuntanathan. SHIELD: Scalable homomorphic implementation of encrypted data-classifiers. IEEE Transactions on Computers, 65(9):2848–2858, 2015. DOI: 10.1109/TC.2015.2500576
[KK21]
Sharmila Devi Kannivelu and Sunwoong Kim. A homomorphic encryption-based adaptive image filter using division over encrypted data. In 2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 67-72, Los Alamitos, CA, USA. August 2021. IEEE Computer Society. DOI: 10.1109/RTCSA52859.2021.00016
[LATV12]
Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pages 1219–1234. 2012. DOI: 10.1145/2213977.2214086
[MGH10]
Carlos Aguilar Melchor, Philippe Gaborit, and Javier Herranz. Additively homomorphic encryption with d-operand multiplications. In Advances in Cryptology–CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30, pages 138–154. 2010. Springer. DOI: 10.1007/978-3-642-14623-7_8
[Mon87]
Peter Lawrence Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation, 48(177):243–264, 1987. DOI: 10.1090/s0025-5718-1987-0866113-7
[NK15]
Koji Nuida and Kaoru Kurosawa. (Batch) fully homomorphic encryption over integers for non-binary message spaces. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 537–555. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_21
[NS98]
David Naccache and Jacques Stern. A new public key cryptosystem based on higher residues. In Proceedings of the 5th ACM Conference on Computer and Communications Security, pages 59–66. 1998. DOI: 10.1145/288090.288106
[Pai99]
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 223–238. 1999. Springer. DOI: 10.1007/3-540-48910-X_16
[RAD+78]
Ronald L Rivest, Len Adleman, Michael L Dertouzos, and others. On data banks and privacy homomorphisms. Foundations of Secure Computation, 4(11):169–180, 1978.
[Rap02]
Joseph Raphson. Analysis aequationum universalis, volume 1. Typis T.B. prostant venales apud A. and I. Churchill 1702.
[Rot11]
Ron Rothblum. Homomorphic encryption: From private-key to public-key. In Theory of Cryptography Conference, pages 219–234. 2011. Springer. DOI: 10.1007/978-3-642-19571-6_14
[SS10]
Damien Stehlé and Ron Steinfeld. Faster fully homomorphic encryption. In Advances in Cryptology - ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16, pages 377–394. 2010. Springer. DOI: https://doi.org/10.1007/978-3-642-17373-8_22
[SS11]
Peter Scholl and Nigel P Smart. Improved key generation for Gentry’s fully homomorphic encryption scheme. In IMA International Conference on Cryptography and Coding, pages 10–22. 2011. Springer. DOI: https://doi.org/10.1007/978-3-642-25516-8_2
[SV10]
Nigel P Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Public Key Cryptography–PKC 2010: 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010. Proceedings 13, pages 420–443. 2010. Springer. DOI: https://doi.org/10.1007/978-3-642-13013-7_25
[VDGHV10]
Marten Van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29, pages 24–43. 2010. Springer. DOI: https://doi.org/10.1007/978-3-642-13190-5_2
PDF
History
Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Jean Belo Klamti, M. Anwarul Hasan, and Koray Karabina, Efficient Methods for Simultaneous Homomorphic Inversion. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/abe0iv7sf.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.