Revisiting Key Switching Techniques with Applications to Light-Key FHE

Fully Homomorphic Encryption (FHE) allows for data processing while it remains encrypted, enabling privacy-preserving outsourced computation. However, FHE faces challenges in real-world applications, such as communication overhead and storage limitations, due to the large size of its evaluation key. This paper revisits existing key switching algorithms widely used in FHE, which may account for over 90 \(\%\) of the total evaluation key size. Although these algorithms work towards the same goal, they differ significantly in functionality, computational complexity, noise management and key size. We close their functional gap and reanalyze them under a common standard, proposing theorems and comparative results to provide a flexible time-space trade-off when designing FHE applications. To validate the efficacy of our theoretical results, we propose a light-key bootstrapping method using a lower-sized key switching variant. This approach reduces the key size of the well-known GINX bootstrapping by a factor of 88.8 \(\%\) . It also outperforms the state-of-the-art light-key FHE by reducing 48.4 \(\%\) bootstrapping key size and 8 \(\%\) transfer key size.