{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:04:56Z","timestamp":1753895096681,"version":"3.41.2"},"reference-count":52,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T00:00:00Z","timestamp":1736812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,3,11]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.62056\/abe0iv7sf","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:23:17Z","timestamp":1744147397000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Methods for Simultaneous Homomorphic Inversion"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9231-1129","authenticated-orcid":false,"given":"Jean","family":"Klamti","sequence":"first","affiliation":[{"name":"National Research Council Canada","place":["Ottawa, Ontario, Canada"],"department":["Digital Technologies Research Center"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4103-7945","authenticated-orcid":false,"given":"M.","family":"Hasan","sequence":"additional","affiliation":[{"name":"University of Waterloo","place":["Waterloo, Ontario, Canada"],"department":["Electrical and Computer Engineering"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9538-8877","authenticated-orcid":false,"given":"Koray","family":"Karabina","sequence":"additional","affiliation":[{"name":"National Research Council Canada","place":["Ottawa, Ontario, Canada"],"department":["Digital Technologies Research Center"]},{"name":"University of Waterloo","place":["Waterloo, Ontario, Canada"],"department":["Combinatorics and Optimization Department"]}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:RiAdDe78","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"Ronald L Rivest","year":"1978","journal-title":"Foundations of Secure Computation"},{"key":"ref2:Zvika18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1145\/3335741.3335762","article-title":"Fundamentals of fully homomorphic encryption - a survey","volume":"25","author":"Zvika Brakerski","year":"2018"},{"key":"ref3:Gen09","series-title":"STOC '09","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/1536414.1536440","article-title":"Fully homomorphic encryption using ideal lattices","author":"Craig Gentry","year":"2009"},{"key":"ref4:Rot11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-19571-6_14","article-title":"Homomorphic encryption: From private-key to public-key","author":"Ron Rothblum","year":"2011"},{"key":"ref5:Gal02","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s00145-001-0015-6","article-title":"Elliptic curve Paillier schemes","volume":"15","author":"Steven D Galbraith","year":"2002","journal-title":"Journal of Cryptology"},{"key":"ref6:BoGoNi05","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-540-30576-7_18","article-title":"Evaluating 2-DNF formulas on ciphertexts","author":"Dan Boneh","year":"2005"},{"key":"ref7:GoMi82","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1145\/800070.802212","article-title":"Probabilistic encryption & how to play mental poker keeping\n  secret all partial information","author":"Shafi Goldwasser","year":"1982"},{"key":"ref8:El85","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on\n  discrete logarithms","volume":"31","author":"Taher ElGamal","year":"1985","journal-title":"IEEE transactions on Information Theory"},{"key":"ref9:Ben94","first-page":"120","article-title":"Dense probabilistic encryption","author":"Josh Benaloh","year":"1994"},{"key":"ref10:NaSt98","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/288090.288106","article-title":"A new public key cryptosystem based on higher residues","author":"David Naccache","year":"1998"},{"key":"ref11:Pa99","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","article-title":"Public-key cryptosystems based on composite degree\n  residuosity classes","author":"Pascal Paillier","year":"1999"},{"key":"ref12:MeGaHe10","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-642-14623-7_8","article-title":"Additively homomorphic encryption with d-operand\n  multiplications","author":"Carlos Aguilar Melchor","year":"2010"},{"key":"ref13:SmVe10","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-642-13013-7_25","article-title":"Fully homomorphic encryption with relatively small key and\n  ciphertext sizes","author":"Nigel P Smart","year":"2010"},{"key":"ref14:GeHa11","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1109\/FOCS.2011.94","article-title":"Fully homomorphic encryption without squashing using\n  depth-3 arithmetic circuits","author":"Craig Gentry","year":"2011"},{"key":"ref15:ScSm11","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/978-3-642-25516-8_2","article-title":"Improved key generation for Gentry\u2019s fully homomorphic\n  encryption scheme","author":"Peter Scholl","year":"2011"},{"key":"ref16:StSt10","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-642-17373-8_22","article-title":"Faster fully homomorphic encryption","author":"Damien Stehl\u00e9","year":"2010"},{"key":"ref17:VaGeHaVa10","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","article-title":"Fully homomorphic encryption over the integers","author":"Marten Van Dijk","year":"2010"},{"key":"ref18:CoMaNaTi11","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-642-22792-9_28","article-title":"Fully homomorphic encryption over the integers with shorter\n  public keys","author":"Jean-S\u00e9bastien Coron","year":"2011"},{"key":"ref19:CoNaTi12","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-642-29011-4_27","article-title":"Public key compression and modulus switching for fully\n  homomorphic encryption over the integers","author":"Jean-S\u00e9bastien Coron","year":"2012"},{"key":"ref20:ChCoKiLeLeTiYu13","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-38348-9_20","article-title":"Batch fully homomorphic encryption over the integers","author":"Jung Hee Cheon","year":"2013"},{"key":"ref21:NuKu15","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/978-3-662-46800-5_21","article-title":"(Batch) fully homomorphic encryption over integers for\n  non-binary message spaces","author":"Koji Nuida","year":"2015"},{"key":"ref22:CoLeTi14","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-642-54631-0_18","article-title":"Scale-invariant fully homomorphic encryption over the\n  integers","author":"Jean-S\u00e9bastien Coron","year":"2014"},{"key":"ref23:ChSt15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-662-46800-5_20","article-title":"Fully homomophic encryption over the integers revisited","author":"Jung Hee Cheon","year":"2015"},{"key":"ref24:CrDuPeRe16","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-662-49896-5_20","article-title":"Recovering short generators of principal ideals in\n  cyclotomic rings","author":"Ronald Cramer","year":"2016"},{"key":"ref25:ChNg12","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-642-29011-4_30","article-title":"Faster algorithms for approximate common divisors: Breaking\n  fully-homomorphic-encryption challenges over the integers","author":"Yuanmi Chen","year":"2012"},{"key":"ref26:BrVa11a","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1109\/FOCS.2011.12","article-title":"Efficient fully homomorphic encryption from (standard)\n  LWE","author":"Zvika Brakerski","year":"2011"},{"key":"ref27:BrVa11b","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-642-22792-9_29","article-title":"Fully homomorphic encryption from ring-LWE and security for\n  key dependent messages","author":"Zvika Brakerski","year":"2011"},{"key":"ref28:LoTrVa12","doi-asserted-by":"publisher","first-page":"1219","DOI":"10.1145\/2213977.2214086","article-title":"On-the-fly multiparty computation on the cloud via multikey\n  fully homomorphic encryption","author":"Adriana L\u00f3pez-Alt","year":"2012"},{"key":"ref29:BoLaLoNa12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-642-45239-0_4","article-title":"Improved security for a ring-based fully homomorphic\n  encryption scheme","author":"Joppe W Bos","year":"2013"},{"key":"ref30:DoSu16","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1515\/jmc-2015-0052","article-title":"Flattening NTRU for evaluation key free homomorphic\n  encryption","volume":"14","author":"Yark\u0131n Dor\u00f6z","year":"2020","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref31:GeSaWa13","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","article-title":"Homomorphic encryption from learning with errors:\n  conceptually-simpler, asymptotically-faster, attribute-based","author":"Craig Gentry","year":"2013"},{"key":"ref32:BrGeVa14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2090236.2090262","article-title":"(Leveled) fully homomorphic encryption without\n  bootstrapping","volume":"6","author":"Zvika Brakerski","year":"2014","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"volume-title":"Somewhat practical fully homomorphic encryption","year":"2012","author":"Junfeng Fan","key":"ref33:FaVe12"},{"key":"ref34:Bra12","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/978-3-642-32009-5_50","article-title":"Fully homomorphic encryption without modulus switching from\n  classical GapSVP","author":"Zvika Brakerski","year":"2012"},{"key":"ref35:KhGuVa15","doi-asserted-by":"publisher","first-page":"2848","DOI":"10.1109\/TC.2015.2500576","article-title":"SHIELD: Scalable homomorphic implementation of encrypted\n  data-classifiers","volume":"65","author":"Alhassan Khedr","year":"2015","journal-title":"IEEE Transactions on Computers"},{"key":"ref36:BrVa14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2554797.2554799","article-title":"Lattice-based FHE as secure as PKE","author":"Zvika Brakerski","year":"2014"},{"key":"ref37:AlPe14","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-662-44371-2_17","article-title":"Faster bootstrapping with polynomial error","author":"Jacob Alperin-Sheriff","year":"2014"},{"key":"ref38:DuMi15","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-662-46800-5_24","article-title":"FHEW: Bootstrapping homomorphic encryption in less than a\n  second","author":"L\u00e9o Ducas","year":"2015"},{"key":"ref39:ChGaGeIz20","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/s00145-019-09319-x","article-title":"TFHE: Fast fully homomorphic encryption over the torus","volume":"33","author":"Ilaria Chillotti","year":"2020","journal-title":"Journal of Cryptology"},{"key":"ref40:ChKiKiSo17","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-70694-8_15","article-title":"Homomorphic encryption for arithmetic of approximate\n  numbers","author":"Jung Hee Cheon","year":"2017"},{"key":"ref41:Cheby1854","first-page":"539","article-title":"Memoires des savants etrangers pr\u00e9sent\u00e9s \u00e1\n  l'acad\u00e9mie de Saint-P\u00e9tersbourg","volume":"7","author":"Pafnuty Lvovich Chebyshev","year":"1854","journal-title":"Ch. Th\u00e9orie des m\u00e9canismes connus sous le nom de\n  parall\u00e9logrammes"},{"key":"ref42:Rap1702","volume-title":"Analysis aequationum universalis","volume":"1","author":"Joseph Raphson","year":"1702"},{"volume-title":"Applications of division by convergence","year":"1964","author":"Robert E. Goldschmidt","key":"ref43:Gol64"},{"key":"ref44:AlBa22","series-title":"WAHC'22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1145\/3560827.3563379","article-title":"OpenFHE: Open-source fully homomorphic encryption\n  library","author":"Ahmad Al Badawi","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450398770"},{"volume-title":"Arithmetic using word-wise homomorphic encryption","year":"2015","author":"Gizem Selcan Cetin","key":"ref45:CeDoSuMa15"},{"key":"ref46:ChKiKiLeLe19","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-030-34621-8_15","article-title":"Numerical method for comparison on homomorphically\n  encrypted numbers","author":"Jung Hee Cheon","year":"2019"},{"key":"ref47:KaKi21","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/RTCSA52859.2021.00016","article-title":"A homomorphic encryption-based adaptive image filter using\n  division over encrypted data","author":"Sharmila Devi Kannivelu","year":"2021"},{"key":"ref48:IlIzMePe22","doi-asserted-by":"publisher","first-page":"670","DOI":"10.56553\/popets-2022-0127","article-title":"Homomorphically counting elements with the same property","volume":"4","author":"Ilia Iliashenko","year":"2022","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"ref49:bmi_video","doi-asserted-by":"crossref","DOI":"10.56553\/popets-2022-0127","volume-title":"Homomorphically counting elements with the same property","author":"Ilia Iliashenko","year":"2022"},{"key":"ref50:Montg87","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1090\/s0025-5718-1987-0866113-7","article-title":"Speeding the Pollard and elliptic curve methods of\n  factorization","volume":"48","author":"Peter Lawrence Montgomery","year":"1987","journal-title":"Mathematics of Computation"},{"volume-title":"Simultaneous field divisions: an extension of Montgomery's\n  trick","year":"2008","author":"David G. Harris","key":"ref51:Har08"},{"key":"ref52:ChSoYh22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.4134\/JKMS.j200650","article-title":"Practical FHE parameters against lattice attacks","volume":"59","author":"Jung Hee Cheon","year":"2022","journal-title":"J. Korean Math. Soc"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:25:26Z","timestamp":1744147526000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":52,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/abe0iv7sf","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2025-01-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-1-59"}}