Ciphertext Expansion

The choice of homomorphic encryption scheme is the primary determinant of expansion magnitude.

• BFV/BGV: Typically exhibit expansion factors between 10x and 50x due to large ciphertext moduli required for exact integer arithmetic.
• CKKS: Often shows lower expansion, but the size fluctuates based on the scaling factor and polynomial modulus degree.
• TFHE: Operates on individual bits or small integers, leading to extreme expansion per bit (often >1000x), but this is mitigated by packing techniques.

The bit-security level directly dictates the lattice dimension and modulus sizes.

• A jump from 128-bit to 256-bit post-quantum security often doubles the ciphertext size.
• The ring dimension (N)—typically 1024, 2048, 4096, or 8192—defines the polynomial degree and is the fundamental block of expansion.
• Higher security levels require larger parameters, creating a direct trade-off between quantum resistance and storage efficiency.

How plaintext data is mapped into polynomial slots dramatically changes effective expansion.

• SIMD Packing: Using the Chinese Remainder Theorem, a single ciphertext can hold N values (e.g., 4096 floats). This amortizes the expansion overhead, making the effective per-element expansion very low.
• Sparse Encoding: Encoding a single scalar into a full polynomial slot wastes capacity, resulting in massive effective expansion.
• Complex Numbers: CKKS encodes complex vectors, doubling the data per slot compared to real-only schemes.

Operations that manage the noise budget introduce temporary or permanent size changes.

• Relinearization: Reduces a ciphertext from 3 polynomials back to 2 after multiplication, preventing quadratic growth.
• Modulus Switching: Reduces the modulus chain, physically shrinking the ciphertext size after each operation.
• Bootstrapping: Refreshes the noise but often requires a large evaluation key and temporarily bloats memory during the procedure.

Ciphertext expansion is only part of the storage story; auxiliary keys are often much larger.

• Public Keys: Typically 2 polynomials, similar in size to a fresh ciphertext.
• Evaluation Keys (Relinearization/Galois): Required for multiplication and rotations. These can be 10x to 100x larger than a standard ciphertext.
• Galois Keys: Enable slot rotations in SIMD packing but require storing a key for every rotation step, significantly increasing the total key material footprint.

Ciphertext size is not static throughout a computation.

• Fresh Ciphertexts: Encrypted by the client, typically consist of 2 polynomials.
• Evaluated Ciphertexts: After multiplication without relinearization, they grow to 3 polynomials, increasing size by 50%.
• Modulus Chain Depth: In leveled schemes, a fresh ciphertext contains the full modulus chain (largest size), while an exhausted ciphertext at the end of computation is physically smaller.