BGV & BFV Schemes for Integer Operations
Perform encrypted integer addition and multiplication using BGV.
BGV & BFV Schemes for Integer Operations is a free Cryptology Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Cryptology Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
BGV Overview
BGV (Brakerski-Gentry-Vaikuntanathan, 2012) is a leveled FHE scheme based on RLWE. It supports arbitrary additions and multiplications on packed integer plaintexts. "Leveled" means it handles circuits up to a fixed depth L without bootstrapping.
Plaintext Space
BGV and BFV encode plaintexts as polynomials in Z_t[x]/(x^n+1) where t is a small plaintext modulus (e.g., t=65537). Each polynomial encodes n integer values (one per coefficient). Arithmetic on ciphertexts operates on all n values simultaneously — SIMD parallelism.
Noise Management in BGV
BGV reduces noise by modulus switching: after each multiplication, the ciphertext modulus q is reduced from Q_L to Q_{L-1}. This divides the noise by Q_L/Q_{L-1}, keeping noise within decryptable bounds. Circuit depth L corresponds to L modulus levels.
BFV Overview
BFV (Brakerski/Fan-Vercauteren, 2012) is similar to BGV but uses a different noise management strategy: scale invariant. BFV does not require modulus switching; instead it rescales the ciphertext after multiplication. Simpler to implement; used in Microsoft SEAL.
Batch Encoding (NTT Slots)
Via the Chinese Remainder Theorem over the plaintext ring, each ciphertext can hold n/2 independent integer values (slots). An addition ciphertext operation adds all n/2 pairs in parallel. A multiplication multiplies all pairs. Throughput: n/2 integer ops per ciphertext op.
Multiplication Relinearization
After multiplying two degree-1 ciphertexts, the result is degree-2 (3 components). Relinearization uses evaluation keys (relin keys) to convert back to degree-1 at the cost of added noise. This step is required after every multiplication.
Python Example with SEAL
from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))
Rotation
Ciphertext rotation shifts the n/2 plaintext slots cyclically. Useful for: sum-reduce (accumulate all slots into one), matrix-vector multiplication (rotate and accumulate), convolutions (shift and multiply). Requires Galois keys (precomputed rotation keys).
Performance
BFV with n=8192: addition ~10 µs, multiplication ~5 ms (with relinearization). Bootstrapping (if needed): 30-60 seconds. Batch of 4096 integers: amortized ~1 µs per integer per multiplication. Impractical for real-time but viable for offline analytics.
Selecting Parameters
Choosing n and q: SEAL recommends n=4096 for 128-bit security with Q < 2^109; n=8192 for larger circuits. The HE standard (homomorphicencryption.org) provides parameter tables. Always use recommended parameters — custom choices easily undermine security.
Use Cases
Encrypted database queries (search encrypted records without decrypting). Private genomic analysis (compute statistics on encrypted DNA). Encrypted financial aggregations (sum encrypted account balances without seeing individuals). Secure model evaluation.
Quick Check
What technique does BGV use to manage noise growth after multiplications?
Recap
BGV and BFV perform encrypted integer arithmetic using RLWE. Batch encoding provides SIMD parallelism. BGV uses modulus switching; BFV uses scale invariance. Relinearization restores degree after multiplication. Next: CKKS for approximate arithmetic and ML.
Frequently asked questions
Is the “BGV & BFV Schemes for Integer Operations” lesson free?
Yes — the full text of “BGV & BFV Schemes for Integer Operations” is free to read here on the web, and the Cryptology Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Cryptology Academy course, upgrade to CoddyKit PRO.
What will I learn in “BGV & BFV Schemes for Integer Operations”?
Perform encrypted integer addition and multiplication using BGV. You practise Cryptology Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Cryptology Academy?
No prior experience is required. Cryptology Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “BGV & BFV Schemes for Integer Operations” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Cryptology Academy lesson?
Yes. Every Cryptology Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- What Is Homomorphic Encryption?
- Learning With Errors (LWE) Foundation
- BGV & BFV Schemes for Integer Operations
- CKKS for Approximate Arithmetic & ML