Paper 2023/1642

A New Perspective on Key Switching for BGV-like Schemes

Abstract

Fully homomorphic encryption is a promising approach when computing on encrypted data, especially when sensitive data is involved. For BFV, BGV, and CKKS, three state-of-the-art encryption schemes, the most costly homomorphic primitive is the so-called key switching. While a decent amount of research has been devoted to optimizing other aspects of these schemes, key switching has gone largely untouched. One exception has been a recent work [26] introducing a new double-decomposition technique. Its contributions are a great addition to the current state-of-the-art with one flaw: The authors take a skewed perspective on key switching parameters and their asymptotic complexity leading to incorrect conclusions about how effective their approach really is. In this work, we deep dive into key switching and correct, enhance, and improve the current state-of-the-art. We provide a new perspective on the key switching parameters $P$, $\omega$, and $\tilde\omega$ resulting in the asymptotic bounds $\mathcal{O}(\omega \ell)$ and $\mathcal{O}(\omega \ell / \tilde\omega + \tilde\omega \ell / \omega)$ for the single- and double-decomposition technique, respectively. We also revisit an idea by Gentry, Halevi, and Smart [18] to reduce the number of multiplications, which speeds up key switching by up to 63% and up to 11.6%, respectively.