Verifiable FHE via Lattice-based SNARKs

Shahla Atapoor; Karim Baghery; Hilder V. L. Pereira; Jannik Spiessens

doi:10.62056/a6ksdkp10

Verifiable FHE via Lattice-based SNARKs

Authors

Shahla Atapoor, Karim Baghery, Hilder V. L. Pereira, Jannik Spiessens

Shahla Atapoor

COSIC, KU Leuven, Leuven, Belgium
shahla dot atapoor at esat dot kuleuven dot be

Karim Baghery

COSIC, KU Leuven, Leuven, Belgium
karim dot baghery at esat dot kuleuven dot be

Hilder V. L. Pereira

Universidade de Campinas (UNICAMP), Campinas, Brazil
hilder at unicamp dot br

Jannik Spiessens

COSIC, KU Leuven, Leuven, Belgium
jannik dot spiessens at esat dot kuleuven dot be

Keywords: Fully-Homomorphic Encryption Verifiable FHE Lattice-based SNARKs Computation on Encrypted Data

Abstract

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.

References

[ACGSV23]

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.

Google Scholar ePrint

[APS15]

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. https://doi.org/10.1515/jmc-2015-0016.

Google Scholar ePrint

[BCFK21]

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. https://doi.org/10.1007/978-3-030-75248-4_19.

Google Scholar ePrint

[BCI⁺13]

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. https://doi.org/10.1007/978-3-642-36594-2_18.

Google Scholar ePrint

[BGGJ19]

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. https://doi.org/10.1007/978-3-030-20951-3_20.

Google Scholar ePrint

[BGV12]

Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012, 309–325. January 2012. ACM. https://doi.org/10.1145/2090236.2090262.

Google Scholar ePrint

[BISW17]

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. https://doi.org/10.1007/978-3-319-56617-7_9.

Google Scholar ePrint

[BPTG15]

Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. Machine learning classification over encrypted data. In NDSS 2015. February 2015. The Internet Society. https://doi.org/?

Google Scholar ePrint

[CDNP23]

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. https://doi.org/10.1145/3576915.3624388.

Google Scholar ePrint

[CGG16]

Ilaria Chillotti, Nicolas Gama, and Louis Goubin. Attacking FHE-based applications by software fault injections. 2016.

Google Scholar ePrint

[CKKS17]

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. https://doi.org/10.1007/978-3-319-70694-8_15.

Google Scholar ePrint

[CT15]

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. https://doi.org/10.1007/978-3-319-16295-9_13.

Google Scholar ePrint

[FGP14]

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. https://doi.org/10.1145/2660267.2660366.

Google Scholar ePrint

[FNP20]

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. https://doi.org/10.1007/978-3-030-45388-6_5.

Google Scholar ePrint

[FV12]

Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. 2012.

Google Scholar ePrint

[GGP10]

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. https://doi.org/10.1007/978-3-642-14623-7_25.

Google Scholar ePrint

[GGPR13]

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. https://doi.org/10.1007/978-3-642-38348-9_37.

Google Scholar ePrint

[GGW23]

Sanjam Garg, Aarushi Goel, and Mingyuan Wang. How to prove statements obliviously? 2023.

Google Scholar ePrint

[GKP⁺13]

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. https://doi.org/10.1007/978-3-642-40084-1_30.

Google Scholar ePrint

[GKR08]

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. https://doi.org/10.1145/1374376.1374396.

Google Scholar ePrint

[GMNO18]

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. https://doi.org/10.1145/3243734.3243845.

Google Scholar ePrint

[GNS23]

Chaya Ganesh, Anca Nitulescu, and Eduardo Soria-Vazquez. Rinocchio: SNARKs for ring arithmetic. Journal of Cryptology, 36(4):41, October 2023. https://doi.org/10.1007/s00145-023-09481-3.

Google Scholar ePrint

[Gro16]

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. https://doi.org/10.1007/978-3-662-49896-5_11.

Google Scholar ePrint

[GWC19]

Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. 2019.

Google Scholar ePrint

[ISW21]

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. https://doi.org/10.1145/3460120.3484572.

Google Scholar ePrint

[KPZ21]

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. https://doi.org/10.1007/978-3-030-92078-4_21.

Google Scholar ePrint

[LMPR08]

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. https://doi.org/10.1007/978-3-540-71039-4_4.

Google Scholar ePrint

[vGHV10]

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. https://doi.org/10.1007/978-3-642-13190-5_2.

Google Scholar ePrint

[VKH23]

Alexander Viand, Christian Knabenhans, and Anwar Hithnawi. Verifiable fully homomorphic encryption. CoRR, 2023. https://doi.org/10.48550/arXiv.2301.07041.

Google Scholar ePrint

[ZAM23]

ZAMA. fhEVM. 2023.

Google Scholar ePrint

[Zuc18]

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.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a6ksdkp10

History

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.

License

Copyright is held by the author(s)

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

@article{CiC-1-1-24,
    author = "Atapoor, Shahla and Baghery, Karim and Pereira, Hilder V. L. and Spiessens, Jannik",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Verifiable {FHE} via Lattice-based {SNARK}s",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a6ksdkp10"
}

TY - JOUR
AU - Atapoor, Shahla
AU - Baghery, Karim
AU - Pereira, Hilder
AU - Spiessens, Jannik
PY - 2024
TI - Verifiable FHE via Lattice-based SNARKs
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 1
DO - 10.62056/a6ksdkp10
UR - https://doi.org/10.62056/a6ksdkp10
AB - <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. </p>
ER -

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.