Revisiting Homomorphic Encryption Schemes for Finite Fields¶
Authors: Kim, Polyakov, Zucca
Year: 2021
Venue: ASIACRYPT 2021
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2021/204
Summary¶
Auto-extracted summary (unreviewed)
Kim, Polyakov and Zucca revisit BGV and BFV, proposing an improved BFV variant whose modified encryption sharply reduces noise growth (making it slightly better than BGV even for large plaintext moduli), a lower-complexity BFV homomorphic multiplication with lazy scaling, an improved RNS decryption, and a more usable BGV variant. Implemented in PALISADE, the best BFV variant is up to 4x faster in homomorphic multiplication than prior RNS BFV for deep computations; BFV wins for small plaintext moduli while BGV is faster for intermediate and large moduli.
Abstract¶
The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/ Fan-Vercauteren (BFV) schemes are the two main homomorphic encryption (HE) schemes to perform exact computations over finite fields and integers. Although the schemes work with the same plaintext space, there are significant differences in their noise management, algorithms for the core homomorphic multiplication operation, message encoding, and practical usability. The main goal of our work is to revisit both schemes, focusing on closing the gap between the schemes by improving their noise growth, computational complexity of the core algorithms, and usability. The other goal of our work is to provide both theoretical and experimental performance comparison of BGV and BFV. More precisely, we propose an improved variant of BFV where the encryption operation is modified to significantly reduce the noise growth, which makes the BFV noise growth somewhat better than for BGV (in contrast to prior results showing that BGV has smaller noise growth for larger plaintext moduli). We also modify the homomorphic multiplication procedure, which is the main bottleneck in BFV, to reduce its algorithmic complexity. Our work introduces several other novel optimizations, including lazy scaling in BFV homomorphic multiplication and an improved BFV decryption procedure in the Residue Number System (RNS) representation. We also develop a usable variant of BGV as a more efficient alternative to BFV for common practical scenarios. We implement our improved variants of BFV and BGV in PALISADE and evaluate their experimental performance for several benchmark computations. The experimental results suggest that our BGV implementation is faster for intermediate and large plaintext moduli, which are often used in practical scenarios with ciphertext packing, while our BFV implementation is faster for small plaintext moduli. 1 Contents
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | improved BFV encryption with significantly reduced noise growth | llm | 0.85 |
| contribution | modified BFV homomorphic multiplication with lower algorithmic complexity and lazy scaling | llm | 0.85 |
| contribution | improved BFV decryption in the HPS RNS variant | llm | 0.85 |
| contribution | more usable BGV variant for practical scenarios | llm | 0.85 |
| contribution | theoretical and experimental comparison of BGV and BFV in the same library (PALISADE) | llm | 0.85 |
| schemes | BFV | llm | 0.85 |
| schemes | BGV | llm | 0.85 |
| libraries | PALISADE | llm | 0.85 |
| tasks | exact HE arithmetic over finite fields | llm | 0.85 |
| tasks | binary tree multiplication | llm | 0.85 |
| tasks | polynomial evaluation | llm | 0.85 |
| tasks | inner product | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | http://github.com/ldsec/lattigo (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| llm relevance | low | llm | 0.85 |
| key result | homomorphic multiplication speed-up: up to 4x (best BFV variant vs prior state-of-the-art RNS BFV, deeper computations) | llm | 0.85 |
| key result | noise growth: improved BFV somewhat better than BGV (contrasting prior results favouring BGV at large plaintext moduli) | llm | 0.85 |
| key result | scheme comparison: BFV faster for small t; BGV faster for intermediate/large t (PALISADE benchmarks) | llm | 0.85 |
System card: Revisited BGV/BFV for finite fields¶
| Group | 4. Alternative FHE schemes |
| Family | RNS BGV/BFV |
| Arithmetic | Exact integers |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Widely used |
| Relation to the SoK | Modern BGV/BFV variants implemented in OpenFHE. |
| Note | Lower noise and faster RNS BFV/BGV multiplication. |
| Code | https://github.com/openfheorg/openfhe-development |
| Systems page | Revisited BGV/BFV for finite fields |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: BFV 265 [p.1], BGV 203 [p.1], CKKS 4 [p.4], FHEW 4 [p.4], RSA 3 [p.30], TFHE 2 [p.4], Leveled / somewhat HE 2 [p.9]
- library: PALISADE 11 [p.1], HElib 7 [p.8], Microsoft SEAL 5 [p.6], Lattigo 2 [p.6]
- model: Logistic regression 1 [p.31]
- technique: Key switching 84 [p.2], Modulus switching 49 [p.3], RNS 47 [p.1], Relinearization 12 [p.5], Bootstrapping 11 [p.4], NTT 11 [p.13], SIMD packing 3 [p.1]
- assumption: RLWE 8 [p.4], LWE 8 [p.5], Lattice-based 4 [p.29]
- topic: Homomorphic encryption 27 [p.1], Benchmark 7 [p.1], Open source 2 [p.29]
Related papers¶
- this paper follow up of Somewhat Practical Fully Homomorphic Encryption — follow-up listed for scheme "BFV"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/4-051_revisiting-homomorphic-encryption-schemes-for-finite-fields.pdf |
catalogue | 46 | 535.4 KB | 3e77f5330fec |
|
references/schemes/s15-2_eprint-2021-204.pdf |
schemes | 46 | 535.4 KB | 3e77f5330fec |
byte-identical to references/catalogue/4-051_revisiting-homomorphic-encryption-schemes-for-finite-fields.pdf |
Database key: revisiting-homomorphic-encryption-schemes-for-finite-fields · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set revisiting-homomorphic-encryption-schemes-for-finite-fields COLUMN VALUE