Skip to content

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]

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