Communications in Cryptology IACR CiC

Verifiable FHE via Lattice-based SNARKs


Shahla Atapoor, Karim Baghery, Hilder V. L. Pereira, Jannik Spiessens
Shahla Atapoor ORCID
COSIC, KU Leuven, Leuven, Belgium
shahla dot atapoor at esat dot kuleuven dot be
Karim Baghery ORCID
COSIC, KU Leuven, Leuven, Belgium
karim dot baghery at esat dot kuleuven dot be
Hilder V. L. Pereira ORCID
Universidade de Campinas (UNICAMP), Campinas, Brazil
hilder at unicamp dot br
Jannik Spiessens ORCID
COSIC, KU Leuven, Leuven, Belgium
jannik dot spiessens at esat dot kuleuven dot be


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 >100 ciphertexts in less than 1 second while maintaining reasonable prover costs.


Diego F. Aranha, Anamaria Costache, Antonio Guimarães, and Eduardo Soria-Vazquez. Heliopolis: verifiable computation over homomorphically encrypted data from interactive oracle proofs is practical. 2023.
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015.
Alexandre Bois, Ignacio Cascudo, Dario Fiore, and Dongwoo Kim. Flexible and efficient verifiable computation on encrypted data. In Juan Garay, editor, PKC 2021, Part II, volume 12711 of LNCS, 528–558. May 2021. Springer, Heidelberg.
Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct non-interactive arguments via linear interactive proofs. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, 315–333. March 2013. Springer, Heidelberg.
Christina Boura, Nicolas Gama, Mariya Georgieva, and Dimitar Jetchev. Simulating homomorphic evaluation of deep learning predictions. In Shlomi Dolev, Danny Hendler, Sachin Lodha, and Moti Yung, editors, Cyber Security Cryptography and Machine Learning, 212–230. Cham, 2019. Springer International Publishing.
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012, 309–325. January 2012. ACM.
Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu. Lattice-based SNARGs and their application to more efficient obfuscation. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, 247–277. April / May 2017. Springer, Heidelberg.
Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. Machine learning classification over encrypted data. In NDSS 2015. February 2015. The Internet Society.
Kelong Cong, Debajyoti Das, Georgio Nicolas, and Jeongeun Park. Poster: panacea — stateless and non-interactive oblivious ram. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS '23, 3585–3587. New York, NY, USA, 2023. Association for Computing Machinery.
Ilaria Chillotti, Nicolas Gama, and Louis Goubin. Attacking FHE-based applications by software fault injections. 2016.
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, 409–437. December 2017. Springer, Heidelberg.
Massimo Chenal and Qiang Tang. On key recovery attacks against existing somewhat homomorphic encryption schemes. In Diego F. Aranha and Alfred Menezes, editors, LATINCRYPT 2014, volume 8895 of LNCS, 239–258. September 2015. Springer, Heidelberg.
Dario Fiore, Rosario Gennaro, and Valerio Pastro. Efficiently verifiable computation on encrypted data. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, ACM CCS 2014, 844–855. November 2014. ACM Press.
Dario Fiore, Anca Nitulescu, and David Pointcheval. Boosting verifiable computation on encrypted data. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part II, volume 12111 of LNCS, 124–154. May 2020. Springer, Heidelberg.
Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. 2012.
Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: outsourcing computation to untrusted workers. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, 465–482. August 2010. Springer, Heidelberg.
Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, 626–645. May 2013. Springer, Heidelberg.
Sanjam Garg, Aarushi Goel, and Mingyuan Wang. How to prove statements obliviously? 2023.
Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. How to run Turing machines on encrypted data. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, 536–553. August 2013. Springer, Heidelberg.
Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, 113–122. May 2008. ACM Press.
Rosario Gennaro, Michele Minelli, Anca Nitulescu, and Michele Orrù. Lattice-based zk-SNARKs from square span programs. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, 556–573. October 2018. ACM Press.
Chaya Ganesh, Anca Nitulescu, and Eduardo Soria-Vazquez. Rinocchio: SNARKs for ring arithmetic. Journal of Cryptology, 36(4):41, October 2023.
Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, 305–326. May 2016. Springer, Heidelberg.
Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. 2019.
Yuval Ishai, Hang Su, and David J. Wu. Shorter and faster post-quantum designated-verifier zkSNARKs from lattices. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021, 212–234. November 2021. ACM Press.
Andrey Kim, Yuriy Polyakov, and Vincent Zucca. Revisiting homomorphic encryption schemes for finite fields. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, 608–639. December 2021. Springer, Heidelberg.
Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen. SWIFFT: a modest proposal for FFT hashing. In Kaisa Nyberg, editor, FSE 2008, volume 5086 of LNCS, 54–72. February 2008. Springer, Heidelberg.
Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, 24–43. May / June 2010. Springer, Heidelberg.
Alexander Viand, Christian Knabenhans, and Anwar Hithnawi. Verifiable fully homomorphic encryption. CoRR, 2023.
ZAMA. fhEVM. 2023.
Vincent Zucca. Towards Efficient Arithmetic for Ring-LWE based Homomorphic Encryption. (Vers une arithmétique efficace pour le chiffrement homomorphe basé sur le Ring-LWE). PhD thesis, Pierre and Marie Curie University, Paris, France, 2018.

PDFPDF Open access

Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Shahla Atapoor, Karim Baghery, Hilder V. L. Pereira, and Jannik Spiessens, "Verifiable FHE via Lattice-based SNARKs," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a6ksdkp10.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.