BFV Scheme

Unlike the CKKS scheme which performs approximate fixed-point arithmetic, BFV operates on exact integers modulo a plaintext modulus. This means computations produce precise, deterministic results without approximation errors.

• Ideal for counting operations, financial calculations, and discrete logic
• No floating-point rounding errors accumulate during computation
• Plaintext space is the ring Z_t for some integer modulus t
• Supports exact equality checks and branching logic on encrypted data

BFV's security rests on the Ring Learning With Errors (RLWE) problem, a lattice-based hardness assumption believed to be resistant to quantum attacks.

• Classified as post-quantum cryptography
• Provides IND-CPA security (indistinguishability under chosen-plaintext attack)
• Operates over polynomial rings R_q = Z_q[x]/(x^n + 1)
• Security level determined by ring dimension n and ciphertext modulus q

Every ciphertext in BFV contains an inherent noise component that grows with each homomorphic operation. If noise exceeds a critical threshold, decryption fails.

• Addition: Noise grows additively (relatively slow)
• Multiplication: Noise grows multiplicatively (rapid expansion)
• Relinearization reduces ciphertext size after multiplication
• Modulus switching scales down noise proportionally to extend the noise budget

BFV supports Single Instruction Multiple Data (SIMD) parallelism by packing multiple plaintext integers into a single ciphertext using the Chinese Remainder Theorem (CRT).

• Encodes up to n integers in one ciphertext (n = ring dimension)
• Homomorphic operations execute on all packed values simultaneously
• Amortizes computational cost across batched data vectors
• Critical for achieving practical throughput in encrypted computation

After a homomorphic multiplication, the resulting ciphertext grows from 2 polynomials to 3, increasing storage and subsequent computation costs. Relinearization is a key-switching technique that reduces the ciphertext back to 2 polynomials.

• Prevents exponential growth in ciphertext dimensions
• Requires a relinearization key generated during key setup
• Essential for evaluating deep multiplicative circuits
• Trades a one-time computational cost for sustained efficiency

The plaintext modulus t defines the integer range for computation and must be carefully chosen based on the application's arithmetic requirements.

• All computations are performed modulo t
• Larger t supports wider integer ranges but increases noise growth
• Must be coprime to the ciphertext modulus q for correct decryption
• Typical choices: t = 2 for binary circuits, larger primes for integer arithmetic
• Overflow wraps around modulo t, requiring application-level management

The finite amount of cryptographic noise a ciphertext can tolerate before decryption fails. In BFV, each homomorphic multiplication consumes a significant portion of this budget, requiring careful circuit design.

• Initial budget: Determined by encryption parameters (polynomial modulus degree, coefficient modulus)
• Consumption: Additions are cheap; multiplications are expensive
• Management: Use modulus switching or relinearization to extend budget
• Exhaustion: Results in incorrect decryption

A computationally intensive procedure that refreshes a ciphertext's noise budget by homomorphically evaluating the decryption circuit. For BFV, bootstrapping enables unlimited computation depth, transforming a somewhat homomorphic scheme into a fully homomorphic one.

• Cost: The most expensive operation in FHE
• Mechanism: Encrypts the secret key under itself, then evaluates decryption homomorphically
• Practical impact: Often dominates total computation time in deep circuits

A key-switching technique that reduces ciphertext size after a homomorphic multiplication. In BFV, multiplying two ciphertexts of size 2 produces a ciphertext of size 3; relinearization compresses it back to size 2.

• Purpose: Prevents exponential growth in ciphertext dimensions
• Requires: Relinearization keys generated during key setup
• Trade-off: Adds computational overhead but essential for multi-step circuits
• Without it: Ciphertext size grows quadratically with multiplication depth

A technique that encodes multiple plaintext values into a single ciphertext using the Chinese Remainder Theorem. BFV leverages this to perform parallel homomorphic operations across vectors, dramatically amortizing computational cost.

• Mechanism: Maps a vector of integers to a single polynomial
• Benefit: Enables single-instruction-multiple-data (SIMD) parallelism
• Constraint: Operations apply element-wise; data movement requires rotation
• Example: Encrypt 8,192 integers in one ciphertext for parallel addition