Paper 2024/1764

Fully Homomorphic Encryption with Efficient Public Verification

Mi-Ying (Miryam) Huang, University of Southern California
Baiyu Li, Google (United States)
Xinyu Mao, University of Southern California
Jiapeng Zhang, University of Southern California
Abstract

We present an efficient Publicly Verifiable Fully Homomorphic Encryption scheme that, along with being able to evaluate arbitrary boolean circuits over ciphertexts, also generates a succinct proof of correct homomorphic computation. Our scheme is based on FHEW proposed by Ducas and Micciancio (Eurocrypt'15), and we incorporate the GINX homomorphic accumulator (Eurocrypt'16) for improved bootstrapping efficiency. In order to generate the proof efficiently, we generalize the widely used Rank-1 Constraint System (R1CS) to the ring setting and obtain Ring R1CS, to natively express homomorphic computation in FHEW. In particular, we develop techniques to efficiently express in our Ring R1CS the "non-arithmetic" operations, such as gadget decomposition and modulus switching used in the FHEW construction. We further construct a SNARG for Ring R1CS instances, by translating the Ring R1CS instance into a sum-check protocol over polynomials, and then compiling it into a succinct non-interactive proof by incorporating the lattice-based polynomial commitment scheme of Cini, Malavolta, Nguyen, and Wee (Crypto'24). Putting together, our Publicly Verifiable FHE scheme relies on standard hardness assumptions about lattice problems such that it generates a succinct proof of homomorphic computation of circuit $C$ in time $O(|C|^2\cdot poly(\lambda))$ and of size $O(\log^2{|C|}\cdot poly(\lambda))$. Besides, our scheme achieves the recently proposed IND-SA (indistinguishability under semi-active attack) security by Walter (EPrint 2024/1207) that exactly captures client data privacy when a homomorphic computation can be verified.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
FHESNARGsVerifiable Computation
Contact author(s)
miying huang @ usc edu
baiyuli @ google com
xinyumao @ usc edu
jiapengz @ usc edu
History
2024-10-30: approved
2024-10-29: received
See all versions
Short URL
https://ia.cr/2024/1764
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1764,
      author = {Mi-Ying (Miryam) Huang and Baiyu Li and Xinyu Mao and Jiapeng Zhang},
      title = {Fully Homomorphic Encryption with Efficient Public Verification},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1764},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1764}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.