{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T04:13:31Z","timestamp":1777349611212,"version":"3.51.4"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>Fully Homomorphic Encryption (FHE) enables computation directly on encrypted data. This property is desirable for outsourced computation of sensitive data as it relies solely on the underlying security of the cryptosystem and not in access control policies. Even though FHE is still significantly slower than unencrypted computation, practical times are possible for applications easily representable as low-order polynomials, since most FHE schemes support modular addition and multiplication over ciphertexts. If, however, an application cannot be expressed with low-order polynomials, then Boolean logic must be emulated. This bit-level arithmetic enables any computation to be performed homomorphically. Nevertheless, as it runs on top of the natively supported modular arithmetic, it has poor performance, which hinders its use in the majority of scenarios. In this work, we propose Bridging, a technique that allows conversion from bit-level to modular arithmetic and vice-versa. This enables the use of the comprehensive computation provided by bit-level arithmetic and the performance of modular arithmetic within the same application. Experimental results show that Bridging can lead to 1-2 orders of magnitude performance improvement for tested benchmarks and two real-world applications: URL denylisting and genotype imputation. Bridging performance comes from two factors: reduced number of operations and smaller multiplicative depth.<\/jats:p>","DOI":"10.1145\/3665280","type":"journal-article","created":{"date-parts":[[2024,5,16]],"date-time":"2024-05-16T11:25:23Z","timestamp":1715858723000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Coupling bit and modular arithmetic for efficient general-purpose fully homomorphic encryption"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1938-912X","authenticated-orcid":false,"given":"Eduardo","family":"Chielle","sequence":"first","affiliation":[{"name":"Center for Cyber Security, New York University Abu Dhabi, Abu Dhabi, United Arab Emirates"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5131-9044","authenticated-orcid":false,"given":"Oleg","family":"Mazonka","sequence":"additional","affiliation":[{"name":"Center for Cyber Security, New York University Abu Dhabi, Abu Dhabi, United Arab Emirates"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3256-783X","authenticated-orcid":false,"given":"Homer","family":"Gamil","sequence":"additional","affiliation":[{"name":"Center for Cyber Security, New York University Abu Dhabi, Abu Dhabi United Arab Emirates"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6899-0651","authenticated-orcid":false,"given":"Michail","family":"Maniatakos","sequence":"additional","affiliation":[{"name":"Center for Cyber Security, New York University Abu Dhabi, Abu Dhabi, United Arab Emirates"}]}],"member":"320","published-online":{"date-parts":[[2024,6,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1515\/jmc-2019-0026"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_50"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2633600"},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1145\/3314221.3314605","volume-title":"ACM Conference on Programming Language Design and Implementation","author":"Cauligi Sunjay","year":"2019","unstructured":"Sunjay Cauligi, Gary Soeller, Brian Johannesmeyer, Fraser Brown, Riad S. Wahby, John Renner, Benjamin Gr\u00e9goire, Gilles Barthe, Ranjit Jhala, and Deian Stefan. 2019. FaCT: A DSL for timing-sensitive computation. In ACM Conference on Programming Language Design and Implementation. 174\u2013189."},{"key":"e_1_3_3_7_2","first-page":"360","volume-title":"EUROCRYPT","author":"Cheon Jung Hee","year":"2018","unstructured":"Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. 2018. Bootstrapping for approximate homomorphic encryption. In EUROCRYPT. Springer, 360\u2013384."},{"key":"e_1_3_3_8_2","article-title":"Homomorphic Encryption for Arithmetic of Approximate Numbers","author":"Cheon Jung Hee","year":"2016","unstructured":"Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2016. Homomorphic Encryption for Arithmetic of Approximate Numbers. Cryptology ePrint Archive, Report 2016\/421. https:\/\/eprint.iacr.org\/2016\/421","journal-title":"Cryptology ePrint Archive, Report 2016\/421"},{"key":"e_1_3_3_9_2","first-page":"409","volume-title":"ASIACRYPT","author":"Cheon Jung Hee","year":"2017","unstructured":"Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic encryption for arithmetic of approximate numbers. In ASIACRYPT. Springer, 409\u2013437."},{"key":"e_1_3_3_10_2","volume-title":"Design, Automation and Test in Europe Conference","author":"Chielle Eduardo","year":"2021","unstructured":"Eduardo Chielle, Homer Gamil, and Michail Maniatakos. 2021. Real-time private membership test using homomorphic encryption. In Design, Automation and Test in Europe Conference."},{"key":"e_1_3_3_11_2","article-title":"E \\(^3\\) : A Framework for Compiling C++ Programs with Encrypted Operands","author":"Chielle Eduardo","year":"2018","unstructured":"Eduardo Chielle, Oleg Mazonka, Nektarios Georgios Tsoutsos, and Michail Maniatakos. 2018. E \\(^3\\) : A Framework for Compiling C++ Programs with Encrypted Operands. Cryptology ePrint Archive, Report 2018\/1013. Online: https:\/\/eprint.iacr.org\/2018\/1013, GitHub repository: https:\/\/github.com\/momalab\/e3","journal-title":"Cryptology ePrint Archive, Report 2018\/1013"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53887-6_1"},{"key":"e_1_3_3_13_2","first-page":"1020","volume-title":"ACM Conference on Computer and Communications Security (CCS)","author":"Crockett Eric","year":"2018","unstructured":"Eric Crockett, Chris Peikert, and Chad Sharp. 2018. Alchemy: A language and compiler for homomorphic encryption made easy. In ACM Conference on Computer and Communications Security (CCS). 1020\u20131037."},{"key":"e_1_3_3_14_2","first-page":"617","volume-title":"EUROCRYPT","author":"Ducas L\u00e9o","year":"2015","unstructured":"L\u00e9o Ducas and Daniele Micciancio. 2015. FHEW: Bootstrapping homomorphic encryption in less than a second. In EUROCRYPT. Springer, 617\u2013640."},{"key":"e_1_3_3_15_2","first-page":"144","article-title":"Somewhat practical fully homomorphic encryption.","volume":"2012","author":"Fan Junfeng","year":"2012","unstructured":"Junfeng Fan and Frederik Vercauteren. 2012. Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive 2012 (2012), 144.","journal-title":"IACR Cryptology ePrint Archive"},{"issue":"1","key":"e_1_3_3_16_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.3390\/cryptography6010013","article-title":"On the IND-CCA1 security of FHE schemes","volume":"6","author":"Fauzi Prastudy","year":"2022","unstructured":"Prastudy Fauzi, Martha Norberg Hovd, and H\u00e5vard Raddum. 2022. On the IND-CCA1 security of FHE schemes. Cryptography 6, 1 (2022), 13.","journal-title":"Cryptography"},{"key":"e_1_3_3_17_2","volume-title":"A Fully Homomorphic Encryption Scheme","author":"Gentry Craig","year":"2009","unstructured":"Craig Gentry. 2009. A Fully Homomorphic Encryption Scheme. Vol. 20. Stanford University, Stanford."},{"key":"e_1_3_3_18_2","first-page":"169","volume-title":"41st Annual ACM Symposium on Theory of Computing","author":"Gentry Craig","year":"2009","unstructured":"Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In 41st Annual ACM Symposium on Theory of Computing. 169\u2013178."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"e_1_3_3_20_2","first-page":"201","volume-title":"International Conference on Machine Learning","author":"Gilad-Bachrach Ran","year":"2016","unstructured":"Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2016. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International Conference on Machine Learning. 201\u2013210."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2021.10.003"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/978-3-662-46800-5_25","volume-title":"Advances in Cryptology\u2013EUROCRYPT 2015","author":"Halevi Shai","year":"2015","unstructured":"Shai Halevi and Victor Shoup. 2015. Bootstrapping for HElib. In Advances in Cryptology\u2013EUROCRYPT 2015. Springer, 641\u2013670. GitHub (commit #65ef24c): github.com\/homenc\/HElib\/tree\/master\/src\/ Test_bootstrapping.cpp."},{"key":"e_1_3_3_23_2","article-title":"Faster Homomorphic Linear Transformations in HElib","author":"Halevi Shai","year":"2018","unstructured":"Shai Halevi and Victor Shoup. 2018. Faster Homomorphic Linear Transformations in HElib. Cryptology ePrint Archive, Report 2018\/244. https:\/\/eprint.iacr.org\/2018\/244","journal-title":"Cryptology ePrint Archive, Report 2018\/244"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3474366.3486923"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00002"},{"issue":"5","key":"e_1_3_3_26_2","first-page":"845","article-title":"Leakage resilient leveled FHE on multiple bits message","volume":"7","author":"Li Zengpeng","year":"2017","unstructured":"Zengpeng Li, Chunguang Ma, and Ding Wang. 2017. Leakage resilient leveled FHE on multiple bits message. IEEE Transactions on Big Data 7, 5 (2017), 845\u2013858.","journal-title":"IEEE Transactions on Big Data"},{"issue":"3","key":"e_1_3_3_27_2","first-page":"1885","article-title":"Quantum-safe round-optimal password authentication for mobile devices","volume":"19","author":"Li Zengpeng","year":"2020","unstructured":"Zengpeng Li, Ding Wang, and Eduardo Morais. 2020. Quantum-safe round-optimal password authentication for mobile devices. IEEE Transactions on Dependable and Secure Computing 19, 3 (2020), 1885\u20131899.","journal-title":"IEEE Transactions on Dependable and Secure Computing"},{"key":"e_1_3_3_28_2","volume-title":"27th USENIX Security Symposium (USENIX Security 18)","author":"Lipp Moritz","year":"2018","unstructured":"Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Anders Fogh, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. 2018. Meltdown: Reading kernel memory from user space. In 27th USENIX Security Symposium (USENIX Security 18)."},{"key":"e_1_3_3_29_2","first-page":"1057","volume-title":"2021 IEEE Symposium on Security and Privacy (SP)","author":"Lu Wen-jie","year":"2021","unstructured":"Wen-jie Lu, Zhicong Huang, Cheng Hong, Yiping Ma, and Hunter Qu. 2021. PEGASUS: Bridging polynomial and non-polynomial evaluations in homomorphic encryption. In 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 1057\u20131073."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2016.2569062"},{"key":"e_1_3_3_31_2","unstructured":"Christian Vincent Mouchet Jean-Philippe Bossuat Juan Ram\u00f3n Troncoso-Pastoriza and Jean-Pierre Hubaux. 2020. Lattigo: A multiparty homomorphic encryption library in go. In Proceedings of the 8th Workshop on Encrypted Computing and Applied Homomorphic Cryptography. 64\u201370."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/LCA.2018.2812814"},{"key":"e_1_3_3_33_2","article-title":"Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP","author":"Mukherjee Tamalika","year":"2019","unstructured":"Tamalika Mukherjee and Noah Stephens-Davidowitz. 2019. Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP. Cryptology ePrint Archive, Report 2019\/1142. https:\/\/eprint.iacr.org\/2019\/1142","journal-title":"Cryptology ePrint Archive, Report 2019\/1142"},{"key":"e_1_3_3_34_2","unstructured":"nuFHE 2018. NuCypher fully homomorphic encryption (NuFHE). https:\/\/github.com\/nucypher\/nufhe. NuCypher."},{"key":"e_1_3_3_35_2","unstructured":"Yuriy Polyakov Kurt Rohloff Gerard W. Ryan and Dave Cousins. 2020. PALISADE Lattice Cryptography Library User Manual (v.1.10.6). https:\/\/palisade-crypto.org\/documentation"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480070"},{"key":"e_1_3_3_37_2","unstructured":"SEAL 2019. Microsoft SEAL (release 3.3.2). https:\/\/github.com\/Microsoft\/SEAL. Microsoft Research Redmond WA."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-012-9720-4"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00089"},{"issue":"4","key":"e_1_3_3_40_2","first-page":"708","article-title":"Two birds with one stone: Two-factor authentication with security beyond conventional bound","volume":"15","author":"Wang Ding","year":"2016","unstructured":"Ding Wang and Ping Wang. 2016. Two birds with one stone: Two-factor authentication with security beyond conventional bound. IEEE Transactions on Dependable and Secure Computing 15, 4 (2016), 708\u2013722.","journal-title":"IEEE Transactions on Dependable and Secure Computing"},{"key":"e_1_3_3_41_2","article-title":"Quantum2fa: Efficient quantum-resistant two-factor authentication scheme for mobile devices","author":"Wang Qingxuan","year":"2021","unstructured":"Qingxuan Wang, Ding Wang, Chi Cheng, and Debiao He. 2021. Quantum2fa: Efficient quantum-resistant two-factor authentication scheme for mobile devices. IEEE Transactions on Dependable and Secure Computing (2021).","journal-title":"IEEE Transactions on Dependable and Secure Computing"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665280","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3665280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:34Z","timestamp":1750294714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3665280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3665280"],"URL":"https:\/\/doi.org\/10.1145\/3665280","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2023-10-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}