{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T13:29:52Z","timestamp":1778160592973,"version":"3.51.4"},"reference-count":31,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"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":[[2024,3,5]]},"abstract":"<jats:p>Fully Homomorphic Encryption (FHE) is a prevalent cryptographic primitive that allows for computation on encrypted data. In various cryptographic protocols, this enables outsourcing computation to a third party while retaining the privacy of the inputs to the computation. However, these schemes make an honest-but-curious assumption about the adversary. Previous work has tried to remove this assumption by combining FHE with Verifiable Computation (VC). Recent work has increased the flexibility of this approach by introducing integrity checks for homomorphic computations over rings. However, efficient FHE for circuits of large multiplicative depth also requires non-ring computations called maintenance operations, i.e. modswitching and keyswitching, which cannot be efficiently verified by existing constructions. We propose the first efficiently verifiable FHE scheme that allows for arbitrary depth homomorphic circuits by utilizing the double-CRT representation in which FHE schemes are typically computed, and using lattice-based SNARKs to prove components of this computation separately, including the maintenance operations. Therefore, our construction can theoretically handle bootstrapping operations. We also present the first implementation of a verifiable computation on encrypted data for a computation that contains multiple ciphertext-ciphertext multiplications. Concretely, we verify the homomorphic computation of an approximate neural network containing three layers and &gt;100 ciphertexts in less than 1 second while maintaining reasonable prover costs. <\/jats:p>","DOI":"10.62056\/a6ksdkp10","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T19:27:10Z","timestamp":1712690830000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":13,"title":["Verifiable FHE via Lattice-based SNARKs"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6035-9520","authenticated-orcid":false,"given":"Shahla","family":"Atapoor","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7213-8496","authenticated-orcid":false,"given":"Karim","family":"Baghery","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1303-3760","authenticated-orcid":false,"given":"Hilder","family":"Pereira","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04wffgt70","id-type":"ROR","asserted-by":"publisher"}],"name":"Universidade de Campinas (UNICAMP)","place":["Campinas, Brazil"],"department":["Instituto de Computa\ufffd\ufffdo"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-4738-5758","authenticated-orcid":false,"given":"Jannik","family":"Spiessens","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"ref1:panacea","series-title":"CCS '23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"3585","DOI":"10.1145\/3576915.3624388","article-title":"Poster: Panacea \u2014 Stateless and Non-Interactive Oblivious\n  RAM","volume-title":"Proceedings of the 2023 ACM SIGSAC Conference on Computer\n  and Communications Security","author":"Kelong Cong","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9798400700507"},{"key":"ref2:NDSS:BPTG15","article-title":"Machine Learning Classification over Encrypted Data","volume-title":"NDSS\u00a02015","author":"Raphael Bost","year":"2015"},{"key":"ref3:mlaas","isbn-type":"print","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-030-20951-3_20","article-title":"Simulating Homomorphic Evaluation of Deep Learning\n  Predictions","volume-title":"Cyber Security Cryptography and Machine Learning","author":"Christina Boura","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030209513"},{"key":"ref4:fhevm","article-title":"fhEVM","author":"ZAMA","year":"2023"},{"key":"ref5:ARXIV:ViaKnaHit23","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2301.07041","article-title":"Verifiable Fully Homomorphic Encryption","volume":"abs\/2301.07041","author":"Alexander Viand","year":"2023","journal-title":"CoRR"},{"key":"ref6:LC:CheTan14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-319-16295-9_13","article-title":"On Key Recovery Attacks Against Existing Somewhat\n  Homomorphic Encryption Schemes","volume-title":"LATINCRYPT\u00a02014","volume":"8895","author":"Massimo Chenal","year":"2015"},{"key":"ref7:EPRINT:ChiGamGou16","article-title":"Attacking FHE-based applications by software fault\n  injections","author":"Ilaria Chillotti","year":"2016"},{"key":"ref8:CCS:FioGenPas14","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/2660267.2660366","article-title":"Efficiently Verifiable Computation on Encrypted Data","volume-title":"ACM CCS 2014","author":"Dario Fiore","year":"2014"},{"key":"ref9:JC:GanNitSor23","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00145-023-09481-3","article-title":"Rinocchio: SNARKs for Ring Arithmetic","volume":"36","author":"Chaya Ganesh","year":"2023","journal-title":"Journal of Cryptology"},{"key":"ref10:PKC:BCFK21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/978-3-030-75248-4_19","article-title":"Flexible and Efficient Verifiable Computation on Encrypted\n  Data","volume-title":"PKC\u00a02021, Part\u00a0II","volume":"12711","author":"Alexandre Bois","year":"2021"},{"key":"ref11:EC:Groth16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","article-title":"On the Size of Pairing-Based Non-interactive Arguments","volume-title":"EUROCRYPT\u00a02016, Part\u00a0II","volume":"9666","author":"Jens Groth","year":"2016"},{"key":"ref12:EPRINT:GabWilCio19","article-title":"PLONK: Permutations over Lagrange-bases for Oecumenical\n  Noninteractive arguments of Knowledge","author":"Ariel Gabizon","year":"2019"},{"key":"ref13:CCS:GMNO18","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1145\/3243734.3243845","article-title":"Lattice-Based zk-SNARKs from Square Span Programs","volume-title":"ACM CCS 2018","author":"Rosario Gennaro","year":"2018"},{"key":"ref14:CCS:IshSuWu21","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/3460120.3484572","article-title":"Shorter and Faster Post-Quantum Designated-Verifier\n  zkSNARKs from Lattices","volume-title":"ACM CCS 2021","author":"Yuval Ishai","year":"2021"},{"key":"ref15:ITCS:BraGenVai12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/2090236.2090262","article-title":"(Leveled) fully homomorphic encryption without\n  bootstrapping","volume-title":"ITCS 2012","author":"Zvika Brakerski","year":"2012"},{"key":"ref16:EPRINT:FanVer12","article-title":"Somewhat Practical Fully Homomorphic Encryption","author":"Junfeng Fan","year":"2012"},{"key":"ref17:AC:CKKS17","series-title":"LNCS","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","volume-title":"ASIACRYPT\u00a02017, Part\u00a0I","volume":"10624","author":"Jung Hee Cheon","year":"2017"},{"key":"ref18:FSE:LMPR08","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-71039-4_4","article-title":"SWIFFT: A Modest Proposal for FFT Hashing","volume-title":"FSE\u00a02008","volume":"5086","author":"Vadim Lyubashevsky","year":"2008"},{"key":"ref19:zucca18","article-title":"Towards Efficient Arithmetic for Ring-LWE based Homomorphic\n  Encryption. (Vers une arithm\u00e9tique efficace pour le chiffrement\n  homomorphe bas\u00e9 sur le Ring-LWE)","author":"Vincent Zucca","year":"2018"},{"key":"ref20:AC:KimPolZuc21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-030-92078-4_21","article-title":"Revisiting Homomorphic Encryption Schemes for Finite\n  Fields","volume-title":"ASIACRYPT\u00a02021, Part\u00a0III","volume":"13092","author":"Andrey Kim","year":"2021"},{"key":"ref21:EC:vGHV10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","article-title":"Fully Homomorphic Encryption over the Integers","volume-title":"EUROCRYPT\u00a02010","volume":"6110","author":"Marten van Dijk","year":"2010"},{"key":"ref22:C:GenGenPar10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-14623-7_25","article-title":"Non-interactive Verifiable Computing: Outsourcing\n  Computation to Untrusted Workers","volume-title":"CRYPTO\u00a02010","volume":"6223","author":"Rosario Gennaro","year":"2010"},{"key":"ref23:C:GKPVZ13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-642-40084-1_30","article-title":"How to Run Turing Machines on Encrypted Data","volume-title":"CRYPTO\u00a02013, Part\u00a0II","volume":"8043","author":"Shafi Goldwasser","year":"2013"},{"key":"ref24:PKC:FioNitPoi20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-030-45388-6_5","article-title":"Boosting Verifiable Computation on Encrypted Data","volume-title":"PKC\u00a02020, Part\u00a0II","volume":"12111","author":"Dario Fiore","year":"2020"},{"key":"ref25:cryptoeprint:2023\/1609","article-title":"How to Prove Statements Obliviously?","author":"Sanjam Garg","year":"2023"},{"key":"ref26:cryptoeprint:2023\/1949","article-title":"HELIOPOLIS: Verifiable Computation over Homomorphically\n  Encrypted Data from Interactive Oracle Proofs is Practical","author":"Diego F. Aranha","year":"2023"},{"key":"ref27:STOC:GolKalRot08","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1145\/1374376.1374396","article-title":"Delegating computation: interactive proofs for muggles","volume-title":"40th ACM STOC","author":"Shafi Goldwasser","year":"2008"},{"key":"ref28:Albrecht","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of Learning with Errors","volume":"9","author":"Martin R. Albrecht","year":"2015","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref29:TCC:BCIOP13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-36594-2_18","article-title":"Succinct Non-interactive Arguments via Linear Interactive\n  Proofs","volume-title":"TCC\u00a02013","volume":"7785","author":"Nir Bitansky","year":"2013"},{"key":"ref30:EC:BISW17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-319-56617-7_9","article-title":"Lattice-Based SNARGs and Their Application to More\n  Efficient Obfuscation","volume-title":"EUROCRYPT\u00a02017, Part\u00a0III","volume":"10212","author":"Dan Boneh","year":"2017"},{"key":"ref31:EC:GGPR13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-38348-9_37","article-title":"Quadratic Span Programs and Succinct NIZKs without\n  PCPs","volume-title":"EUROCRYPT\u00a02013","volume":"7881","author":"Rosario Gennaro","year":"2013"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:25:32Z","timestamp":1733865932000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/1\/24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":31,"URL":"https:\/\/doi.org\/10.62056\/a6ksdkp10","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"2024-01-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-1-60"}}