relinearization

Relinearization is a technique used primarily in the field of lattice–based cryptography to manage the size and complexity of ciphertexts. When performing operations such as multiplication on ciphertexts in fully homomorphic encryption schemes, the resulting ciphertexts can grow in length and noise level. Relinearization contracts the expanded ciphertext back to its original dimension, typically two or three blocks, by applying a predetermined set of linear transformations derived from the scheme’s public parameters.

The process works by precomputing encryption of the scheme’s secret key or related auxiliary data, which is then used as a “relinearization key.” During decryption, these keys are applied to the expanded ciphertext, effectively cancelling the extra components introduced by multiplication. This restores the ciphertext’s size while preserving security. Besides size reduction, relinearization also decreases noise, allowing for more successive operations before decryption fails. The technique is integral to schemes such as Brakerski–Vaikuntanathan, BFV, and CKKS, where efficient handling of ciphertext growth is essential for practical performance. By enabling repeated arithmetic on encrypted data without exponential blow‑up, relinearization contributes significantly to the feasibility of real‑world applications of homomorphic encryption.