The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits
Abstract
We describe a new approach for constructing fully homomorphic encryption (FHE) schemes. Previous FHE schemes all use the same blueprint from [Gentry 2009]: First construct a somewhat homomorphic encryption (SWHE) scheme, next "squash" the decryption circuit until it is simple enough to be handled within the homomorphic capacity of the SWHE scheme, and finally "bootstrap" to get a FHE scheme. In all existing schemes, the squashing technique induces an additional assumption: that the sparse subset sum problem (SSSP) is hard. Our new approach constructs FHE as a hybrid of a SWHE and a multiplicatively homomorphic encryption (MHE) scheme, such as Elgamal. Our construction eliminates the need for the squashing step, and thereby also removes the need to assume the SSSP is hard. We describe a few concrete instantiations of the new method, including a "simple" FHE scheme where we replace SSSP with Decision Diffle-Hellman, an optimization of the simple scheme that let us "compress" the FHE ciphertext into a single Elgamal ciphertext(J), and a scheme whose security can be (quantumly) reduced to the approximate ideal-SIVP. We stress that the new approach still relies on bootstrapping, but it shows how to bootstrap without having to "squash" the decryption circuit. The main technique is to express the decryption function of SWHE schemes as a depth-3 Q2 (Σ Π Σ) arithmetic circuit of a particular form. When evaluating this circuit homomorphically (as needed for bootstrapping), we temporarily switch to a MHE scheme, such as Elgamal, to handle the Π part. Due to the special form of the circuit, the switch to the MHE scheme can be done without having to evaluate anything homomorphically. We then translate the result back to the SWHE scheme by homomorphically evaluating the decryption function of the MHE scheme. Using our method, the SWHE scheme only needs to be capable of evaluating the MHE scheme's decryption function, not its own decryption function. We thereby avoid the circularity that necessitated squashing in the original blueprint.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315
Cited by
Gentry, C., Sahai, A., & Waters, B. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_5 · Cited by 1,492
Self-citationEfficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
(Leveled) Fully Homomorphic Encryption without Bootstrapping
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014) · ACM Transactions on Computation Theory · doi:10.1145/2633600 · Cited by 1,430
Self-citationFully Homomorphic Encryption without Modulus Switching from Classical GapSVP
Brakerski, Z. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_50 · Cited by 1,252
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
Micciancio, D., & Peikert, C. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_41 · Cited by 1,224
Metadata
- Authors
- Gentry, C., & Halevi, S.
- Venue
- 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2011-10
- Volume
- 2011
- Pages
- 107-109
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2129580084
- Cited by
- 214
- References
- 2
- FWCI
- 19.60
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.