Somewhat Practical Fully Homomorphic Encryption¶
Authors: J. Fan; F. Vercauteren
Year: 2012
Venue: CRYPTO 2012 / ePrint 2012
type: scheme collection: catalogue, schemes, sok-references status: auto
Links: ePrint 2012/144
Visual lesson: BFV · Scheme table row: BFV
Summary¶
Auto-extracted summary (unreviewed)
Fan and Vercauteren port Brakerski's LWE-based fully homomorphic encryption scheme to the ring-LWE setting, yielding what is now known as the FV/BFV scheme. They introduce two optimized relinearisation variants with smaller keys and faster computation, give a detailed yet simple analysis with tight worst-case noise bounds for multiplication, relinearisation and bootstrapping (simplified via a modulus-switching trick), and derive concrete parameters for which the scheme is fully homomorphic at a given security level.
Abstract¶
In this paper we port Brakerski’s fully homomorphic scheme based on the Learning With Errors (LWE) problem to the ring-LWE setting. We introduce two optimised versions of relinearisation that not only result in a smaller relinearisation key, but also faster computations. We provide a detailed, but simple analysis of the various homomorphic operations, such as multiplication, relinearisation and bootstrapping, and derive tight worst case bounds on the noise caused by these operations. The analysis of the bootstrapping step is greatly simplified by using a modulus switching trick. Finally, we derive concrete parameters for which the scheme provides a given level of security and becomes fully homomorphic.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Port of Brakerski's scale-invariant LWE FHE scheme to ring-LWE (the FV/BFV scheme) | llm | 0.90 |
| contribution | Two optimized relinearisation methods with smaller relinearisation keys and faster computation | llm | 0.90 |
| contribution | Tight worst-case noise bounds for homomorphic multiplication, relinearisation and bootstrapping | llm | 0.90 |
| contribution | Simplified bootstrapping analysis via a modulus switching trick | llm | 0.90 |
| contribution | Concrete parameters for a fully homomorphic scheme at a given security level | llm | 0.90 |
| schemes | BFV | llm | 0.90 |
| schemes | RLWE | llm | 0.90 |
| tasks | fully homomorphic encryption | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| limitations | Derived noise bounds are worst-case rather than average-case | llm | 0.90 |
| limitations | Implementation and practical aspects deferred to follow-up work | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
Scheme card: BFV¶
| Group | 2. Exact word-wise FHE (BGV / BFV family) |
| Kind | Scheme |
| Hardness assumption | RLWE |
| Plaintext type | Exact integers mod p |
| SIMD packing | Yes |
| Bootstrapping | Yes, slow |
| Post-quantum | Yes |
| Status | Widely used |
| Fit for LLM inference | Most used for linear layers in HE+MPC hybrids such as Cheetah, BOLT and BumbleBee. |
| Follow-ups | Scale-invariant LWE scheme (Brakerski, 2012/078); RNS BFV/BGV (Kim–Polyakov–Zucca, 2021/204). |
| Libraries | OpenFHE, SEAL, Lattigo, Phantom, HEonGPU |
| Follow-up papers in the archive | Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP Revisiting Homomorphic Encryption Schemes for Finite Fields |
System card: BFV¶
| Group | 4. Alternative FHE schemes |
| Family | RLWE, scale-invariant |
| Arithmetic | Exact integers mod p, SIMD |
| Interaction | Non-interactive |
| Model scale | Linear layers in HE+MPC hybrids |
| Status | Widely used |
| Relation to the SoK | Exact scheme widely used for the linear layers of hybrid protocols. |
| Note | Basis of Cheetah, BOLT, BumbleBee and Nimbus linear layers. No native approximate arithmetic. |
| Code | https://github.com/microsoft/SEAL |
| Systems page | BFV |
SoK reference [65]¶
J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” Cryptology ePrint Archive, Report 2012/144, 2012. [Online]. Available: https://eprint.iacr.org/2012/144
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Leveled / somewhat HE 7 [p.1]
- technique: Relinearization 34 [p.1], Bootstrapping 14 [p.1], Modulus switching 4 [p.1], SIMD packing 3 [p.14]
- assumption: RLWE 21 [p.1], LWE 16 [p.1], Lattice-based 8 [p.1]
- topic: Homomorphic encryption 19 [p.1]
Related papers¶
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP follow up of this paper — follow-up listed for scheme "BFV"
- Revisiting Homomorphic Encryption Schemes for Finite Fields follow up of this paper — follow-up listed for scheme "BFV"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/4-049_somewhat-practical-fully-homomorphic-encryption.pdf |
catalogue | 19 | 380.6 KB | 72d554d8302f |
|
references/schemes/s15-0_somewhat-practical-fully-homomorphic-encryption.pdf |
schemes | 19 | 380.6 KB | 72d554d8302f |
byte-identical to references/catalogue/4-049_somewhat-practical-fully-homomorphic-encryption.pdf |
references/sok-references/065_somewhat-practical-fully-homomorphic-encryption.pdf |
sok-references | 19 | 380.6 KB | 72d554d8302f |
byte-identical to references/catalogue/4-049_somewhat-practical-fully-homomorphic-encryption.pdf |
Database key: somewhat-practical-fully-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set somewhat-practical-fully-homomorphic-encryption COLUMN VALUE