The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$
Abstract
A fully homomorphic encryption (FHE) scheme allows anyone to transform an encryption of a message, $m$, into an encryption of any (efficient) function of that message, $f(m)$, without knowing the secret key. We present a leveled FHE scheme that is based solely on the (standard) learning with errors ($\mathsf{LWE}$) assumption. (Leveled FHE schemes are initialized with a bound on the maximal evaluation depth. However, this restriction can be removed by assuming “weak circular security.'') Applying known results on $\mathsf{LWE}$, the security of our scheme is based on the worst-case hardness of “short vector problems” on arbitrary lattices. Our construction improves on previous works in two aspects: 1. We show that “somewhat homomorphic” encryption can be based on $\mathsf{LWE}$, using a new relinearization technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 2. We deviate from the “squashing paradigm” used in all previous works. We introduce a new dimension-modulus reduction technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, without introducing additional assumptions. Our scheme has very short ciphertexts, and we therefore use it to construct an asymptotically efficient $\mathsf{LWE}$-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is $k\cdot\mathrm{polylog}(k)+\log|\mathtt{DB}|$ bits per single-bit query, in order to achieve security against $2^k$-time adversaries (based on the best known attacks against our underlying assumptions).
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
Factoring polynomials with rational coefficients
Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982) · Mathematische Annalen · doi:10.1007/bf01457454 · Cited by 4,018
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
A hierarchy of polynomial time lattice basis reduction algorithms
Schnorr, C. P. (1987) · Theoretical Computer Science · doi:10.1016/0304-3975(87)90064-8 · Cited by 648
The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
Micciancio, D. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539700373039 · Cited by 212
A first glimpse of cryptography's Holy Grail
Micciancio, D. (2010) · Communications of the ACM · doi:10.1145/1666420.1666445 · Cited by 70
Cited by
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397
Data security and privacy-preserving in edge computing paradigm: survey and open issues
Zhang, J., Chen, B., Zhao, Y., Cheng, X., & Hu, F. (2018) · IEEE Access · doi:10.1109/access.2018.2820162 · Cited by 514
Data Security and Privacy Protection for Cloud Storage: A Survey
Yang, P., Xiong, N., & Ren, J. (2020) · IEEE Access · doi:10.1109/access.2020.3009876 · Cited by 502
A Survey on Big Data Market: Pricing, Trading and Protection
Liang, F., Yu, W., An, D., Yang, Q., Fu, X., & Zhao, W. (2018) · IEEE Access · doi:10.1109/access.2018.2806881 · Cited by 356
Fast Private Set Intersection from Homomorphic Encryption
Chen, H., Laine, K., & Rindal, P. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134061 · Cited by 352
Metadata
- Authors
- Brakerski, Z., & Vaikuntanathan, V.
- Venue
- SIAM Journal on Computing
- Published
- 2014-01
- Volume
- 43
- Issue
- 2
- Pages
- 831-871
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W1979120705
- Cited by
- 538
- References
- 6
- FWCI
- 30.04
- Type
- journal article
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$. https://app.cochat.ai/papers/10.1137/120868669
- The paper
- Brakerski, Z., & Vaikuntanathan, V. (2014). Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$. SIAM Journal on Computing. https://doi.org/10.1137/120868669
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.