Key Switching

Key switching relies on a public evaluation key (also called a switching key) that encodes the relationship between two secret keys. This key is generated by encrypting fragments of the source secret key under the target secret key, typically using a gadget decomposition technique to control noise growth. The operation is unidirectional: a switching key from key A to key B cannot be used to switch from B to A. Security is preserved because the evaluation key is a public parameter that does not reveal either secret key, relying on the hardness of the Ring Learning With Errors (RLWE) problem.

The primary application of key switching is relinearization, which reduces ciphertext dimension after homomorphic multiplication. When two ciphertexts are multiplied, the result grows from 2 ring elements to 3 ring elements, and the secret key becomes the quadratic product of the original key. Relinearization applies key switching to transform this expanded ciphertext back to 2 elements under the original linear secret key. Without this step, successive multiplications would cause exponential growth in ciphertext size, making computation impractical after only a few operations.

Key switching enables homomorphic rotation of packed ciphertext slots through Galois keys. In schemes like CKKS and BFV, plaintext vectors are encoded into ciphertext slots for SIMD parallelism. Rotating these slots requires applying an automorphism that changes the underlying secret key. A Galois key is a specialized key-switching key that transforms the ciphertext back to the original secret key after the rotation. Common Galois keys include left/right rotation by 1, and rotation by powers of 2 for efficient arbitrary shifts.

Key switching introduces additional noise into the ciphertext, which must be carefully managed. The operation uses gadget decomposition to break the input ciphertext into smaller components before applying the switching key, reducing the noise added per operation. The decomposition base and digit count are tunable parameters: a smaller base reduces noise but increases computational cost. In practice, key switching noise is additive and predictable, allowing cryptographers to budget it alongside multiplication noise within the overall noise budget of the scheme.

Key switching generalizes to proxy re-encryption, where a semi-trusted proxy transforms ciphertexts between different parties' public keys without accessing the plaintext. This enables secure data sharing scenarios: a data owner can delegate access by generating a re-encryption key from their key to a recipient's key. The proxy applies this key to convert stored ciphertexts, but never learns the underlying data. This primitive is foundational for secure cloud storage, encrypted email forwarding, and access control in privacy-preserving systems.

In Fully Homomorphic Encryption (FHE), bootstrapping homomorphically evaluates the decryption circuit to refresh ciphertext noise. This process internally uses key switching to transform the encrypted secret key bits into a form compatible with the refreshed ciphertext. Specifically, bootstrapping requires switching from a high-noise ciphertext under a complex key representation back to a clean ciphertext under the original secret key. The efficiency of this key-switching step directly impacts bootstrapping latency, making it a critical optimization target in schemes like TFHE and CKKS.

A specific application of key switching that reduces a ciphertext's size back to two ring elements after a homomorphic multiplication. Without relinearization, each multiplication would increase the ciphertext dimension quadratically, making further computation impractical. The operation transforms a degree-2 ciphertext (encrypted under s⊗s) back to a degree-1 ciphertext (encrypted under s) using a relinearization key, which is a public evaluation key generated from the secret key.

Public evaluation keys that enable homomorphic rotation of the slots within a packed ciphertext. These keys are generated via key switching and allow the evaluator to cyclically shift the plaintext vector encoded in a ciphertext without decrypting it. Essential for implementing matrix transposition, convolution, and summation operations in the encrypted domain. Each distinct rotation step requires its own Galois key, creating a storage trade-off between key material size and computational flexibility.

A noise-management technique that homomorphically evaluates the decryption circuit on a ciphertext, producing a fresh encryption of the same plaintext with a reset noise budget. Bootstrapping itself relies heavily on key switching to transform ciphertexts between different key representations during the recursive evaluation. In the TFHE scheme, bootstrapping is performed after every gate operation; in CKKS, it enables arbitrary-depth computation by periodically refreshing the ciphertext.

A noise management technique that scales a ciphertext down to a smaller modulus, proportionally reducing the absolute noise magnitude. Unlike key switching, modulus switching does not require an evaluation key and operates without knowledge of the secret key. It is a lightweight alternative for noise control in the BGV scheme, often used in conjunction with key switching to maintain ciphertext integrity across a chain of decreasing moduli.

A cryptographic primitive allowing a semi-trusted proxy to transform a ciphertext encrypted under Alice's public key into a ciphertext encrypted under Bob's public key without ever decrypting the underlying plaintext. While conceptually similar to key switching, proxy re-encryption operates at the application layer for access delegation rather than at the circuit layer for noise management. The proxy uses a re-encryption key generated by Alice from her secret key and Bob's public key.

The finite capacity for error accumulation within a lattice-based ciphertext. Each homomorphic operation—especially multiplication—consumes a portion of this budget. Key switching itself introduces a small additive noise term, contributing to budget depletion. Once the noise exceeds a critical threshold relative to the ciphertext modulus, decryption becomes unreliable or impossible. Managing this budget through key switching, modulus switching, and bootstrapping is the central engineering challenge in FHE.